Séance de cours

Théorie de calcul : problèmes de comptage et de décision

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Description

Cette séance de cours couvre la théorie du calcul, en se concentrant sur le comptage des ensembles infinis et les problèmes de décision. Il examine le concept de la comptabilité, montrant comment compter des ensembles infinis comme des entiers positifs et des paires d'entiers positifs. La séance de cours explore également la notion de décidabilité, en distinguant les problèmes décidables et les problèmes indécis. Il présente des exemples de problèmes décidables, comme la vérification si un nombre est un multiple d'un autre, et introduit le problème d'arrêt indécis. À travers des démonstrations d'auto-référence et de paradoxes, la séance de cours illustre les limites du calcul dans la résolution de certains problèmes. Il conclut en soulignant l'importance de reconnaître les problèmes indécis et le pouvoir de l'auto-référence dans la théorie computationnelle.

Cette vidéo est disponible exclusivement sur Mediaspace pour un public restreint. Veuillez vous connecter à Mediaspace pour y accéder si vous disposez des autorisations nécessaires.

Regarder sur Mediaspace

Source officielle

Proximité ontologique

Mathématiques

Logique mathématique: Théorie des ensembles

Concepts associés (32)

Ensemble dénombrable

En mathématiques, un ensemble est dit dénombrable, ou infini dénombrable, lorsque ses éléments peuvent être listés sans omission ni répétition dans une suite indexée par les entiers. Certains ensembles infinis, au contraire, contiennent « trop » d'éléments pour être parcourus complètement par l'infinité des entiers et sont donc dits « non dénombrables ». Il existe deux usages du mot « dénombrable » en mathématiques, suivant que l'on comprend ou non parmi les ensembles dénombrables les ensembles finis, dont les éléments peuvent être numérotés par les entiers positifs inférieurs à une valeur donnée.

Problème de décision

En informatique théorique, un problème de décision est une question mathématique dont la réponse est soit « oui », soit « non ». Les logiciens s'y sont intéressés à cause de l'existence ou de la non-existence d'un algorithme répondant à la question posée. Les problèmes de décision interviennent dans deux domaines de la logique : la théorie de la calculabilité et la théorie de la complexité. Parmi les problèmes de décision citons par exemple le problème de l'arrêt, le problème de correspondance de Post ou le dernier théorème de Fermat.

Ensemble infini

En mathématiques, plus précisément en théorie des ensembles, un ensemble infini est un ensemble qui n'est pas fini, c'est-à-dire qu'il n'y a aucun moyen de « compter » les éléments de cet ensemble à l'aide d'un ensemble borné d'entiers. Un ensemble en bijection avec un ensemble infini est donc infini. Tout ensemble contenant un ensemble dénombrable est infini. Dans la théorie de Zermelo (Z), l'axiome de l'infini permet de construire l'ensemble N des entiers naturels, qui est alors un ensemble infini.

Dedekind-infinite set

In mathematics, a set A is Dedekind-infinite (named after the German mathematician Richard Dedekind) if some proper subset B of A is equinumerous to A. Explicitly, this means that there exists a bijective function from A onto some proper subset B of A. A set is Dedekind-finite if it is not Dedekind-infinite (i.e., no such bijection exists). Proposed by Dedekind in 1888, Dedekind-infiniteness was the first definition of "infinite" that did not rely on the definition of the natural numbers.

Undecidable problem

In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. The halting problem is an example: it can be proven that there is no algorithm that correctly determines whether arbitrary programs eventually halt when run. A decision problem is a question which, for every input in some infinite set of inputs, answers "yes" or "no"..

Afficher plus

Séances de cours associées (62)

Relations, séquences et sommations

Couvre les chaînes, les ensembles dénombrables, la cardinalité et le concept de dénombrabilité, explorant la dénombrabilité de divers ensembles et la diagonalisation de Cantor.

Espaces L2 séparables

Couvre le concept de L 2 espaces séparables, démontrant des propriétés et fournissant des exemples.

Fractales et étranges attracteurs

Plonge dans la renormalisation, les fractales et les attracteurs étranges, explorant les propriétés des ensembles dénombrables et innombrables.

Théorie des probabilités: Lecture 2

Explore les modèles de jouets, les sigma-algèbres, les variables aléatoires à valeur T, les mesures et l'indépendance dans la théorie des probabilités.

Dynamiques non linéaires : chaos et systèmes complexes

Explore les ensembles dénombrables et innombrables, l'ensemble Cantor, l'ensemble Mandelbrot et la dimension Box dans la dynamique non linéaire et les systèmes complexes.

Afficher plus

Concepts associés (32)

Ensemble dénombrable

Problème de décision

Ensemble infini

Dedekind-infinite set

Undecidable problem

Afficher plus