Algorithmique Avancée & Complexité

Ce cours approfondit l’algorithmique du S1 : il apprend à analyser rigoureusement le coût d’un algorithme, à concevoir des solutions efficaces à l’aide des grands paradigmes (diviser pour régner, programmation dynamique, glouton, backtracking), à choisir les structures de données adaptées (arbres équilibrés, tables de hachage, tas, graphes) et à reconnaître les problèmes difficiles pour lesquels on se contente d’heuristiques. Ces compétences sont décisives pour un développeur au Niger comme ailleurs : une application de Mobile Money qui traite des millions de transactions, un moteur de recherche de produits d’un site e-commerce ou l’optimisation des tournées de livraison d’une entreprise de Niamey exigent des algorithmes qui passent à l’échelle, sur des serveurs aux ressources souvent limitées. Tous les programmes sont écrits en Python 3 et ont été exécutés ; les résultats affichés sont reproductibles.

Objectifs d’apprentissage

• Maîtriser les paradigmes de conception algorithmique avancés : diviser pour régner, programmation dynamique.
• Analyser la complexité temporelle et spatiale des algorithmes avec rigueur mathématique.
• Concevoir des algorithmes efficaces sur les structures de données avancées : arbres, graphes.
• Résoudre des problèmes algorithmiques classiques de niveau intermédiaire (NP-complétude, heuristiques).

Prérequis

Algorithmique & Structures de Données (ALG1141) — GELO S1 ; Mathématiques Discrètes & Logique (MDS2121) — GELO S2 (récurrences, graphes, dénombrement).

Plan du cours

1. Leçon 1 — Analyse de la Complexité
2. Leçon 2 — Paradigmes Algorithmiques Avancés
3. Leçon 3 — Structures de Données Avancées
4. Leçon 4 — Problèmes Difficiles et Heuristiques

Travaux pratiques

• Le syllabus ne prévoit pas de TP encadrés (0 h de TP) ; les 8 h de TD alternent exercices sur papier et programmes Python à exécuter.
• Deux activités guidées proposées en travail personnel (TPE, 36 h) : tests empiriques de complexité sur des instances croissantes (Leçon 1) ; implémentation et comparaison d’algorithmes de tri et de recherche de chemin (Leçon 4).

Modalités d’évaluation

Volume horaire : CM 16 h, TD 8 h, TP 0 h, TPE 36 h, soit 60 h (CTT) — 3 crédits. Évaluation : contrôle continu (CC) 30 % + examen terminal (ET) 70 % ; nature mixte (M) : épreuves écrites et programmes.

Bibliographie

• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction à l’algorithmique, Dunod.
• S. S. Skiena, The Algorithm Design Manual, Springer.
• Complément : J. Kleinberg & É. Tardos, Algorithm Design, Pearson.