Sciences naturelles
Questions sur les algorithmes
Existe-t-il toujours un algorithme permettant de répondre à une question donnée ?

Questions sur les algorithmes. LR200311369

Article mis en ligne le 29 juin 2007
dernière modification le 28 août 2011

par Bernard Vuilleumier

Au cours de sa longue histoire, le concept d’algorithme a connu plusieurs significations. Mais ces différentes significations ont toutes en commun la référence à la notion de règles opératoires.


Questions

  1. Où rencontre-t-on des algorithmes ?
  2. Y a-t-il aussi des algorithmes en mathématiques ?
  3. Quand la notion d’algorithme a-t-elle été explicitée ?
  4. Y a-t-il un rapport entre logarithme et algorithme ?
  5. Existe-t-il toujours un algorithme pour toute question ?
  6. Quel lien y a-t-il entre un algorithme et un programme d’ordinateur ?
  7. Comment comparer des algorithmes ?
  8. Peut-on produire du hasard à partir d’algorithmes ?
  9. Qu’est-ce qu’un algorithme probabiliste ?
  10. Les algorithmes ont-ils une influence sur les mathématiques ?

Activités [1]
- Décrivez un algorithme permettant de trouver le PGCD de deux nombres
- Donnez une interprétation géométrique de l’algorithme d’Euclide
- Trouvez le plus grand commun diviseur des nombres p, q donnés
- Observez l’algorithme à l’œuvre dans le jeu des tours de Hanoï
- Déplacez un cavalier afin qu’il visite toutes les cases d’un échiquier une seule fois


Sujet lié
- Problèmes d’optimisation


Extension
- Étude de machines de Turing (from Wolfram Demonstrations Project)