COGNITIA • DÉVELOPPER VOTRE POTENTIEL
Tableau de bord
Votre espace pour apprendre, vous entraîner et progresser.
Retour à
Algorithmes : puissance, limites et performance
Existe t il un algorithme pour chaque problème Décidabilité 2
Problèmes résolus Problèmes indécidables Décidabilité vs. Calculabilité Testez vos connaissances : https://cognitia.ucomtech.eu/qcm/quiz_turing_avance.php
Vidéo du coursRegardez la vidéo puis poursuivez avec le contenu.
Problèmes résolus : Certains problèmes peuvent être résolus par un algorithme, qui donne une réponse (oui/non) en un temps fini. Exemple : Vérifier si un nombre est premier .
Problèmes indécidables : D'autres, comme le problème de l'arrêt , n'ont pas de solution algorithmique universelle. Alan Turing a prouvé qu'il existe des problèmes pour lesquels aucun algorithme ne peut garantir une réponse.
Décidabilité vs. Calculabilité : La décision concerne les problèmes binaires (oui/non), tandis que la calculabilité inclut aussi les problèmes nécessitant une sortie constructive (ex. : calculer une valeur).
Problèmes indécidables : D'autres, comme le problème de l'arrêt , n'ont pas de solution algorithmique universelle. Alan Turing a prouvé qu'il existe des problèmes pour lesquels aucun algorithme ne peut garantir une réponse.
Décidabilité vs. Calculabilité : La décision concerne les problèmes binaires (oui/non), tandis que la calculabilité inclut aussi les problèmes nécessitant une sortie constructive (ex. : calculer une valeur).