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.

Prérequis

Les prérecquis sont ceux des enseignements de la première année de la licence d'informatique de l'ufr-Sciences pour les étudiants qui ont suivi leur cursus à l'université de Toulon. Pour les autres, quatre enseignements sont indispensables :

  1. Informatique générale : Une connaissance des différents concepts de l'informatique ;
  2. Algorithmique : Une introduction à la conception des algorithmes simples et principalement itératifs ;
  3. Programmation : La pratique d'un langage de programmation avec des applications dans un langage évolué, comme Python ;
  4. Mathématiques : Les éléments d'analyse étudiés en première année universitaire et un cours de mathématiques discrètes.

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. ✍ Notations asymptotiques
  6. ⚙ Exponentiation rapide (Square & Multiply)
  7. ⚙ Évaluation d'une fonction polynomiale (Horner)
  8. ⚙ Addition et multiplication multiprécision
  9. ⚙ Calcul des fonctions trigonométriques (cordic)
  10. ⚙ Recherche d'un motif (Knuth-Morris-Pratt)
  11. ⚙ Analyse des tris empiriques
  12. ⚙ Tri fusion
  13. ⚙ Tri rapide
  14. ⚙ Tri par tas
  15. ✍ Complexité des tris comparatifs
  16. ⚙ Tri par dénombrement et par répartition
  17. ✍ Modèle et structures de données “liste”
  18. ⚙ Évaluation d'une expression avec une pile
  19. ✍ Modèle et structures de données “ensemble”
  20. ⚙ Ordre lexicographique
  21. ⚙ Tri lexicographique

Annales des contrôles terminaux