9. Algorithmique

Durée : 9+6 périodes de 45 minutes Discipline obligatoire, 1ère année : Fiches Option complémentaire : Chapitre 9

Ce qu'il faudra retenir du chapitre 9

• Le problème des huit dames
• Algorithmes gloutons
• Algorithmes de tri
• Quelques algorithmes géométriques
  
  
• Algorithmes probabilistes
• Métaheuristiques

Chapitre 9

Algorithmique

Version 2020.12

Annexe 9

Métaheuristiques

Version 2025.3

Compléments

• Exemples d'algorithmes : la multiplication de deux entiers
• Résolution d'un Rubik's cube 2x2
• Le problème des huit dames
• Le problème des 8 reines... et au-delà, Jean-Paul Delahaye, Interstices, 20.11.20
• Algorithmes de tri
• Le problème du sac à dos
• Chan's Algorithm Demo, Chris Gregory, 2016

Pour les curieux

• Qu’est-ce qu’un algorithme ?, Prof. Jean Cardinal, The Conversation, 2021
• Les algorithmes : des boîtes noires, vraiment ?, David Monniaux, The Conversation, 2024

Fiches d'activités

Fiche 9.1 : Doomsday Algorithm	Fiche 9.2 : carrés magiques
Fiche 9.3 : le crêpier psychorigide	Fiche 9.4 : des algorithmes de tri
Fiche 9.5 : les rubans de Pascal	Fiche 9.6 : le barman aveugle
Fiche 9.7 : les labyrinthes	Couples stables et prix Nobel (Accromath vol. 18.2, 2023)

Vidéos

• Qu'est-ce qu'un algorithme ? Explication avec la recette du gâteau au chocolat (4'), Big Bang Science, 2019
• Algorithme : Il vous connait mieux que vous-même (22'), Fabien Olicard, 2025
• Nos algorithmes pourraient-ils être BEAUCOUP plus rapides ? (P=NP ?) (27'), Science étonnante, 2020
  
  
• Gift Wrapping Algorithm (Convex Hull)
  
  
• Comment s'évader d'un labyrinthe à tous les coups ? ft Manon Bril - Scilabus, 2020
  
  
• PARCOURSUP et les algorithmes de mariage stable, Science étonnante, 2020

Ebauches et corrigés des exercices

Ebauches : 9.8, 9.9, 9.10 Corrigés : 9.1, 9.2, 9.3, 9.4, 9.5, 9.6, 9.7, 9.8, 9.9, 9.10 Corrigés des fiches : Pancake sort Corrigés de l'annexe : A9.1, A9.2, A9.3, A9.4, A9.5, A9.11a, A9.11b, A9.11c Comparaisons des résultats des exercices A9.6, A9.7, A9.8, A9.9 et A9.10

Programmes Python de l'annexe 9

• descente de plus grande pente
• recherche avec tabous
• recuit simulé
• algorithme génétique
  
  
• ruzzle_fr.py, dico_ruzzle.txt

Sites de référence

• Wikipédia : Algorithmique
• Wikipédia : Algorithme de tri
• Wikipédia : Enveloppe convexe

Livres

• The Art of Computer Programming, Donald E. Knuth, Addison Wesley, 2011
• Data Structures and Algorithm Analysis in C++, Mark A. Weiss, Pearson, 2005
• Algorithms, Robert Sedgewick, Addison Wesley, 2011
• Introduction à l'algorithmique, Thomas H. Cormen et al., Dunod, 2002
• Programmation Efficace, Christoph Dürr, Jill-Jênn Vie, Ellipse, 2016
• Algorithmique, conception et analyse, G. Brassard, P. Bratley, Masson, 1987
  
  
• Métaheuristiques pour l'optimisation difficile, Dréo et al., Eyrolles, 2003
• Métaheuristiques, Bastien Chopard et Marco Tomassini, Presses universitaires de Perpignan, 2017