Les chapitres du cours, planches de td et de tp

Les corrections (éventuelles) des planches de travaux dirigés et des sujets de travaux pratiques ne seront disponibles qu'après les séances.

Liens vers les chapitres de cours

Liens vers les planches de td et les corrections

• 01 : Généralités (correction)
• 02 : Machine ram, langage algorithmique (correction)
• 03 : Complexité, notations asymptotiques (correction)
• 04 : Square & Multiply, Hörner (correction)
• 05 : Calcul multiprécision (correction)
• 06 : Tris empiriques (correction)
• 07 : Tri par tas (correction)
• 08 : Tri fusion et tri rapide (correction)
• 09 : Tri par dénombrement, par répartition et tri lexicographique (correction)
• 10 : Listes, files, piles, évaluation à l'aide d'une pile (correction)

Liens vers les séances de tp

• tp 01 : Machine ram
• tp 02 : Syracuse et Gnuplot
• tp 03 : Estimation pratique de la complexité
• tp 04 : Square & Multiply et Hörner
• tp 05 : Calcul multiprécision
• tp 06 : Tris empiriques
• tp 07 : Tri par tas
• tp 08 : Tri fusion et Tri rapide
• tp 09 : Evaluation avec une pile

  Prérequis

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

  1. Informatique générale : une connaissance des différents concepts de l'informatique, architecture, assembleur, circuits, système, réseaux, bases de données ;
  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 le Python ;
  4. Mathématiques : les éléments d'analyse étudiés en première année universitaire et un cours de mathématiques pour l'informatique.

  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

  Modalités

  Le contrôle des connaissances est constitué de :

  1. Trois contrôles continus de 30' environ (qcm) toutes les 4 à 5 semaines ;
  2. Une épreuve écrite de 2h15  en fin de semestre ;
  3. Une épreuve pratique de 2h15 en fin de semestre.

  Les épreuves écrites et les épreuves de travaux pratiques de l'année scolaire 2019-2020 ont été annulées et remplacées par des épreuves en ligne à cause du confinement lors de l'épidémie de covid19.

  Annales des épreuves écrites

  1. Session 1 - Session 2 (2018-2019)
  2. Session 1 - Session 2 (2020-2021)
  3. Session 1 - Session 2 (2021-2022)
  4. Session 1 - Session 2 (2022-2023)
  5. Session 1 - (2023-2024)

  Annales des épreuves pratiques

  1. Session unique (2018-2019)
  2. Session unique (2020-2021)
  3. Session unique (2021-2022)
  4. Session unique (2022-2023)
  5. Session unique (2023-2024)