| ||||
Sigle : INF4143 Gr. 01 Titre : Algorithmique I Session : Hiver 2018 Horaire et local Professeur : Pelc, Andrzej | ||||
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
|
09 jan. 2018 | ||
2 |
Analyse de l'efficacité des algorithmes
Laboratoire #1 : le 23 janvier 2014 - Analyse de l'efficacité des algorithmes |
16 jan. 2018 | ||
3 |
Analyse de l'efficacité des algorithmes (suite)
Laboratoire #2 : le 30 janvier 2014 - Analyse de l'efficacité des algorithmes (suite) |
23 jan. 2018 | ||
4 |
Les algorithmes voraces
Laboratoire #3 : le 6 février 2014 - Les algorithmes voraces |
30 jan. 2018 | ||
5 |
Les algorithmes voraces (suite)
Laboratoire #4 : le 13 février 2014 - Les algorithmes voraces (suite) |
06 fév. 2018 | ||
6 |
Diviser pour régner
Laboratoire #5 : le 20 février 2014 - Diviser pour régner |
13 fév. 2018 | ||
7 |
Diviser pour régner (suite)
Laboratoire #6 : le 27 février 2014 - Diviser pour régner (suite) |
20 fév. 2018 | ||
8 | Semaine d'étude | 27 fév. 2018 | ||
9 | Examen de mi-session | 06 mars 2018 | ||
10 |
La programmation dynamique
Exploration des graphes
Laboratoire #7 : le 20 mars 2014 - La programmation dynamique et exploration des graphes |
13 mars 2018 | ||
11 |
Algorithmes à retour arrière (« backtracking »)
« Branch and bound »
Laboratoire #8 : le 27 mars 2014 - Algorithmes à retour arrière (« backtracking »)et « Branch and bound » |
20 mars 2018 | ||
12 |
La théorie des bornes inférieures
Laboratoire #9 : le 3 avril 2014 - La théorie des bornes inférieures |
27 mars 2018 | ||
13 |
Introduction à la NP-complétude
Laboratoire #10 : le 10 avril 2014 - Introduction à la NP-complétude |
03 avr. 2018 | ||
14 |
Avenues de recherche en algorithmique
Laboratoire #11 : le 17 avril 2014 - Révision |
10 avr. 2018 | ||
15 | Examen final | 17 avr. 2018 | ||
6. Évaluation du cours : | ||||
| ||||
7. Politiques départementales et institutionnelles : | ||||
| ||||
8. Principales références : | ||||
| ||||
9. Page Web du cours : | ||||
https://moodle.uqo.ca |