[PDF] Introduction aux mathématiques discrètes

View - Download Introduction aux mathématiques discrètes

Previous PDF

Next PDF

1/104Introduction aux mathématiques discrètes

François Schwarzentruber

Université de Rennes 1

1/104

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

2/104Pourquoi cette mise à niveau en mathématiques ?

Plus tard :

I

Développeur

I

Ingénieur

I

Chercheur

Pour avoir les idées claires :

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 1Introduction aux mathématiques discrètes 2

3/104Introduction

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

Bibliographie

I André Arnold, Irène Guessarian. Mathématiques pour l"informatique. I Alfred Aho, Jeffrey Ullman. Concepts fondamentaux de l"informatique. 3/104

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

4/104Plan

Démonstration

Ensembles

Deux techniques de démonstration

Relations

Logique

Cardinalité

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

5/104Plan

Démonstration

Implication

Equivalence

Ensembles

Deux techniques de démonstration

Relations

Logique

Cardinalité

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

6/104Syllogismes

On sait que :

I

Tous les hommes sont mortels;

I

Socrate est un homme.

On en déduit :

I

Socrate est mortel.

6/104

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

7/104Démonstration

On sait que :

1.

T ousles hommes sont des pr imates;

2.

T ousles mamifères sont mor telset sympas;

3.

T ousles pr imatessont des mamifères; Theorem

Socrate est un homme alors Socrate est mortel. (on note

Socrate est un homme)Socrate est mortel)Proof.

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

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

8/104Plan

Démonstration

Implication

Equivalence

Ensembles

Deux techniques de démonstration

Relations

Logique

Cardinalité

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

9/104Equivalence

On dit queA,Bsi:

I A)B I B)A. 9/104

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

10/104Exercice

On sait que :

1.

T ousles hommes sont des pr imates;

2.

T ousles hommes sont intelligents;

3.

T ousles pr imatessont des mamifères;

4.

T ousles êtres intelligents sont conscients;

5.

Les mamifères conscients sont des hommes;

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

10/104

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

11/104Plan

Démonstration

Ensembles

Deux techniques de démonstration

Relations

Logique

Cardinalité

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

12/104Plan

Démonstration

Ensembles

Base

Opérations

Produits cartésiens

Parties

Structure de données

Deux techniques de démonstration

Relations

Logique

Cardinalité

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

13/104Ensembles - Motivation

Manipulation d"ensembles dans un algorithme :

I

Ensemble de chansons

I

Jeu vidéo : ensemble des ennemis

I Trajet en train : parcours d"un graphe et ensemble des sommets visités I etc.

13/104

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

14/104Ensemble

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

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

15/104Ensemble

On crée un ensemble :Notation :f1;2;3g

15/104

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

16/104Relation entre éléments et ensemble : appartenance

l"élémentxappartient à l"ensembleE ou xest dansENotation x2EI

12 f1;2;3g

1 appartient à l"ensemblef1;2;3g

I

462 f1;2;3g

4 n"appartient pas à l"ensemblef1;2;3g

16/104

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

17/104Des ensembles... on peut en créer pleins !

I f1;2;3;5g I f3;6g I f1g I f1;:::;100g I

N(ensemble des entiers naturels)

17/104

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

18/104L"ensemble vide

Notation

;Remarque

Pour tout élément x, on a x62 ;!18/104François Schwarzentruber Université de Rennes 1Introduction aux mathématiques discrètes 18

19/104Ensemble : l"ordre n"a pas d"importance

f1;2;3g f1;3;2g f2;1;3g:::

19/104

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

20/104Définition en intension

Notation

Ensemble des éléments de A qui vérifient la propriété P : fx2AjP(x)gfx2Njxest pairg fx2Njxest impairg

20/104

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

21/104Egalité de deux ensembles

Definition

Deux ensembles sont égaux s"ils contiennent les même

éléments.Notation

A=BI f1;2;3g=f2;1;3g I f1;2g=f1;2g I f1;2g 6=f1;2;3g

21/104

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

22/104Inclusion entre ensembles

Definition

L"ensembleAest inclu dans l"ensembleBsi tous les éléments deAsont dansB.Notation ABI f1;2g f1;2;3g

22/104

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

23/104Héritage et inclusion

Si la classe Chat hérite de la classe Animal, alors l"ensemble des instances de Chat est inclus dans l"ensemble des instances de Animal.

23/104

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

24/104Cardinalité

Definition

SoitAun ensemble fini. Le cardinal deAest le nombre d"éléments dansA.Exemple I card(f1;4;456g) =3; I

card(f1;4;456;5;6g) =5.24/104François Schwarzentruber Université de Rennes 1Introduction aux mathématiques discrètes 24

25/104Mise au point

I

Pour tout ensembleAon a; A

I

ABetBAsi, et seulement siA=B.

25/104

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

26/104Plan

Démonstration

Ensembles

Base

Opérations

Produits cartésiens

Parties

Structure de données

Deux techniques de démonstration

Relations

Logique

Cardinalité

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

27/104Union et intersection

I

Union : "on prend tout"f1;2g [ f2;3g=f1;2;3g

I

Intersection : "on prend ce qui est commun"

f1;2g \ f2;3g=f2g27/104François Schwarzentruber Université de Rennes 1Introduction aux mathématiques discrètes 27

28/104Complémentaire

Definition

Aprivé deBest l"ensemble des éléments deAqui ne sont pas dansB.Notation

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

29/104Complémentaire - exemples

I f1;2;3g n f1;2g=f3g I Nn f1;2;3g: ensemble des entiers naturels qui ne sont ni

1, ni 2 et ni 3.

29/104

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

30/104Algè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

Sn(T[R) = (SnT)nR;

I (S[T)nR= (SnR)[(TnR) I

S[ ;=S;

I

S[S=S\S=S

30/104

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

31/104Exercices

Exercice

Montrer que

AB,A\B=A,A[B=B

.Exercice

Montrer que

A=B,A[B=A\B

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

32/104Plan

Démonstration

Ensembles

Base

Opérations

Produits cartésiens

Parties

Structure de données

Deux techniques de démonstration

Relations

Logique

Cardinalité

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

33/104Couple

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

33/104

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

34/104Produit cartésien

Le produit cartésien deAetBest l"ensemble des couples (x;y)oùx2Aety2B.Notation

ABNNest l"ensemble des couples d"entiers.

f1;2g f3;4;5g=:::

34/104

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

35/104Exercice

Exercice

Résoudre l"équation AB=;.Exercice

I

A-t-on(A\B)(C\D) =?(AC)\(B\D)?

I

A-t-on(A[B)(C[D) =?(AC)[(B\D)?

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

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

36/104Plan

Démonstration

Ensembles

Base

Opérations

Produits cartésiens

quotesdbs_dbs47.pdfusesText_47

[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