| ||||
Sigle : INF4143 Gr. 01 Titre : Algorithmique I Session : Hiver 2007 Horaire et local Professeur : Kupczynski, Marian | ||||
1. Description du cours paraissant à l'annuaire : | ||||
ObjectifsFournir à l'étudiant des outils pour choisir une solution algorithmique efficace à un problème donné et estimer sa performance. Le sensibiliser à l'importance de choisir la solution la plus adéquate.ContenuCritères de choix d'une solution algorithmique de problèmes, complexité d'algorithme versus performance de l'implantation, complexité en pire cas et en moyenne. Principaux types d'algorithmes, leurs qualités et défauts : algorithmes voraces, diviser pour régner, retour arrière, «branch and bound», programmation dynamique; exemples de problèmes résolus par des algorithmes de chaque type et leur analyse. Méthodes d'exploitation des graphes et leurs applications. Bornes inférieures de performance des algorithmes. Problèmes polynomiaux et intraitables, problèmes NP-complets, heuristiques, solutions approximatives. | ||||
2. Objectifs spécifiques du cours : | ||||
| ||||
3. Stratégies pédagogiques : | ||||
| ||||
4. Heures de disponibilité ou modalités pour rendez-vous : | ||||
5. Plan détaillé du cours sur 15 semaines : | ||||
Semaine | Thèmes | Dates | ||
1 |
Préliminaires
|
10 jan. 2007 | ||
2 |
Analyse de l'efficacité des algorithmes
|
17 jan. 2007 | ||
3 |
Analyse de l'efficacité des algorithmes (suite)
|
24 jan. 2007 | ||
4 |
Les algorithmes voraces
|
31 jan. 2007 | ||
5 |
Les algorithmes voraces (suite)
|
07 fév. 2007 | ||
6 |
Diviser pour régner
|
14 fév. 2007 | ||
7 | Examen de mi-session | 21 fév. 2007 | ||
8 | Semaine d'études | 28 fév. 2007 | ||
9 |
Diviser pour régner (suite)
|
07 mars 2007 | ||
10 | Algorithmes de permutations et de tautologie | 14 mars 2007 | ||
11 |
La programmation dynamique
|
21 mars 2007 | ||
12 |
Exploration des graphes
|
28 mars 2007 | ||
13 |
La théorie des bornes inférieures
Algorithmes à retour arrière (« backtracking »)
« Branch and bound »
|
04 avr. 2007 | ||
14 |
Introduction à la NP-complétude |
11 avr. 2007 | ||
15 |
Examen final |
18 avr. 2007 | ||
6. Évaluation du cours : | ||||
| ||||
7. Politiques départementales et institutionnelles : | ||||
| ||||
8. Principales références : | ||||
| ||||
9. Page Web du cours : | ||||