Embed Size (px)
Citation preview
Présentation
Ce cours abordera :
les mathématiques pour l’informatique (mathématiques discrètes, logique, dénombrement)
la formalisation des objets informatiques (induction, langages formels, théorie des graphes)
l’étude des performances des ordinateurs (complexité)
BibliographieConcepts fondamentaux de l’informatique Aho & Ullman, éd. Dunod.
Mathématiques pour l’informatiqueA. Arnold & I. Guessarian, éd. EdiScience.
Méthodes mathématiques pour l’informatique J. Vélu, éd. Dunod.
Introduction à l’algorithmique Cormen, Leiserson & Rivest, éd. Dunod.
Mathématiques discrètes et informatique, N.H. Xuong, éd. Masson.
Organisation du semestreDébut des cours le mardi 9 Septembre
Début des TD le mardi 16 Septembre
Cours et TD du Mardi 11 Novembre remplacés le 18 Novembre
Quelques interrogations écrites de 10mn en TD, dont la moyenne sera pondérée par l’asssiduité et la participation
EvaluationDeux devoirs surveillés (coeff 1/3 chacun)
Mardi 18 Novembre
Mardi 16 Décembre
Quelques interrogations écrites de 10mn en TD, dont la moyenne sera pondérée par l’asssiduité et la participation(coeff 1/3)
Supports
Polycopiés distribués en cours
Transparents
Feilles de TD
Supports disponibles également sur votre espace jalon
Votre espace “Jalon”
Votre espace “Jalon”
Votre espace “Jalon”
Travaux Dirigés
Filière Math-Info
Groupe 1. J-M. Fédou
Mercredi 8h30 - 10h M1-4
Mercredi 14h45-16h15 M2-7
Groupe 2. S. Julia
Mercredi 8h30 - 10h M1-6
Mercredi 13h-14h30 M1-1
Filière MPIE
Groupe 1. J-M. Fédou,
Mardi 8h30 -11h45 , M2-4
Groupe 2. B. Beauquier
Lundi 13h-14h30 M2-3
Jeudi 8h30-10hM2-4
Groupe 3. B. Beauquier
Mardi 10H15- 11h45 M2-3
Jeudi 8h30-10h M2-5
Motivations Mathématiques discrètes et Informatique
L’informatique ne manipule que des suites FINIES de 0 et de 1
Textes. Une page A4 comporte environ 2500 caractères, chacun codé sur 8 bits en ISO 8859-1 (Latin1)
Images. Une image standard contient aujourd’hui 8 millions de pixels
Sons. Un morceau de musique de 6mn au format MPeg 3 nécessite 8 Mégaoctets
Vidéos. Une vidéo de 6mn sur youtube nécessite 15 Mo
Programmes. Le programme qui a permis d’écrire ce document a une taille de 283,7 Mégaoctets
La géométrie de l’ordinateur n’est pas euclidienne
12
La géométrie informatique n’est pas euclidienne
Deux droites non parallèles peuvent
• n’avoir aucun points d’intersection
• ou peuvent en avoir plusieurs
Limites de l’informatique
Certains problèmes n’ont pas de solutions, comme le problème de l’arrêt.
D’autres ont des solutions, mais algorithmiquement inefficaces (Sac à dos, Voyageur de commerce)
Certains algorithmes sont meilleurs que d’autres
Langages
Au début étaient les cartes perforées, l’assembleur et ce n’est que dans les années 50-60 que sont apparus des langages de programmation plus pratiques à utiliser
La théorie des langages est à la base des compilateurs ou interpréteurs que vous utilisez : analyse lexicale, analyse syntaxique, analyse sémantique ...
La théorie des langages a des applications dans bien d’autres domaines
Cryptographie, codes
Compression
Biologie (Etude du génome)
Théorie des graphes
Les graphes modélisent les réseaux de communication, les bases de données, le web, ....
Les algorithmes de graphes sont utilisés partout en Informatique
La recherche dans le domaine des graphes et des réseaux est très active
Théorie des graphes
Image du web
Théorie des graphes
Réseaux sociaux
Théorie des graphes
Systèmes de fichiers
Graphes de dépendances
Structure RNA
Plan du cours
1. Ensembles et Dénombrabilité
2. Relations, Fonctions et Ordres
3. Récurrence et Induction
4. Logique Propositionnelle
5. Logique des Prédicats
6. Dénombrement
7. Suites Récurrentes
8. Graphes et Arbres
9. Complexité des Algorithmes
10. Langages Rationnels
11. Automates finis
12. Algorithmique de graphes
Ensembles
et
dénombrabilité
Ensembles et élémentsUn ensemble d’éléments est une collection d’objets distincts.
Un ensemble est défini par les éléments qu’il contient et qui lui appartiennent.
La relation d’appartenance d’un élément à un ensemble est notée ∈ (ex: x ∈ E).
L’unique ensemble qui ne contient aucun élément est l’ensemble vide, noté ∅
Les éléments d’un ensemble ne sont pas ordonnés entre eux.
Un ensemble peut être élément d’un autre ensemble, mais pas de lui-même ! (voir le paradoxe de Russell)
Calcul ensemblisteOpérations sur les ensembles:
Union : x∈A∪B ssi (x∈A ou x∈B)
Intersection : x∈A∩B ssi (x∈Aet x∈B)
Complémentaire : x∈A = C(A) ssi x∉A
Différence : A\B=A∩B
Différence symétrique : A∆B=A\B∪B\A
Produit cartésien : (x,y)∈A×B ssi x∈A et y∈B
Note: deux ensembles sont dits disjoints si leur intersection est vide.
BA
A∩B
Calcul ensemblisteSoient A, B et C trois ensembles.
Commutativité : A∪B = B∪A A∩B=B∩A
Associativité : (A∪B)∪C=A∪(B∪C) (A∩B) ∩C=A∩(B∩C)
Distributivité:
De l’union par rapport à l’intersection ( à gauche et à droite)
A∪(B∩C) =(A∪B) ∩(A∪C) (A∩B) ∪C=(A∪C) ∩(B∪C)
De l’intersection par rapport à l’union ( à gauche et à droite)
A∩(B∪C) =(A∩B) ∪(A∩C) (A∪B) ∩C=(A∩C) ∪(B∩C)
Lois de Morgan : A∪B = B∩A A∩B = B∪A
Fonction caractéristiqueLa fonction caractéristique d’une partie A d’un ensemble E est définie par XA : E {0,1}
XA(x) = 1 si x ∈ A
XA(x) = 0 si x∉A
On remarque que
XA∩B(x)= XA(x) XB(x)
XA∪B(x)= XA(x)+ XB(x)-XA∩B(x)XA(x)= 1-XA(x)
Définition d’un ensembleUn ensemble peut être défini :
en extension: par la liste exhaustive de ses éléments
ex. {2,4,6,8}
en compréhension: par une propriété vérifiée par ses éléments (en général déjà définis dans un (sur-)ensemble donné)
ex: les entiers naturels pairs (dans le sur-ensemble IN)
ExemplesDans la sémantique de Java, un type primitif correspond à un ensemble de valeurs.
le type boolean s’interprète comme l’ensemble {VRAI, FAUX}
le type int, comme l’ensemble des entiers d’un intervalle [ −2 32 , 232 [
le type long, comme l’ensemble des entiers d’un intervalle [ −2 64 , 264 [
le type float, comme l’ensemble des nombres flottants à double précision (représentés sur 32 bits)
le type double, comme l’ensemble des nombres flottants à double précision (représentés sur 64 bits) . Attention, ce n’est pas l’ensemble R, puisque c’est un ensemble fini (il n’y a que 264 valeurs possibles), qui contient seulement certains nombres réels
Inclusion d’ensembleOn dit qu’un ensemble E est inclus dans un ensemble F lorsque tout élément de E est également élément de F.
La relation d’inclusion entre deux ensembles est notée ⊆ : A ⊆ B ssi (x ∈ A ⇒ x ∈ B)
donc A=B ssi (A ⊆ B et B ⊆ A)
Ensemble des parties d’un ensemble
Etant donné un ensemble E, l’ensemble de ses parties est noté P(E)
P(E)={A/ A ⊂ E}
Attention, si x ∈ E, alors
{x} ⊂ E
{x} ∈ P(E)
P(E) contient au moins ∅ et E comme éléments
Paradoxe de Russell
Considérons la définition E={F tel que F est un ensemble},Autrement di, E est l’ensemble de tous les ensembles.
On a une contradiction en remarquant que :
«F est un ensemble» est bien une propriété mais ici le sur-ensemble serait E lui-même...
Et donc, si E était un ensemble bien défini alors on aurait E∈E!
Il fut découvert par Bertrand Russell vers 1901 et publié en 1903. Il avait été découvert par Ernst Zermelo, autour de 1900, qui ne l'a pas publié
Paradoxe de Russell Raisonnement par l’absurde: si E est bien un ensemble, alors on peut aussi définir l’ensemble
A={G∈E tel que G∉G}
De deux choses l’une:
soit A∈A et alors A∉A ⇒ contradiction
soit A∉A et alors A∈A ⇒ contradiction aussi
D’où le paradoxe L’ensemble de tous les ensembles n’existe pas !
Le cardinal d’un ensemble précise la notion de nombre d’éléments . On dira que deux ensembles ont même cardinalité lorsqu’il peuvent être mis en bijection.
On distingue en particulier
Les ensembles finis (dénombrables au sens large), sont les ensembles qui peuvent être mis en bijection avec {1,2,…,n}
Les ensembles infinis dénombrables, en bijection avec IN, de cardinal noté ℵ0.
Les ensembles infinis non-dénombrables, impossibles à mettre en bijection avec IN.
Cardinalité
L’ensemble [0,1[ est infini non dénombrable
Argumentation : diagonale de Cantor
- Si [0,1[ était dénombrable alors [0,1[={xi ,i ∈ IN}.
- Tout réel xi admet un écriture décimale illimitée xi=0,xi1xi2...xii... où ik ∈{0,1,2,...,9}
- Considérons alors une suite d’entier yn de {0,1,2,...,8} tq
. yn ≠ xnn pour tout entier n
- Alors y=0, y0 y1 y2 ... yn ... est différent de chacun des xi
L’ensemble IN2 est dénombrable
0 1 2 3 4 5 6 7 8 9
0 0 2 5 9 14 20
1 1 4 8 13 19
2 3 7 12 18
3 6 11 17 24
4 10 16 23
5 15 22
6 21
7
8
Le cardinal d’un ensemble E fini est noté |E |. Remarquons que |E | = Σx∈E XE(x)
Si E et F sont deux ensembles disjoints alors
|E∪ F | = |E |+ |F |
Si (Ei)est une partition d’un ensemble E alors |E | = Σi |Ei |
Si E et F sont deux ensembles quelconques alors |E∪ F |= |E |+ |F | − |E ∩ F |
Formule du Crible (généralisation à n ensembles (Ei)1 ≤ i ≤ n)
Cardinaux finis
Soient E, F des ensembles finis.
Principe multiplicatif
|E × F |= |E |∗ |F |
Généralisation à n ensembles
Principe d’égalité
Il existe une bijection entre E et F ssi |E|= |F|
Cardinaux finis
Soient E et F deux ensembles finis.
Principe d’inégalité ou principe des tiroirs : (pigeon-hole principle)
Si |E |> |F | alors il n’existe pas d’injection de E dans F.
Interprétation équivalente :
Si n objets sont dans m tiroirs et si n>m, alors il existe au moins un tiroir qui contient au moins deux objets.
Si n pigeons nichent dans m trous, alors il y a au moins deux pigeons dans un même trou
Cardinaux finis
