Résumer

Rappel de notions mathématiques
Dans ce chapitre, nous rappelons certaines notions élémentaires de mathéma-
tiques discrètes et de logique utiles à la conception et l’analyse d’algorithmes.
0.1 Notation et objets élémentaires
0.1.1 Ensembles
Rappelons qu’un ensemble est une collection (finie ou infinie) d’éléments non
ordonnés et sans répétitions. Par exemple, {2, 3, 7, 11, 13} est l’ensemble des
cinq premiers nombres premiers, ∅ est l’ensemble vide, {aa, ab, ba, bb} est l’en-
semble des mots de taille deux formés des lettres a et b, et {0, 2, 4, 6, 8, . . .} est
l’ensemble des nombres pairs non négatifs.
Nous utiliserons souvent des définitions en compréhension. Par exemple,
l’ensemble des nombres pairs non négatifs peut s’écrire ainsi:
{2n : n ∈ N} .
La taille d’un ensemble fini X est dénoté par |X|, par ex. |{a, b, c}| = 3 et
|∅| = 0. Nous écrivons x ∈ X et x ̸∈ X afin de dénoter, respectivement, que x
appartient et n’appartient pas à X. Nous écrivons X ⊆ Y afin de dénoter que
tous les éléments de X appartiennent à Y (inclusion), et nous écrivons X ⊂ Y
lorsque X ⊆ Y et X ̸= Y (inclusion stricte). Lorsque X ⊆ E, où E est considéré
comme un univers, nous écrivons X afin de dénoter le complément
X := {e ∈ E : e ̸∈ X} .
Rappelons que ∪, ∩, \ et × dénotent respectivement l’union, intersection, la
différence et le produit cartésien, définis comme suit:
X ∪ Y := {x : x ∈ X ∨ x ∈ Y }, X \ Y := {x : x ∈ X ∧ x ̸∈ Y },
X ∩ Y := {x : x ∈ X ∧ x ∈ Y }, X × Y := {(x, y) : x ∈ X ∧ y ∈ Y }.

• Télécharger
• Voir Plus

Resultats du Test [Algorithmes et structures de données ]