[PDF] Dénombrabilité mot et langage - Intelligence Artificielle et Systèmes





Previous PDF Next PDF



denombrabilite.pdf

14 mai 2005 Montrer que l'ensemble des sous-ensembles finis de N est dénombrable. Solution de l'exercice 9. Polynômes `a coefficients entiers. A chaque ...



Annexe A - Ensembles dénombrables

dénombrable. On remarque qu'on a montré dans la démonstration qu'un ensemble infini dénombrable est en fait en bijection avec N. Comme conséquence immédiate 



ensembles-au-plus-denombrables.pdf

est une bijection de 2 sur ). On montre que. ? Le produit cartésien d'une suite finie d'ensembles dénombrables est dénombrable. Conséquence :.



Dénombrabilité

On dit qu'un ensemble E est dénombrable s'il est en bijection avec une partie Il suffit de démontrer que toute partie infinie E ? N est en bijection.



Chapitre 4 : Ensembles finis et infinis 1 Ensembles finis

On dit qu'un ensemble E a n éléments ou est de cardinal n



Dénombrabilité mot et langage - Intelligence Artificielle et Systèmes

Savoir définir une bijection entre deux ensembles dénombrables. Savoir montrer qu'un ensemble est non dénombrable. Connaitre le cardinal de l'ensemble des 



1 Tribus

On rappelle qu'une tribu sur R est un ensemble de parties de R contenant famille dénombrable d'éléments de C ; on veut montrer que ?i?I Ai ? C.



12.2 Exercices du chapitre 2 - 12.2.1 Tribus

Corrigé 10 (Tribu engendrée). Soit E un ensemble. 1. Montrer qu'une intersection quelconque de tribus sur E est une tribu sur E.



TD 1 : correction

Déjà l'ensemble I est dénombrable : par définition d'une partition



Ensembles dBnombrables

DBfinition 2 Un ensemble est au plus dénombrable s@il est fini ou dénom brable. Il est simple aussi de démontrer que *$ % est dénombrable puisque.



[PDF] Ensembles dénombrables

On dit d'un ensemble qu'il est dénombrable s'il est en bijection avec une partie de N En particulier un ensemble fini est considéré comme dénombrable



[PDF] Ensembles dénombrables

10 sept 2021 · On dit d'un ensemble qu'il est dénombrable s'il est en bijection avec une partie de N En particulier un ensemble fini est considéré comme 



[PDF] DENOMBRABILITE

14 mai 2005 · Exercice 6 Montrer que N × N est dénombrable En déduire que le produit d'un nombre fini d'ensembles dénombrables est dénombrable



[PDF] 2 Ensembles et dénombrabilité

Un ensemble est défini par les éléments qu'il contient et qui lui appartiennent Les ensembles infinis dénombrables en bijection avec IN de cardinal



[PDF] Montrer quun ensemble est dénombrable - Devmath

Ici nous utilisons la définition des ensembles dénombrables de Cantor Nous considérons qu'un ensemble dénombrable est doncinfini



[PDF] Ensembles dénombrables topologie de R suites numériques

existe une bijection de E dans F • On dit qu'un ensemble E est dénombrable lorsqu'il est équipotent à N Exemples : - N est dénombrable



[PDF] DÉNOMBRABLE OU CONTINU

puissance du continu si et seulement si il est équipotent à \ Résultats préliminaires Soit A B et C trois ensembles Démontrer que :



Exercices corrigés -Ensembles dénombrables ensembles équipotents

Les ensembles suivants sont-ils dénombrables? Démontrer que l'ensemble des nombres algébriques est dénombrable Indication



[PDF] Quelques notions sur la dénombrabilité - Gargantua de lX

On dit qu'un ensemble X est dénombrable s'il est fini ou s'il est en bijection avec N Exercice : Montrer que pour tout N ? 1 NN est dénombrable

  • Comment démontrer qu'un ensemble est dénombrable ?

    On dit qu'un ensemble X est dénombrable s'il est fini ou s'il est en bijection avec N. Exemple : N ? {0}, 2N, Z sont dénombrables. (1) ?0(n) = n + 1 réalise une bijection de N sur N ? {0}.

  • Pourquoi Q est dénombrable ?

    Par l'application en question, un élément de N a un nombre fini d'antécédents, c'est tout. Les autres repéresentants de chacun des rationnels antécédents n'interviennent pas. A vrai dire, ils ont d'autant moins d'importance qu'ils constituent eux-mêmes un ensemble dénombrable.

  • Pourquoi l'ensemble R n'est pas dénombrable ?

    Pour démontrer que ? est non dénombrable, il suffit de démontrer la non-dénombrabilité du sous-ensemble [0, 1[ de ?, donc de construire, pour toute partie dénombrable D de [0, 1[, un élément de [0, 1[ n'appartenant pas à D. Soit donc une partie dénombrable de [0, 1[ énumérée à l'aide d'une suite r = (r1, r2, r3, … ).
  • Plus formellement, un ensemble E est dit fini s'il existe un entier naturel n et une bijection entre E et l'ensemble des entiers naturels strictement plus petits que n. Cet entier n, qui est alors unique, est appelé le nombre d'éléments, ou cardinal, de l'ensemble fini E.
Dénombrabilité mot et langage - Intelligence Artificielle et Systèmes Intelligence Artificielle et Syst`emes Formels (IASF)

2 mati`eres dans 1 UE :

Syst`emes Formels :

fondement de l"informatique, bases avant compilationIntelligence Artificielle : Comportement intelligent humain fait par une machineWeb page de l"enseignement : http://www-lisic.univ-littoral.fr/ ≂verel

Syst`emes Formels

Utilisations pratiques

Sp´ecification des langages de programmation,

Compilation, analyseur syntaxique,

Recherche de motifs (texte, BD, web, etc.),

les TALN

Syst`emes d"exploitation,

Compression de texte,

Cryptographie,

Automatique,

etc.

Syst`emes Formels

Questions fondamentales - et pratiques!

Sp´ecification de programmes:

S´emantique d"un programmeV´erification de programmes:

Correction du programmeComplexit´e:

Temps, espace pour ex´ecuter le calculCalculabilit´e:

Que peut-on calculer `a l"aide d"un algorithme?

Quels probl`emes peut-on r´esoudre avec un ordinateur?Mot : r´eponse possible `a un probl`eme Langage : ensemble des r´eponses positives au probl`eme Mod`ele de calcul : programme qui "calcule" le langage automate, machine de Turing, automate cellulaire, lambda-calcul, fonction r´ecursive, etc.

Syst`emes Formels

Questions fondamentales - et pratiques!

Sp´ecification de programmes:

S´emantique d"un programmeV´erification de programmes:

Correction du programmeComplexit´e:

Temps, espace pour ex´ecuter le calculCalculabilit´e:

Que peut-on calculer `a l"aide d"un algorithme?

Quels probl`emes peut-on r´esoudre avec un ordinateur?Mot : r´eponse possible `a un probl`eme Langage : ensemble des r´eponses positives au probl`eme Mod`ele de calcul : programme qui "calcule" le langage automate, machine de Turing, automate cellulaire, lambda-calcul, fonction r´ecursive, etc.

D´enombrabilit´e, mot et langage

Intelligence Artificielle et Syst`emes Formels

Master 1 I2L

S

´ebastien Verel

verel@lisic.univ-littoral.fr http://www-lisic.univ-littoral.fr/ ≂verelUniversit´e du Littoral Cˆote d"Opale

Laboratoire LISIC

Equipe CAMOME

Mot d"introductionD´enombrabilit´eMots et langages

Objectifs de la s´eance 01

Savoir d´efinir mot et langage.

Savoir ´ecrire une expression r´eguli`ere simple

Savoir d´efinir un ensemble d´enombrable

Savoir d´efinir une bijection entre deux ensembles d´enombrablesSavoir montrer qu"un ensemble est non d´enombrable Connaitre le cardinal de l"ensemble des partis d"un ensemble finiQuestion principale du jour :

Quelle langue parlons-nous?

Mot d"introductionD´enombrabilit´eMots et langages

Objectifs de la s´eance 01

Savoir d´efinir mot et langage.

Savoir ´ecrire une expression r´eguli`ere simple

Savoir d´efinir un ensemble d´enombrable

Savoir d´efinir une bijection entre deux ensembles d´enombrablesSavoir montrer qu"un ensemble est non d´enombrable Connaitre le cardinal de l"ensemble des partis d"un ensemble finiQuestion principale du jour :

Quelle langue parlons-nous?

Mot d"introductionD´enombrabilit´eMots et langages

R´ef´erences

Sources principales

Denis Robilliard, Universit´e du Littoral Cˆote d"Opale, http://www-lisic.univ-littoral.fr/ ≂robilliaSandrine Julia, Universit´e Nice Sophia Antipolis, deptinfo.unice.fr/ ≂julia/IT/Mots cl´es langage rationnel, automate, automate fini d´eterministe, Kleene, expression r´eguli`ere, d´etermination, lemme de l"´etoile, machine de

Turing, etc.

Mot d"introductionD´enombrabilit´eMots et langages Plan

1Mot d"introduction

2D´enombrabilit´e

3Mots et langages

Mot d"introductionD´enombrabilit´eMots et langages

Quelques exemples de mots...

ulysse toison heureux beau celui-l`a voyage

Joachim DU BELLAY (1522-1560)

Mot d"introductionD´enombrabilit´eMots et langages

Quelques exemples de mots...

ulysse toison heureux beau celui-l`a voyage

Joachim DU BELLAY (1522-1560)

Mot d"introductionD´enombrabilit´eMots et langages

Quelques exemples de mots...

Ou encore :

0605547781

0492942724

0675389509

0492946666

Ou encore :

as1sce as2ce as3scel Mot d"introductionD´enombrabilit´eMots et langages

Quelques exemples de mots...

Ou encore :

0605547781

0492942724

0675389509

0492946666

Ou encore :

as1sce as2ce as3scel Mot d"introductionD´enombrabilit´eMots et langages

D´efinition de mot

Alphabet

UnalphabetΣ est un ensembled´enombrable.

Les ´el´ements de Σ sont appel´es leslettresousymbolesde l"alphabet.Remarque : tr`es souvent un alphabet sera mˆeme un ensemble fini. Mot d"introductionD´enombrabilit´eMots et langages

Au fait

Les notions de fini et d´enombrable

interviennent beaucoup dans ce cours, et plus g´en´eral en informatiquePetit crochet pour l"´etudiant

Grand crochet pour l"informatique

(mais pas trop grand) Mot d"introductionD´enombrabilit´eMots et langages

Au fait

Les notions de fini et d´enombrable

interviennent beaucoup dans ce cours, et plus g´en´eral en informatiquePetit crochet pour l"´etudiant

Grand crochet pour l"informatique

(mais pas trop grand) Mot d"introductionD´enombrabilit´eMots et langages

Petite r´eflexion venue de loin

2 enclos contigus enferment beaucoup de moutons de deux bergers.

Comment savoir s"ils ont le mˆeme nombre de moutons? Pr´ecisions : les moutons peuvent bouger ´enorm´ement mais il est possible de les faire passer par une porte...Cardinalit´e Comparer les ensembles au moyen des bijections (et injections) Mot d"introductionD´enombrabilit´eMots et langages

Petite r´eflexion venue de loin

2 enclos contigus enferment beaucoup de moutons de deux bergers.

Comment savoir s"ils ont le mˆeme nombre de moutons? Pr´ecisions : les moutons peuvent bouger ´enorm´ement mais il est possible de les faire passer par une porte...Cardinalit´e Comparer les ensembles au moyen des bijections (et injections) Mot d"introductionD´enombrabilit´eMots et langages

Cardinalit´e

Bijection (correspondance 1 - 1)

f:X→Yest une fonctionbijectivessi :injective : pour toutx,x??Xtel quef(x) =f(x?) alorsx=x?surjective : pour touty?Y, il existex?Xtel quey=f(x)?pour touty?Y, il existe un uniquex?Xtel quey=f(x)

Autant de moutons de chaque cˆot´e,

autant de "trucs" de chaque cˆot´e, r´e´ecriture/codage de Y par X, cl´e unique, ... Mot d"introductionD´enombrabilit´eMots et langages

Cardinalit´e

Comparer les ensembles au moyen des bijections (et injections)

Equipotent

Les ensemblesXetYont lemˆeme cardinal(´equipotent)

s"il existe une bijection de X dans Y"A chaque fois que X pr´esente un nouvel ´el´ement, Y pr´esente un nouvel

´el´ement, et r´eciproquement."Subpotent

Le cardinal deXest plus petit ou ´egale au cardinal deY

(subpotent) s"il existe une injection de X dans Y"A chaque fois que X pr´esente un nouvel ´el´ement, Y pr´esente un nouvel

´el´ement."Exercices fiche TD 01.

Mot d"introductionD´enombrabilit´eMots et langages

Ensemble d´enombrable

Ensemble fini

Un ensembleXest fini ssi il existe un entier naturelnet une bijection de l"ensemble des entiers compris entre 0 etn-1 dans

X. Le nombre d"´el´ements (cardinal) deXest alorsn.Remarque : l"ensemble vide∅est fini.Ensemble d´enombrable

Un ensemble d´enombrable est soit un ensemble fini, soit un ensemble en

bijection avec l"ensemble des entiers naturelIN.Remarque :INest un ensemble d´enombrable.Remarque intuitive

Un ensemble est d´enombrable lorsqu"on peut num´eroter ses ´el´ements avec les entiers (cf. exercices fiche TD 01) - d´efinit la bijection. Mot d"introductionD´enombrabilit´eMots et langages

Ensemble d´enombrable

Ensemble fini

Un ensembleXest fini ssi il existe un entier naturelnet une bijection de l"ensemble des entiers compris entre 0 etn-1 dans

X. Le nombre d"´el´ements (cardinal) deXest alorsn.Remarque : l"ensemble vide∅est fini.Ensemble d´enombrable

Un ensemble d´enombrable est soit un ensemble fini, soit un ensemble en

bijection avec l"ensemble des entiers naturelIN.Remarque :INest un ensemble d´enombrable.Remarque intuitive

Un ensemble est d´enombrable lorsqu"on peut num´eroter ses ´el´ements avec les entiers (cf. exercices fiche TD 01) - d´efinit la bijection. Mot d"introductionD´enombrabilit´eMots et langages Exemple fondamental : cardinalit´e de [0,1]Th´eor`eme L"ensemble des nombres r´eels entre 0 et 1 n"est pas d´enombrable. Cons´equence : on ne peut pas coder l"ensemble des nombres r´eels de

[0,1] avec un ordinateur!Preuve :Proc´ed´e diagonal de Cantor, voir au tableau.Georg Cantor, math´ematicien allemand, 1845 - 1918.

Th´eorie des ensembles

Ensemble bien ordonn´e

"infinit´e d"infinis" Mot d"introductionD´enombrabilit´eMots et langages Exemple fondamental : cardinalit´e de [0,1]Th´eor`eme L"ensemble des nombres r´eels entre 0 et 1 n"est pas d´enombrable. Cons´equence : on ne peut pas coder l"ensemble des nombres r´eels de

[0,1] avec un ordinateur!Preuve :Proc´ed´e diagonal de Cantor, voir au tableau.Georg Cantor, math´ematicien allemand, 1845 - 1918.

Th´eorie des ensembles

Ensemble bien ordonn´e

quotesdbs_dbs28.pdfusesText_34
[PDF] r n'est pas dénombrable

[PDF] p(n) non dénombrable

[PDF] montrer que n*n est dénombrable

[PDF] comment savoir si une fonction est bijective

[PDF] montrer qu'une fonction est injective

[PDF] bijection réciproque exercices corrigés

[PDF] montrer que f réalise une bijection

[PDF] baguier virtuel sans imprimer

[PDF] baguier gratuit

[PDF] controle francais 4eme poesie lyrique

[PDF] évaluation français entrée 4ème collège

[PDF] bilan exemple

[PDF] bilan définition

[PDF] le bilan comptable cours

[PDF] bilan ulis