Lernzettel: Structures de données et algorithmes fondamentaux

📋 Plan du Cours

1. Structures de données
2. Listes chaînées, piles et files
3. Arbres binaires et ABR
4. Graphes et représentations
5. Modèle relationnel et normalisation
6. SQL et manipulation des données
7. Architecture matérielle et systèmes
8. Protocoles réseau et routage
9. Récursivité, POO et modularité
10. Tri et recherche dichotomique
11. Parcours de graphes et Dijkstra
12. Complexité algorithmique

📖 1. Structures de données

🔑 Notions clés & Définitions

• Structure de données : Une structure de données organise et stocke des informations pour faciliter l’accès et les opérations nécessaires aux algorithmes.
• Choix de structure : Choisir la bonne structure conditionne les performances, car les coûts (temps/mémoire) varient selon l’opération.

📝 Points essentiels

• Une mauvaise structure peut dégrader fortement le temps d’accès et ralentir l’algorithme global.

📖 2. Listes chaînées, piles et files

🔑 Notions clés & Définitions

• Liste chaînée : Une liste chaînée est une suite de maillons où chaque maillon stocke une valeur et une référence vers le suivant.
• Pile : Une pile est une structure LIFO où le dernier élément empilé est le premier dépilé.
• File : Une file est une structure FIFO où le premier élément entré est le premier sorti.

📝 Points essentiels

• Dans une liste chaînée, l’accès par indice n’est pas direct : accéder à un élément nécessite de parcourir depuis la tête en O(n).
• Sur une liste chaînée, l’insertion et la suppression en tête sont en O(1).
• Une pile vide fait échouer pop et top via une exception IndexError quand aucune valeur n’est empilée.
• Une file utilise une structure de type deque et défile avec popleft, ce qui modélise le FIFO.

💡 Astuce mémo

LIFO = Last In First Out (dernier entré = premier sorti) ; FIFO = premier entré = premier sorti.

📖 3. Arbres binaires et ABR

🔑 Notions clés & Définitions

• Arbre binaire : Un arbre binaire est une structure hiérarchique où chaque nœud a au plus un fils gauche et un fils droit.
• Feuille : Une feuille est un nœud d’un arbre binaire qui ne possède aucun fils.
• Hauteur d’un arbre : La hauteur d’un arbre est le nombre d’arêtes du chemin le plus long entre la racine et une feuille.
• Arbre binaire de recherche : Un ABR est un arbre binaire tel que les valeurs du sous-arbre gauche sont inférieures et celles du sous-arbre droit sont supérieures.
• Parcours infixe : Le parcours infixe visite gauche puis racine puis droite, ce qui donne un ordre croissant pour un ABR.

📝 Points essentiels

• La hauteur vaut -1 si l’arbre est None, et la taille vaut 0 si l’arbre est None.
• Pour un ABR équilibré, la recherche et l’insertion ont un comportement proche de O(log n), tandis que le pire cas dégénère en O(n).
• L’insertion d’une valeur égale à un nœud ne modifie pas l’arbre car le cas valeur < et valeur > seulement sont traités.

💡 Astuce mémo

ABR : Gauche plus petit, Droite plus grand ; Infixe = tri naturel (croissant).

📖 4. Graphes et représentations

🔑 Notions clés & Définitions

• Graphe : Un graphe est un ensemble de sommets reliés par des arêtes, orientées ou non, et éventuellement pondérées.
• Matrice d’adjacence : La matrice d’adjacence code les arêtes dans un tableau 2D où matrice[i][j] indique la présence d’une arête de i vers j.
• Liste d’adjacence : La liste d’adjacence associe à chaque sommet la liste de ses voisins, ce qui économise la mémoire pour les graphes creux.

📝 Points essentiels

• Avec une matrice d’adjacence, tester l’existence d’une arête se fait en O(1), mais la mémoire coûte O(n²).
• Avec une liste d’adjacence, on évite de stocker les absences, ce qui réduit l’espace pour les graphes creux.

💡 Astuce mémo

Matrice = rapide en test, mais lourde en mémoire ; Liste = légère si peu d’arêtes.

📖 5. Modèle relationnel et normalisation

🔑 Notions clés & Définitions

• Modèle relationnel : Le modèle relationnel représente les données sous forme de tables décrites par un schéma et composées de lignes.
• Clé primaire : La clé primaire identifie de façon unique chaque enregistrement d’une table et ne peut pas être NULL.
• Clé étrangère : La clé étrangère référence la clé primaire d’une autre table pour relier les données entre tables.
• 1NF : La première forme normale impose que chaque attribut contienne une valeur atomique, sans valeurs multiples.
• 2NF : La deuxième forme normale impose que chaque attribut non clé dépende de l’ensemble de la clé primaire.

📝 Points essentiels

• La propriété clé étrangère garantit l’intégrité référentielle en liant les lignes via des références vers une clé primaire existante.

💡 Astuce mémo

1NF atomique, 2NF dépend de la clé entière, 3NF supprime la dépendance transitive.

📖 6. SQL et manipulation des données

🔑 Notions clés & Définitions

• SELECT : SELECT construit une requête SQL pour récupérer des colonnes en filtrant et en triant via les clauses WHERE et ORDER BY.
• Jointure : Une jointure combine des tables pour afficher des informations liées, comme les notes associées à chaque élève.
• INSERT : INSERT crée de nouvelles lignes dans une table en fournissant les valeurs des colonnes.
• UPDATE : UPDATE modifie des valeurs existantes dans des lignes sélectionnées par une condition WHERE.
• DELETE : DELETE supprime des lignes correspondant à une condition définie dans la clause WHERE.

📝 Points essentiels

• Une requête de comptage par classe utilise GROUP BY et COUNT(*) pour produire une valeur agrégée par groupe.
• Une jointure d’élèves et notes relie e.id à n.id_eleve et peut filtrer des notes avec WHERE puis trier avec ORDER BY.
• Un UPDATE de note cible une ligne avec une condition double (id_eleve et matiere) pour éviter de toucher d’autres lignes.

📖 7. Architecture matérielle et systèmes

🔑 Notions clés & Définitions

• Architecture de von Neumann : L’architecture de von Neumann organise l’exécution via un CPU qui traite les instructions et une RAM qui stocke données et programmes temporairement.
• Hiérarchie des mémoires : La hiérarchie des mémoires ordonne la vitesse et la capacité des registres vers le cache, puis la RAM, puis le stockage secondaire.
• Processus : Un processus est un programme en cours d’exécution avec un état qui évolue pendant son cycle de vie.
• Ordonnanceur : L’ordonnanceur choisit à chaque instant quel processus doit s’exécuter parmi ceux prêts.
• Interblocage : L’interblocage est une situation où des processus s’attendent mutuellement pour avancer, bloquant l’exécution.

📝 Points essentiels

• La RAM stocke temporairement à la fois les données et les programmes, tandis que les registres sont très rapides et très petits.
• Le système gère des états de processus comme prêt, en exécution, en attente et terminé.
• Round Robin, priorité et FCFS sont des exemples d’algorithmes d’ordonnancement mentionnés dans le cours.

💡 Astuce mémo

CPU exécute, RAM stocke temporairement, bus relie ; OS choisit via l’ordonnanceur.

📖 8. Protocoles réseau et routage

🔑 Notions clés & Définitions

• TCP : TCP assure une transmission fiable via connexion et mécanismes de vérification et retransmission.
• UDP : UDP transmet rapidement sans garantie de fiabilité, ce qui convient à des usages tolérants aux pertes.
• IP : IP attribue une adresse unique à chaque machine et assure le routage au niveau Internet.
• DNS : DNS traduit les noms de domaine en adresses IP.
• RIP : RIP est un protocole de routage qui utilise le nombre de sauts pour choisir les routes.

📝 Points essentiels

• IPv4 utilise 32 bits pour représenter une adresse, alors qu’IPv6 en utilise 128.
• HTTPS ajoute le chiffrement TLS au protocole HTTP pour sécuriser les échanges.
• IP (au sens du cours) donne l’adresse unique aux machines, tandis que TCP/UDP gèrent la couche transport.

💡 Astuce mémo

RIP = sauts ; OSPF = coût des liens + Dijkstra.

📖 9. Récursivité, POO et modularité

🔑 Notions clés & Définitions

• Récursivité : La récursivité est une technique où une fonction s’appelle elle-même pour résoudre un problème en le réduisant.
• Cas de base : Le cas de base est la condition d’arrêt d’une fonction récursive qui évite l’appel infini.
• POO : La programmation orientée objet structure le code autour d’objets qui regroupent des données et des comportements.
• Classe : Une classe est un plan à partir duquel on crée des objets, appelés instances.
• Encapsulation : L’encapsulation regroupe attributs et méthodes dans une classe et limite l’accès direct selon les conventions de nommage.

📝 Points essentiels

• Une fonction récursive doit avoir un appel récursif qui converge vers le cas de base pour terminer.
• Chaque appel récursif empile un nouveau contexte d’exécution, et trop d’appels provoquent un RecursionError en Python avec une limite par défaut de 1000.
• En Python, un fichier .py correspond à un module importable via import ou from ... import ....

💡 Astuce mémo

Récursif = base + réduction ; pile d’appels = risque de RecursionError si trop profond.

📖 10. Tri et recherche dichotomique

🔑 Notions clés & Définitions

• Tri par insertion : Le tri par insertion insère chaque élément à la bonne position dans la partie déjà triée.
• Tri fusion : Le tri fusion divise le tableau, trie récursivement les moitiés, puis fusionne deux listes triées.
• Tri rapide : Le tri rapide choisit un pivot pour partitionner en éléments inférieurs, égaux et supérieurs, puis trie récursivement chaque partie.
• Recherche dichotomique : La recherche dichotomique cherche dans un tableau trié en comparant l’élément au milieu et en éliminant la moitié à chaque étape.

📝 Points essentiels

• Le tri par insertion est O(n²) en moyenne et au pire, et O(n) au meilleur cas quand la liste est déjà triée.
• Le tri fusion est O(n log n) dans tous les cas et nécessite de la mémoire supplémentaire, donc n’est pas en place.
• Le tri rapide est O(n log n) en moyenne et O(n²) au pire cas si le pivot est mal choisi.
• La recherche dichotomique retourne -1 quand la valeur n’est pas trouvée dans le tableau trié.

💡 Astuce mémo

Insertion : simple mais quadratique ; Fusion : régulier n log n ; Rapide : rapide en moyenne, fragile au pire.

📖 11. Parcours de graphes et Dijkstra

🔑 Notions clés & Définitions

• BFS : BFS explore les sommets par niveaux de distance croissante depuis un départ en utilisant une file.
• DFS : DFS explore en profondeur en tentant d’aller le plus loin possible avant de revenir en arrière.
• Relaxation : La relaxation met à jour la meilleure distance connue d’un voisin si un chemin via le sommet courant donne une amélioration.
• Algorithme de Dijkstra : Dijkstra calcule des plus courts chemins depuis une source vers tous les sommets d’un graphe pondéré à poids positifs.

📝 Points essentiels

• BFS rend utile la découverte d’un plus court chemin en nombre d’arêtes dans un graphe non pondéré grâce à l’exploration par niveaux.
• DFS peut servir à détecter des cycles et aussi pour des ordres topologiques selon le cours.
• Dijkstra initialise les distances à l’infini sauf la source à 0 et sélectionne ensuite le sommet non visité de distance minimale.
• Dijkstra effectue la mise à jour via relaxation et pousse les nouvelles paires (distance, sommet) dans une file de priorité.

📖 12. Complexité algorithmique

🔑 Notions clés & Définitions

• Complexité asymptotique : La complexité asymptotique décrit comment le temps ou la mémoire d’un algorithme croît quand la taille d’entrée n augmente.
• Notations O : La notation O exprime un ordre de grandeur de la complexité dans le pire cas à l’aide d’une fonction de n.

📝 Points essentiels

• O(1) correspond à un accès direct à un élément comme un accès par indice dans un tableau.
• La recherche dichotomique est en O(log n) car l’espace de recherche est coupé par deux à chaque comparaison.
• Le tri par insertion a une complexité O(n²) dans le pire cas, tandis que la Fibonacci naïve suit O(2ⁿ).
• Tri fusion et tri rapide (moyenne) sont en O(n log n), tandis que le parcours d’un tableau est en O(n).

📅 Repères chronologiques

Date	Événement
1970	Publication associée au modèle relationnel par Edgar F. Codd
1945	Mise en place de l’architecture de von Neumann
1959	Algorithme de Dijkstra

📊 Tableaux de synthèse

Comparaison des représentations de graphes

Représentation	Test d’arête	Mémoire
Matrice d’adjacence	O(1)	O(n²)
Liste d’adjacence	Non précisé	Plus économe pour graphes creux

Comparaison de tri (complexités et propriétés)

Tri	Complexité	Propriété annoncée
Insertion	O(n²) moyen/pire ; O(n) meilleur	stable ; en place
Tri fusion	O(n log n) tous cas	stable ; pas en place
Tri rapide	O(n log n) moyen ; O(n²) pire	instable ; en place

⚠️ Pièges & confusions fréquents

1. Confondre la file FIFO avec la pile LIFO mène à inverser push/pop et enqueue/dequeue.
2. Penser que l’accès par indice fonctionne aussi vite dans une liste chaînée que dans une liste Python conduit à ignorer le coût O(n).
3. Croire que Dijkstra fonctionne avec des poids négatifs contredit l’hypothèse du cours sur des poids positifs.
4. Interpréter l’infixe d’un ABR comme une simple visite sans conséquence temporelle fait perdre l’idée d’ordre croissant pour les valeurs.
5. Confondre la recherche dichotomique avec la dichotomie sur une liste non triée produit un résultat non garanti.
6. Oublier que la hauteur de l’arbre vide est -1 (et non 0) fausse les calculs sur des cas limites.

✅ Checklist Examen

1. Définir une liste chaînée et expliquer pourquoi l’accès par indice n’est pas en O(1).
2. Citer les opérations et le sens (LIFO) d’une pile et le comportement en cas de pile vide.
3. Citer les opérations et le sens (FIFO) d’une file et le lien avec BFS.
4. Définir un arbre binaire, et donner les définitions de feuille, taille et hauteur.
5. Lister les trois parcours (préordre, infixe, postordre) dans le bon ordre des visites.
6. Définir un ABR et relier le parcours infixe à l’ordre croissant des valeurs.
7. Décrire deux représentations de graphes (matrice et liste d’adjacence) et leurs compromis mémoire/test.
8. Définir clé primaire et clé étrangère et donner la contrainte “pas de NULL” pour la clé primaire.
9. Expliquer la normalisation via 1NF, 2NF et 3NF en termes de contraintes sur dépendances.
10. Lire et interpréter des requêtes SQL de sélection avec WHERE/ORDER BY, de comptage avec GROUP BY, et de jointure.
11. Connaître les syntaxes d’INSERT, UPDATE et DELETE avec une condition WHERE.
12. Décrire l’architecture de von Neumann et la hiérarchie des mémoires du cours.
13. Expliquer ce qu’est un processus, citer des états et le rôle de l’ordonnanceur et de l’interblocage.
14. Décrire le rôle des couches TCP/IP du cours et rappeler le chiffrement TLS pour HTTPS.