Cours de Conception
et analyse des algorithmes
(8INF806)
Hiver 2005
Notes définitives : consulter
Nouvelles
du jour
Le
cours du jeudi 21 avril est reporté au mardi 26 avril à 17h30.
- Le cours débute ce mardi 11 janvier 2005.
- Nouveaux
horaire et local du cours pour le reste de la session:
Jeudi: 16h – 18h45; local: P1- 5010.
- Une
séance de TD de ce Mardi 1 février 2005 aura lieu de 17h30 à 18h45 au local: P1-7060.
- Une séance de TD de
ce Mardi 8 Février aura lieu de 17h30 à 18h45 au local P1-5010.
- La séance de cours
aura lieu ce Mercredi, comme convenu, de 17h30 à 18h45 au local P1-5010
- Une séance de TD de
ce Mardi 8 Mars aura lieu de 17h30 à 18h45 au local P1-5010.
Remarque : pour faciliter les calculs de l’exercice 7
du devoir 1, veuillez prendre t(2) = 1 au lieu de
t(1) =1.
-
comme convenu, il y a une séance d’exercices le
mardi 22 février 2005, de 17h30 à 18h45 au local P1-5010.
-
l’examen de mi-session aura lieu le jeudi 10
mars 2005.
-
l’examen portera sur les chapitre 1, 2, 3. Le
chapitre sur la programmation dynamique ne fait pas partie du sujet de
l’examen.
Note
Importante :
Une
erreur s’est glissée dans l’énoncé de l’exercice 6 : les 
doivent être mis dans l’ordre décroissants au lieu de croissant
comme je l’ai écrit. Consultez l’énoncé du devoir pour plus de détails. La remise des devoirs est prolongée en conséquence jusqu’au dimanche 27
février 2005.
Liste de
sujet proposés : consulter ;
Objectifs : Outre l’étude des méthodes algorithmiques dont on
n’a pas eu l’opportunité de voir en classe,
l’étudiant(e) aura à s’initier à bien lire et synthétiser les points
importants du sujet choisi, à savoir rechercher
l’information utile à son sujet. L’autre but recherché dans ce travail est
le développement du
niveau de
communication écrite et orale des étudiants.
Modalités d’évaluation : La durée d’une présentation orale, sur le
sujet choisi, est d’environ 30 minutes.
On réservera 10 minutes au plus pour les questions. L’étudiant aura à
remettre un tapuscrit d’une
quinzaine à une vingtaine de pages sur le sujet choisi.
Les présentations se feront, comme convenu, les mardi de 17h30-18h45,
durant les 3 dernières semaines. Je ferais en sorte que le local sera toujours
le P1-5010.
L’évaluation de cette activité se fera comme suit :
|
Présence |
5% |
|
Questions : |
10% |
|
Présentation orale |
40% |
|
Rapport écrit : |
45% |
Syllabus:
consulter
1.
Petit rappel de mathématiques: consulter
2.
Aide mémoire pour survivre aux mathématiques: consulter
3.
Bref rappel sur les probabilités : consulter
|
Notes
de cours |
Travaux
dirigés |
Devoirs |
|
Chapitre 0 : une introduction |
série 1: consulter |
devoir 1: consulter ;
solutionnaire |
|
|
série 2: consulter |
devoir 2: consulter ; solutionnaire
|
|
|
série 3: serieetsolutionnaire |
devoir 3: consulter ;
solutionnaire |
|
Chapitre 1 :
analyse des algorithmes |
série 4:
diviseretregner |
Devoir 4 : |
|
|
|
|
|
|
série 5: programmation |
|
|
|
|
|
|
Chapitre 2 : Résolution des
équations |
série 6 :
branch and bound
|
|
|
Chapitre 3 : Les algorithmes voraces |
série 7 : réduction
solutionnaire |
|
|
|
|
|
|
Chapitre 4 : la méthode diviser et régner |
|
|
|
|
|
|
|
Chapitre 5 : Programmation dynamique |
|
|
|
|
|
|
|
Chapitre 6:
méthode de
branch and bound |
|
|
|
Chapitre 7 : techniques de réduction |
|
|
|
|
|
|
|
Chapitre 8 : NP-complétude |
|
|