info204 - Algorithmique

Nombre de crédits

5

Pré-requis

math101, info102, info201

Parcours

• obligatoire pour la mention informatique de la licence

Objectifs

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

Organisation

semaine

1

2

3

4

5

6

7

8

9

10

11

12

13

C (1h30)

×

×

×

×

×

×

×

×

×

×

×

×

TD (1h30)

×

×

×

×

×

×

×

×

×

×

×

×

TP (2h00)

×

×

×

×

×

×

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

• 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).

Responsable(s)

François Boulier

fichier source pour édition/modification