Algorithmique et programmation 4

Ce cours d’Algorithmique et programmation (L2, semestre 4) fait suite au cours de programmation C du semestre 3 et approfondit, en langage C, les structures de données introduites en L1 : listes, piles, files et arbres. Là où le cours de L1 présentait les principes en pseudo-code, celui-ci vise des implémentations complètes, modulaires et sûres : tableau dynamique à redimensionnement (realloc), listes doublement chaînées et circulaires avec sentinelle, piles et files génériques, file de priorité par tas binaire, arbres n-aires en représentation premier fils – frère droit, arbres binaires de recherche avec suppression, et arbres équilibrés AVL. Chaque structure est analysée en complexité et testée avec les outils du développeur sécurisé (options d’avertissement, AddressSanitizer, valgrind). Ces structures sont au cœur des outils de sécurité : tri des alertes d’un SOC par criticité, parcours d’arborescences lors d’un contrôle d’intégrité de fichiers, index d’adresses IP d’un pare-feu, tables de sessions d’un IDS.

Objectifs d’apprentissage

• Implanter un tableau dynamique et analyser le coût amorti de son redimensionnement.
• Programmer des listes doublement chaînées et circulaires, avec gestion rigoureuse de la mémoire.
• Réaliser des piles et des files modulaires (fichiers .h/.c) et une file de priorité par tas binaire.
• Représenter un arbre n-aire en C et programmer ses parcours récursifs et itératifs.
• Programmer un ABR complet (recherche, insertion, suppression) et l’équilibrer par rotations AVL.

Prérequis

Algorithmique et programmation S1-S2 (structures de données en pseudo-code) et S3 (langage C : fonctions, tableaux, struct, pointeurs).

Plan du cours

1. Leçon 1 — Listes séquentielles dynamiques et listes chaînées avancées en C
2. Leçon 2 — Piles, files et files de priorité en C
3. Leçon 3 — Arbres généraux n-aires en C : représentation et parcours
4. Leçon 4 — Arbres binaires de recherche et arbres équilibrés AVL en C

Modalités d’évaluation

Volume horaire : 10 h de CM, 10 h de TD, 10 h de TP et 30 h de TPE ; 3 crédits. Évaluation : contrôle continu (TP guidés rendus avec code source et rapport valgrind, quiz en ligne) pour 40 % et examen terminal (écrit : traces d’exécution, écriture de fonctions C sur les structures) 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 et 3, Addison-Wesley.
• B. W. Kernighan, D. M. Ritchie, Le langage C : norme ANSI, Dunod.
• R. C. Seacord, Secure Coding in C and C++, Addison-Wesley.