Vous êtes ici

  1. Accueil
  2. Algorithmique et complexité

Algorithmique et complexité

Algorithmique et complexité

En pratique :

Volume horaire de cours : 20
Volume horaire global de TD : 14
Volume horaire global de TP : 14
Langue principale : français

Description du contenu de l'enseignement

  • Découvrir et adopter la pensée algorithmique : problèmes, fonctions, algorithmes, programmes, calculabilité, complexité, réduction.
  • Découvrir et comprendre les limites formelles qui encadrent la pensée algorithmique: non-décidabilité, classes de complexité P et NP.
  • Découvrir et comprendre des algorithmes variés, et les principes généraux qui les sous-tendent : diviser pour régner, mémoïser, changer de représentation, gloutonnerie, etc.
  • Découvrir différentes façons de s'approcher des limites ainsi définies : force brute, relâchement de la consigne, quasi-algorithmes et pseudo-algorithmes.
  • Découvrir des mesures de complexité moins classiques : ex. complexité amortie et taille de circuit.

Compétences à acquérir

  • Comprendre la cartographie des problèmes algorithmiques : insolubles, difficilement solubles, aisément solubles.
  • Comprendre et savoir appliquer les outils de mesure de la complexité: ordres de grandeur.
  • Savoir évaluer la complexité d'algorithmes courants.
  • Avoir assimilé des stratégies de résolution de problèmes algorithmiques.
  • Savoir mettre en œuvre et évaluer la mise en œuvre d'algorithmes compliqués.

Bibliographie, lectures recommandées

  • « Petite introduction à l'algorithmique - à la découverte des mathématiques du pas à pas », Pierre Damphousse, (Ellipses, 2005) : pour ce que le titre indique.
  • « The new Turing Omnibus - 66 excursions in computer science », A.K. Dewdney (Owl Books, 2001) : pour une belle brochette de sujets informatiques, dont beaucoup d'algorithmes.
  • « Histoire d'algorithmes, du caillou à la puce », Jean-Luc Chabert et al. (Belin, 1994) : pour une belle brochette d'algorithmes d'avant l'informatique (algorithmes mathématiques) et pour une présentation de l'émergence du concept moderne d'algorithme.
  • « Computers LTD, what they really can’t do », David Harel (OUP, 2003) : pour une introduction très vivante et très compacte aux frontières de l'algorithmique, développe donc plus la calculabilité que l'algorithmique.
  • « Algorithmics, The Spirit of Computing », David Harel (Addison-Wesley, 1987) : pour une approche très progressive des différentes problématiques de l'algorithmique, calculabilité, complexité, et correction, ne constitue pas un catalogue d'algorithmes.
  • « Calculateurs, calculs, calculabilité », Olivier Ridoux et Gilles Lesventes (Dunod, 2008) : pour une autre introduction aux frontières de l'algorithmique, avec un accent sur comment ces choses-là sont démontrées.
  • « Computer algorithms - Introduction to Design and Analysis », Sara Baase (Addison-Wesley, 2nde édition, 1991) : pour l'analyse détaillée d'une belle collection d'algorithmes.
  • « Algorithms Unlocked », Thomas Cormen (MIT Press, 2013, ftp://djvu.dlinkddns.com/Copy/Computing/Algorithms_Unlocked.pdf) : pour le même usage que la référence précédente, avec juste une sélection d'algorithmes différente.
  • « Introduction to the Design & Analysis of Algorithms », Anany Levitin (Addison Wesley, 2003) : comme les deux précédents en plus développé. Avec en prime une tentative de classification des algorithmes qui est intéressante (il n'y a pas de catégorie « Autres » hypertrophiée).
  • « Intelligence artificielle et informatique théorique », Jean-Marc Alliot, Thomas Schiex, Pascal Brisset, Frédéric Garcia (Cépaduès, 2002) : pour une large introduction aux modèles de l'informatique théorique, avec beaucoup d'algorithmes et pseudo-algorithmes qui sortent des sentiers battus. http://www-i1.informatik.rwth-aachen.de/~algorithmus/ : pour ceux à qui il reste un peu d'allemand. Une belle collection d'algorithmes, dont même la traduction automatique de Google rend assez bien compte. Cette collection est devenue un livre : « Algorithms Unplugged », Berthold Vöcking et al. (Springer, 2011). Le site est remarquable, mais le livre est à la fois plus accessible, plus précis, et plus riche : à lire.
  • « Algorithmic Puzzles », Anany et Maria Levitin (Oxford, 2011) : 150 puzzles pour stimuler la pensée algorithmique. Certains sont très connus, mais beaucoup ne le sont pas. Certaines entreprises les utilisent lors des entretiens d'embauche.