Programme de la formation
Maîtriser les Fondamentaux et Concepts Avancés en Algorithmique

• 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.

• 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.

• 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.

• 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é.

• 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.

• Plus courts chemins dans les graphes
• Arbres couvrants minimaux (ACM)
• Algorithmes gloutons (Greedy Algorithms)

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

• 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.

• 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.

• 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.

• 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.