[PDF] Outils Formels pour lInformatique

View - Download Outils Formels pour lInformatique

Previous PDF

Next PDF

Outils Formels pour

l'Informatique

Jean-Marc Fédou

fedou@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é)

Bibliographie

Concepts fondamentaux de l'informatique

Aho & Ullman, éd. Dunod.

Mathématiques pour l'informatique

A. 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 semestre

Dé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

Evaluation

Deux 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 fichiersGraphes de dépendancesStructure 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éments

Un 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 ensembliste

Opé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 ensembliste

Soient 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éristique

La fonction caractéristique d'une partie A d'un ensemble E est définie par X A : E {0,1} X A (x) = 1 si x ∈ A X A (x) = 0 si x∉A

On remarque que

XA∩B(x)= X

A (x) X B (x) X

A∪B

(x)= X A (x)+ X B (x)-XA∩B(x)

XA(x)= 1-X

A (x)

Définition d'un ensemble

Un 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)

Exemples

Dans 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
, 2 32
le type long, comme l'ensemble des entiers d'un intervalle [ -2 64
, 2 64

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 2 64
valeurs possibles), qui contient seulement certains nombres réels

Inclusion d'ensemble

On 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[={x

i ,i ∈ IN}.

Tout réel x

i admet un écriture décimale illimitée x i =0,x i 1 x i 2 ...x i i ... où i k ∈{0,1,2,...,9}

Considérons alors une suite d'entier y

n de {0,1,2,...,8} tq y n x n n pour tout entier n

Alors y=0, y

0 y 1 y 2 ... y n ... est différent de chacun des x i

L'ensemble IN

2 est dénombrable Le cardinal d'un ensemble E fini est noté |E |. Remarquons que |E | = Є x∈E X E (x)

Si E et F sont deux ensembles disjoints alors

|E∪ F | = |E |+ |F | Si (E i )est une partition d'un ensemble E alors |E | = Є i |E i Si E et F sont deux ensembles quelconques alors |E∪ F |= |E |+ |F | - |E ∩ F | Formule du Crible (généralisation à n ensembles (E i 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

quotesdbs_dbs47.pdfusesText_47

[PDF] Mathématiques Dm 4éme

[PDF] mathématiques dm 5

[PDF] Mathematiques dm n1

[PDF] Mathématiques DM pour le 18/09/2015

[PDF] Mathematiques dur besoins de vous

[PDF] mathématiques ecriture scientifque urgent c pour demin g controle SVP

[PDF] mathématiques en économie

[PDF] mathématiques en économie-gestion pdf

[PDF] mathematiques en factorisation ^^

[PDF] mathematiques en geoétrie cned 3eme

[PDF] Mathématiques en option ES (terminale) Matrices

[PDF] MATHEMATIQUES enquete

[PDF] mathématiques enquete policiere

[PDF] Mathématiques équation, besoin d'aide

[PDF] Mathématiques Equations 3