Algorithmique IV (UE41)

Avertissement

Ce cours a été rédigé et développé pour un navigateur supportant les principales normes en vigueur. En revanche, il n'est pas responsive design comme diraient les ingénieur·e·s pédagogiques. Les smartphones ne sont pas conçus pour lire un cours d'algorithmique. Le lecteur est invité à télécharger un navigateur libre comme chromium ou firefox, avec lesquels ces pages ont été testées et va­li­dées.

Les termes introduits dans chaque nouveau chapitre sont distingués des autres par une police italique et une autre couleur. Ils sont récapitulés en tête de chapitre sous le sommaire et dirigent le lecteur à la position où ils/elles ont été int­ro­duit·e·s (voir ici même). Un terme ou un groupe de termes distingué de cette manière permet, en le survolant, d'afficher l'information associée et/ou d'ouvrir un hyperlien vers le document concerné.

Les chapitres contiennent des applications interactives censées aider le lecteur à comprendre un résultat en effectuant ses propres expérimentations. Pour cela, des permettent de modifier certains paramètres et sont ma­té­ria­li­sés par un cadre en trai­til­lés jaunes.

Les scripts javascript présents dans ces pages ne servent qu'à la mise en page des mathématiques avec le processeur MathJax et à l'exécution des dif­fé­rents pro­gram­mes qui illustrent le cours. Pour faciliter la lecture, les preuves des théorèmes et les solutions des exercices sont repliés et se déplient en cliquant sur les boutons preuves et les solutions. On peut également déplier toutes les preuves ou toutes les solutions avec deux boutons dédiés en tête de chapitre.

Deux chapitres du cours sont inactivés, ils ont été sacrifiés sur l'autel de la soutenabilité de nos formations.

La soutenabilité désigne la capacité d'un système économique à se maintenir dans le temps sans compromettre les ressources ou les équilibres nécessaires à son fonctionnement.

Ce néologisme, dont la traduction française est plus un rond pour l'université publique !, est l'un de ces maquillages tartinés à la truelle par nos neo-managers pour faire passer un vulgaire beaujolais nouveau pour un Romanée Conti. Un étudiant en fac des sciences est donc passé en moins de 30 ans de \(800\) heures d'enseignements disciplinaires annuels à environ \(450\) heures. Dans l'éventualité où cette piquette ne suffisait pas à nous pousser à plus de sobriété, elle est systématiquement accompagnée de son toast au beurre rance, l'efficience :

L'efficience désigne la capacité à atteindre un objectif en utilisant de manière optimale les ressources disponibles, avec un minimum de gaspillage.

En termes clairs, c'est démerdez-vous avec les moyens du bord*(*) Les étudiants en prépas scientifiques, eux, n'ont pas eu droit à la visite de nos Dupont & Dupont et ont toujours une formation annuelle de plus de \(1\,100\) heures.. Moins de profs, mais plus d'ingénieurs pédagogiques pour nous expliquer comment moderniser nos enseignements afin de cons­trui­re la France des winners de demain. Le budget com est, en revanche, à la mesure de cette nouvelle ambition pour la jeunesse.

Bienvenue dans l'Université d'aujourd'hui.

Organisation des enseignements

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

Chapitres du cours

  1. Introduction
  2. Modèle abstrait : la machine ram
  3. Pseudo langage algorithmique
  4. Preuve et complexité
  5. Notations asymptotiques
  6. Exponentiation rapide
  7. Évaluation d'une fonction polynomiale
  8. Calcul multiprécision
  9. Calcul des fonctions trigonométriques
  10. Recherche de motifs
  1. Analyse des tris empiriques
  2. Complexité des tris comparatifs
  3. Tri par tas
  4. Tri fusion
  5. Tri rapide
  6. Modèle et structure de liste
  7. Tri dénombrement et répartition
  8. Ordre et tri lexicographique
  9. Évaluation d'une expression postfixe
  10. Modèle et structure d'ensemble

Planches de td et corrections

Planches de tp et corrections

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, cinq 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 générales : les éléments d'analyse étudiés en première année universitaire*.(*) Polycopié aimablement four­ni par mon estimée col­lè­gue Gloria Faccanoni.
  5. Mathématiques pour l'informatique : les mathématiques pour l'informatique étudiées en première année universitaire.

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 tout juste effleuré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. Un contrôle intermédiaire d'une heure environ (qcm) après la moitié du semestre ;
  2. Une première session écrite de 2h15 en fin de semestre ;
  3. Une seconde session écrite de 2h15 pour ceux qui n'auraient pas validé l'ue ;
  4. 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)