Algorithmique et programmation 2

Ce cours d’Algorithmique et programmation (semestre 2) prolonge le cours du semestre 1 (types, structures de contrôle, tableaux, sous-programmes, récursivité, tris, pointeurs). Il introduit les structures de données fondamentales, qui organisent l’information en mémoire pour la traiter efficacement : listes séquentielles et chaînées, piles, files, arbres n-aires et arbres binaires. Chaque structure est présentée comme un type abstrait (opérations et propriétés), puis par ses représentations (contiguë dans un tableau, ou chaînée par pointeurs), avec le coût de ses opérations. Ces structures sont omniprésentes en cybersécurité : liste noire d’adresses IP, pile d’appels d’un programme, file d’attente des alertes d’un SOC ou des paquets d’un routeur, arborescence de fichiers d’un serveur Linux, index de recherche dans des journaux. Les implémentations avancées en C (listes doubles, files de priorité, arbres équilibrés) seront approfondies en L2 (semestre 4).

Objectifs d’apprentissage

• Définir une structure de données comme type abstrait et choisir entre représentation contiguë et chaînée.
• Écrire les algorithmes d’insertion, de suppression, de recherche et de parcours sur une liste chaînée.
• Implanter piles et files (tableau, tableau circulaire, chaînage) et les appliquer (parenthésage, expressions postfixées, files d’attente).
• Maîtriser le vocabulaire des arbres et les parcours préfixe, infixe, postfixe et en largeur.
• Construire et interroger un arbre binaire de recherche, et estimer le coût des opérations.

Prérequis

Algorithmique et programmation S1 : tableaux, enregistrements, fonctions et procédures, récursivité, pointeurs et allocation dynamique en C.

Plan du cours

1. Listes séquentielles et listes linéaires chaînées
2. Les piles : principe LIFO, représentations et applications
3. Les files : principe FIFO, file circulaire et applications
4. Arbres généraux n-aires et arbres binaires

Modalités d’évaluation

Volume horaire : 20 h de CM, 10 h de TD, 10 h de TP et 40 h de TPE ; 4 crédits. Évaluation : contrôle continu (TD, comptes rendus des TP guidés en C, quiz en ligne) pour 40 % et examen terminal écrit (algorithmes sur listes, piles, files et arbres, traces d’exécution) pour 60 %.

Bibliographie

• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Algorithmique, Dunod.
• R. Sedgewick, Algorithms in C, parts 1-4, Addison-Wesley.
• D. E. Knuth, The Art of Computer Programming, vol. 1 : Fundamental Algorithms, Addison-Wesley.
• B. W. Kernighan, D. M. Ritchie, Le langage C : norme ANSI, Dunod.