GIF270 - Structures de données et complexité

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.00 crédits

---

* Sujet à changement