5.00 crédits
30.0 h + 22.5 h
Q1
Enseignants
Blondel Vincent; Delvenne Jean-Charles; Delvenne Jean-Charles (supplée Blondel Vincent);
Langue
d'enseignement
d'enseignement
Préalables
Ce cours suppose une maturité suffisante en mathématique, d'un niveau équivalent à celle d'un étudiant ingénieur arrivé au terme de sa troisième année d'étude. Le cours est une introduction à l'algorithmique et traite principalement des aspects non numériques. On y fait une analyse mathématique de l'existence et de la complexité d'algorithmes pour des problèmes classiques liés aux structures et problèmes discrets. Il est utile que les étudiants aient déjà été confrontés à des questions algorithmiques non-élémentaires ; il n'y a toutefois pas de prérequis particulier en algorithmique.
Thèmes abordés
Ce cours est une introduction à l'algorithmique et traite principalement des aspects non numériques. On y fait une analyse mathématique de l'existence et de la complexité d'algorithmes pour des problèmes classiques liés aux structures et problèmes discrets.
Acquis
d'apprentissage
d'apprentissage
A la fin de cette unité d’enseignement, l’étudiant est capable de : | |
| 1 |
Eu égard au référentiel AA, ce cours contribue au développement, à l'acquisition et à l'évaluation des acquis d'apprentissage suivants :
|
Contenu
a) Analyse de complexité en moyenne et dans le pire des cas: bornes supérieures et inférieures, méthodes de théorie de l'information et lemme de Yao, illustration sur des algorithmes élémentaires (tri, implémentation efficace de structures de données)
b) Coût énergétique du calcul: théorie (borne de Landauer) et pratique.
c) Quelques stratégies d'algorithmes: diviser pour régner, programmation dynamique, méthodes gloutonnes.
d) Algorithmes probabilistes: méthodes Monte Carlo and Las Vegas, générateurs pseudo-aléatoires, dérandomisation.
e) Aspects de la théorie de la complexité : classes de complexité (déterministes, non-déterministes et probabilistes ; uniformes et non-uniformes), existence d'algorithmes.
f) Algorithmes quantiques: qubits, no-cloning theorem, algorithmes de Grover et Shor, perspectives.
b) Coût énergétique du calcul: théorie (borne de Landauer) et pratique.
c) Quelques stratégies d'algorithmes: diviser pour régner, programmation dynamique, méthodes gloutonnes.
d) Algorithmes probabilistes: méthodes Monte Carlo and Las Vegas, générateurs pseudo-aléatoires, dérandomisation.
e) Aspects de la théorie de la complexité : classes de complexité (déterministes, non-déterministes et probabilistes ; uniformes et non-uniformes), existence d'algorithmes.
f) Algorithmes quantiques: qubits, no-cloning theorem, algorithmes de Grover et Shor, perspectives.
Méthodes d'enseignement
Le cours est organisé autour de séances de cours ex cathedra et de devoirs. Pas d'exercices en salle obligatoires.
Modes d'évaluation
des acquis des étudiants
des acquis des étudiants
En session, les étudiants sont évalués individuellement et par écrit (ou par oral selon les circonstances) sur base des objectifs particuliers énoncés plus haut. Cet examen compte pour 75% de la note finale.
En outre les étudiants réalisent des devoirs pendant les semaines de cours. Les notes obtenues pour les devoirs pendant le quadrimestre sont comptabilisées dans la note finale (de janvier et d'août, à l'identique) à hauteur de 25%.
En outre les étudiants réalisent des devoirs pendant les semaines de cours. Les notes obtenues pour les devoirs pendant le quadrimestre sont comptabilisées dans la note finale (de janvier et d'août, à l'identique) à hauteur de 25%.
Ressources
en ligne
en ligne
Page Moodle du cours
Bibliographie
- Algorithmics: Theory and Practice, G. Brassard and P. Bratley, Prentice Hall, 1988.
- Introduction to Algorithms, T.H. Cormen, C.E. Leierson and R.L. Rivest, MIT Press 1986.
- Notes on the Moodle page
Support de cours
- Documents sur le Moodle / Documents on Moodle
Faculté ou entité
en charge
en charge
MAP
