Teaching
INFO601cmi

INFO601cmi

INFO601_cmi - Algorithmique III

Cours du semestre 6 de Licence Informatique, CMI3 Informatique. [Jacques-Olivier Lachaud, November 2025]

Ces ressources sont des outils de travail et de révision. Elles ne remplacent pas les cours et/ou les td, qui peuvent contenir d’autres informations.

Objectifs

Ce module propose quelques éléments nouveaux d’algorithmique, qui font suite à l’étude des structures de données linéaires et arborescentes, tout en restant assez indépendant des algorithmes sur les graphes. Il donne des techniques pour déterminer les temps d’exécution en pire cas des algorithmes, même dans le cas récursif. Il présente aussi l’analys amortie, qui permet d’affiner l’analyse de complexité en pire cas. Il présente aussi les structures de données pour représenter les ensembles disjoints (et donc les relations d’équivalence). Enfin quelques algorithmes classiques de géométrie algorithmique sont présentés.

Pour les travaux pratiques, il présuppose une certaine connaissance du langage C (vous pouvez vous référer aux notes de cours de INFO505 - Programmation C, sur le même site), notamment sa syntaxe, ses mécanismes d’allocation mémoire (pile, tas), son organisation (fichiers sources, fichiers en-tête), son cycle de développement.

Cours, Leçons et exercices

Anciennes fiches de TD

TPs et autres travaux pratiques

  • Aller à la Pages des TPs.
  • Le langage choisi est le langage C.
  • Les TPs sont évalués et à rendre via TPLab

Annales

Références

  • ‘‘Introduction à l’Algorithmique’’, de Cormen, Leiserson, Rivest et Stein, Ed. Dunod;
  • ‘‘The C programming language’’, de Kernighan et Ritchie;
  • ‘‘Le langage C’’, version française du précédent;
  • Le wikilivre [http://fr.wikibooks.org/wiki/Programmation_C ‘‘Programmation C’’]: un livre de cours sur le mode wikipedia.

Historique