Descriptif
- Leçon : 28
Diplôme(s) concerné(s)
UE de rattachement
- TC-C : Informatique
Format des notes
Numérique sur 20Pour 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 de 10)- 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.