Le sous-module IF5.05(B): conception et analyse des algorithmes

ATTENTION: les informations ci-dessous sont modifiées en continu.

---

Ce cours est une introduction à la conception d'algorithmes et à l'analyse de leur efficacité. Les sujets suivants seront abordés: complexité et optimalité, ordre de complexité, estimation des constantes de complexité et lien avec le temps de calcul réel, algorithmes sur les arbres, algorithmes de tri, algorithmes sur les suite, les matrices etc.

---

Format 2002-2003:

11 séances de cours+TD le jeudi 10h15-12h25 (sauf exceptions notées ci-dessous).
Calendrier prévu:

CM1 5/9	Algorithmes, complexité, notations O, Omega, Theta.	TD1
CM2 12/9	Complexité moyenne, optimalité.	TD2
CM3 19/9	Calcul de suites.	TD3
CM4 26/9	Multiplication de polynômes et de matrices.	TD4
CM5 3/10	Polynomes et matrices bis.	TD5
CM6 10/10	Calcul de la médiane (sélection)	TD6
CM7 17/10	Calcul de la médiane (sélection)	TD7
CM8 24/10	Borne inférieure. Tri par classement. Partiel à faire à la maison et rendre au CM9	TD8
CM9 14/11	Arbres binaires de tri.	TD9
CM10 21/11	Arbres optimaux.	TD10
CM11 MARDI 26/11 9h30-11h40	Correction du partiel. B-arbres. Evaluation du cours	TD11
16/12, Amphi. 1 14-17h.	Examen sur ce sous-module 15h30-17h (juste après l'examen sur l'autre sous-module).

Matériel pédagogique

(*.ps: postscript; *.tex: latex; *.gz: compressé avec gzip; [...] dernière révision du fichier)

• Chapitres du cours
• Chapitre sur les notions de complexité [10/2000]: intro.pdf ou
• Chapitre sur le calcul de suites [10/2000]: suites.pdf.
• Chapitre sur le produit de polynômes et de matrices [10/2000]: matrices.pdf.
• Chapitre sur la sélection et le calcul de la médiane [2/10/2000]: selection.pdf.
• Chapitre sur le tri [10/2000]: tri.pdf.
• Chapitre sur les arbres [10/2000]: arbres.pdf.
• Chapitre sur les B-arbres: Voir p.238-... du livre de Froidevaux et al.
• Chapitre sur les graphes [11/2000]: graphes.pdf.
• Feuilles de TD
• Feuille 1 Notations asymptotiques, estimations de complexité
• Feuille 2 Algorithmes pour le calcul de suites
• Feuille 3 Multiplication de polynômes et de matrices.
• Feuille 4 Sélection et calcul de la médiane
• Feuille 5 Algorithmes de tri
• Feuille 6 Arbres binaires
• Solutions sol6.txt pour la feuille de TD 6.
• Sujets d'examens pour ce cours:
• Sujet du final de decembre 2002. final_dec2002.html.
• Sujet du partiel de novembre 2002. partiel_nov2002.html.
• Corrigé du partiel de novembre 2002. corrige_nov2002.txt.
• Sujet du final de décembre 2001. final_dec2001.html.
• Corrigé du final de décembre 2001. corrige_dec2001.txt.
• Sujet du partiel de novembre 2001. partiel_nov2001.html.
• Sujet de l'examen de juin 2001. examen_jun2001.html.
• Corrigé de l'examen de juin 2001. corrige_jun2001.txt.
• Sujet du final de décembre 2000. final_dec2000.html.
• Sujet du partiel d'octobre 2000. partiel_oct2000.html.
• Sujet du final de juin 2000 eli5-alg-controle-jun2000.tex
• Sujet du partiel de mars 2000 eli5-alg-controle-mar2000.tex
• Sujet de l'examen de juin 1999 eli5-alg-controle-jun99.tex
• Sujet du partiel de mars 1999 eli5-alg-controle-mar99.tex

Références

• A.Aho, J.Hopcroft, and J.Ullman. The Design and Analysis of Computer Algorithms Addison-Wesley, 1974.
• G.Brassard et P.Bratley. Algorithmique. Conception et Analyse Masson-Presses de l'Université de Montréal, 1987.
• C. Froidevaux, M.-C. Gaudel et M. Soria, Types de Données et Algorithmes, Ediscience International, 1993.
• D.E. Knuth, The Art of Computer Programming. Vol.1: fundamental algorithms, Addison-Wesley, 1973.
• D.E. Knuth, The Art of Computer Programming. Vol.3: sorting and searching, Addison-Wesley, 1973.
• L.Kronsjö, Computational Complexity of Sequential and Parallel Algorithms, 1985.
• M.Loomis. Data Management and File Structures Prentice-Hall, 1989.
• S. S. Skiena, The Algorithm Design Manual, Springer-Verlag, 1998.

Contrôle des connaissances pour IF5.05(B)

Ce sous-module fait partie du module IF5.05 qui contient aussi Génie Logiciel et Systèmes d'Information et Anglais. Le contrôle des connaissances prévu pour IF5.05(B) est un examen partiel sur l'analyse des algorithmes et un examen final commun avec la partie IF5.05(A) GLSI.

---

Gaétan HAINS