Questions sur les algorithmes

Existe-t-il toujours un algorithme permettant de répondre à une question donnée ?
vendredi 29 juin 2007
par  Bernard Vuilleumier
popularité : 1%

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)



[1Ces activités peuvent être réalisées à l’aide de petits programmes disponibles sur le site Wolfram Demonstrations Project. Ces mini-applications sont exécutables avec MathematicaPlayer qui est gratuit. Comment puis-je lire et exécuter un notebook Mathematica si je ne possède pas le logiciel ?