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


Documents du chapitre

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).