info204 - Algorithmique

Credits

5

Prerequisites

math101, info102, info201

Parcours

• mandatory for the computer science mention of the "licence"

Objectives

Savoir que certains problèmes algorithmiques peuvent se résoudre par des méthodes d'optimisation (notions de solution optimale et de sensibilité de la solution à une modification des paramètres). S'initier à la modélisation mathématique de problèmes par la programmation linéaire et la théorie des graphes. Apprendre à utiliser des logiciels de résolution utilisables en entreprise (AMPL). Connaître quelques algorithmes classiques du domaine (preuves de correction, sructures de données les mieux adaptées et complexité en temps dans le pire des cas).

Organization

week

1

2

3

4

5

6

7

8

9

10

11

12

13

C (1h30)

×

×

×

×

×

×

×

×

×

×

×

×

TD (1h30)

×

×

×

×

×

×

×

×

×

×

×

×

TP (2h00)

×

×

×

×

×

×

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

• Modélisation de problèmes en AMPL (version enseignement gratuite).
• Le simplexe : version graphique, l'algorithme du tableau simplicial, la méthode des deux phases, la dualité (sensibilité de la solution optimale).
• Introduction à la théorie des graphes : vocabulaire, historique, problèmes célèbres, parcours en largeur (plus court chemin, files), parcours en profondeur (tri topologique, piles), chemins de valeur minimale (Bellman, Dijkstra, tas binaires), flot maximal (Edmonds-Karp), arbre couvrant de valeur minimale (Kruskal, ensembles disjoints), ordonnancement de tâches (méthode MPM).

Instructor(s)

François Boulier

fichier source pour édition/modification