Plan du cours Algorithmie Avancée

Introduction

1. Présentation du cours
   • Objectifs
   • Prérequis
   • Structure du cours

Partie 1: Fondements de l'Algorithmie

2. Rappels sur les algorithmes de base
   • Notions fondamentales
   • Complexité temporelle et spatiale
   • Notations asymptotiques (O, Ω, Θ)

Partie 2: Structures de Données Avancées

3. Arbres et Graphes
   • Arbres binaires de recherche
   • Arbres AVL, Arbres rouges-noirs
   • Graphes : Définitions, représentations (matrices d'adjacence, listes d'adjacence)
4. Structures de Données Probabilistes
   • Filtres de Bloom
   • Skip lists

Partie 3: Techniques de Conception d'Algorithmes

5. Programmation Dynamique
   • Introduction et principes
   • Exemples : problème du sac à dos, plus longue sous-séquence commune
6. Algorithmes Gloutons
   • Concepts et exemples
   • Algorithme de Prim, Kruskal
7. Diviser pour Régner
   • Techniques et applications
   • Tri rapide, Tri fusion

Partie 4: Algorithmes sur les Graphes

8. Parcours de Graphes
   • Parcours en profondeur (DFS)
   • Parcours en largeur (BFS)
9. Algorithmes de Plus Court Chemin
   • Dijkstra
   • Bellman-Ford
   • Floyd-Warshall
10. Algorithmes de Flots
    • Flot maximum : Ford-Fulkerson, Edmonds-Karp

Partie 5: Algorithmes de Recherche et Tri Avancés

11. Algorithmes de Tri
    • Tri fusion
    • Tri rapide
    • Tri par tas
12. Algorithmes de Recherche
    • Recherche binaire
    • Arbres de recherche équilibrés (AVL, arbres rouges-noirs)
    • Tables de hachage

Partie 6: Algorithmes Probabilistes et Approximatifs

13. Algorithmes Probabilistes
    • Monte Carlo vs Las Vegas
    • Applications et exemples
14. Algorithmes Approximatifs
    • Introduction et concepts
    • Exemples : problème du voyageur de commerce, couplage dans les graphes

Partie 7: Optimisation et Complexité

15. Introduction à la Théorie de la Complexité
    • Classes de complexité (P, NP, NP-complet, NP-difficile)
    • Réductions de problèmes
16. Méthodes d'Optimisation
    • Optimisation linéaire
    • Optimisation non linéaire
    • Méthodes heuristiques : recuit simulé, algorithmes génétiques

Partie 8: Algorithmes en Données Massives (Big Data)

17. Traitement des Données Massives
    • Introduction et enjeux
    • Algorithmes MapReduce
18. Streaming de Données
    • Modèles et techniques
    • Algorithmes de streaming

Conclusion

19. Résumé et Perspectives
    • Synthèse des concepts clés
    • Applications pratiques et avancées
    • Pistes pour aller plus loin