Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Daniel KPO LOUA Enseignant-Chercheur en Informatique à l’INP-HB Laboratoire de

Daniel KPO LOUA Enseignant-Chercheur en Informatique à l’INP-HB Laboratoire de Recherche en Informatique et Télécommunication (LARIT) DFR : Maths – Info kpo.loua@inphb.ci / 00225 40 28 31 08 BDR P 2 Cours de Programmation Avancée en Python Base de Données Relationnelles TS STIC 1 2018 - 2019 05 Septembre 2019 Classes Préparatoires aux Grandes Ecoles (CPGE) A Celui qui peut tout Et qui me rend capable de tout, Mon bien-aimé Père ! 1 Classes Préparatoires aux Grandes Ecoles Approfondissement en Python 3 Table des matières PARTIE 1 : NOTION DE BASE DE DONNEES ................................................................................................. 4 Chapitre 1 : Bases de données relationnelles (6H) ................................................................................ 6 1.1. Principes ................................................................................................................................. 6 1.1.2. Enjeux ................................................................................................................................. 6 1.2. L’architecture d’une base de données ................................................................................... 7 1.3. Le modèle relationnel ............................................................................................................. 8 1.4. Algèbre relationnelle ............................................................................................................ 11 TD n°1 - Algèbre relation et les requêtes ----------------------------- (2H) ............................................. 18 Chapitre 2 : Le langage SQL (8H) .......................................................................................................... 21 2.1. Définition .............................................................................................................................. 21 TP n°1 – Environnement de l’outil MySQL -------------------------------(1H) .......................................... 31 TP n°2 – Manipulation de requêtes SQL, interface avec Python ------------- (1H) ............................. 31 PARTIE 2 : ALGORITHME AVANCE ............................................................................................................ 32 Chapitre 3 : Complexité algorithmique (8H) ........................................................................................ 34 3.1. Introduction .......................................................................................................................... 34 3.2. Motivation ............................................................................................................................ 34 3.3. Complexité et notation O ..................................................................................................... 35 3.3.2. Notation de Landau .......................................................................................................... 36 3.4. Comment mesurer la complexité d'un algorithme .............................................................. 36 3.5. Différentes nuances de complexité ...................................................................................... 38 TDn°2 – Manipulation des ordres de grandeurs, performance d’un algorithme, calcul de complexité ------------------------------------ (4H) ................................................................................... 38 Chapitre 4 : Notion de pile (2H)............................................................................................................ 39 4.1. Rappels et compléments sur les listes.................................................................................. 39 4.2. Manipulation des piles ......................................................................................................... 39 4.3. Création d’une pile ............................................................................................................... 39 4.4. Applications .......................................................................................................................... 41 Chapitre 5 : Récursivité (8H) ................................................................................................................. 42 5.1. Introduction .......................................................................................................................... 42 5.2. Fonction récursive ................................................................................................................ 42 5.3. Complexité d’un algorithme récursif .................................................................................... 43 TDn°3 – Manipulation des piles, notions de récursivité, complexité----------- (4H).......................... 45 5.4. Résolution des récurrences .................................................................................................. 45 2 Classes Préparatoires aux Grandes Ecoles Approfondissement en Python 3 TPn°3 – Simulation de piles ----------------------------------------- (2H) ................................................... 45 Chapitre 6 : Algorithmes de tri (10H) ................................................................................................... 46 6.1. Introduction .......................................................................................................................... 46 6.2. Algorithmes de tri par insertion ........................................................................................... 46 6.3. Algorithme de tri rapide ....................................................................................................... 48 6.4. Algorithme du Tri par fusion ................................................................................................ 50 TDn°4 – Tri rapide, tri fusion, complexité de tri avancé ------------------ (4H) .................................... 53 TPn°5 – Implémentation de Tris avancés : rapide, tri fusion ------------- (2H) ................................... 53 3 Classes Préparatoires aux Grandes Ecoles Approfondissement en Python 3 Objectifs ▪ Gérer des données de bases structurées ou non ▪ Approfondir les connaissances en langage de programmation évolué et moderne 4 Classes Préparatoires aux Grandes Ecoles Approfondissement en Python 3 PARTIE 1 : NOTION DE BASE DE DONNEES 5 Classes Préparatoires aux Grandes Ecoles Approfondissement en Python 3 Savoir-faire : ▪ Comprendre et décrire les rôles des différents éléments d'une architecture trois tiers ▪ Recourir aux concepts des bases de données relationnelles ; ▪ Traduire les questions posées dans un langage de requête en respectant sa syntaxe ▪ Prototyper et créer une base de données simple, à l’aide d’un outil interactif ▪ Consulter une base de données à travers des requêtes de type SQL ; 6 Classes Préparatoires aux Grandes Ecoles Approfondissement en Python 3 Chapitre 1 : Bases de données relationnelles (6H) Durée : CM --------------------------------------------------------------------------------- (4H) 1.1. Principes 1.1.1. Définition Il est difficile de donner une définition exacte de la notion de base de données. Une définition très générale pourrait être : Une Base de données est un ensemble organisé d'informations avec un objectif commun. Peu importe le support utilisé pour rassembler et stocker les données (papier, fichiers, etc.), dès lors que des données sont rassemblées et stockées d'une manière organisée dans un but spécifique, on parle de base de données. Plus précisément, on appelle base de données un ensemble structuré et organisé permettant le stockage de grandes quantités d'informations afin d'en faciliter l'exploitation (ajout, mise à jour, recherche de données). Bien entendu, dans le cadre de ce cours, nous nous intéressons aux bases de données informatisées. 1.1.2. Enjeux Les bases de données ont pris une place importante en informatique, et particulièrement dans le domaine de la gestion. L'étude des bases de données a conduit au développement de concepts, méthodes et algorithmes spécifiques, notamment pour gérer les données en mémoire secondaire (i.e. disques durs). En effet, dès l'origine de la discipline, les informaticiens ont observé que la taille de la RAM ne permettait pas de charger l'ensemble d'une base de données en mémoire. Cette hypothèse est toujours vérifiée, car le volume des données ne cesse de s'accroître sous la poussée des nouvelles technologies du WEB. Ainsi, les bases de données de demain devront être capables de gérer plusieurs dizaines de Téra-Octets de données, géographiquement distribuées à l'échelle d'Internet, par plusieurs dizaines de milliers d'utilisateurs dans un contexte d'exploitation changeant (on ne sait pas très bien maîtriser ou prédire les débits de communication entre sites) voire sur des nœuds volatiles. En physique des hautes énergies, on prédit qu'une seule expérience produira de l'ordre du pétaoctet de données par an. Comme il est peu probable de disposer d'une technologie de disque permettant de stocker sur un unique disque cette quantité d'informations, les bases de données se sont orientées vers des architectures distribuées ce qui permet, par exemple, d'exécuter potentiellement 7 Classes Préparatoires aux Grandes Ecoles Approfondissement en Python 3 plusieurs instructions d'entrée/sortie en même temps sur des disques différents et donc de diviser le temps total d'exécution par un ordre de grandeur. 1.2. L’architecture d’une base de données En règle générale, une application peut aisément se diviser en trois niveaux distincts : les données, le traitement de ces données et leur affichage. La couche de donnée regroupe le stockage et les mécanismes d’accès des données de façon qu’elle soit utilisable par l’application au niveau traitement. La couche de traitement concerne à la fois les tâches à réaliser par l’application sur les données et les traitements nécessaires pour donner suite à une action de l’utilisateur. Enfin, la couche de présentation qui permet l’interaction entre l’utilisateur et l’application. Ces trois niveaux pouvant être imbriqués ou repartis, leur découpage et leur répartition permettent de distinguer les architectures applicatives suivantes : – L’architecture un tiers, – L’architecture deux tiers, – L’architecture trois tiers. 1.2.1. L’architecture client-serveur (deux tiers) Dans une architecture deux tiers ou client-serveur de données, le poste client se contente de déléguer la gestion des données à un service spécialisé. Ce type d’application permet de tirer parti de la puissance des ordinateurs déployés en réseau pour fournir à l'utilisateur une interface riche, tout en garantissant la cohérence des données, qui restent gérées de façon centralisée. 1.2.2. Architecture trois tiers L’architecture trois tiers applique les principes suivants : – Les données sont toujours gérées de façon centralisée ; 8 Classes Préparatoires aux Grandes Ecoles Approfondissement en Python 3 – La présentation est toujours prise en charge par le poste client ; – La logique applicative est prise en charge par un serveur intermédiaire. Par conséquent, cette architecture appelée encore client-serveur de deuxième génération ou client-serveur distribué, sépare l’application en trois niveaux de service distinct : ▪ Premier niveau (Couche présentation) : Elle correspond à la partie de l'application visible et interactive avec les utilisateurs. On parle d'interface homme-machine. La couche présentation relaie les requêtes de l'utilisateur à destination de la couche métier, et en retour lui présente les informations renvoyées par les traitements de cette couche. ▪ Deuxième niveau (Couche métier ou business) : Elle correspond à la partie fonctionnelle de l'application, celle qui implémente la « logique », et qui décrit les opérations que l'application opère sur les données en fonction des requêtes des utilisateurs effectuées au travers de la couche présentation. Les différentes règles de gestion et de contrôle du système sont mises en œuvre dans cette couche. ▪ Troisième niveau (Couche accès aux données) : Elle consiste en la partie gérant l’accès aux données qui sont destinées à être conservées sur la durée, voire de manière définitive. 1.3. Le modèle relationnel Une base de données relationnelle est une base de données structurée suivant les principes de l'algèbre relationnelle. Le père des bases de données relationnelles est Edgar Frank Codd. Chercheur chez IBM à la fin des années 1960, il étudiait alors de nouvelles méthodes pour gérer de grandes quantités de données, car les modèles et les logiciels de l'époque ne le satisfaisaient pas. Mathématicien de formation, il était persuadé qu'il pourrait utiliser des branches spécifiques des mathématiques (la théorie des ensembles et la logique des prédicats du premier ordre) pour résoudre des difficultés telles que la redondance des données, l'intégrité des données ou l'indépendance de la structure de la base de données avec sa mise en œuvre physique. 9 Classes Préparatoires aux Grandes Ecoles Approfondissement en Python 3 En 1970, il publia un article où il proposait de stocker des données hétérogènes dans des tables, permettant d'établir des relations entre elles. De nos jours, ce modèle est extrêmement répandu, mais en 1970, cette idée uploads/Science et Technologie/ classes-preparatoires-aux-grandes-ecoles-cpge-cours-de-programmation-avancee-en-python.pdf