Formation Maîtriser les Fondamentaux et Concepts Avancés en Algorithmique

01.Introduction et complexité des algorithmes

• —Rappels fondamentaux et définitions de l'algorithmique.
• —Notions de complexité temporelle et spatiale: notation O, Ω, Θ.
• —Analyse des cas pire, meilleur et moyen. Exemples pratiques.

02.Structures de données fondamentales et avancées

• —Révision des listes, piles, files, arbres binaires.
• —Graphes: représentation (matrice, listes d'adjacence).
• —Tables de hachage: résolution des collisions.

03.Algorithmes de tri avancés et recherche dichotomique

• —Tri fusion (Merge Sort), tri rapide (Quick Sort), tri par tas (Heap Sort).
• —Analyse comparative des performances des algorithmes de tri.
• —Recherche dichotomique sur tableaux et listes triées.

04.Programmation dynamique: principes et applications

• —Introduction à la programmation dynamique: optimisation de problèmes récursifs.
• —Résolution du problème du sac à dos (Knapsack Problem).
• —Calcul des nombres de Fibonacci optimisé.

05.Algorithmes de graphes: parcours et connectivité

• —Parcours en largeur (BFS) et en profondeur (DFS).
• —Recherche de composants fortement connexes (Kosaraju, Tarjan).
• —Application: détection de cycles.

06.Plus courts chemins dans les graphes

07.Arbres couvrants minimaux (ACM)

08.Algorithmes gloutons (Greedy Algorithms)

• —Principes des algorithmes gloutons.
• —Problème du rendu de monnaie.
• —Problème de sélection d'activités.

09.Algorithmes de hachage et fonctions de hachage

• —Fonctions de hachage cryptographiques vs. non-cryptographiques.
• —Applications avancées des tables de hachage.
• —Collision, uniformité et bonnes pratiques.

10.Algorithmes de compression de données

• —Codage de Huffman: principe et construction de l'arbre.
• —Algorithmes basés sur les dictionnaires: LZ77, LZ78, LZW.
• —Concepts de taux de compression et limites.

11.Introduction aux algorithmes de chaînes de caractères

• —Recherche de motifs: algorithmes de Knuth-Morris-Pratt (KMP).
• —Algorithme de Rabin-Karp.
• —Algorithmes de matching approximatif.

12.Introduction à la complexité et problèmes NP-Complets

• —Classes de complexité P, NP, NP-Complet.
• —Réduction polynomiale: exemples concrets.
• —Stratégies d'approche pour les problèmes NP-difficiles: heuristiques et approximations.