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

Credits

5

Prerequisites

(Licence mention informatique), info204

Parcours

• mandatory for the computer science mention of the master of science

Objectives

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 ».

Organization

week

1

2

3

4

5

6

7

8

9

10

11

12

13

C (1h)

×

×

×

×

×

×

×

×

×

×

×

×

TD (1h30)

×

×

×

×

×

×

×

×

×

×

×

×

TP (1h30)

×

×

×

×

×

×

×

×

×

×

×

×

Student personal work

about 50h

Evaluation

• for UE without Labs : sup ( Ex, (2Ex + CC)/3)
• for UE with Labs : (2TP + 3 sup(Ex, (2Ex + CC)/3))/5

Contents

• 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

Instructor(s)

Sophie Tison

fichier source pour édition/modification