GM4 - Algorithmique et Structures de Données

Objectifs du cours

L'objectif de ce cours est d’aborder l’algorithmique et les structures de donnée avancées :

• Collections : File, Pile, Liste, Liste ordonnée, Ensemble, Dictionnaire, Arbre binaire, Arbre binaire de recherche, Graphe.
• Structures de données dynamiques : liste chaînée, arbre binaire, arbre-B.
• Algorithmes avancés : arbres AVL, programmation dynamique.

The objective of this course is to cover algorithms and advanced data structures:

• Collections: Queue, Stack, List, Ordered List, Set, Dictionary, Binary Tree, Binary Search Tree, Graph.
• Dynamic data structures: Linked List, Binary Tree, B-Tree.
• Advanced algorithms: AVL trees, Dynamic Programming.

Contenus

Rappels sur les TADs (Types Abstraits de Données)

• Définition et formalisme.
• Collections non récursives : Pile, File, Liste, ListeOrdonnée, Ensemble, Dictionnaire.
• Collections récursives : ListeChainée, TADs hiérarchiques.

Structures de données dynamiques

• Allocation statique vs allocation dynamique.
• Structures linéaires : liste chaînée, liste doublement chaînée.
• Structures hiérarchiques : arbre binaire.

Conception du TAD Collection

• Conception préliminaire : opérations, fonctions / procédures, utilisation.
• Conception détaillée :
  • Représentation à l’aide de tableaux.
  • Représentation à l’aide de structures de données dynamiques (SDD).
  • Utilisation de la SDD ListeChainée.
  • Utilisation de la SDD ArbreBinaire.
• Le TAD Dictionnaire : utilisation d’une table de hachage.

Graphes

• Conception détaillée :
  • Représentation par matrice.
  • Représentation par liste.
  • Représentation des étiquettes et des valeurs.
• Algorithmes sur les graphes :
  • Parcours (BFS/DFS).
  • Tri topologique.
  • Plus court chemin (Dijkstra).
  • A*.

Programmation dynamique

• Introduction à la programmation dynamique.
• Le problème du sac à dos (Knapsack Problem).

Arbres-B

• Recherche, insertion et suppression dans un arbre-B.

Compétences visées / Learning outcomes

• Concevoir et implémenter des structures de données avancées (listes chaînées, arbres, graphes, tables de hachage, etc.).
• Analyser la complexité algorithmique et choisir les structures de données adaptées à un problème donné.
• Implémenter des algorithmes sur des structures complexes comme les arbres AVL, les arbres B et les graphes.
• Utiliser la programmation dynamique pour résoudre des problèmes d’optimisation.
• Modéliser des problèmes à l’aide de TADs et de leurs représentations concrètes.
• Comparer les stratégies d’allocation statique et dynamique dans la conception de structures de données.

• Design and implement advanced data structures (linked lists, trees, graphs, hash tables, etc.).
• Analyze algorithmic complexity and select appropriate data structures for specific problems.
• Implement algorithms on complex data structures such as AVL trees, B-trees, and graphs.
• Apply dynamic programming to solve optimization problems.
• Model problems using Abstract Data Types (ADTs) and their concrete representations.
• Compare static and dynamic memory management strategies in data structure design.

Bibliographie / Bibliography

• Introduction à l'algorithmique
  Thomas Cormen, Charles Leiserson, Ronald Rivest
  Dunod — ISBN : 2-10-003128-7
• Structures de données et algorithmes
  Alfred Aho, John Hopcroft, Jeffrey David Ullman
  InterÉditions — ISBN : 978-2-7296-0194-2
• Data Structures and Algorithms
  Alfred V. Aho, Jeffrey D. Ullman, John E. Hopcroft
  Addison-Wesley — ISBN : 978-0201000238