| ||||
Sigle : INF4143 Gr. 01 Titre : Algorithmique I Session : Hiver 2017 Horaire et local Professeur : Godon, Maxime | ||||
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. Ce cours comporte des séances obligatoires de travaux dirigés (TD) de deux heures par semaine. | ||||
2. Objectifs spécifiques du cours : | ||||
| ||||
3. Stratégies pédagogiques : | ||||
| ||||
4. Heures de disponibilité ou modalités pour rendez-vous : | ||||
Sur rendez-vous. | ||||
5. Plan détaillé du cours sur 15 semaines : | ||||
Semaine | Thèmes | Dates | ||
1 |
Préliminaires
|
10 jan. 2017 | ||
2 |
Analyse de l'efficacité des algorithmes
Laboratoire #1 : Le 19 janvier 2017 - Analyse de l'efficacité des algorithmes |
17 jan. 2017 | ||
3 |
Analyse de l'efficacité des algorithmes (suite)
Laboratoire #2 : Le 26 janvier 2017 - Analyse de l'efficacité des algorithmes (suite)
|
24 jan. 2017 | ||
4 |
Les algorithmes voraces
Laboratoire #3 : Le 2 février 2017 - Les algorithmes voraces |
31 jan. 2017 | ||
5 |
Les algorithmes voraces (suite)
Laboratoire #4 : Le 9 février 2017 - Les algorithmes voraces (suite)
|
07 fév. 2017 | ||
6 |
Diviser pour régner
Laboratoire #5 : Le 16 février 2017 - Diviser pour régner
|
14 fév. 2017 | ||
7 |
Diviser pour régner (suite)
Laboratoire #6 : Le 23 février 2017 - Diviser pour régner (suite) |
21 fév. 2017 | ||
8 | Semaine d'études | 28 fév. 2017 | ||
9 | Examen de mi-session | 07 mars 2017 | ||
10 |
La programmation dynamique
Exploration des graphes
Laboratoire #7 : Le 16 mars 2017 - La programmation dynamique et exploration des graphes
|
14 mars 2017 | ||
11 |
Algorithmes à retour arrière (« backtracking »)
« Branch and bound »
Laboratoire #8 : Le 23 mars 2017 - Algorithmes à retour arrière (« backtracking »)et « Branch and bound » |
21 mars 2017 | ||
12 |
La théorie des bornes inférieures
Laboratoire #9 : Le 30 mars 2017 - La théorie des bornes inférieures
|
28 mars 2017 | ||
13 |
Introduction à la NP-complétude
Laboratoire #10 : Le 6 avril 2017 - Introduction à la NP-complétude |
04 avr. 2017 | ||
14 |
Avenues de recherche en algorithmique
Laboratoire #11 : Le 13 avril 2017 - Révision |
11 avr. 2017 | ||
15 | Examen final | 18 avr. 2017 | ||
6. Évaluation du cours : | ||||
| ||||
7. Politiques départementales et institutionnelles : | ||||
| ||||
8. Principales références : | ||||
| ||||
9. Page Web du cours : | ||||
https://moodle.uqo.ca |