GIF270 - Structures de données et complexité
Présentation
Sommaire
- Cycle
- 1er cycle
- Crédits
- 2 crédits
- Faculté/Centre
- Faculté de génie
Cible(s) de formation
Sélectionner et utiliser les structures de données appropriées pour solutionner un problème donné; analyser la complexité des algorithmes applicables à un problème donné.
Contenu
Structures de données : listes, graphes, arbres, tableaux de hachage, ensembles. Tri. Algorithmes associés : tri à bulles, tri fusion, tri rapide, listes chaînées et doublement chaînées, insertion, retrait, flot maximum, coupe minimum, détection de cycles, largeur d’abord, profondeur d’abord, recherche binaire, équilibrage, fonctions de hachage.
Complexité des algorithmes : machine de Turing, complexité P, NP, pire cas, meilleur cas, cas moyen.