v2.3.4 (2913)

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.

nombre d'heure en présentiel

30

nombre de blocs

20

Volume horaire par type d'activité pédagogique : types d'activité

  • Leçon : 28

Diplôme(s) concerné(s)

Format des notes

Numérique sur 20

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

Le rattrapage est autorisé (Note de rattrapage conservée écrêtée à une note seuil)
  • le rattrapage est obligatoire si :
    Note initiale < 6
  • le rattrapage peut être demandé par l'étudiant si :
    6 ≤ note initiale < 10

Le coefficient de l'UE est : 20

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