MATHÉMATIQUES DISCRÈTES

7I 3 Opérations sur les ensembles Remarque I 3 On a P(˘) = f˘get P(P(˘)) = f˘,f˘gg La notation ˘ décrit un ensemble qui ne contient rien alors que f˘gdécrit un ensemble contenant un élément, l’ensemble vide

Mathématiques discrètes, 1ère année

Le langage mathématique En mathématiques, après un raisonnement ou un calcul on se pose (presque) toujours deux questions : 1 a-t-on bien utilisé toutes les hypothèses du problème? 2 ne pourrait-on pas améliorer le raisonnement ou le calcul en supprimant l'une des hypothèses?

Mathématiques Discrètes - fil

1 k +1 2k k 6n 2k n 2k Q 3 5 [1 point] CombiendeprogrammesBrainfuck delongueurn ,syntaxiquementcorrects,peut-on écrire? On donnera le résultat sous la forme d’une somme qu’on ne cherchera pas à calculer Éléments de

Introduction aux mathématiques discrètes

I communiquer ses idées dans un langage mathématique propre I comprendre les autres, I raisonner (terminaison d’un programme, etc ) 2/104 François Schwarzentruber Université de Rennes 1 Introduction aux mathématiques discrètes 2

NOTES DE COURS POUR LE COURS MATHÉMATIQUES DISCRÈTES MAT1500

NOTES DE COURS POUR LE COURS MATHÉMATIQUES DISCRÈTES MAT1500 ABRAHAM BROER Références [R] Kenneth H Rosen, Mathématiques discrètes, Édition révisée Chenelière McGraw-Hill, 2002

MAT210 Logique et math matiques discr tes : Cours 1

2 1 RAISONNEMENTSVALIDES 3 Solution: Ce raisonnement est valide Il s’agit d’unmodus tollens p →q ¬q e ∴ ¬p où p désigne «il pleut» et q désigne «les trottoirssont mouillés»

Université Pierre et Marie Curie Master IAD Module PDML

On appelle prgroammation mathématique discrète l'étude des programmes mathé-matiques discrets Il s'agit d'un domaine plutôt récent qui n'est pas constitué d'une seule approche théorique Il existe beaucoup de cas particuliers, de cadres théoriques ou expérimentaux qui ont apporté des réussites parfois surprenantes : c'est le cadre

Méta-mathématique

Mathématique discrète ISommes et produits nis Leçon - 1 -Sommes et produits nis ( pdf correction)(tex) IIThéorie des graphes Leçon - 1 -Graphes approche

Cours 1: lois discrétes classiques en probabilités

L’espérance mathématique E[X] d’une variable aléatoire X joue le rôle dévolu à la moyenne en statistiques : elle correspond à la valeur moyenne espérée par un observateur lors d’une réalisation de la variable aléatoire X On a : E[X] = XN i=1 pi xi = XN i=1 xi P[X = xi] lorsque X peut prendre N valeurs différentes x1;:::;xN avec

Livret de formules pour le cours de mathématiques NM

Tables des matières Acquis préliminaires 2 Thèmes 3 Thème 1 − Algèbre 3 Thème 2 − Fonctions et équations 4

[PDF] environnement fle a2

[PDF] fiche pedagogique environnement fle

[PDF] cornériser définition

[PDF] la démocratie dans le monde d'aujourd'hui pdf

[PDF] arguments pour la démocratie

[PDF] vocabulaire environnement fle

[PDF] signifiant signifié référent

[PDF] signifiant signifié semiologie

[PDF] signe plastique sémiologie

[PDF] signification emoji francais

[PDF] insérer note de bas de page openoffice

[PDF] openoffice note de bas de page sur deux pages

[PDF] numérotation bas de page open office

[PDF] dans un traitement de texte comment doit-on faire pour numéroter automatiquement les pages ?

[PDF] note de bas de page exemple

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.

quotesdbs_dbs10.pdfusesText_16

[PDF] MATHÉMATIQUES DISCRÈTES