Algorithmique ii (I41)

Objectifs

Cet enseignement en ligne couvre le programme d'algorithmique de la deuxième année d'une licence, peu importe comment ce programme est réparti annuellement. Il s'agit d'étudier progressivement des algorithmes plus sophistiqués que ceux proposés en première année et d'introduire des modèles et des structures de données plus évolués que les tableaux/listes et les scalaires, comme les graphes et les arbres, quand bien même les tableaux/listes restent majoritaires à ce stade. La récursivité est abordée naïvement comme une simple déclinaison de la ré­cur­ren­ce en ma­thé­ma­ti­ques sans être un objet d'étude à part entière.

L'analyse de la complexité des algorithmes est introduite à l'aide d'un modèle abstrait de machine de type ram pour étudier précisément cette notion. Ce modèle sera repris en troisième année et en master, notamment en théorie de la complexité, pour ceux qui poursuivront dans cette voie. L'im­plan­ta­tion des algorithmes pour les travaux pratiques se fait en langage Python et/ou en C selon la nature de l'algorithme.

Les enseignements sont répartis administrativement en cours/td/tp. Dès la rentrée universitaire 2018-2019, à l'exception de la première séance de présentation, les 12 cours magistraux heb­do­ma­dai­res seront remplacés par cet enseignement en ligne. Le principe est simple, chaque séance devra être préparée en lisant le cours au préalable et en faisant, d'une part les exercices suggérés dans le cours, et d'autre part ceux d'un questionnaire sur une plateforme en ligne (moodle ou autre, le choix technique est en cours de discussion). L'étudiant pourra reprendre les exercices autant de fois que nécessaire jusqu'à la séance de travaux dirigés correspondante.

Les algorithmes étudiés servent d'ossature au cours plutôt que d'exercices applicatifs. Les travaux pratiques permettent d'appliquer concrètement ce qui a été abordé en cours/td et de mettre en évidence les difficultés propres à la programmation.

Contrôle des connaissances

Le contrôle des connaissances sera constitué de :

  1. Trois qcm de contrôle continu d'une durée de 45 minutes toutes les quatre séances ;
  2. Une épreuve écrite de 2 heures ;
  3. Une épreuve pratique de 2 heures et 30 minutes.

Les chapitres du cours

  1. ✍ Introduction
  2. ✍ La machine ram
  3. ✍ Pseudo langage algorithmique
  4. ✍ Preuve et complexité
  5. ✍ Mémento mathématique
  6. ✍ Notations asymptotiques
  7. ⚙ Exponentiation rapide (Square & Multiply)
  8. ⚙ Évaluation d'une fonction polynomiale (Horner)
  9. ⚙ Addition et multiplication multiprécision
  10. ⚙ Calcul des fonctions trigonométriques (cordic)
  11. ⚙ Recherche d'un motif (Knuth-Morris-Pratt)
  12. ⚙ Analyse des tris empiriques
  13. ⚙ Tri par tas
  14. ✍ Complexité des tris comparatifs
  15. ⚙ Tri par dénombrement et par répartition
  16. ✍ Modèle et structures de données “liste”
  17. ⚙ Évaluation d'une expression avec une pile
  18. ✍ Modèle et structures de données “ensemble”
  19. ⚙ Ordre lexicographique
  20. ⚙ Tri lexicographique

Annales des contrôles terminaux