Fiche de révision : Graphes et programmation dynamique

📋 Plan du Cours

1. Types et contrôle Python
2. Fonctions et portée des variables
3. Listes et tuples en Python
4. Modules et fichiers Python
5. Écriture, erreurs et tests
6. Algorithmes de recherche
7. Complexité et preuves
8. Listes et tableaux
9. Piles, files et deque
10. Représentation et parcours des graphes
11. Parcours en profondeur et cycles
12. Plus courts chemins pondérés
13. Programmation dynamique et applications
14. Partition équilibrée d’entiers
15. Plus longue sous-séquence commune
16. Classification par k plus proches voisins
17. Regroupement par k-moyennes
18. Schéma des tables CLIENTS et PARTENAIRES

📖 1. Types et contrôle Python

🔑 Notions clés & Définitions

• Chaîne de caractères : Suite de caractères définie entre apostrophes ou guillemets, et les triples guillemets permettent notamment de l’écrire sur plusieurs lignes.

★ À maîtriser

• Les chaînes sont immuables : on ne peut pas remplacer directement un caractère par une affectation telle que c[position] = valeur.

• Les opérateurs booléens and et or évaluent leurs opérandes de gauche à droite et s’arrêtent dès que le résultat est déterminé, tandis que not inverse la valeur booléenne.

• Une boucle for parcourt successivement les éléments d’un itérable, notamment un range, une liste ou une chaîne, et range(a, b, pas) fournit les termes a + k·pas strictement inférieurs à b.

• Une boucle while exécute son bloc tant que sa condition est vraie ; les variables déterminant cette condition doivent généralement être modifiées dans le bloc pour éviter une boucle infinie.

Compléments

• Python distingue les entiers, les flottants, les nombres complexes et les booléens, ces derniers prenant les valeurs True et False, correspondant respectivement aux entiers 1 et 0.

• Sur les nombres, +, -, * réalisent les opérations classiques, // la division entière, / la division flottante, % le reste de la division euclidienne, abs la valeur absolue et pow(x, y) ou x**y la puissance.

• Les opérations usuelles sur les chaînes comprennent la concaténation avec +, la répétition avec *, l’accès par indice, les tranches s[i:j] et s[i:j:k], ainsi que len(s) pour obtenir la longueur.

• La conversion de données s’effectue généralement avec le constructeur du type visé, par exemple int('123'), float('123') ou str(35).

• Modifier la variable de parcours dans une boucle for ne change pas la valeur que l’itérateur fournira au passage suivant.

📌 Dans une boucle, break quitte la boucle et poursuit le programme après celle-ci, tandis que return quitte définitivement la fonction qui contient la boucle.

📖 2. Fonctions et portée des variables

★ À maîtriser

• Une fonction Python se définit avec def, peut prendre plusieurs paramètres et n’est pas obligée de renvoyer une valeur ; elle peut renvoyer des objets de différents types.

📌 Dans une fonction, les arguments et les variables auxquelles on affecte une valeur sont locaux, sauf déclaration explicite avec le mot-clé global.

Compléments

• L’opérateur lambda permet de définir une fonction simple sans lui donner un nom explicite, notamment pour la transmettre comme argument à une autre fonction.

• Une fonction peut être définie à l’intérieur d’une autre fonction et utiliser un argument de la fonction englobante.

• La recherche d’une variable dans une fonction examine d’abord les variables locales et celles des fonctions englobantes, puis les variables globales.

📌 Les annotations de type des arguments et du retour d’une fonction indiquent les types attendus, mais Python ne les contrôle pas lors de l’appel.

📖 3. Listes et tuples en Python

🔑 Notions clés & Définitions

• Liste : Ensemble ordonné d’éléments pouvant être de types différents, défini entre crochets et modifiable par accès à ses éléments.
• Tuple : N-uplet défini avec des parenthèses ou par des valeurs séparées par des virgules, dont les éléments ne sont pas modifiables.

★ À maîtriser

📌 L’expression l + [a] crée une nouvelle liste sans modifier l, tandis que l.append(a) ajoute effectivement a à la liste l.

• Une variable Python est un alias qui pointe vers un emplacement mémoire contenant un objet ; affecter une autre valeur à la variable peut la faire pointer vers un autre emplacement sans modifier l’objet initial.

Compléments

• Une liste peut être créée directement, à partir d’un itérable, par concaténation, par copie, par répétition ou par compréhension, éventuellement avec un filtrage.

• Les indices des listes commencent à 0 ; les éléments sont accessibles par indice, les tranches sélectionnent une partie de la liste et len(l) en donne la longueur.

• Quand la taille est connue à l’avance, il est préférable de créer directement la liste de cette taille ; pour ajouter un élément, append est généralement préférable à la création d’une nouvelle liste avec +.

• Un tuple peut servir de clé de dictionnaire si tous ses éléments sont hachables.

• La méthode pop(indice) retire et renvoie l’élément indiqué, ou le dernier élément par défaut, et renvoie une erreur si la liste est vide.

📖 4. Modules et fichiers Python

🔑 Notions clés & Définitions

• Espace de noms : Zone mémoire propre où les objets d’un module sont placés sans se mélanger aux variables déjà affectées.

★ À maîtriser

• Un module Python peut être importé avec son nom, sous un alias avec « import module as alias », ou par importation directe d’objets avec « from module import objet » ou « from module import * ».

📌 L’ouverture d’un fichier avec le mode « r » lit le fichier, le mode « w » l’ouvre en écriture en le vidant, et le mode « a » ajoute à la fin en créant le fichier s’il n’existe pas.

• Le module csv fournit reader pour lire un flux CSV en lignes représentées par des listes et DictReader pour produire des dictionnaires associés aux noms de colonnes, fournis par la première ligne ou par fieldnames.

Compléments

• Lorsque deux variables Python désignent la même liste, modifier un élément de cette liste est visible par les deux variables, car elles partagent le même identifiant.

• Le module math fournit notamment les constantes pi et e, des fonctions de racine, exponentielle, logarithme, trigonométrie et fonctions hyperboliques, ainsi que gamma, lgamma et erf.

• Parmi les modules usuels, : numpy sert au calcul numérique avec des tableaux array, matplotlib sert aux graphiques, deepcopy sert à la copie profonde de listes, os sert à l’interaction avec le système, random sert à l’aléatoire, time sert à la mesure du temps

• Les méthodes de fichier comprennent : read lit tout le contenu ou un nombre maximal de caractères, readline lit une ligne, readlines renvoie les lignes dans une liste, write écrit une chaîne, writelines écrit une liste de lignes sans ajouter de retours à la ligne, close ferme le flux, tell indique la position courante

• Un fichier CSV est un fichier texte où chaque ligne correspond à une ligne de tableau et où les champs sont séparés par un élément fixe, avec des champs éventuellement protégés par des guillemets.

• Le module csv propose writerow, writerows, writeheader et DictWriter pour écrire des lignes, plusieurs lignes, un en-tête et des données sous forme de dictionnaires.

• Les fonctions usuelles du module os sont : getcwd pour obtenir le répertoire courant, chdir pour changer le répertoire courant, mkdir pour créer un répertoire, listdir pour lister les fichiers d’un répertoire, remove pour effacer un fichier, rename pour renommer un fichier ou dossier

📖 5. Écriture, erreurs et tests

🔑 Notions clés & Définitions

• Assertion : Contrôle exécuté par assert qui vérifie une condition et déclenche AssertionError si elle est fausse.

★ À maîtriser

• La gestion générale d’une exception consiste à la lever avec raise, puis éventuellement à la récupérer avec try et except, avec une branche else exécutée en l’absence d’exception.

📌 Les tests par partitionnement choisissent une entrée représentative dans chaque sous-ensemble de données, tandis que les tests aux limites vérifient le comportement aux bornes et juste au-delà.

Compléments

📌 Les noms de variables importants doivent être explicites, les noms en majuscules désignent généralement des constantes, et les commentaires documentent les parties non immédiates du programme.

• Une docstring placée juste après la définition d’une fonction documente son but, ses entrées, ses sorties et éventuellement des exemples, et elle est consultable avec help(fonction).

• Les erreurs usuelles citées comprennent IndexError, KeyError, NameError, ValueError et ZeroDivisionError, et une exception générique peut être levée avec raise Exception(message).

• Pour tester un maximum de liste, on examine notamment une liste vide, une liste à un élément, une liste normale, les maxima aux extrémités, les maxima répétés et des éléments non comparables.

📖 6. Algorithmes de recherche

★ À maîtriser

• Un test d’appartenance à une liste parcourt ses éléments ou ses positions, renvoie True dès qu’un élément égal à la valeur cherchée est trouvé, et renvoie False si le parcours s’achève sans résultat.

• La recherche dichotomique dans une liste triée maintient les bornes g et d, examine l’indice milieu m, puis conserve la moitié gauche ou droite selon la comparaison, en excluant m avec m−1 ou m+1 lorsqu’il ne convient pas.

• La recherche d’un mot dans une chaîne teste les positions de départ possibles et compare successivement les caractères du mot, en s’arrêtant quand le mot correspond ou que la chaîne ne permet plus de le contenir.

📌 Le comptage avec chevauchement examine chaque position de départ successive, tandis que le comptage sans chevauchement reprend après une occurrence trouvée à la position suivante située après le mot.

Compléments

• Une recherche de position dans une liste peut renvoyer l’indice du premier élément égal à la valeur cherchée et renvoyer -1 si cette valeur est absente.

• Un comptage d’occurrences dans une liste parcourt ses éléments, incrémente un compteur à chaque égalité avec la valeur recherchée et renvoie le compteur final.

📖 7. Complexité et preuves

🔑 Notions clés & Définitions

• Complexité asymptotique : Ordre de croissance du coût quand la taille n des entrées devient grande, en ignorant les constantes multiplicatives et les termes de moindre ordre.

★ À maîtriser

📌 La complexité temporelle mesure le temps de calcul en fonction des données d’entrée, tandis que la complexité spatiale mesure la mémoire utilisée ; le cours étudie la complexité temporelle.

📌 La notation O(f(n)) exprime une majoration asymptotique, Ω(f(n)) une minoration et Θ(f(n)) un encadrement asymptotique du coût par des constantes multiples de f(n).

• La preuve d’une boucle établit un invariant vrai à chaque passage, prouve la terminaison — notamment par un variant entier strictement décroissant pour une boucle while — puis vérifie que la sortie correspond au résultat attendu.

• Dans la division euclidienne par soustractions répétées, on initialise q à 0 et r à a, puis tant que r ≥ b on remplace r par r−b et q par q+1 ; à la sortie, a=bq+r et 0≤r<b.

Compléments

📌 La complexité maximale est le coût le plus élevé parmi les entrées de taille n, la complexité minimale est le coût le plus faible et la complexité moyenne pondère les coûts par la probabilité des entrées.

• Le calcul du maximum d’une liste par parcours séquentiel a une complexité temporelle Θ(n), donc aussi O(n).

📖 8. Listes et tableaux

★ À maîtriser

📌 Un tableau a une taille fixe, tandis qu’une liste dynamique peut varier en nombre d’éléments.

• Dans un tableau homogène contigu, l’adresse de l’élément en position k est calculée par debut + k × taille, ce qui permet un accès direct en lecture et en écriture.

📌 Une liste simplement chaînée donne facilement accès à son début et permet les insertions et suppressions en tête, mais atteindre une position k nécessite de parcourir les éléments précédents.

• Le type list de Python utilise un tableau d’adresses, permettant l’accès rapide aux éléments et des insertions en fin de liste en temps amorti constant.

Compléments

• Dans une liste doublement chaînée, chaque élément contient l’adresse de l’élément suivant et de l’élément précédent, ce qui facilite les insertions et suppressions en tête, en queue et à une position atteinte.

• Supprimer un élément intermédiaire d’une liste Python nécessite de décaler les cases, tandis que concaténer deux listes a une complexité de l’ordre de leur taille totale.

💡 Astuce mémo

Tableau : accès direct ; liste chaînée : parcours des liens.

📖 9. Piles, files et deque

🔑 Notions clés & Définitions

• Pile : Structure de données LIFO dans laquelle l’objet ajouté en dernier est le premier récupéré et supprimé.
• File : Structure FIFO dans laquelle l’objet arrivé en premier est le premier récupéré et supprimé.

📝 Points essentiels

• Les opérations essentielles d’une pile sont : la création d’une pile vide, le test de vacuité, l’ajout au sommet, la récupération avec suppression de l’objet au sommet

• Avec une liste Python, on empile avec append(x), on dépile avec pop() et on teste la vacuité avec L == [] ou len(L) == 0.

• La pile d’exécution stocke notamment :

  • les arguments
  • l’adresse de retour
  • les variables locales
  • la valeur de retour

• Le module collections.deque permet des ajouts et retraits aux deux extrémités avec append, appendleft, pop et popleft.

• Pour un deque, l’accès aux extrémités est en O(1), tandis que l’accès au milieu est en O(n).

💡 Astuce mémo

Pile LIFO : le dernier entre sort d’abord ; file FIFO : le premier entre sort d’abord.

📖 10. Représentation et parcours des graphes

🔑 Notions clés & Définitions

• Graphe orienté : Un graphe orienté est un couple $G=(S,A)$ où S est l’ensemble des sommets et A un ensemble de couples ordonnés de sommets appelés arcs.

★ À maîtriser

📌 Dans un graphe orienté, un arc est un couple ordonné, tandis que dans un graphe non orienté, une arête est un ensemble de deux sommets dont l’ordre ne compte pas.

• Un parcours en largeur explore un graphe par niveaux à partir d’un sommet et permet de déterminer les distances minimales depuis ce sommet ainsi qu’un prédécesseur pour reconstruire un chemin.

• Dans ce parcours en largeur depuis A, les distances sont 0 pour A, 1 pour B et H, 2 pour C, D et I, et 3 pour E, F et G.

Compléments

• Dans un graphe orienté, le degré sortant d’un sommet compte ses arcs sortants, son degré entrant compte ses arcs entrants et son degré total est leur somme.

• Une matrice d’adjacence indique par ses entrées la présence d’un arc ou d’une arête entre deux sommets, et elle est symétrique pour un graphe non orienté.

• Une liste d’adjacence associe à chaque sommet la liste des sommets qui lui sont adjacents ou successeurs.

• Un dictionnaire Python peut représenter un ensemble de sommets déjà vus, avec les sommets comme clés, afin de bénéficier de tests d’appartenance rapides et d’une unicité des clés.

• Dans l’exemple de parcours en largeur du graphe non orienté depuis A, les successeurs sont A→[B,H], B→[C,D], H→[I], C→[E,F,G], et D, I, E, F et G n’ont aucun successeur.

• Le chemin menant à un sommet se reconstitue récursivement en remontant ses prédécesseurs jusqu’au sommet d’origine, puis en concaténant les sommets dans l’ordre du parcours.

• Retirer le premier élément d’une liste avec pop(0) a une complexité en O(n), tandis qu’une file comme deque convient à l’ajout en fin et au retrait en tête.

📖 11. Parcours en profondeur et cycles

🔑 Notions clés & Définitions

• Parcours en profondeur : Explore un graphe en allant aussi loin que possible depuis un sommet avant de revenir sur ses pas.

★ À maîtriser

• À chaque étape, le parcours en profondeur prend le premier voisin non vu, l’ajoute aux successeurs du sommet courant, mémorise son prédécesseur et l’empile ; s’il n’existe aucun nouveau voisin, il dépile le sommet et le marque comme épuisé.

Compléments

• Le parcours en profondeur utilise une pile représentant le chemin en cours, avec le sommet de départ au bas et le sommet exploré au sommet de la pile.

• Dans l’algorithme de parcours en profondeur présenté, le statut 0 signifie non vu, 1 signifie en cours sur le chemin et 2 signifie épuisé, sans successeur à explorer.

• Dans un graphe non orienté, un sommet épuisé qui possède un voisin encore marqué en cours sur le chemin peut révéler un cycle, mais cette méthode ne détecte pas nécessairement tous les cycles.

• Dans l’exemple, la chaîne A-B-C-E-D révèle le cycle BCDEB, car D possède le voisin B encore présent sur le chemin.

💡 Astuce mémo

La largeur avance par file ; la profondeur s’enfonce avec une pile.

📖 12. Plus courts chemins pondérés

🔑 Notions clés & Définitions

• Algorithme de Dijkstra : Calcule les plus courtes distances depuis un sommet vers tous les autres sommets connexes d’un graphe pondéré orienté ou non, si tous les poids sont positifs ou nuls.
• Algorithme A* : Choisit un sommet non exploré selon un coût combinant la distance déjà parcourue depuis l’origine et une heuristique estimant sa distance jusqu’à la destination.

★ À maîtriser

• Dijkstra initialise toutes les distances à l’infini et celle du départ à 0, choisit à chaque tour le sommet non exploré de distance minimale, le marque comme exploré, puis met à jour les distances de ses voisins non marqués avec le minimum entre leur distance actuelle et la distance du sommet courant augmentée du poids de l’arc ou de l’arête.

📐 Formule - Dans A*, le coût d’un sommet S est $\operatorname{cout}(S)=d(S)+h(S)$, où d(S) est la distance calculée depuis l’origine et h(S) l’heuristique estimant la distance jusqu’à la destination.

Compléments

• La mise à jour d’une distance dans Dijkstra s’écrit $$D(s')=\min\bigl(D(s'),D(s_{act})+w(s_{act},s')\bigr).

• Pour reconstituer les chemins minimaux, il suffit d’enregistrer le sommet courant comme prédécesseur de s’ lorsque sa distance est améliorée.

• Dijkstra est un algorithme glouton dont le choix du sommet non exploré de distance minimale peut être accéléré à l’aide d’une file de priorité.

• La distance euclidienne peut servir d’heuristique dans A*, et l’heuristique ne doit pas surestimer la distance jusqu’à la destination si l’on veut préserver un résultat optimal.

💡 Astuce mémo

Dijkstra classe par distance depuis le départ ; A* ajoute une estimation vers l’arrivée.

📖 13. Programmation dynamique et applications

🔑 Notions clés & Définitions

• Programmation dynamique : Résout un problème en le décomposant en sous-problèmes liés et en réutilisant les résultats déjà calculés.

★ À maîtriser

📌 La programmation dynamique repose sur une sous-structure optimale, où une solution optimale contient des solutions optimales de sous-problèmes, et sur le chevauchement des sous-problèmes, qui permet de réutiliser des calculs.

📌 Pour rendre la monnaie, l’algorithme glouton choisit à chaque fois la plus grande pièce possible, mais il ne garantit pas toujours le nombre minimal de pièces.

📐 Formule - Pour des pièces de valeurs appartenant à L, le nombre minimal de pièces pour rendre n vérifie $t_n=1+\min_{c\in L,\ c\le n}t_{n-c}$, avec $t_0=0$.

📐 Formule - Dans un tableau de valeurs positives parcouru vers le haut ou la droite, le gain maximal à la case (i,j) vérifie $t_{i,j}=a_{i,j}+\max(t_{i-1,j},t_{i,j-1})$.

Compléments

📌 Une approche Top-Down part du problème demandé et descend récursivement vers les sous-problèmes, tandis qu’une approche Bottom-Up calcule les petites instances avant de remonter vers la solution.

• Pour la suite de Fibonacci définie par F₀=F₁=1 et Fₙ=Fₙ₋₁+Fₙ₋₂ pour n≥2, la mémoïsation évite de recalculer plusieurs fois les mêmes termes.

• Pour Fibonacci, la mémoïsation fait passer la complexité de l’algorithme récursif basique d’exponentielle à linéaire, tandis que la version récursive reste limitée par la profondeur de récursion de Python.

• Avec les pièces de valeurs 1, 4 et 6, l’algorithme glouton rend 8 avec trois pièces (6+1+1), alors que deux pièces de 4 suffisent.

• Pour reconstruire les pièces rendues, on peut mémoriser une pièce ou un montant prédécesseur à chaque amélioration du minimum, puis remonter récursivement jusqu’au montant nul.

• Pour calculer les gains maximaux d’un tableau, on initialise la première ligne et la première colonne, puis on remplit les autres cases ligne par ligne à l’aide de la relation de récurrence.

• Le calcul du tableau des gains maximaux pour une matrice de p lignes et q colonnes a une complexité en O(pq).

• Pour reconstituer un chemin optimal dans le tableau, on part de la case terminale et on remonte à chaque étape vers la case précédente de gain maximal, ou l’on suit les prédécesseurs mémorisés lors du calcul.

📖 14. Partition équilibrée d’entiers

🔑 Notions clés & Définitions

• Partition équilibrée : Répartit les éléments d’une liste d’entiers positifs en deux sous-listes dont les sommes sont aussi proches que possible.

★ À maîtriser

• Pour construire les sommes atteignables avec les k premiers éléments, on conserve les sommes déjà possibles et on leur ajoute celles obtenues en ajoutant le terme suivant ; on cherche ensuite la plus grande somme atteignable inférieure ou égale à la moitié du total.

• La programmation dynamique calcule les sous-sommes atteignables en ajoutant successivement chaque terme : à chaque étape, les sommes possibles sont les précédentes et celles obtenues en ajoutant le nouveau terme.

Compléments

• Pour deux sous-listes L₁ et L₂ de sommes respectives S(L₁) et S(L₂), l’objectif est de minimiser $|S(L_1)-S(L_2)|$ sous les contraintes qu’elles forment une partition de la liste.

• Si la somme totale des éléments vaut s, minimiser l’écart entre les deux sous-listes revient à chercher une sous-liste dont la somme est la plus proche possible de s/2.

📌 Pour la partition équilibrée, l’approche gloutonne et l’énumération de toutes les partitions ne sont pas adaptées : la première peut échouer et la seconde a une complexité en O(n2ⁿ).

• On reconstruit une partition en remontant les dictionnaires de sous-sommes depuis la somme cible, en retrouvant à chaque étape le dernier entier utilisé puis en le soustrayant à la somme restante.

• La complexité de la méthode par programmation dynamique pour les sous-sommes est décrite comme à peu près quadratique, sans analyse précise des coûts de création et d’ajout dans les dictionnaires.

📖 15. Plus longue sous-séquence commune

🔑 Notions clés & Définitions

• Sous-séquence : Suite de caractères pris dans l’ordre de la chaîne, sans nécessairement être consécutifs.
• Plus longue sous-séquence commune : Sous-séquence présente dans les deux chaînes et de longueur maximale.

★ À maîtriser

• Le calcul des plus longues sous-séquences communes de préfixes est réutilisé dans de nombreux calculs de préfixes plus grands, ce qui crée un chevauchement important des sous-problèmes et motive la programmation dynamique.

Compléments

📌 Si les derniers caractères de deux chaînes sont égaux, ils terminent une plus longue sous-séquence commune, obtenue en ajoutant ce caractère à une plus longue sous-séquence commune des deux préfixes précédents.

📌 Si les derniers caractères des deux chaînes sont différents, la longueur recherchée est le maximum des longueurs obtenues en retirant le dernier caractère de l’une ou de l’autre chaîne.

📖 16. Classification par k plus proches voisins

🔑 Notions clés & Définitions

• Matrice de confusion : Tableau comparant les catégories détectées par l’algorithme, en lignes, aux catégories réelles, en colonnes, à partir des données de test.

★ À maîtriser

• L’algorithme des k plus proches voisins est un algorithme d’apprentissage supervisé qui attribue à un nouvel objet la catégorie dominante parmi ses k voisins de référence les plus proches.

• KNN calcule les distances entre le nouveau point et les données étiquetées, conserve les k indices les plus proches, détermine la catégorie dominante parmi eux, puis renvoie cette catégorie.

Compléments

• Une image en niveaux de gris de taille n × n peut être représentée par un vecteur de n² composantes correspondant aux valeurs des pixels, comprises par exemple entre 0 et 255 ou renormalisées entre 0 et 1.

• La recherche des k plus petites distances par un algorithme inspiré du tri par insertion a une complexité en O(k·n), où n est le nombre de données.

📌 Une valeur impaire de k est souvent choisie pour favoriser une catégorie dominante, mais une égalité reste possible lorsque plusieurs catégories sont représentées.

• Dans une matrice de confusion, une détection est jugée satisfaisante lorsque les valeurs de la diagonale sont grandes et les autres petites.

📖 17. Regroupement par k-moyennes

★ À maîtriser

• L’algorithme des k-moyennes est un algorithme d’apprentissage non supervisé qui regroupe des points proches sans disposer de catégories de référence.

• Les k-moyennes choisissent aléatoirement k centres, affectent chaque donnée au centre le plus proche, recalculent les barycentres des classes, puis répètent ces opérations jusqu’à stabilisation des classes.

Compléments

• La convergence des k-moyennes signifie qu’à partir d’un certain moment les classes n’évoluent plus.

• La somme des distances des points au barycentre de leur classe peut servir à évaluer un regroupement et à comparer des choix de centres initiaux ou de k.

• Les k-moyennes peuvent converger vers des regroupements différents selon le choix aléatoire des centres de départ.

📖 18. Schéma des tables CLIENTS et PARTENAIRES

🔑 Notions clés & Définitions

• Nombres de Bernoulli : La suite des nombres de Bernoulli $(b_n)_{n\in\mathbb{N}}$ est définie par $b_0=1$ et, pour tout entier $n\geq 1$, $b_n=-\frac{1}{n+1}\sum_{k=0}^{n-1}\binom{n+1}{k}b_k$.

★ À maîtriser

• Pour extraire les identifiants des clients provenant de Toulouse, la requête SQL filtre la table CLIENTS sur ville = "Toulouse" et sélectionne id.

• Pour extraire les emails des clients ayant SCEI comme partenaire, la requête SQL relie CLIENTS.id à PARTENAIRES.id_client, filtre partenaire = "SCEI" et sélectionne email.

📐 Formule - Pour tout entier $k\geq1$, la formule attribuée à Leonhard Euler exprime la valeur de zêta aux entiers pairs par $\zeta(2k)=\frac{(-1)^{k-1}2^{2k-1}\pi^{2k}b_{2k}}{(2k)!}$.

Compléments

• La table CLIENTS possède les attributs suivants :

  • id (entier, clé primaire)
  • nom (chaîne de caractères)
  • prenom (chaîne de caractères)
  • ville (chaîne de caractères)
  • email (chaîne de caractères)

• La table PARTENAIRES possède les attributs suivants : id (entier, clé primaire), id_client (entier correspondant à l’attribut id de CLIENTS), partenaire (nom du partenaire, chaîne de caractères)

• La valeur exacte de $b_{10}$ est $\frac{5}{66}$, et une approximation décimale est 0{,}075 757 575 757 575 76.

📊 Tableaux de synthèse

Structures de données séquentielles