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 rapide à 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 !
 

Méthode d'évaluation

L'évaluation comporte deux parties : une évaluation continue des travaux pratiques et un examen oral.
  • É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 supérieure ou égale à 35% (7/20).
  • 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 supérieure à égale à 7/20.
Ces deux évaluations sont considérées comme des activités d'apprentissage distinctes d'une même unité d'enseignement. Une note strictement inférieure à 7/20 à l'une de ces deux activités d'apprentissage entrainera automatiquement une note d'échec pour l'unité d'enseignement. Une note supérieure ou égale à 10/20 peut être reportée pour la session d'août de la même année uniquement. Il n'y aura pas d'évaluation pour cette unité d'enseignement lors de la session de juin. En cas d'échec à l'évaluation continue en janvier, l'étudiant pourra remettre une nouvelle version de ses TP avant le début de la session d'évaluation d'août suivant les modalités définies par les assistants.
 
La présence aux travaux pratiques est obligatoire, une présence insuffisante pourra résulter 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.
 
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'instruction

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