MATHÉMATIQUES POUR
INFORMATICIENS
MAT-1919
Aujourd'hui :
On révise!
1
-Voir solution devoir 2
-Voir la page Conseils pour l'examen final
-Voir questionnaires sur le site
3
Rappel
• Démonstration par cas de
5
Une relation
6
Technique de démonstration appliquée sur les fonctions
La fonction suivante est-elle:
A. Injective?
B. Surjective?
7
10
co r rection
i est d e la
ce qu
Pour
1 1 1
4 pour clarté représentation
5 pour bijection
1
2
11
1.5.15
1.5.23
12
1.5.1
6
1.5.1
7
Note : 7, 8 et 9 découlent du fait que l'ordre est total
13
1.5.1
8
1.5.1
9
1.5.2
0
14
Questions d’examen antérieur (ouf):
[Link]
15
||
||
||
||
16
Exercice
Classez ces ensembles en ordre croissant, selon leur cardinalité.
Certains ont la même cardinalité !
Mots binaires finis, Mots binaires infinis,
Mots finis de l’alphabet, nombres réels dont tous les chiffres sont pairs,
18
Les Ensembles infinis non dénombrables
[Link]
Le Chat de Philippe geluck
1.5.21
[Link]
19
Les Ensembles infinis non dénombrables
[Link]
1.5.21
Au final, comment se comparent nos ensembles préférés?
Hypothèse du continu de
Cantor: il n'y a pas de
cardinalité entre les 2!
En fait =
Mais ce n'est pas si simple à démontrer. On obtient ≥ avec l'idée suivante
(car les terminaisons en infinité de 1 donnent que 2 fonctions sont envoyées sur le même réel)
20
Exemples:
2024-04-23
Les classes d’équivalence - une partition
• Une classe d'équivalence est un ensemble maximal
d'éléments tous équivalents.
o la relation « même modulo 3 » : classes [0], [1] et [2]
• Une classe peut s'écrire à l'aide de n'importe quel de ses
élément
o la relation « même modulo 3 » : classes [0] = [9] = [15]
• Une partition d’un ensemble est formée de sous-ensembles
disjoints dont l'union donne l'ensemble lui-même
o les nbs pairs, les nbs impairs forment une partition de ℕ
• Une partition définit naturellement une relation
d’équivalence
• Une relation d'équivalence définit naturellement une
partition
22
Exemples:
2024-04-23
2024-04-23
Des diagrammes de Hasse dans la vraie vie (d'étudiants chercheurs)
Projet de recherche avec Alexandre Mathieu, de 1 er cycle
25
26
• Prendre la fermeture transitive et réflexive nous
assure qu'une relation sera un ordre partiel vrai ou
faux?
27
2024-04-23
La père des récurrences
Kurt Godel
[Link]
photo_gallery.htm
2024-04-23
2024-04-23
Blaise Pascal
(1623-1662)
2024-04-23
[Link]
Montrez que
truc: ne pas
calculer ici!
< Première égalité: def de c0 ; deuxième égalité : arithmétique > autre façon
d'écrire:
02 = 0, ce qui est
bien égal à c0
(sans autre
justification)
Attention!
Si vous écrivez
c0 = 02 = 0
comment
justifier?
2024-04-23
Les différents principes d'induction mathématique :
(Le seul qu'on démontre!)
2024-04-23
+d Suite géométrique
Suite arithmétique
2 2 2 2
4 2+4 4 2+4
6 2+4+6 8 2+4+8
8 2+4+6+8 16 2+4+8+16
. . . .
es
v o us v.e rrez les term s . . .
Note :
m m e” , Σ.. . Toutes ce
”, “so. concept! .
“sommation nt au même . .
réfère
appelations
37
Les suites arithmétiques et géométriques
2
4
6
8
.
.
.
2
4
8
16
.
.
.
38
2
2+4
2+4+6
2+4+6+8
.
.
.
2
2+4
2+4+8
2+4+8+16
.
.
. 39
Suite géométrique
40
[Link]
2013_04_01_archive.html0
Exercice
Les paires de graphe suivants sont-ils isomorphes? Si oui, démontrez-le
formellement à l’aide d’une fonction bijective (isomorphisme) approprié. Sinon,
Donnez une raison pourquoi cela est impossible.
Questions (V/F, sans justification)
-Deux graphes peuvent être isomorphe même
s’ils possèdent des nombres différents de régions.
-Deux graphes peuvent être isomorphe même
s’ils possèdent des nombres différents de cycles distincts.
(Note: on dira que deux cycles sont distincts s’il existe un sommet présent
dans un cycle mais non dans l’autre)
Planarité et théorème des 4 couleurs
[Link]