Outils Formels pour l’Informatiquefedou/OFI2008-2009/OFI-Cours1.pdf · 2009. 11. 18. ·...

Outils Formels pour l’Informatique

Jean-Marc Fédoufedou@unice.fr

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