Acquis d'apprentissage

Ce cours constitue une introduction à différents concepts liés à l'algorithmique et avec certaines spécificités liées au calcul scientifique, ainsi qu'une mise en pratique lors de nombreux travaux en pool informatique.

Objectifs

  • Connaitre les bases de la conception d'algorithmes et pouvoir analyser leur complexité
  • Être capable d'implémenter différentes sortes d'algorithmes en langage C et Matlab
  • Connaitre les différentes méthodes d'intégration numérique d'équations différentielles
  • Savoir reconnaitre des problèmes de complexité non-polynomiale
  • Concevoir des stratégies algorithmiques heuristiques ou probabilitistes

Contenu

Le cours débutera par une introduction à la programmation en langage C ainsi que par diverses spécificités avancées concernant ce langage, y compris la représentation en mémoire des types entiers et flottants. Les premiers mini TP seront consacrés à une exploration de ce langage.

La suite du cours théorique contient les éléments suivants :

  • La complexité algorithmique : Caractéristiques d’un bon algorithme, Les classes de complexité, Complexité des algorithmes récursifs, Algorithmes de tri
  • Les stratégies algorithmiques : Les structures de données (piles, files, listes chainées, arbres de recherche), Les différentes stratégies algorithmiques (algorithmes gloutons, diviser pour régner, programmation dynamique, backtracking, branch-and-bound)
  • Les algorithmes d’intégration numérique : Euler, Runge-Kutta, adaptation du pas d'intégration, méhodes multi-pas, méthodes prédicteur-correcteur
  • Les algorithmes non-polynomiaux : Problèmes de décision, Classes P, NP et NP-complet, preuves de NP-complétude
  • Les algorithmes probabilistes : Algorithmes aléatoires, Algorithmes de Monte-Carlo et Las Vegas, Méthodes de Monte-Carlo, Méthodes MCMC, Monte Carlo Tree Search

Plusieurs TP importants, en C et en Matlab, seront basés sur le contenu et les exemples du cours théorique.

Méthodes d'enseignement

Cours magistral donné en partie au tableau, avec quelques exemples informatiques.

Travaux de programmation en pool informatique (C et Matlab).

Attention : en raison d'une évaluation continue, la présence aux TP de programmation en pool informatique est obligatoire ! En cas d'absences répétées et injustifiées, une note non remédiable de 0/20 sera appliquée à l'ensemble de l'unité d'enseignement, en application de l'Article 49 du REE.

 

Méthode d'évaluation

L'évaluation comporte deux parties : une évaluation continue des travaux pratiques et un examen oral portant sur la théorie. Ces deux évaluations sont considérées comme des activités d'apprentissage distinctes d'une même unité d'enseignement. Une note inférieure ou égale à 7/20 à l'une de ces deux activités d'apprentissage entrainera automatiquement une note d'échec pour l'unité d'enseignement (note absorbante).

  • Évaluation continue des travaux pratiques : les séances de travaux pratiques en pool informatique seront constituées de plusieurs TP évalués et à rendre selon le calendrier et les instructions définis par les assistants. La moyenne de ces évaluations compte pour 50% de la note finale, à condition que cette moyenne soit strictement supérieure à 35% (7/20). La présence aux travaux pratiques est obligatoire, une présence insuffisante résultera en une note d'échec pour l'unité d'enseignement. Les travaux de l'évaluation continue sont individuels, tout travail collectif ou plagiat pourra être sanctionné par une note de 0/20 à l'unité d'enseignement pour non respect des consignes. Attention, cette évaluation continue est non remédiable. La note de la session de janvier, comptabilisant les différents TP, est donc définitive. En cas de réussite, cette note est automatiquement reportée à l'année suivante.
  • Examen oral : les questions portent sur la théorie, à la fois sur des questions de présentation de la matière ou de démonstrations, ainsi que sur la capacité de l'étudiant à concevoir une stratégie algorithmique à partir d'un problème donné. Cette évaluation compte pour 50% de la note finale, à condition d'être strictement supérieure à 7/20. En cas d'échec à l'examen oral en janvier, une seconde session est organisée en août. Il n'y a pas d'évaluation pour cette activité d'apprentissage lors de la session de juin. En cas de réussite, cette note n'est par contre pas reportée à l'année suivante.


Utilisation de ChatGPT/IA : 

  • Suivant le calendrier fixé par les assistants, certaines séances seront effectuées en pool informatique avec interdiction formelle d'utiliser ChatGPT ou toute autre IA, avec remise de codes (éventuellement partiels) dès la fin de la séance. La notation de ces codes fera partie intégrante de l'évaluation continue, soit en étant compabilisée directement dans la moyenne soit en modulant la notation finale du TP en cours. L'objectif sera ici de vérifier que l'étudiant possède bien les compétences de base en programmation.
  • Pour les autres séances et les remises de travaux situées en dehors d'une fin de séance, l'utilisation de ChatGPT ou assimilé est tolérée à condition que celle-ci se résume à des aides ponctuelles et non à la réalisation du TP en lui-même. En cas de suspicion d'utilisation d'intelligence artificielle ayant eu pour but ou pour effet de soustraire l’étudiant aux objectifs fixés par l’évaluation, à savoir la conception et programmation d'algorithmes, les enseignants se réservent la possibilité d'interroger l'étudiant à la suite de la remise de ses travaux, en présentiel ou par teams, afin de déterminer ce qui a été effectivement réalisé et si la maitrise des compétences est suffisante. Dans le cas contraire, l'attribution d'une note de 0/20 au TP ou à l'unité d'enseignement pourra être envisagée en application de l'article 79 du REE.

 

Sources, références et supports éventuels

Un syllabus disponible sur webcampus.

Référence sur le langage C : Claude Delannoy, Langage C, Eyrolles, ISBN 2-212-11123-1

 

Langue d'enseignement

Français
Formation Programme d’études Bloc Crédits Obligatoire
Bachelier en sciences mathématiques Standard 0 5
Bachelier en sciences mathématiques Standard 3 5