Mathématiques discrètes, 1ère année
Mathématiques discrètes, 1ère année Laurent Regnier 25 octobre 2010 2 Chapitre 1 Étudier les mathématiques soit relire le pol,y soit trouver un livre
Introduction aux mathématiques discrètes
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 1 Introduction aux mathématiques discrètes 3
MATHEMATIQUES DISCRETES
• Mathématiques discrètes : étude des structures mathématiques fondamentalement discrètes, dans le sens où la notion de continuité n'est pas exigée ou supportée • Mathématiques discrètes : populaires du fait de leurs applications dans l’informatique – notations et concepts des mathématiques discrètes utilisés pour
MAT210 Logique et math matiques discr tes : Cours 1
Lasection 1 6 du livre de référence DiscreteMathematicsand its applications,Seventh Editionde K H Rosen présente les règles d’inférence La tableau 1 de la page 72 résume les principales Ces formesde raisonnementsont valides: elles garantissent la véracité de la conclusion quandtoutesles prémisses sont vraies
NOTES DE COURS MAT1500 MATHÉMATIQUES DISCRÈTES AUTOMNE 2018
NOTES DE COURS MAT1500 MATHÉMATIQUES DISCRÈTES AUTOMNE 2018 ABRAHAM BROER Références [R] Kenneth H Rosen, Mathématiques discrètes, Édition révisée Chenelière McGraw-Hill, 2002
Mathématiques discrètes pour linformatique
Mathématiques discrètes 10 Théorie des Graphes Exemples Passeur, Loup, Chèvre et chou Un Passeur doit faire traverser une rivière à un Loup, une Chèvre et un chou Il ne peut prendre qu'un seul des trois à chaque traversée Il ne peut pas laisser seuls sur une rive, sans sa surveillance: – le Loup et la Chèvre,
Version PDF - Cours
MAT210 : Logique et mathématiques discrètes (4 crédits) 3UpDODEOHV 3RXUWRXVOHVpWXGLDQWV 0$7 8QLWpVG DJUpPHQW 7RWDOG XQLWpVG DJUpPHQW 4XDOLWpVGHO LQJpQLHXU Qualité visée dans ce cours Qualité visée dans un autre cours Compétence enseignée Compétence évaluée Compétence enseignée et évaluée 'HVFULSWLIGXFRXUV
Mathématiques pour l’informatique
Mathématiques pour l’informatique Christophe GUYEUX et Jean-François COUCHOT guyeux[arobase]iut-bm univ-fcomte[point] couchot[arobase]iut-bm univ-fcomte[point] 3 novembre 2010
MODÉLISATION MATHÉMATIQUE POUR L ÉCOLOGIE (MAP 556, ANNÉE
Les premiers modèles mathématiques en écologie remontent aux années 1920, avec Lotka et surtout Volterra Pour diverses raisons, ce sont d’abord des modèles basés sur équations différentielles, c -à-d des modèles purement dé-terministes, qui ont été proposés Une modélisation stochastique semble pour-
[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 en économie
[PDF] mathématiques en économie-gestion pdf
[PDF] mathematiques en factorisation ^^
[PDF] Mathématiques en option ES (terminale) Matrices
[PDF] MATHEMATIQUES enquete
[PDF] mathématiques enquete policiere
[PDF] Mathématiques équation, besoin d'aide
[PDF] Mathématiques Equations 3
1/104Introduction aux mathématiques discrètes
François Schwarzentruber
Université de Rennes 1
1/104François Schwarzentruber Université de Rennes 1Introduction aux mathématiques discrètes 1
2/104Pourquoi cette mise à niveau en mathématiques ?
Plus tard :
IDéveloppeur
IIngénieur
IChercheur
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/104Franç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/104Franç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 :
ITous les hommes sont mortels;
ISocrate est un homme.
On en déduit :
ISocrate est mortel.
6/104Franç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 noteSocrate 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/104Franç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
BaseOpé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 :
IEnsemble de chansons
IJeu 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 x2EI12 f1;2;3g
1 appartient à l"ensemblef1;2;3g
I462 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 IN(ensemble des entiers naturels)
17/104
François Schwarzentruber Université de Rennes 1Introduction aux mathématiques discrètes 17
18/104L"ensemble vide
Notation
;RemarquePour 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 impairg20/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;3g21/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;3g22/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; Icard(f1;4;456;5;6g) =5.24/104François Schwarzentruber Université de Rennes 1Introduction aux mathématiques discrètes 24
25/104Mise au point
IPour tout ensembleAon a; A
IABetBAsi, et seulement siA=B.
25/104
François Schwarzentruber Université de Rennes 1Introduction aux mathématiques discrètes 25
26/104Plan
Démonstration
Ensembles
BaseOpé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
IUnion : "on prend tout"f1;2g [ f2;3g=f1;2;3g
IIntersection : "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.NotationAnB28/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 ni1, ni 2 et ni 3.
29/104
François Schwarzentruber Université de Rennes 1Introduction aux mathématiques discrètes 29
30/104Algèbre
IS[T=T[S;
IS[(T[R) = (S[T)[R;
IS\T=T\S;
IS\(T\R) = (S\T)\R;
IS\(T[R) = (S\T)[(S\R);
IS[(T\R) = (S[T)\(S[R);
ISn(T[R) = (SnT)nR;
I (S[T)nR= (SnR)[(TnR) IS[ ;=S;
IS[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
.ExerciceMontrer 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
BaseOpé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.NotationABNNest 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