[PDF] Introduction à la notion d'ensembles - Université de Toulouse



Previous PDF Next PDF


























[PDF] Les Ensembles de Nombres

[PDF] Les ensembles de nombres

[PDF] Les ensembles de nombres - Maths, 2nde

[PDF] les ensembles de nombres cours

[PDF] les ensembles de nombres exercices

[PDF] les ensembles de nombres exercices corrigés

[PDF] les ensembles de nombres pdf

[PDF] Les ensembles dénombrables aide

[PDF] les ensembles mathématiques

[PDF] les ensembles mathématiques exercices corrigés

[PDF] les ensembles mathématiques pdf

[PDF] les ensembles n z q r

[PDF] les ensembles n z q r pdf

[PDF] les ensembles n z q r tronc commun

[PDF] Les entiers - Mathématiques

Introduction à la notion d"ensembles

Université de Toulouse

Année 2020/2021

1 / 16

Introduction à la notion d"ensembles

Introduction à la notion d"ensembles2 / 16

Premières notions

Notion d"ensembles

Unensembleest une collection d"objets deux à deux distincts appelés

éléments. On peut définir un ensemble de deux manières :enextension: on donne la liste des éléments;encompréhension: on donne une propriété commune vérifiée par les

éléments de l"ensemble.

Introduction à la notion d"ensemblesPremières notions3 / 16

Exemples

Ensembles d"élèves :

I fPierre; Paul;Marie;Julie;KarimgI félèves de la classe qui ont les yeux bleusgI félèves qui viennent en cours en pyjamag(certainement vide!)Ensembles classiques de nombres : I ?=f0;1;2;3;:::gest l"ensemble des nombres naturels; I?=f:::;3;2;1;0;1;2;3;:::gest l"ensemble des nombres entiers;

I?=fp=q:p2?etq2?avecq6=0g;

I?l"ensemble des nombres réels;Dans les langages de programmation, comme Python, certaines variables soient déclarées avec un certaintype de données: I bools"interprète comme l"ensemblefVrai;Fauxg,

Iints"interprète comme l"ensemble des entiers

Ifloats"interprète comme l"ensemble des nombres à virgule flottante Istrs"interprète comme l"ensemble des chaînes de caractères Ilists"interprète comme l"ensemble des listes.KarimPierre

PaulMarieJulie

Introduction à la notion d"ensemblesPremières notions4 / 16

Exemples

Ensembles d"élèves :

I fPierre; Paul;Marie;Julie;KarimgI félèves de la classe qui ont les yeux bleusgI félèves qui viennent en cours en pyjamag(certainement vide!)Ensembles classiques de nombres : I ?=f0;1;2;3;:::gest l"ensemble des nombres naturels; I?=f:::;3;2;1;0;1;2;3;:::gest l"ensemble des nombres entiers;

I?=fp=q:p2?etq2?avecq6=0g;

I?l"ensemble des nombres réels;Dans les langages de programmation, comme Python, certaines variables soient déclarées avec un certaintype de données: I bools"interprète comme l"ensemblefVrai;Fauxg,

Iints"interprète comme l"ensemble des entiers

Ifloats"interprète comme l"ensemble des nombres à virgule flottante Istrs"interprète comme l"ensemble des chaînes de caractères

Ilists"interprète comme l"ensemble des listes.Introduction à la notion d"ensemblesPremières notions4 / 16

Exemples

Ensembles d"élèves :

I fPierre; Paul;Marie;Julie;KarimgI félèves de la classe qui ont les yeux bleusgI félèves qui viennent en cours en pyjamag(certainement vide!)Ensembles classiques de nombres : I ?=f0;1;2;3;:::gest l"ensemble des nombres naturels; I?=f:::;3;2;1;0;1;2;3;:::gest l"ensemble des nombres entiers;

I?=fp=q:p2?etq2?avecq6=0g;

I?l"ensemble des nombres réels;Dans les langages de programmation, comme Python, certaines variables soient déclarées avec un certaintype de données: I bools"interprète comme l"ensemblefVrai;Fauxg,

Iints"interprète comme l"ensemble des entiers

Ifloats"interprète comme l"ensemble des nombres à virgule flottante Istrs"interprète comme l"ensemble des chaînes de caractères

Ilists"interprète comme l"ensemble des listes.Introduction à la notion d"ensemblesPremières notions4 / 16

Exemples

Ensembles d"élèves :

I fPierre; Paul;Marie;Julie;KarimgI félèves de la classe qui ont les yeux bleusgI félèves qui viennent en cours en pyjamag(certainement vide!)Ensembles classiques de nombres : I ?=f0;1;2;3;:::gest l"ensemble des nombres naturels; I?=f:::;3;2;1;0;1;2;3;:::gest l"ensemble des nombres entiers;

I?=fp=q:p2?etq2?avecq6=0g;

I?l"ensemble des nombres réels;Dans les langages de programmation, comme Python, certaines variables soient déclarées avec un certaintype de données: I bools"interprète comme l"ensemblefVrai;Fauxg,

Iints"interprète comme l"ensemble des entiers

Ifloats"interprète comme l"ensemble des nombres à virgule flottante Istrs"interprète comme l"ensemble des chaînes de caractères

Ilists"interprète comme l"ensemble des listes.Introduction à la notion d"ensemblesPremières notions4 / 16

Principales règles de fonctionnement

Sans rentrer dans l"axiomatique, la notion d"ensemble satisfait un certain nombre de règles de fonctionnement : Relation d"appartenanceOn notex2Asi l"élémentxest dansA. Objets distinctsOn peut distinguer deux éléments entre eux et un ensemble ne peut pas contenir deux fois le même objet. Ensemble videIl existe un ensemble qui ne contient aucun élément, c"est l"ensemble vide noté;. Paradoxe de RussellUn ensemble peut être élément d"un autre ensemble mais pas de lui même. Introduction à la notion d"ensemblesPremières notions5 / 16

Inclusion

Inclusion

L"ensembleAest unsous-ensembledeBsi tous les éléments deAsont des éléments deB, autrement dit x2A=)x2B

On le noteAB(AinclusdansB).Exemple :

f0;1;2g f0;1;2;3g ????? Remarque :A=Bsi et seulement siABetBAIntroduction à la notion d"ensemblesSous ensembles6 / 16

Ensemble des parties

Ensemble des parties

SoitAun ensemble, l"ensemble des parties deAnotéP(A)est l"ensemble des sous-ensembles deA.Remarque :

On a toujours

; 2 P(A)car; A,A2 P(A)carAA.

Exemple :SiA=f1;2;3galors

P(A) =f;;f1g;f2g;f3g;f1;2g;f1;3g;f2;3g;f1;2;3ggIntroduction à la notion d"ensemblesSous ensembles7 / 16

Union et intersection

AB Union

A[B=féléments deAou deBgA[BPropriétés

Idempotence :A[A=A

Commutativité :A[B=B[A

Associativité :A[(B[C) = (A[B)[C

Elément neutre :A[ ;=AIntersection

A\B=féléments deAet deBgA\BPropriétés

Idempotence :A\A=A

Commutativité :A\B=B\A

Associativité :A\(B\C) = (A\B)\C

Elément neutre :A\

=ADistributivité

A[(B\C) = (A[B)\(A[C)etA\(B[C) = (A\B)[(A\C)Introduction à la notion d"ensemblesOpérations sur les ensembles8 / 16

Différences et complémentaire

AB

Différence

ArB=féléments dansAmais pas dansBgArBDifférence symétrique

AB=féléments dansA[Bmais pas dansA\Bg

= (A[B)r(A\B)ABComplémentaire A= rAA

Propriétés

Involution :A=A

Loi de Morgan :A\B=A[BetA[B=A\B

Introduction à la notion d"ensemblesOpérations sur les ensembles9 / 16

Produit cartésien

Produit cartésien

AB=f(a;b)oùa2Aetb2Bg.

A

1 Ak=f(a1;:::;ak)oùai2Aipour touti2 f1;:::;kgg.Exemple :

Pour le système de codage informatique des couleurs RGB, (de l"anglais "Red, Green, Blue") une couleur est un élément de [0;255][0;255][0;255] = [0;255]3deux couleurs qui ont le même triplet sont égale; on peut définir des ensembles de couleur : fcouleur à dominante verteg=§ (r;g;b) :g45 (r+b)ª Introduction à la notion d"ensemblesOpérations sur les ensembles10 / 16

Notions de langages

Notions de langages11 / 16

Exemples de problèmes

Langage naturel

L"ensemble des mots fo rmeun dictionnaire qui s"a rrangent suivant des règles grammaticales pour former des phrases.

Stockage informatique

de l"info rmationpa rune succession de bits

Algorithme du texte

Recherche de chaîne de ca ractèresdans un texte...

Compilation

Un p rogrammeest une suite de ca ractèrequi doit être analysé par le compilateur.

Bio-informatique

L"ADN co del "informationgénétique.

Notions de langagesExemples de problèmes12 / 16

Un peu de vocabulaire

Alphabet

Ensemble fini (pa rexemple : B=f0;1gest l"alphabet binaire,A=fa;b;c;:::;zgun alphabet à 26 lettres.) Mot Suite finie d"éléments de Aon le noteu=u1u2:::unetn est la longueur du motu, notéejuj.

Mot vide

Le mot vide est noté ".

On noteAl"ensemble des mots surAetA+l"ensemble des mots sans le mot vide. Concaténationw=u:vest le mot de longueurjuj+jvjtel que w=u1u2:::ujujv1v2:::vjvj

Puissance

on définit pa rrécurrence unpar u

0="etun+1=u:unpour toutn2?

Préfixevpréfixe deus"il existe un motwtel queu=v:w

Suffixevsuffixe deus"il existe un motwtel queu=w:vNotions de langagesMots sur un alphabet fini13 / 16

Equidivisibilité

Lemme de Levy

Soientu;v;z;t2 Atels queu:v=z:t. Alors il existew2 Atel que :ou bienu=z:wett=w:vsijuj jzj,ou bienz=u:wetv=w:tsijuj jzj.uv

ztwou bienztuvw

Corollaire : simplification à droite

Soientu;v;zett2 A.

Siu:v=u:talorsv=t.

De même siu:v=z:valorsu=z.Notions de langagesMots sur un alphabet fini14 / 16

Définition et exemples de langages

Langage

UnlangageLsur un alphabet finiAest un ensemble de mots surA. Autrement ditL A.Exemples :Exemples de langages surB=f0;1g:; 6=f"g;B =f";0;1;00;01;10;11;000;001;:::g;B

+=f0;1;00;01;10;11;000;001;:::g;f0n:n2?g;f0n1m:n;m2?g;f0n1n:n2?g;f0p:p2?nombre premierg;fu2B:uest le codage en binaire d"un nombre premierg;fu2B:uest un palindromeg;fu2Bcode html certifiég 6=fu2Bcode html interprété par Firefoxg;fu2B:ucodage en MP3 de votre chanson préféréeg;fu2B:ucodage d"un programme qui s"arête sur l"entrée videg:::Notions de langagesLangage15 / 16

Opérations sur les langages

Union:L1[ L2Intersection:L1\ L2Compémentaire:L=ArLConcaténation:L1:L2=fu1:u2:u12 L1etu22 L2gPuissance: Par récurrence la puissancenèmedeL, est définie par

L

0=f"getLn+1=L:Ln

Attention, en général

L n=fu2 A:9u1;u2;:::;un2 Ltel queu=u1:u2::ung 6=fun:n2?;u2 LgFermeture de Kleene: L n0LnetL+=[ n>0LnNotions de langagesLangage16 / 16quotesdbs_dbs46.pdfusesText_46