GIF270 - Structures de données et complexité

programmes offrant cette activité pédagogique (cours)

Baccalauréat en génie informatique

Baccalauréat en génie robotique

Sommaire

Cycle
1er cycle
Crédits
2 crédits
Durée
1 trimestre
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.

Préalable(s)
Avoir obtenu 9 crédits