Formation CNAM - DUT Informatique (DUT1200A)

Crédits ECTS : 4.

• Ensembles, éléments, parties d'un ensemble, fonctions, opérations sur les ensembles.
[Contenu]   [Explications]


- Ensembles ; symbole d'appartenance ; de non appartenance ; inclusion ; désinclusion ; ensemble vide.
• Ensembles classiques : \( \mathbb{B}, \mathbb{N}, \mathbb{Z}, \mathbb{R}\)   Symboles : , \( \not\in \) , \( \in \) , \( \subseteq \) , \( \not \subseteq \) , \( \supset \) , \( \emptyset \)
- Définitions en compréhension, en extension.
• Comp = {x³, x entiers de 3 à 5} ; Exten = {27, 64, 125}
- Notion d'application ; de fonctions ; domaine de définition ; image ; mots binaires.
- Injection ; surjection ; bijection; application réciproque ; fonction composée.
- Parité ; intervalle ; fonctions de définition d'accolades



• Cardinal d'un ensemble, ensemble fini, ensemble dénombrable.
[Contenu]   [Explications]


- Cardinal d'un ensemble
• C'est le nombre d'éléments que comporte un ensemble.
- Produit d'ensembles ; diagramme cartésien ; notion de n-uplet ; axiome du choix ; union ; intersection ; ensembles disjoints.
• Le résultat d'un produit cartésien (ou ensemble-produit) est un ensemble noté AxB.
Il forme tous les couples (a, b) où a est un élément de A, et b un élément de B.
- Un n-uplet est une collection ordonnée de n objets, appelés « composantes » ou « éléments » ou « termes » de ce n-uplet.
- Théorèmes de la bijection, injection et surjection.
• A ensemble de définition et B ensemble image donnés, bijection ssi |A| = |B|, injection ssi |A| <= |B|, surjection ssi |A| => |B|.
- Principe des tiroirs de Dirichlet.
• si |A| >= |B| alors il n'existe pas d'injection de A dans B.
- Ensemble dénombrable ; équipotence d'un ensemble.
• Ensemble dénombrable : ici un ensemble E est dit dénombrable quand il existe une bijection entre l'ensemble N des entiers naturels et E.
- Equipotence : une relation selon laquelle deux ensembles sont équivalents lorsqu'il existe une bijection entre eux.
- Notions d'infini.
• Propriété : N est infini parce qu'il est en bijection avec l'ensemble des carrés possibles.
En effet un ensemble E est infini quand il existe une bijection entre E et l'un de ses sous-ensembles stricts.



• Arrangements, combinaisons, permutations, formule du binôme.
[Contenu]   [Explications]


- Principe des choix successifs ; p1 premier choix ; p1p2p3p4p[n...] façons différentes d'enchaîner n choix.
- Soient E1, E2, E3 des ensembles finis, |E1 * E2 * E3| = |E1| * |E2| * |E3| ; le nombre d'éléments du produit est le produit du nombre d'éléments.
- Notions d'arrangements : A[n, p] = n(n - 1)(n - 2) ... (n - p + 1).
- B^A : désigne le nombre d'applications de A vers B ; B^A = |B|^|A|.
- Théorème : le nombre d'arrangements de p objets pris dans un ensemble à n éléments est : A[n, p].
- Une permutation de E est une bijection de f : E -> E. C'est en effet A[n, n]. C'est la factorielle, et elle est notée n!.
- Aussi n! sert aussi à numéroter n objets de 1 à n. De plus n! sert aussi à ranger n objets dans n boites avec 1 seul objet par boite.
- On a : n! = n(n-1)!, avec n => 2.
- A[n, p] = (n!) / (n-p)!, avec 1 <= p <= n.
- Combinaison : un sous-ensemble de E qui possède p éléments s'appelle une combinaison de p éléments de E.
Dans un arangement les éléments sont numéroter de 1 à p. Alors que ici (pour une combinaison) ils sont notés en vrac.
- On note C[n, p] = le nombre de combinaisons à p élements dans un ensemble à n éléments.
- On passe d'une combinaison à un arrangement en numérotant ses éléments.
- Théorème : C[n, p] = C[n-p, p].
- Triangle de Pascal ; formule du binôme.



• Relation d'équivalence.
[Contenu]   [Explications]


- On veut traduire en termes mathématiques l'idée concrète : "être en relation".
- Relation R qui porte sur deux ensembles A et B. Les éléments de AxB sont les couples (a,b) , avec a dans A et b dans B. Un sous-ensemble (quelconque) de AxB s'appelle une relation entre A et B.
- Diagramme sagital ; diagramme cartésien ; relation binaire ; une relation ternaire est un sous-ensemble (quelconque) de AxBxC.
- Relation binaire entre A et B avec A = B.
- R est réflexive si aRa, quelque soit a dans A.
- R est symétrique si bRa à chaque fois que aRb. Sur un diagramme cartésien, ici il y a une symétrie par rapport à la diagonale.
- R est transitive si aRc à chaque fois que aRb et bRc.
- Relation d'équivalence : réflexive, symétrique et transitive.
- Classe d'équivalence : on se donne un élément a. L'ensemble des b tels que aRb s'appelle la classe d'équivalence de a. On la note Cl(a) ou [a]. Une classe d'équivalence n'est jamais vide et la réunion de toutes les classes est A. Ces classes découpent une partition de cet ensemble A.
- Si b est dans Cl(a) alors Cl(b) = Cl(a).



• Relation d'ordre, diagramme de Hasse, éléments maximaux, minimaux, plus grand et plus petit élément.
[Contenu]   [Explications]


- R est antisymétrique si on ne peut pas avoir en même temps aRb et bRa avec a != b.
- Relation d'ordre : réflexive, antisymétrique et transitive. On dit que l'ensemble A est ordonné par la relation A.
- Le dessin du diagramme de Hasse s'obtient à partir du diagramme sagital en enlevant les flèches. Boucles : réflexivité ; flèche : transitivté
- Le digramme de Hasse peut apparaître comme un cube avec des flèches comme arrêtes.
- Un ensemble A est totalement ordonné, alors R est une relation d'ordre total quand quelques soit x et y : xRy et xRy. On reconnaît ce type d'ensemble à son diagramme de Hasse qui est une chaîne.
- Diagramme de Hasse :
 Avec un ensemble A ordonné, les éléments extrêmes sont : l'élement M est maximal quand il n'existe pas de majorant M autre que lui-même.
 Même principe pour M est minimal.
 M est le plus grand élément de A s'il majore tous les éléments de A, nommé sup(A).
 Même principe pour M est le plus petit élément, nommé inf(A).



• Treillis, algèbre de Boole, théorème de Stone.
[Contenu]   [Explications]


- Treillis : on note, Maj(x) = ensemble des majorants de x ; Min(x) = ensemble des minorants de x. Même principe pour Maj(x,y) et Min(x,y).
 Si z est le plus petit élément de Maj(x,y), alors Maj(x,y) est l'ensemble des majorants de z. Autrement dit : Maj(x,y) = Maj(z).
 Cet élément z n'existe pas toujours mais s'il existe on écrit z = sup(x,y) ou z = x \/ y et on dit que z est la borne supérieure de x et y.
 Même principe z le plus grand élément : z = inf(x,y) ou z = x /\ y. Ici z est la borne inférieure de x et y.
- L'ensemble ordonné A est un treillis quand z = x \/ y et z = x /\ y existent quelques soient x et y.
 Un ensemble totalement ordonné A est un treillis.
- Ordre : x <= (x \/ y) ; y <= (x \/ y) ; (x /\ y) <= x ; (x /\ y) <= y.
- Un treillis possède toujours un plus grand élément et un plus petit élément.
- Notion de treillis distributif ; notion de complémentation.
- Une algèbre de Boole est un treillis distributif mais aussi complémenté.
- L'opération \/ s'appelle la somme booléenne.
- Sur B^N, l'ensemble des mots binaires de longueur n a une relation d'ordre notée <= :
 [a1a2an] <= [b1b2bn] ssi a1 <= b1, a2 <= b2, etc... Avec an (ou bn) égal à 0 ou 1.
- sup(B^N) = [111...1] et inf(B^N) = [000...0].
- Notion de complément d'un mot binaire ; loi de De Morgan.
- Lien entre les opérations booléennes et les relations d'ordre : x /\ y = x ssi x <= y ; x ∨ y = y ssi x <= y.
- Principe de dualité : x = (y /\ z) ∨ (^a /\ e) ssi ^x = (^y ∨ ^z) /\ (a ∨ ^e).
- Théorème de Stone : toutes les algèbres de Boole finies se ramènent aux ensemble B^N.
- Si A est une algèbre de Boole finie, son nombre d'éléments est de la forme 2^n pour un certain n et son diagramme de Hasse est le n-cube.
- Un "atôme" : tout élément de l'algèbre qui est un successeur immédiat d'un élément autre "s".
Tout élément s'écrit de façon unique comme une somme booléenne d'atômes. C'est la somme booléenne des atômes qui le minorent. Cette propriété permet d'associer un mot binaire de longueur n à chaque élément.



• Parties d'un ensemble.
[Contenu]   [Explications]


- Soit P(E), l'ensemble des parties d'un ensemble ; l'inclusion est une relation d'ordre sur P(E).
- Soit A un ensemble appartenant à E. On appelle fonction caractéristique de A l'application de E dans B définie par C[A](x) :
C[A](x) = 1 quand x appartient à A.
C[A](x) = 0 quand x n'appartient pas à A.
C[∅](x) vaut toujours 0 et C[A](x) vaut toujours 1.
- Relation d'ordre pour B^E : X <= 'X, C[A] <= C'[A] quand C[A](x) <= C[A]'(x) quelque soit x.
- Relation d'ordre pour B^n : a1...an <= b1...bn quelque soit i appartenant à [1, n].
- Relation d'ordre pour P(E) : l'inclusion ⊂.
- Relation supérieure, pour P(E) il s'agit de la réunion ∪.
- Pour B^E : X'' = X(x) ∨ X'(x) quelque soit x. Avec X = C[E](x).
- Pour B^n : c1...cn = (a1...an) ∨ (b1...bn) avec ci = ai \/ bi quelque soit i.
- Relation inférieure, pour P(E) il s'agit de l'interserction ∩.
- Pour B^E : X'' = X(x) ∧ X'(x) quelque soit x. Avec X = C[E](x)
- Pour B^n : c1...cn = (a1...an) ∧ (b1...bn) avec ci = ai ∧ bi quelque soit i.
- Complémentation : pour P(E) il s'agit de simplement du complément.
- Pour B^E : ¬ X avec ¬ X(x) = ¬ (X(x)) quelque soit x.
- Pour B^n : c1...cn = ¬ (a1...an) avec ci = ¬ (ai) quelque soit i.
- Liens entre deux bits x et y avec les opérations arithmétiques :
¬ x = 1 - x ; x ∧ y = xy ; x ∨ y = x + y - xy.
- On a aussi : C ¬ [A] = 1 - C[A] ; C[A ∩ B] = C[A] * C[B] ; C[A ∪ B] = C[A] + C[B] - C[A] * C[B].
- On pose X = C[E], on a le théorème suivant : X(e1) + X(e2) + ... + X(en) = |A|.
- On a donc pour simplifier : ∑(i = 1, n) [X(ei)] = |A|. Avec n le nombre d'élement dans le sous-ensemble A dans E.
- On a : |¬A| = |E| - |A|.
En effet ∑(i = 1, n) [X[¬A] (ei)] = n - ∑(i = 1, n) [X[A] (ei)], avec n le nombre de bits.
- Principe d'inclusion-exclusion : |A ∪ B| = |A| + |B| - |A ∩ B|.



• Épreuves, événements, lois de probabilité, probabilités conditionnelles, indépendance, essais répétés.
[Contenu]   [Explications]


- Les phénomènes qui dépendent du hasard ; ensemble des phénomènes aléatoires Ω ; un élément de Ω s'appelle une épreuve ou une issue.
- Sortir deux fois le même numéro.
- On appelle évènement toute partie de Ω. Donc ∅ et Ω sont des évènements.
- On dit que l'issue réalise l'évènement E quand x ∈ E.
- Règles de représensation :
A ⊂ Ω : A est un évènement.
x ∈ E : l'issue x réalise l'évènement A.
A est un singleton : A est un évènement élémentaire.
A ⊂ B : l'évènement A entraîne l'évènement B.
¬ A : A^C est la non réalisation de A.
A ⋂ B : A et B est la conjonction de A et B.
A ⋂ B = ∅ : A et B sont incompatibles.
A ⋃ B : A et B est la disjonction de A et B.
- Une pièce lancée tombe soit côté Pile soit côté Face. Pour un phénomène aléatoire ; expérimentalement une probabilité
est attachée à chaque événement. Soit P(A) la probabilité de l'événement A.
On considère que c'est une grandeur physique.
- On a une valeur approchée de P(A) avec f(A) la fréquence de l'événement A.
On obtient f(A) en reproduisant le phénomène N fois, et on note "a" le nombre de fois où l'événement A est réalisé.
Alors f(A) = a / N.
- Quand N tend vers l'infini, f(A) tend vers P(A).
On voit que P(A) ne dépend que de A et du dispostif expérimental.
Alors que f(A) ne dépend que du hasard.



• Fonctions booléennes, forme canonique disjonctive.
• Systèmes d'équations booléennes.
• Synthèse : chaînes de contacts, portes.
• Simplification des formules, méthode de Karnaugh, méthode des consensus.


• Division euclidienne, nombres premiers, PGCD, PPCM, identité de Bézout.


• Calcul propositionnel.
• Propositions, connecteurs, formes propositionnelles.
• Prédicats, quantificateurs.
• Récurrences, définitions récursives.