Algorithmique ii (I31)

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.

Les enseignements sont répartis administrativement en cours/td/tp. Dès la rentrée universitaire 2017-2018, à 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. Quatre épreuves de contrôle continu d'une durée de 45 minutes (actuellement deux) toutes les trois séances sur la platerforme en ligne. Il s'agit de 20 questions tirées au hasard parmi les 60 questions déjà étudiées pour la préparation des trois séances passées ;
  2. Une épreuve écrite de 2 heures ;
  3. Une épreuve pratique de 3 heures.

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. ⚙ Recherche d'un motif (Knuth-Morris-Pratt)
  11. ⚙ Analyse des tris empiriques (sélection, propagation, insertion)
  12. ⚙ Tri par tas
  13. ✍ Complexité des tris comparatifs
  14. ⚙ Tri par dénombrement et par répartition
  15. ✍ Modèle et structures de données “liste”
  16. ⚙ Évaluation d'une expression avec une pile
  17. ✍ Modèle et structures de données “ensemble”
  18. ⚙ Ordre lexicographique
  19. ⚙ Tri lexicographique

Annales des contrôles terminaux