Séance de cours
Halting Problem : des problèmes insolubles
Dans cours
DEMO: excepteur ipsum eu adipisicing
Aliquip voluptate consectetur velit eiusmod veniam ea commodo incididunt in ex laboris dolore. Est ea velit sunt fugiat nulla pariatur in deserunt cupidatat sint incididunt nisi ea minim. Anim consequat in ullamco labore incididunt. Excepteur sint consequat dolor aliqua minim dolore esse non pariatur incididunt enim fugiat incididunt aliquip. Nisi magna proident veniam cillum dolore eiusmod pariatur deserunt anim cillum consequat.
Description
Cette séance de cours traite du concept de problèmes insolubles dans les algorithmes, en se concentrant sur le problème d'arrêt introduit par Turing. Il présente une esquisse de preuve démontrant qu'il ne peut pas y avoir de procédure pour déterminer si un programme va s'arrêter. La séance de cours se termine en soulignant les limites des algorithmes dans la résolution de chaque problème.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Proximité ontologique
Séances de cours associées (28)
Halting Problem : des problèmes insolubles
Explore l'insolvabilité du problème d'arrêt dans les algorithmes et les limites des procédures dans la détermination de l'arrêt du programme.
Théorie de la calculabilité et problème d'arrêtMOOC: Information, Calcul, Communication: Introduction à la pensée informatique
Couvre la théorie de la calculabilité et le problème de l'arrêt dans les algorithmes.
L'indécidabilité : langages récursifs et machines de Turing
Explore l'indécidabilité à travers les langages récursifs, les machines de Turing et le problème de l'arrêt.
Éléments de complexité computationnelle
Introduit la complexité computationnelle, les problèmes de décision, la complexité quantique et les algorithmes probabilistes, y compris les problèmes dures au NP et les problèmes complets au NP.
Indécidabilité: Partie 1
Introduit l'indécidabilité dans les langages récursifs et les machines Turing, montrant des langages sans reconnaissance algorithmique.