Introduction aux mathématiques...

Introduction aux mathématiques discrètes

François SchwarzentruberUniversité de Rennes 1

1/104 François Schwarzentruber Université de Rennes 1 Introduction aux mathématiques discrètes 1

Pourquoi cette mise à niveau en mathématiques ?

Plus tard :I DéveloppeurI IngénieurI Chercheur

Pour avoir les idées claires :I communiquer ses idées dans un langage mathématique

propreI comprendre les autres,I raisonner (terminaison d’un programme, etc.)

Introduction

Ce cours est un voyage au pays des mathématiques discrètes.

BibliographieI André Arnold, Irène Guessarian. Mathématiques pour

l’informatique.I Alfred Aho, Jeffrey Ullman. Concepts fondamentaux de

l’informatique.

Démonstration

Ensembles

Deux techniques de démonstration

Relations

Logique

Cardinalité

DémonstrationImplicationEquivalence

Ensembles

Relations

Logique

Cardinalité

Syllogismes

On sait que :I Tous les hommes sont mortels;I Socrate est un homme.

On en déduit :I Socrate est mortel.

Démonstration

On sait que :1. Tous les hommes sont des primates;2. Tous les mamifères sont mortels et sympas;3. Tous les primates sont des mamifères;

TheoremSocrate est un homme alors Socrate est mortel. (on noteSocrate est un homme⇒ Socrate est mortel)

Proof.Supposons que Socrate est un homme. Par 1. Socrate est uneprimate. Par 3. Socrate est un mamifère. Par 2. Socrate estmortel et sympa, donc en particulier il est mortel.

DémonstrationImplicationEquivalence

Ensembles

Relations

Logique

Cardinalité

Equivalence

On dit que A⇔ B si:I A⇒ BI B ⇒ A.

10/104

Exercice

On sait que :1. Tous les hommes sont des primates;2. Tous les hommes sont intelligents;3. Tous les primates sont des mamifères;4. Tous les êtres intelligents sont conscients;5. Les mamifères conscients sont des hommes;

Montrer que Socrate est un homme ssi Socrate est unmamifère intelligent.

11/104

Démonstration

Ensembles

Relations

Logique

Cardinalité

12/104

Démonstration

EnsemblesBaseOpérationsProduits cartésiensPartiesStructure de données

Relations

Logique

Cardinalité12/104 François Schwarzentruber Université de Rennes 1 Introduction aux mathématiques discrètes 12

13/104

Ensembles - Motivation

Manipulation d’ensembles dans un algorithme :I Ensemble de chansonsI Jeu vidéo : ensemble des ennemisI Trajet en train : parcours d’un graphe et ensemble des

sommets visitésI etc.

14/104

Ensemble

Voici trois entiers, trois éléments...

15/104

Ensemble

On crée un ensemble :

Notation : {1,2,3}

16/104

Relation entre éléments et ensemble : appartenance

l’élément x appartient à l’ensemble E ou x est dans E

Notationx ∈ E

I 1 ∈ {1,2,3}1 appartient à l’ensemble {1,2,3}

I 4 6∈ {1,2,3}4 n’appartient pas à l’ensemble {1,2,3}

17/104

Des ensembles... on peut en créer pleins !

I {1,2,3,5}I {3,6}I {1}I {1, . . . ,100}I N (ensemble des entiers naturels)

18/104

L’ensemble vide

Notation∅

RemarquePour tout élément x, on a x 6∈ ∅!

19/104

Ensemble : l’ordre n’a pas d’importance

{1,2,3} {1,3,2} {2,1,3} . . .

20/104

Définition en intension

NotationEnsemble des éléments de A qui vérifient la propriété P :{x ∈ A | P(x)}{x ∈ N | x est pair}{x ∈ N | x est impair}

21/104

Egalité de deux ensembles

DefinitionDeux ensembles sont égaux s’ils contiennent les mêmeéléments.

NotationA = B

I {1,2,3} = {2,1,3}I {1,2} = {1,2}I {1,2} 6= {1,2,3}

22/104

Inclusion entre ensembles

DefinitionL’ensemble A est inclu dans l’ensemble B si tous les élémentsde A sont dans B.

NotationA ⊆ B

I {1,2} ⊆ {1,2,3}

23/104

Héritage et inclusion

Si la classe Chat hérite de la classe Animal, alors l’ensembledes instances de Chat est inclus dans l’ensemble desinstances de Animal.

24/104

Cardinalité

DefinitionSoit A un ensemble fini. Le cardinal de A est le nombred’éléments dans A.

Exemple

I card({1,4,456}) = 3;I card({1,4,456,5,6}) = 5.

25/104

Mise au point

I Pour tout ensemble A on a ∅ ⊆ AI A ⊆ B et B ⊆ A si, et seulement si A = B.

26/104

Démonstration

Relations

Logique

27/104

Union et intersection

I Union : "on prend tout"{1,2} ∪ {2,3} = {1,2,3}

I Intersection : "on prend ce qui est commun"{1,2} ∩ {2,3} = {2}

28/104

Complémentaire

DefinitionA privé de B est l’ensemble des éléments de A qui ne sont pasdans B.

NotationA \ B

29/104

Complémentaire - exemples

I {1,2,3} \ {1,2} = {3}I N \ {1,2,3} : ensemble des entiers naturels qui ne sont ni

1, ni 2 et ni 3.

30/104

Algèbre

I S ∪ T = T ∪ S;I S ∪ (T ∪ R) = (S ∪ T ) ∪ R;I S ∩ T = T ∩ S;I S ∩ (T ∩ R) = (S ∩ T ) ∩ R;I S ∩ (T ∪ R) = (S ∩ T ) ∪ (S ∩ R);I S ∪ (T ∩ R) = (S ∪ T ) ∩ (S ∪ R);I S \ (T ∪ R) = (S \ T ) \ R;I (S ∪ T ) \ R = (S \ R) ∪ (T \ R)

I S ∪ ∅ = S;I S ∪ S = S ∩ S = S

31/104

Exercices

ExerciceMontrer que

A ⊆ B ⇔ A ∩ B = A⇔ A ∪ B = B

ExerciceMontrer que

A = B ⇔ A ∪ B = A ∩ B

32/104

Démonstration

Relations

Logique

33/104

Couple

(3,5) est un couple composé :I d’une première coordonnée égale à 3 ;I d’une deuxième coordonnée égale à 5.

34/104

Produit cartésien

Le produit cartésien de A et B est l’ensemble des couples(x , y) où x ∈ A et y ∈ B.

NotationA× BN× N est l’ensemble des couples d’entiers.{1,2} × {3,4,5} = ...

35/104

Exercice

ExerciceRésoudre l’équation A× B = ∅.

ExerciceI A-t-on (A ∩ B)× (C ∩ D) =? (A× C) ∩ (B ∩ D)?I A-t-on (A ∪ B)× (C ∪ D) =? (A× C) ∪ (B ∩ D)?

(donner une démonstration ou un contre-exemple)

36/104

Démonstration

Relations

Logique

37/104

Parties d’un ensemble

Quels sont les sous-ensembles de ça ?

38/104

Parties d’un ensemble

Il y en a six :

∅ {1} {2} {3} {1,2} {2,3} {1,3} {1,2,3}

39/104

Ensemble des parties d’un ensemble

{∅, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3}}

40/104

Ensemble des parties d’un ensemble

DefinitionP(A) est l’ensemble des ensembles inclus dans A.

P({1,2,3}) = {∅, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3}}

A ⊆ B ssi A ∈ P(B)

41/104

A vous de jouer !

I P({1,2}) = ...

I P({1}) = ...

I P(∅) = ...

I P(P({1})) = ...

I P(P(P(∅))) = ...

I Expliquer x ∈ P(E), x ⊆ P(E) et x ⊆ E .

42/104

Démonstration

Relations

Logique

43/104

Interface

Ensemble EI Ajouter un élément : E := E ∪ {x}I Supprimer un élément : E := E \ {x}I Tester l’appartenance : x ∈ E

44/104

Implémentations

I TableauI Tableau triéI ListesI Listes triéesI Arbres binaires de recherche (équilibrés)I Vecteurs caractéristiquesI Tables de hâchage

45/104

Démonstration

Ensembles

Relations

Logique

Cardinalité

46/104

Démonstration

Ensembles

Deux techniques de démonstrationRaisonnement par l’absurdeRécurrence - induction

Relations

Logique

Cardinalité

47/104

Raisonnement par l’absurde

48/104

Démonstration

Ensembles

Deux techniques de démonstrationRaisonnement par l’absurdeRécurrence - induction

Relations

Logique

Cardinalité

49/104

Récurrence - induction. Motivation

En informatique, on manipule des structures inductives :I ListesI Arbres (rouges et noirs, arbres syntaxiques, etc.)I Programmes LISP, JAVA etc.I Squelette animé

On veut :I Définir un objet inductifI Démontrer des propriétés

50/104

Exemple : arbres binaires d’entiers

DefinitionSoit V un ensemble. On définit l’ensemble A des arbrescomme le plus petit ensemble tel que :

I V ⊆ A;I Si a1,a2 ∈ A et v ∈ V , alors noeud(v ,a1,a2) ∈ A.

51/104

Récurrence - Induction

I Cas de base : Je montre P(0)...I Cas récursif : Soit k ∈ N. Supposons P(k). Je montre

P(k + 1)...I Par récurrence, j’ai montré que pour tout k ∈ N, P(k) est

vraie.

I Cas de base : Je montre P(v) pour v ∈ V .I Cas inductif : Soit a1,a2 ∈ A pour lesquels je suppose

P(a1) et P(a2). Soit v ∈ V Je montre P(noeud(v ,a1,a2))...I Par induction, j’ai montré que pour tout a ∈ A, P(a) est

vraie.

52/104

A vous de jouer !

Soit f (x) = 13x3 + ax2 + bx .

I Trouver a et b tels que ∀x ∈ R, f (x + 1)− f (x) = x2. Dansla suite, cette propriété est vérifiée.

I Montrer que ∀n ∈ N, f (n) est un entier.I Montrer que pour tout n ∈ N,

Σnk=0k2 = f (n + 1) = n(n+1)(2n+1)

Soit a un arbre binaire. Donner une inégalité entre le nombrede noeud dans a et la hauteur de a.

53/104

Démonstration

Ensembles

Relations

Logique

Cardinalité

54/104

Démonstration

Ensembles

RelationsGénéralitésOrdresRelation d’équivalence

Logique

Cardinalité

55/104

Relations

DefinitionUne relation entre A et B est un sous-ensemble de A× B.

56/104

Relations

DefinitionUne relation sur A est un sous-ensemble de A× A.

I Relation d’amitié dans un réseau socialI Lien entre pages webI Graphe sémantique d’un motI Etat d’une machine s →x :=x+1 s′

I Etats mentaux en psychologie/philosophie (sémantique deKripke)

57/104

Graphe

Une relation sur A est un sous-ensemble de A× A... c’est ungraphe !

58/104

Démonstration

Ensembles

Logique

Cardinalité

59/104

Ordre (partiel)

DefinitionUn ordre sur E est une relation ≤ sur E :

I réflexive : pour tout x ∈ E , x ≤ x ;I antisymétrique : pour tout x , y ∈ E , x ≤ y et y ≤ x

implique x = y ;I transitive : pour tout x , y , z ∈ E , x ≤ y et y ≤ z implique

x ≤ z.

Exemple :I l’inclusion ;I ‘être un préfixe de’ (utilisée dans les algorithmes de

recherche dans une chaîne de caractères)I ‘divise’

60/104

Ordre total

DefinitionUn ordre total sur E est un ordre ≤ sur E tel que pour toutx , y ∈ E , x ≤ y ou y ≤ x .Exemple :

I ≤ sur les entiers, réels etc.I ordre lexicographique sur les mots

61/104

Application : tableur

62/104

Application : tableur

63/104

Application : compilation, liaison

64/104

Application : compilation, liaison

65/104

Majorant, borne supérieure, maximum

Soit (E ,≤) un ensemble ordonné et A ⊆ E .

I M est un majorant de A ssi ∀x ∈ A, x ≤ M.I M est le maximum de A ssi M est un majorant de A et

M ∈ A. (unicité du maximum s’il existe).

(définition analogue pour minorant et minimum)La borne supérieure de A est le minimum de l’ensemble desmajorants (s’il existe). (définition analogue pour borneinférieure)

66/104

Démonstration

Ensembles

Logique

Cardinalité

67/104

Motivation : relation d’équivalence

68/104

Motivation : relation d’équivalence

C’est un peu une "égalité faible".I la méthode equals en JAVAI ‘Avoir la même image par une fonction de hâchage’I les nombres rationnels

69/104

Relation d’équivalence

‘Avoir la même couleur’ sur cet ensemble de crayons

70/104

‘Avoir la même couleur’ sur cet ensemble de crayons

71/104

C’est un peu une "égalité faible".

DefinitionLa relation R sur E est une relation d’équivalence ssi

I R est réflexive : ∀x ∈ E , xRxI R est transitive : ∀x , y , z ∈ E , (xRy et yRz) implique xRzI R est symétrique : ∀x , y ∈ E , xRy implique yRx

72/104

Ensemble quotient

I Classe d’équivalence = ensemble d’éléments qui sontéquivalents.

I Un représentant d’une classe est un élément de cetteclasse.

I Les classes d’équivalence forment une partition.

73/104

Exemple : construction des nombres rationnels

Z× Z∗

74/104

Exemple : les nombres rationnels

Z× Z∗

(a,b)R(x , y) ssi ay = bx .

75/104

Q = Z× Z∗/R

(a,b)R(x , y) ssi ay = bx .

76/104

public class Rat ionne l{

public i n t getNum ( ) { . . . }public i n t getDenom ( ) { . . . }

@Overridepublic boolean equals ( Object ob j ) {

i f ( ob j instanceof Rat ionne l )return getNum ( ) ∗ ob j . getDenom ( )

== getDenom ( ) ∗ obj . getNum ( ) ;else

return fa lse ;}

77/104

Exemple : les nombres rationnels... à vous de jouer !

Montrer que la relation R définie sur Z× Z∗ par (a,b)R(x , y)ssi ay = bx est une relation d’équivalence.

78/104

Structure de données pour une relation d’équivalence

Interface :

I Tester si x est équivalent à y (find) ;I Fusionner deux classes d’équivalence (union).

Implémentation :I Tableaux avec des numéros de classes d’équivalence ;I Arbre binaire (structure Union-Find).

79/104

Démonstration

Ensembles

Relations

Logique

Cardinalité

80/104

Motivation de la logique

I ArchitectureI Résoudre une classe de problèmes (Sudoku, planification,

etc.)I Vérification de programmes / de circuitsI Vérification de démonstration

81/104

Démonstration

Ensembles

Relations

LogiqueLogique des propositionsThéorie des ensemblesLogique du premier ordreLiens avec les ensembles

82/104

Résolution de problèmes avec la logique despropositions

I Propositions... ‘la case (2,3) du sudoku contient un 8’ ;I ϕ1 ∧ ϕ2 : ET ;I ϕ1 ∨ ϕ2 : OU ;I ¬ϕ : NEGATION.

83/104

Résolution de problèmes avec la logique despropositions

→ Démonstration avec SAToulouse

84/104

Démonstration

Ensembles

Relations

85/104

Théorie des ensembles

Applications :I Vérification de démonstrations par ordinateurhttp://us.metamath.org/

De la lecture :I Cori, Lascar. Logique mathématique.I BD Logicomix.

86/104

Paradoxe de Russell

Gottlob Frege - Bertrand Russell. Correspondance. Juin1902-décembre 1904 - mars-juin 1912.

TheoremIl n’existe pas d’ensemble E qui contient tous les ensembles.

Proof.Supposons qu’il existe un ensemble E qui contient tous lesensembles.Soit A = {X ∈ E | X 6∈ X}On a (A ∈ A ssi A 6∈ A).

87/104

Démonstration

Ensembles

Relations

88/104

Logique du premier ordre

I ∀x .ϕ(x). Pour tout x , ϕ(x) est vraie.I ∃x .ϕ(x). Il existe un x tel que ϕ(x) est vraie.

89/104

Démonstration

Ensembles

Relations

90/104

Liens avec les ensembles

I Intersection, et, pour tout...{x ∈ A | P(x)} ∩ {x ∈ A | Q(x)} = {x ∈ A | P(x) ∧Q(x)}

⋂i∈I {x ∈ A | Pi(x)} = {x ∈ A | ∀i ∈ I,Pi(x)}

I Union, ou, il existe...{x ∈ A | P(x)} ∪ {x ∈ A | Q(x)} = {x ∈ A | P(x) ∨Q(x)}

⋃i∈I {x ∈ A | Pi(x)} = {x ∈ A | ∃i ∈ I,Pi(x)}

91/104

Démonstration

Ensembles

Relations

Logique

Cardinalité

92/104

Motivation

Informatique : art de représenter des objets infinis avec unestructure finie...

I Expression régulière ∗.txt dans grep ;I Fonction JAVA int → boolean.

QuestionEst-ce qu’on est capable de tout représenter ?

93/104

Motivation

94/104

Démonstration

Ensembles

Relations

Logique

CardinalitéL’hôtel de HilbertFonctionDénombrabilitéIndénombrabilité

95/104

L’hôtel de Hilbert

96/104

Démonstration

Ensembles

Relations

Logique

97/104

Fonction

Soit A et B deux ensembles.f : A→ B associe à tout élément de A un élément de B.

Examplef : N → N

x 7→ x + 1

98/104

Fonction surjective

Tous les éléments de B sont atteints.∀b ∈ B,∃a ∈ A | b = f (a)

‘A a plus d’éléments que B’.

99/104

Fonction injective

Une image n’a au plus qu’un antécédent.∀a1,a2 ∈ A, f (a1) = f (a2)⇒ a1 = a2

‘A a moins d’éléments que B’

100/104

Fonction bijective

Tout élément de B a un unique antécédent.∀b ∈ B, !∃a ∈ A | b = f (a)

‘A a ‘autant’ d’éléments que B’

101/104

Démonstration

Ensembles

Relations

Logique

102/104

Dénombrabilité

DefinitionUn ensemble E est dénombrable si il existe une bijectionf : N→ E .

Exemple :I N est dénombrable.I N× N est dénombrable.I L’ensemble des mots finis sur {a,b, . . . , z} est

dénombrable.I L’ensemble des fonctions Java int → boolean est

dénombrable.I L’ensemble des mots finis sur N est dénombrable.

103/104

Démonstration

Ensembles

Relations

Logique

104/104

A vous de jouer !

TheoremDémontrer que l’ensemble P(N) n’est pas dénombrable.

Introduction aux mathématiques...

Documents

Mathématiques - lama.univ-savoie.fr · Introduction La seconde est une classe de détermination. Le programme de mathématiques y a pour fonction : de conforter l’acquisition par

Mathématiques - ed.gov.nl.ca · PROGRAMME D’ÉTUDES - MATHÉMATIQUES ACADÉMIQUES 2231 2013 1 INTRODUCTION Objet du présent document INTRODUCTION Les programmes d’études de

Introduction aux mathématiques appliquées et pré-calcul e

Techniques Mathématiques en Assimilation de Données pour ... · Introduction laPrévisionNumériqueduTemps: Assimilation L’assimilationdedonnées L’assimilationdedonnées(AD)viseàestimerlesconditionsinitialesdu

GRAPHES EN INFORMATIQUE. INTRODUCTION Les objets mathématiques appelés graphes apparaissent dans de nombreux domaines comme les mathématiques, la biologie,

Mathématiques Surdité - numerisation.irem.univ-mrs.frnumerisation.irem.univ-mrs.fr/LY/ILY05002/ILY05002.pdf · Mathématiques et surdité - Introduction Groupe maths-surdité, IREM,

Mathématiques Surdité · 2015. 1. 26. · Mathématiques et surdité - Introduction 8 Groupe maths-surdité, IREM, SSEFIS - plus encore qu’avec les élèves entendants, il est

Cours de mathématiques Partie II – Analysealain.troesch.free.fr/2013/Fichiers/coursMPSI-analyse.pdf1 L’outil analytique Introduction Note Historique 1.0.1 Longtemps, les mathématiques

MT94 Introduction aux mathématiques appliquées Cahier d

introduction à La Didactique Des Mathématiques - ac …€¦ · Objet de la didactique des mathématiques • Etude du processus de transmission et d’acquisition des connaissances

Introduction Modélisation Utilisation dun ensemble de relations mathématiques pour refléter le plus adéquatement possible une situation réelle Compromis

Mathématiques...2 MATHÉMATIQUES 5e ANNÉE - PROGRAMME D’ÉTUDES 2017 INTRODUCTION Domaine affectif Pour réussir, les élèves doivent apprendre à se fixer des objectifs réalisables

Cryptographie : outils mathématiques...Introduction Cryptographie Des services informatiques sûrs Conﬁdentialité, Intégrité, Disponibilité Authentiﬁcation, Non Répudiation,

Dyscalculie et troubles logico-mathématiques · Dyscalculie et troubles logico-mathématiques : introduction Page 11 4. Défaut du processus d’automatisation Dans la suite de la

Des problèmes “difficiles”people.irisa.fr/Francois.Schwarzentruber/mit1_algo1_2011/12/trans... · La puissance du problème SAT Des réductions pour montrer la NP-compéltude

Licence Mathématiques (MATH) Parcours Mathématiques ...Licence Mathématiques (MATH) Parcours Mathématiques Appliquées (MAP) Parcours Mathématiques Fondamentales (MF) Admission

Chapitre 3 Ensembles totalement ordonnés : arbres binaires de …people.irisa.fr/Francois.Schwarzentruber/agreg_algo_2015/... · 2016-01-26 · Chapitre 3 Ensembles totalement ordonnés

Physique statistique : modèles mathématiques, …cermics.enpc.fr/~stoltz/Seminars/stoltz_Strasbourg.pdf · Plan de l’exposé Introduction à la physique statistique Description

Biostatistiques et statistiques appliquées aux sciences ... · Introduction Statistiques: domaine cousin mais distinct des Mathématiques Statistiques appliquées Statistiques théoriques/mathématiques

NP-complétude - IRISApeople.irisa.fr/Francois.Schwarzentruber/agreg... · NP-complétude François Schwarzentruber ENS Rennes Table des matières 1 Problèmes de décision dits "de