[PDF] MATHÉMATIQUES DISCRÈTES - Institut de Mathématiques de PDF MathDiscretes.pdf

C'est une relation d'ordre total sur A∗ On a par exemple a ≤lex fa, poule ≤lex poulet, avion ≤lex train, livraison ≤lex livre, foot ≤lex fort

Mathématiques discrètes et leurs applications / Kenneth H Rosen Série de livres du CRC en mathématiques discrètes, composée de plus de 55 volumes sur

[PDF] MATHÉMATIQUES DISCRÈTES - Institut de Mathématiques de

C'est une relation d'ordre total sur A∗ On a par exemple a ≤lex fa, poule ≤lex poulet, avion ≤lex train, livraison ≤lex livre, foot ≤lex fort

[PDF] Mathématiques discrètes, 1ère année

25 oct 2010 · On en trouve toujours, dans le cours, dans les livres, dans les annales d' examens Les exercices doivent être préparés, c'est à dire que l'on doit

[PDF] Cours de mathématiques discrètes - cours-info

3 nov 2010 · Mathématiques pour l'informatique Christophe GUYEUX et Jean-François COUCHOT guyeux[arobase]iut-bm univ-fcomte[point]

[PDF] Mathématiques Discrétes - Hatem MASRI

Mathématiques Discrétes Hatem MASRI Septembre 2003 cipline, aucun cours, ni livre, ne peut prétendre couvrir tout le sujet avec pertinence et rigueur 3

[PDF] Introduction aux mathématiques discrètes - IRISA

Ce cours est un voyage au pays des mathématiques discrètes Bibliographie ▷ André Arnold, Irène Guessarian Mathématiques pour l'informatique ▷ Alfred

[PDF] MAT 115 – Logique et mathématiques discrètes - Informatique

24 août 2020 · Les mathématiques constituent le langage commun des sciences et la logique est le fondement des mathématiques L'informatique a été fondée

[PDF] MAT1500 Mathématiques discrètes Automne 2018 4 crédits

Le livre : Rosen, Mathématiques Discrètes, Édition revisée, Chenelière éducation (2002) est disponible au librairie en bas du tour Ce n'est pas obligatoire,

[PDF] MAT1500 Mathématiques discrètes Automnee 2017 Professeur : A

Informations sur les orientations du bacc en mathématiques MAT1500 2 of 21 Le livre : Rosen, Mathématiques Discrètes disponible au librairie en bas du

[PDF] mathématiques discrètes pdf

[PDF] mathématiques discrètes pour l'informatique

[PDF] Mathématiques Dm 4éme

[PDF] mathématiques dm 5

[PDF] Mathematiques dm n1

[PDF] Mathématiques DM pour le 18/09/2015

[PDF] Mathematiques dur besoins de vous

[PDF] mathématiques ecriture scientifque urgent c pour demin g controle SVP

[PDF] mathématiques en économie

[PDF] mathématiques en économie-gestion pdf

[PDF] mathematiques en factorisation ^^

[PDF] mathematiques en geoétrie cned 3eme

[PDF] Mathématiques en option ES (terminale) Matrices

[PDF] MATHEMATIQUES enquete

[PDF] mathématiques enquete policiere

MATHÉMATIQUES DISCRÈTESMathieu SABLIK

Table des matières

I Introduction à la théorie des ensembles

I.1 Notions sur les ensembles

5 I.1.1 Construction par extension et compréhension 5

I.1.2 Principales règles de fonctionnement

I.1.3 Représentation

I.2 Sous-ensembles

I.2.1 Inclusion

I.2.2 Ensemble des parties

I.3 Opérations sur les ensembles

I.3.1 Union et Intersection

I.3.2 Différence et complémentaire

I.3.3 Produit cartésien

II Notions sur les langages

II.1 Exemples de problèmes

II.2 Mots sur un alphabet fini

II.2.1 Un peu de vocabulaire

II.2.2 Propriété d"équidivisibilité

II.3 Langage

II.3.1 Définition et exemples de langages

II.3.2 Opérations sur les langages

II.3.3 Equations sur les langages

III Fonctions et applications

III.1 Premières notions

III.1.1 Définition

III.1.2 Modes de représentation

III.1.3 Composition de fonction et d"applications

III.1.4 Applications singulières

III.2 Propriétés sur les fonctions

III.2.1 Injection et surjection

III.2.2 Bijection et application réciproque

III.3 Quelques classes importantes de fonctions

III.3.1 Fonction caractéristique d"un ensemble

III.3.2 Suites

IV Cardinalité21

IV.1 Cardinalité des ensembles finis

IV.1.1 Ensembles de même cardinalité

IV.1.2 Cardinal d"un ensemble fini

TABLE DES MATIÈRES2

IV.1.3 Principe des tiroirs

IV.2 Dénombrement

23
IV.2.1 Dénombrement et opération sur les ensembles 23

IV.2.2 Arrangements et combinaisons

IV.3 Cas des ensembles infinis

29
IV.3.1 Définition et premiers exemples d"ensembles dénombrables 29

IV.3.2 Critères de dénombrabilité

IV.3.3 Ensembles non dénombrables

31
31

V Relations sur les ensembles

V.1 Vocabulaire des relations

V.1.1 Définition

V.1.2 Modes de représentations

V.1.3 Quelques notions proches

V.2 Propriétés sur les relations

V.3 Relations d"équivalence

V.3.1 Définition et exemples

V.3.2 Classes d"équivalence et partition

V.3.3 Ensemble quotient

VI Relations d"ordre

VI.1 Premières notions

VI.1.1 Définition

VI.1.2 Exemples de relations d"ordre classiques

VI.1.3 Mode de représentation

VI.1.4 Fonctions croissantes et décroissantes

VI.2 Bornes d"un ensemble

VI.3 Induction

VI.3.1 Ordre bien fondé

42
VI.3.2 Application à l"étude de la terminaison d"algorithme 42
VI.3.3?et le principe de récurrence. . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

VI.3.4 Principe d"induction

VI.3.5 Définition inductive

VIIQuelques problèmes sur les graphes

VII.1Différents problèmes à modéliser

VII.2Premières propriétés

VII.2.1 Graphe orienté ou non

VII.2.2 Isomorphisme de graphe

VII.2.3 Degré

VII.3Quelques classes de graphe importantes

VII.3.1 Graphes isolés

VII.3.2 Graphes cycliques

VII.3.3 Graphes complets

VII.3.4 Graphe biparti

VII.3.5 Graphes planaires

VII.3.6 Arbres

VII.4Problèmes de coloriages

VII.4.1 Position du problème

VII.4.2 Exemples d"applications

VII.4.3 Nombre chromatique de graphes classiques

VII.4.4 Comment calculer un nombre chromatique?

VII.4.5 Résolution algorithmique

VII.4.6 Cas des graphes planaires

3Table des MatièresVII.5Problèmes de chemins dans un graphe. . . . . . . . . . . . . . . . . . . . . . . . . . . 58

VII.5.1 Définitions

VII.5.2 Connexité

VII.5.3 Chemin Eulérien

VII.5.4 Chemins hamiltonien

TABLE DESMATIÈRES4

ChapitreIIntroduction à la théorie des ensembles I.1

Notions sur les ensembles

I.1.1

Construction par extension et compréhension

Intuitivement, unensembleest une collection d"objets deux à deux distincts appeléséléments.

On peut définir un ensemble de deux manières : en extension: on donne la liste exhaustive des éléments qui y figurent;

en compréhension: on donne les propriétés que doivent posséder les éléments de l"ensemble.

ExempleI.1.Voilà quelques exemples d"ensembles d"élèves : -fPierre; Paul; Marieg, on donne les trois éléments qui définissent l"ensemble; -félèves de la classe qui ont les yeux bleusg; -félèves qui viennent en cours en pyjamag, mais cet ensemble est certainement vide! ExempleI.2.Dans votre scolarité vous avez rencontré certains ensembles classiques de nombres : -?=f0,1,2,3,...gest l"ensemble des nombres naturels; -?=f1,2,3,...gest l"ensemble des nombres naturels non nul; -?=f...,3,2,1,0,1,2,3,...gest l"ensemble des nombres entiers; -?=fp/q:p2?etq2?avecq6=0g; -?l"ensemble des nombres réels; -?l"ensemble des nombres complexes. ExempleI.3.Les langages de programmation actuels exigent que certaines variables soient décla-

rées avec un certaintype de données. Un type de données est un ensemble d"objets associés à une

liste d"opérations standards effectuées sur ces objets. Définir le type d"une variable équivaut à

déclarer l"ensemble des valeurs possibles et autorisées pour cette variable. Dans la sémantique de Python vous avez dû rencontrer : le type bools"interprète comme l"ensemblefVrai,Fauxg, le type ints"interprète comme l"ensemble des entiers le type floats"interprète comme l"ensemble des nombres à virgule flottante le type strs"interprète comme l"ensemble des chaînes de caractères le type lists"interprète comme l"ensemble des listes de longueur variable. I.1.2

Principales règles de fonctionnement

On admettra l"existence d"ensembles. Sans rentrer dans l"axiomatique, la notion d"ensemble satisfait un certain nombre de règles de fonctionnement, en voici les principales : Relation d"appartenanceIl faut pouvoir dire si un objet est dans l"ensemble. On notex2Al"élé- mentxest dans l"ensembleA.

Chapitre I. INTRODUCTION À LA THÉORIE DES ENSEMBLES6Objets 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 et on le

noteAEoufg.

Paradoxe de RussellUn ensemble peut être élément d"un autre ensemble mais pas de lui même.

RemarqueI.1.Cette dernière règle peut ne pas sembler naturelle. A la naissance de la théorie des

ensembles, les mathématiciens ne voyaient pas d"objection à envisager un ensemble dont les élé-

ments seraient tous les ensembles : l"ensemble des ensembles. Russell leur opposa le paradoxe suivant : A=fx2E:x/2xg. CommeEcontient tous les ensembles,Aappartient àE. Est-ce queA appartient àA? si A2Aalors par définition deA, on aA/2A, si A/2Aalors par définition deA, on aA2A. I.1.3

Représentation

On peut représenter les ensembles à l"aide d"un diagramme de Venn, ce sont les fameux dia- grammes "patates". ExempleI.4.L"ensembefPierre; Paul; Marie; Julie; Karimgse représente par :KarimPierre

PaulMarieJulie

I.2

Sous-ensembles

I.2.1

Inclusion

Définition I.1(Sous-ensembles).L"ensembleAest unsous-ensembledeBsi tous les éléments deA sont des éléments deB(autrement ditx2A=)x2B). On dit aussi queAestinclusdansB, on le noteAB.

RemarqueI.2.Pour tout ensembleAon aAEAetAA.

ExempleI.5.On af1,2g f1,2,3g.

Bien sûr on a?????.

Définition I.2(Egalité d"ensembles).Deux ensembles sontégauxsi et seulement si ils ont les mêmes éléments, autrement dit siABetBA. I.2.2

Ensemble des parties

Définition I.3(Ensemble des parties).SoitAun ensemble, l"ensemble des parties de A, notéP(A), est l"ensemble des sous-ensembles deA. On remarque que l"on a toujoursAE2 P(A)carAEAetA2 P(A)carAA. ExempleI.6.SiA=f1,2,3galorsP(A) =fAE,f1g,f2g,f3g,f1,2g,f1,3g,f2,3g,f1,2,3gg.

7I.3. Opérations sur les ensembles

RemarqueI.3.On aP(AE) =fAEgetP(P(AE)) =fAE,fAEgg. La notationAEdécrit un ensemble qui ne

contient rien alors quefAEgdécrit un ensemble contenant un élément, l"ensemble vide. Un tiroir

contenant un sac vide (fAEg) n"est pas vide et contient bien un objet. I.3

Opérations sur les ensembles

On présente ici des opérations sur les ensembles qui permettent de construire de nouveaux ensembles. I.3.1

Union et Intersection

deAou deB. On le noteA[B. Proposition I.1 Propriétés de la réunionLa réunion admet certaines propriétés :

Idempotence :A[A=A

Commutativité :A[B=B[A

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

quotesdbs_dbs47.pdfusesText_47

[PDF] [PDF] MATHÉMATIQUES DISCRÈTES - Institut de Mathématiques de