Fiche de révision : Introduction aux structures de données et algorithmes

📋 Plan du Cours

1. Structures de données
2. Mise au point de programmes
3. Piles
4. Programmation orientée objet
5. Graphes et représentations
6. Récursivité
7. Diviser pour régner
8. Files
9. Arbres et processus
10. Bases de données
11. Parcours de graphes et routage
12. Arbres binaires et programmation dynamique

📖 1. Structures de données

🔑 Notions clés & Définitions

• Structure de données : Une structure de données est une façon d’organiser et de stocker des informations, en précisant les valeurs possibles et les opérations pour les manipuler.
• Type de données abstrait : Un type de données abstrait (TDA) décrit les propriétés d’une structure et surtout son interface, c’est-à-dire l’ensemble des opérations disponibles.
• Ensemble dynamique : Un ensemble d’éléments est dit dynamique s’il permet l’insertion et la suppression d’éléments pendant l’exécution.
• Liste simplement chaînée : Une liste simplement chaînée est une structure linéaire et dynamique dont chaque élément pointe vers le suivant, la liste étant pointée par sa tête.
• Dictionnaire tableau associatif : Un dictionnaire est une structure dynamique qui associe des clés à des valeurs via des couples clé:valeur et offre insertion, modification, suppression et recherche.

📝 Points essentiels

• Un TDA se voit comme un cahier des charges : l’interface est fixée, mais plusieurs implémentations peuvent exister.
• La complexité (temps et mémoire) d’une opération dépend de l’implémentation choisie, et pas du TDA.
• Dans un tableau indicé de taille fixe, l’accès à une case se fait en donnant son indice, avec uniquement lecture et modification comme opérations de base.
• Dans une liste simplement chaînée, la liste est vide quand la tête vaut NIL, et le dernier élément est celui dont succ vaut NIL.
• Parcours d’une liste de n objets : la recherche peut nécessiter de parcourir toute la liste, ce qui donne une complexité O(n) dans le pire cas.
• Un dictionnaire permet d’accéder à une valeur à partir d’une clé pour insérer, modifier, supprimer ou rechercher un couple clé:valeur.

💡 Astuce mémo

TDA = cahier des charges d’interface ; implémentation = coût (temps/mémoire)

📖 2. Mise au point de programmes

🔑 Notions clés & Définitions

• assert : Instruction qui vérifie une condition et déclenche une erreur si la condition est fausse.
• exception : Événement anormal détecté pendant l’exécution qui peut interrompre le programme s’il n’est pas géré.
• try except : Structure Python qui permet d’attraper manuellement une exception et de continuer sans arrêter le script.
• développement piloté par les tests : Méthode de développement où l’on écrit d’abord des tests correspondant aux spécifications avant d’implémenter le code.
• doctest : Module Python qui exécute automatiquement des exemples écrits dans une docstring et compare la sortie attendue à la sortie réelle.

📝 Points essentiels

• L’instruction assert attend une expression booléenne et peut fournir un message d’erreur si la condition est fausse en écrivant assert test, message.
• Avec try...except..., l’objectif est de gérer une exception pour éviter l’arrêt du script lors d’un problème à l’exécution.
• En TDD, on commence par un test censé échouer avant d’écrire le code, puis on implémente le minimum pour le faire réussir.
• En TDD, chaque test doit viser un point précis et s’exprimer via une assertion unique.
• Lorsqu’un assert échoue dans une suite de tests, le programme s’arrête au premier échec, donc il faut traiter les assertions une par une.
• Avec doctest, une exécution correcte de tous les tests n’affiche rien à l’écran, tandis qu’en cas d’erreurs le module signale les exemples en échec.

💡 Astuce mémo

TDD : Red d’abord (test échoue) puis Green (code minimal) puis Refactor ensuite (idée de suite par tests).

📖 3. Piles

📖 4. Programmation orientée objet

📖 5. Graphes et représentations

🔑 Notions clés & Définitions

• Arbre libre : Un arbre libre est un graphe non orienté non vide, connexe et sans cycle.
• Chemin unique : Un chemin unique est le fait que deux sommets d’un arbre libre sont reliés par exactement une suite d’arêtes.
• Arbre enraciné : Un arbre enraciné est un arbre libre muni d’un nœud distingué, appelé racine.
• Père et fils : Dans un arbre enraciné, on nomme père le nœud plus proche de la racine et fils le nœud plus éloigné relié par une arête orientée.

📝 Points essentiels

• Dans un graphe non orienté non vide, être un arbre libre équivaut à avoir un unique chemin entre tout couple de nœuds.
• Dans un arbre libre, la connexité et l’absence de cycle donnent aussi l’équivalence connexe mais plus connexe après suppression d’une arête quelconque.
• Dans un arbre libre, on a la relation |E| = |V| - 1.
• En enracinant un arbre, on représente implicitement les arêtes comme orientées en s’éloignant de la racine (père vers fils).
• La longueur d’un chemin est le nombre d’arêtes parcourues.

💡 Astuce mémo

Arbre libre = Connexe + Sans cycle ⇒ Connexion garantie et chemin unique (et |E| = |V|−1).

📖 6. Récursivité

🔑 Notions clés & Définitions

• Définition récursive : Une définition récursive décrit un objet en le ramenant à un sous-cas plus simple, répété jusqu’à atteindre un cas de base.
• Appel récursif : Un appel récursif est une exécution d’une fonction qui se réappelle elle-même sur un sous-problème à partir de la même structure de données.
• Cas de base : Un cas de base est la condition d’arrêt de la récursion, utilisée pour éviter que les appels s’enchaînent indéfiniment.

📝 Points essentiels

• Dans un arbre binaire, la structure est donnée par une définition récursive : l’arbre est vide ou composé d’une racine et de deux sous-arbres binaires, ce qui se répète pour chaque nœud.
• Le parcours en profondeur (DFS) progresse en appelant récursivement l’exploration sur les voisins, avec un marquage des sommets pour ne pas les re-parcourir.
• Pour une fonction récursive sur une structure, une condition d’arrêt explicite (cas de base) est nécessaire, par exemple quand l’entrée vaut null ou quand aucun voisin blanc n’existe.
• La récursion n’est pas nécessairement obligatoire : certains parcours peuvent être obtenus sans récursivité en utilisant une pile à la place.
• Détecter un cycle avec DFS repose sur le fait de rencontrer un sommet déjà visité (gris) pendant l’exploration, ce qui indique l’existence d’un circuit.

💡 Astuce mémo

Cas de base = STOP : si l’entrée vaut null (ou si plus de voisins à explorer), la récursion s’arrête avant de boucler.

📖 7. Diviser pour régner

📖 8. Files

🔑 Notions clés & Définitions

• File FIFO : Une file FIFO est une structure qui suit l’ordre d’arrivée des éléments, avec insertion en fin et suppression en tête.
• Parcours en largeur BFS : Le parcours en largeur est un algorithme de parcours qui explore un graphe niveau par niveau à partir d’un sommet de départ.
• Couleur des sommets : La couleur d’un sommet (blanc ou gris) sert à mémoriser s’il n’a pas encore été découvert ou s’il l’a déjà été.
• Distance en nombre d’arêtes : La distance entre deux sommets est le nombre d’arêtes ou d’arcs nécessaires pour passer de l’un à l’autre.

📝 Points essentiels

• Dans BFS, on utilise une file pour traiter d’abord les sommets découverts le plus tôt, en retirant la tête puis en ajoutant à la queue les voisins non encore vus.
• Avant la boucle, tous les sommets sont mis en couleur blanc, puis le sommet de départ est passé en gris avant d’être inséré dans la file.
• En BFS, l’exploration se fait par distance croissante au sommet de départ, donc l’ordre des sommets visités dépend du sommet choisi en départ.
• Pour un graphe non orienté, le BFS explore la composante connexe du sommet de départ, c’est-à-dire tous les sommets accessibles depuis celui-ci.
• La complexité de BFS (avec listes d’adjacence) est en O(|S|+|A|), car chaque sommet est traité au plus une fois et chaque arc/chaque arête est considéré depuis ses extrémités.
• La distance utilisée dans l’idée de “niveau par niveau” est le nombre d’arêtes/arcs entre deux sommets.

💡 Astuce mémo

BFS = niveaux par distance + File FIFO : on sort toujours le plus ancien découvert (tête) puis on ajoute les nouveaux (queue).

📖 9. Arbres et processus

🔑 Notions clés & Définitions

• Arbre de récursion : Un arbre de récursion est l’organigramme des appels successifs d’un algorithme récursif, où chaque appel engendre des sous-appels plus petits.
• Mémorisation : La mémorisation est la technique qui enregistre les résultats déjà calculés pour éviter de refaire plusieurs fois les mêmes sous-calculs.
• Recoupement des sous-problèmes : Le recoupement des sous-problèmes correspond au fait que différents appels nécessitent les mêmes sous-problèmes, donc des résultats peuvent être réutilisés.

📝 Points essentiels

• Dans fib(n)=fib(n−1)+fib(n−2), l’ensemble des appels forme une structure arborescente, avec des feuilles atteignant les cas de base fib(1)=1 et fib(0)=0.
• Avec la récursion « classique », certains calculs comme fib(4) sont refaits plusieurs fois, ce qui crée des branches redondantes dans l’arbre de récursion.
• En programmation dynamique, on résout chaque sous-problème une seule fois puis on stocke sa solution pour réutiliser les résultats lors des recoupements.
• La programmation dynamique (introduite par Richard Bellman) est pertinente quand les sous-problèmes se recoupent, car cela évite les recomputations coûteuses.
• Dans le cas Fibonacci, la mémorisation transforme l’arbre complet de récursion en un processus où les valeurs déjà obtenues ne sont plus recalculées.

💡 Astuce mémo

Récursion = arbre; Mémorisation = panneau « déjà vu »; Programmation dynamique n’est utile que si plusieurs chemins veulent recalculer les mêmes sous-problèmes.

📖 10. Bases de données

🔑 Notions clés & Définitions

• SELECT : L’instruction SELECT sert à récupérer des enregistrements dans une table selon des colonnes choisies et éventuellement des filtres et un tri.
• WHERE : La clause WHERE filtre les enregistrements en ne gardant que ceux qui vérifient une ou plusieurs conditions.
• ORDER BY : La clause ORDER BY trie les résultats selon une ou plusieurs colonnes, avec un ordre croissant par défaut ou décroissant via DESC.
• SELECT DISTINCT : SELECT DISTINCT supprime les doublons dans les résultats en ne gardant qu’une seule occurrence de chaque ligne pour les colonnes demandées.
• COUNT DISTINCT : COUNT(DISTINCT colonne) compte uniquement les valeurs distinctes non vides de la colonne choisie, après application éventuelle de WHERE.

📝 Points essentiels

• Avec SELECT, * sélectionne toutes les colonnes, tandis qu’une liste de colonnes permet de n’en prendre que certaines.
• WHERE est optionnel, et ORDER BY est optionnel ; DESC indique un tri décroissant sur la colonne spécifiée.
• La variante SELECT DISTINCT supprime les doublons parmi les lignes correspondant aux colonnes sélectionnées.
• COUNT(*) compte tous les enregistrements, et COUNT(colonne) ne compte que les valeurs non vides de colonne.
• La syntaxe COUNT(DISTINCT colonne) permet de compter des valeurs distinctes non vides, par exemple avec un filtre sur Type.
• Une jointure interne s’écrit INNER JOIN ... ON, et JOIN seul équivaut à INNER JOIN.

💡 Astuce mémo

Pensez à la chaîne : WHERE = filtrer, ORDER BY = trier, DISTINCT = dédoublonner, COUNT = compter, JOIN = assembler.

📖 11. Parcours de graphes et routage

🔑 Notions clés & Définitions

• Algorithme glouton : Un algorithme glouton construit une solution étape par étape en faisant des choix locaux sans revenir en arrière.
• Programmation dynamique : La programmation dynamique calcule les solutions de sous-problèmes et les mémorise pour éviter les calculs redondants et obtenir une solution optimale.
• Sous-problème : Un sous-problème est une partie du problème initial dont la résolution aide à reconstruire la solution globale.
• Nombre minimum de pièces : Le nombre minimum de pièces à rendre pour une somme $X$ se note $N_b(X)$ et vaut $\infty$ si $X$ est impossible à rendre.

📝 Points essentiels

• Si un choix glouton mène à une impasse (par exemple l’absence d’une pièce nécessaire), l’algorithme peut ne trouver aucune solution même si une solution existe.
• Un algorithme glouton ne garantit pas l’optimalité : il peut donner une solution ou bloquer dans des cas où la solution optimale existe.
• Pour un problème d’optimisation par rendu de monnaie, on a la récurrence $N_b(0)=0$, $N_b(X)=\infty$ si $X<0$, et pour $X>0$ : $N_b(X)=1+\min_{1\le i\le n} N_b(X-p_i)$.
• Quand l’algorithme récursif refait plusieurs fois les mêmes calculs (par exemple le même sous-chemin), la programmation dynamique permet de mémoriser les réponses intermédiaires et de les réutiliser.
• La version naïve du rendu de monnaie par arbre de recherche traite tous les cas possibles (méthode par force brute) et peut renvoyer une valeur très grande pour rejeter les branches impossibles.

📖 12. Arbres binaires et programmation dynamique

📅 Repères chronologiques

📊 Tableaux de synthèse

BFS vs DFS (parcours de graphes)

⚠️ Pièges & confusions fréquents

1. Confondre TDA et implémentation : la complexité d’une opération dépend de l’implémentation, pas du TDA.
2. Croire qu’un assert continue le programme : en cas d’échec, les tests s’arrêtent au premier échec.
3. Inverser FIFO et LIFO : une file suit FIFO (tête sortie, queue insertion) tandis qu’une pile suit LIFO.
4. Penser qu’une liste chaînée permet un accès au i-ème élément en temps constant : l’accès coûte proportionnel à la distance à la tête.
5. Utiliser BFS en oubliant le marquage couleur : sans blanc/ gris, on peut re-parcourir des sommets et casser l’ordre niveau par niveau.
6. Se tromper dans l’enracinement d’un arbre : les arêtes sont orientées en s’éloignant de la racine (père → fils).
7. Confondre récursion et récursivité : la récursivité est le principe (fonction s’appelle elle-même), la récursion est l’action d’appeler (concret).

✅ Checklist Examen

1. Définir une structure de données et distinguer type de données abstrait (interface) et implémentation (coûts temps/mémoire).
2. Énoncer les opérations de base des tableaux indicés de taille fixe et les conséquences de l’accès par indice.
3. Décrire une liste simplement chaînée (tête, succ, NIL), dire quand la liste est vide et donner le coût O(n) de recherche dans le pire cas.
4. Définir un dictionnaire tableau associatif (clé→valeur) et citer les opérations TAD : insertion, modification, suppression, recherche.
5. Expliquer la différence d’usage entre assert et gestion d’exception (try...except) et les règles en TDD (test qui échoue, assertion unique, code minimal).
6. Présenter doctest : exécution correcte n’affiche rien, et en cas d’erreur le module signale les exemples en échec.
7. Définir pile LIFO et décrire l’implémentation par tableau (pileVide/pile pleine avec sommet) ou par liste Python (append/pop en O(1)).
8. Expliquer ce qu’est un arbre libre (connexe sans cycle) et la relation |E|=|V|−1, puis préciser père/fils et la direction des arêtes en arbre enraciné.
9. Définir récursivité (et cas de base) et justifier la détection de cycle avec DFS en rencontrant un sommet déjà visité (gris).
10. Donner le principe de BFS (file FIFO, couleurs, niveaux par distance) et la complexité O(|S|+|A|) telle qu’indiquée dans le cours.
11. Résumer diviser pour régner en 3 étapes puis calculer pourquoi tri fusion a O(n log2 n) (hauteur log2 n et fusion à chaque niveau).
12. Maîtriser le SQL du cours : clauses WHERE/ORDER BY/DISTINCT, COUNT(*), COUNT(DISTINCT...), INNER JOIN ... ON et les contraintes (clé primaire/clé étrangère, intégrité).