v2.11.0 (5776)

Enseignement scientifique & technique - INF101 : Structures de données et algorithmique

Domaine > Informatique.

Descriptif

Ce cours constitue une introduction à l'algorithmique et à l'optimisation combinatoire. On y introduit diverses structures de données (piles, files, arbres, graphes...) et des algorithmes de base pour des problèmes classiques (recherche, hachage, tris, codage de Huffman, arbre couvrant de poids minimum, plus courts chemins, parcours de graphes, flot de valeur maximum, coloration de graphes). On calculera la complexité de ces algorithmes et on abordera la notion de complexité d'un problème. On évoquera à cette occasion les attitudes possibles face aux problèmes d'optimisation difficiles à résoudre : résolution exacte (à l'aide de méthodes arborescentes par séparation et évaluation) ou approchée (à l'aide d'heuristiques). On montrera en outre comment modéliser certains problèmes pour les traiter à l'aide des algorithmes étudiés.

30 heures en présentiel (20 blocs ou créneaux)
réparties en:
  • Leçon : 27.5
  • Contrôle de connaissance : 1.5

20 heures de travail personnel estimé pour l’étudiant.

Diplôme(s) concerné(s)

Format des notes

Numérique sur 20

Littérale/grade européen

Pour les étudiants du diplôme Diplôme d'ingénieur

Vos modalités d'acquisition :

Contrôle de connaissance à la fin de l'unité d'enseignement.

Unité d’enseignement validée lorsque la note finale de l’UE est supérieure ou égale à 10. Pour chaque unité d’enseignement validée, des crédits ECTS associés sont acquis, et le sont de manière définitive.

L'UE est acquise si Note finale >= 10
  • Crédits ECTS acquis : 2 ECTS
  • Crédit de BCI acquis : 2

La note obtenue rentre dans le calcul de votre GPA.

L'UE est évaluée par les étudiants.

Programme détaillé

Généralités : structures de données (piles, files, arbres...), algorithmes ; algorithmes de tri ; hachage ; algorithme de Huffman ; introduction à la théorie des graphes ; arbre couvrant de poids minimum ; plus courts et plus longs chemins ; parcours de graphes ; flots et applications des flots ; planarité et coloration ; introduction à la théorie de la complexité ; méthodes par séparation et évaluation ; méthodes approchées.

Documents distribués & bibliographie
Le livre (prêté) Méthodes d'optimisation combinatoire d'I.Charon, A. Germa et O. Hudry, Masson, 1996.
Le polycopié Structures de données et algorithmes d'I. Charon et O. Hudry, 2004.
Ces documents seront éventuellement complétés par d'autres supports distribués pendant les cours.

Mots clés

Algorithmique et optimisation combinatoire. structures de données et algorithmes de base. Complexité, complexité d'un problème.
Veuillez patienter