info401 - Algorithmique avancée et complexité de problèmes

Nombre de crédits

5

Pré-requis

(Licence mention informatique), info204

Parcours

• obligatoire pour la mention informatique du master science

Objectifs

L'accent du cours est plus mis sur les méthodes que sur la connaissance d'algorithmes classiques même si ceux-ci serviront d'exemples pour illustrer le cours.

• Connaître quelques schémas "classiques" d'algorithmes et savoir les utiliser.
• Comprendre la notion de complexité de problèmes.
• Connaître quelques méthodes pour aborder des problèmes « durs ».

Organisation

semaine

1

2

3

4

5

6

7

8

9

10

11

12

13

C (1h)

×

×

×

×

×

×

×

×

×

×

×

×

TD (1h30)

×

×

×

×

×

×

×

×

×

×

×

×

TP (1h30)

×

×

×

×

×

×

×

×

×

×

×

×

Volume de travail personnel étudiant estimé

environ 50h

Contrôle et validation des connaissances

• pour les UE sans TP : sup ( Ex, (2Ex + CC)/3)
• pour les UE avec TP obligatoires : (2TP + 3 sup(Ex, (2Ex + CC)/3))/5

Description du contenu

• Schémas d'algorithmes : diviser pour régner, programmation dynamique, algorithmes gloutons
• Complexité de problèmes ; notion de réduction. La classe NP.
• Algorithmes d'exploration (branch-and-bound, min-max, A*)
• Algorithmes d'approximation : heuristiques et métaheuristiques
• Algorithmes probabilistes

Responsable(s)

Sophie Tison

fichier source pour édition/modification