3 nov 2010 · Mathématiques pour l'informatique Christophe GUYEUX et Jean-François COUCHOT guyeux[arobase]iut-bm univ-fcomte[point]
| Previous PDF | Next PDF |
[PDF] Applications mathématiques discrètes
Mathématiques discrètes et leurs applications / Kenneth H Rosen Série de livres du CRC en mathématiques discrètes, composée de plus de 55 volumes sur
[PDF] MATHÉMATIQUES DISCRÈTES - Institut de Mathématiques de
C'est une relation d'ordre total sur A∗ On a par exemple a ≤lex fa, poule ≤lex poulet, avion ≤lex train, livraison ≤lex livre, foot ≤lex fort
[PDF] Mathématiques discrètes, 1ère année
25 oct 2010 · On en trouve toujours, dans le cours, dans les livres, dans les annales d' examens Les exercices doivent être préparés, c'est à dire que l'on doit
[PDF] Cours de mathématiques discrètes - cours-info
3 nov 2010 · Mathématiques pour l'informatique Christophe GUYEUX et Jean-François COUCHOT guyeux[arobase]iut-bm univ-fcomte[point]
[PDF] Mathématiques Discrétes - Hatem MASRI
Mathématiques Discrétes Hatem MASRI Septembre 2003 cipline, aucun cours, ni livre, ne peut prétendre couvrir tout le sujet avec pertinence et rigueur 3
[PDF] Introduction aux mathématiques discrètes - IRISA
Ce cours est un voyage au pays des mathématiques discrètes Bibliographie ▷ André Arnold, Irène Guessarian Mathématiques pour l'informatique ▷ Alfred
[PDF] MAT 115 – Logique et mathématiques discrètes - Informatique
24 août 2020 · Les mathématiques constituent le langage commun des sciences et la logique est le fondement des mathématiques L'informatique a été fondée
[PDF] MAT1500 Mathématiques discrètes Automne 2018 4 crédits
Le livre : Rosen, Mathématiques Discrètes, Édition revisée, Chenelière éducation (2002) est disponible au librairie en bas du tour Ce n'est pas obligatoire,
[PDF] MAT1500 Mathématiques discrètes Automnee 2017 Professeur : A
Informations sur les orientations du bacc en mathématiques MAT1500 2 of 21 Le livre : Rosen, Mathématiques Discrètes disponible au librairie en bas du
[PDF] mathématiques discrètes pour l'informatique
[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
Mathématiques pour l'informatique
Christophe GUYEUXet Jean-François COUCHOT
3 novembre 2010
Table des matières
I Théorie des ensembles10
1 Introduction à la théorie des ensembles11
I Rappels de théorie des ensembles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 I.1 Notion première d'ensemble. . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 I.2 Règles de fonctionnement. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 I.3 Sous-ensembles, ensemble des parties. . . . . . . . . . . . . . . . . . . . . . . 12 I.4 Représentation graphique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 I.5 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 II Opérations sur les ensembles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 II.1 Égalite de deux ensembles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 II.2 Réunion, intersection. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 II.3 Complémentation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 II.4 Produit cartésien. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 III Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 III.1 Ensembles de base. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 III.2 La différence symétrique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 III.3 Généraux. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 Relations binaires entre ensembles19
I Relations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 II Relations d'ordre. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19II.1 Réflexivité, antisymétrie, transitivité. . . . . . . . . . . . . . . . . . . . . . . . 20
II.2 Relation d'ordre. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 II.3 Ordre partiel, ordre total. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 II.4 Éléments maximaux. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21III Relations d'équivalence. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
III.1 Classes d'équivalence. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 III.2 Ensemble-quotient. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24IV Compatibilité entre une opération et une relation binaire. . . . . . . . . . . . . . . . . 25
3 Application d'un ensemble dans un autre26
I Application et relation fonctionnelle. . . . . . . . . . . . . . . . . . . . . . . . . . . . 26II Image et antécédent d'un élément. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
III Applications injectives. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 IV Applications surjectives. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 V Image d'un ensemble par une application. . . . . . . . . . . . . . . . . . . . . . . . . 28 VI Applications bijectives. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 14 Relations-aires30
I Définitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
I.1 Relations orientées et non orientées. . . . . . . . . . . . . . . . . . . . . . . . 30 I.2 Relations équivalentes, relations égales. . . . . . . . . . . . . . . . . . . . . . 31 I.3 Interprétation fonctionnelle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 I.4 SGBD. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 II Projections. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 II.1 Définitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 II.2 Théorème des projections. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32III Opérations sur les relations-aires. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
III.1 Somme et produit. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 III.2 Réunion et intersection. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 III.3 Produit cartésien. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 IV Sélection d'une relation-aire. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34V Dépendances fonctionnelles et clés. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
V.1 Dépendances fonctionnelles. . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 V.2 Théorème des dépendances fonctionnelles. . . . . . . . . . . . . . . . . . . . . 35 V.3 Clés. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35II Arithmétique37
5 Ensembles de nombres entiers38
I Nombres entiers naturels (N). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 I.1 Définition deN. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 I.2 Opérations et relation d'ordre dansN. . . . . . . . . . . . . . . . . . . . . . . 40 I.3 Nombres premiers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 I.4 Relation de divisibilité. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 I.5 Entiers relatifs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 II Division euclidienne dansZet applications. . . . . . . . . . . . . . . . . . . . . . . . 43 II.1 Définition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 II.2 Représentation des nombres entiers. . . . . . . . . . . . . . . . . . . . . . . . 43 II.3 Arithmétique modulo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 II.4 Division " entière» informatique et division euclidienne. . . . . . . . . . . . . 47 II.5 Arithmétique modulondans les ordinateurs. . . . . . . . . . . . . . . . . . . 48 III Algorithmes d'Euclide et applications. . . . . . . . . . . . . . . . . . . . . . . . . . . 51 III.1 PGCD de deux entiers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 III.2 Algorithme d'Euclide. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 III.3 Théorème de Bézout. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 III.4 Algorithme d'Euclide généralisé. . . . . . . . . . . . . . . . . . . . . . . . . . 536 Représentation des nombres réels en machine55
I Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 II Les formats IEEE. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 II.1 La norme IEEE 754. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 II.2 Format " single». . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 II.3 Format " double ». . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 II.4 Format " extended ». . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 II.5 D'une manière générale.... . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 II.6 Format " extended » des microprocesseurs.. . . . . . . . . . . . . . . . . . . . 58III Réels représentables et précision. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
27 Cryptologie et arithmétique.61
I Méthodes de cryptage " à clé publique ». . . . . . . . . . . . . . . . . . . . . . . . . . 61
I.1 Principe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 I.2 Utilisation de l'indicatrice d'Euler. . . . . . . . . . . . . . . . . . . . . . . . . 62 II Choix d'un nombre n. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 II.1 Nombres premiers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 II.2 Décomposition en facteurs premiers. . . . . . . . . . . . . . . . . . . . . . . . 638 Tests de primalité65
I Théorème de Fermat. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 II Test de Miller-Rabin. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 III Tests de Lucas, Selfridge et Pocklington. . . . . . . . . . . . . . . . . . . . . . . . . . 669 Décomposition en facteurs premiers67
I Divisions successives. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 II Algorithme de Monte-Carlo (1975). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 II.1 Présentation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 II.2 L'algorithme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 II.3 Discussion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 III Algorithme du crible quadratique QS de Pomerance. . . . . . . . . . . . . . . . . . . . 69 IV Algorithme?de Pollard. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 V Algorithme de Lenstra (courbes elliptiques). . . . . . . . . . . . . . . . . . . . . . . . 71 V.1 Introduction aux courbes elliptiques. . . . . . . . . . . . . . . . . . . . . . . . 71 V.2 Algorithme de Lenstra. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71III Logique72
10 Algèbre de Boole73
I Propriétés générales. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
II Règles de calcul dans une algèbre de Boole. . . . . . . . . . . . . . . . . . . . . . . . 74
III Fonctions booléennes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
III.1 Définitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 III.2 Fonctions booléennes élémentaires. . . . . . . . . . . . . . . . . . . . . . . . . 76 III.3 Correspondance entre maxtermes et mintermes. . . . . . . . . . . . . . . . . . 77 III.4 Principaux résultats concernant mintermes et maxtermes. . . . . . . . . . . . . 77 III.5 Formes canoniques d'une fonction booléenne. . . . . . . . . . . . . . . . . . . 78 IV Diagrammes de Karnaugh. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80V Résolution d'équations booléennes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
VI Méthode des consensus. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8411 Calcul propositionnel89
I Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 II Les fondements de la logique des propositions. . . . . . . . . . . . . . . . . . . . . . . 89 II.1 Les propositions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 II.2 Les connecteurs logiques. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 II.3 Variables et formules propositionnelles. . . . . . . . . . . . . . . . . . . . . . 93 III Sémantique du calcul propositionnel. . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 III.1 Fonctions de vérité. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 III.2 Formules propositionnelles particulières. . . . . . . . . . . . . . . . . . . . . . 96 III.3 Conséquences logiques. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 III.4 Formules équivalentes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 3 III.5 Simplification du calcul des fonctions de vérité. . . . . . . . . . . . . . . . . . 100 III.6 Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10312 Calcul propositionnel : déductions syntaxiques104
I Présentation de la théorie de la démonstration. . . . . . . . . . . . . . . . . . . . . . . 104
II Axiomes logiques et règles d'inférence du système formel " PR ». . . . . . . . . . . . . 104
III Démonstrations avec ou sans hypothèses. . . . . . . . . . . . . . . . . . . . . . . . . . 105
III.1 Démonstration d'un théorème. . . . . . . . . . . . . . . . . . . . . . . . . . . 105 III.2 Démonstration sous hypothèses. . . . . . . . . . . . . . . . . . . . . . . . . . 106IV Théorème de la déduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
V Quelques théorèmes classiques et quelques règles d'inférence annexes. . . . . . . . . . 109
VI Théorèmes de complétude du calcul propositionnel. . . . . . . . . . . . . . . . . . . . 110
13 Calcul des prédicats112
I Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 I.1 Introduction aux "prédicats ». . . . . . . . . . . . . . . . . . . . . . . . . . . 112 I.2 Introduction à l'"univers du discours». . . . . . . . . . . . . . . . . . . . . . 112 I.3 Introduction à la "quantification ». . . . . . . . . . . . . . . . . . . . . . . . . 112II Définitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
II.1 Termes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 II.2 Prédicats et atomes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 III Quantificateurs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 III.1 Quantificateur universel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 III.2 Quantificateur existentiel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 III.3 Alternance de quantificateurs. . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 III.4 Portée d'un quantificateur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 III.5 Formules du calcul des prédicats. . . . . . . . . . . . . . . . . . . . . . . . . . 116IV Sémantique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
IV.1 Valeurs de vérité. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 IV.2 Simplification de formules quantifiées. . . . . . . . . . . . . . . . . . . . . . . 117 IV.3 Substitutions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11914 Méthode de résolution120
I Cas propositionnel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 I.1 Clauses propositionnelles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 I.2 Résolvantes d'une paire de clauses. . . . . . . . . . . . . . . . . . . . . . . . . 121 I.3 Résolution d'un ensemble de clauses. . . . . . . . . . . . . . . . . . . . . . . 121 II Formes normales en logique des prédicats. . . . . . . . . . . . . . . . . . . . . . . . . 122 II.1 Forme prénexe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 II.2 Forme de Skolem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 II.3 Forme clausale. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124III Résolution en logique des prédicats. . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
III.1 Résolvante d'une paire de clauses. . . . . . . . . . . . . . . . . . . . . . . . . 124 III.2 Résolution d'un ensemble de clauses. . . . . . . . . . . . . . . . . . . . . . . 124 III.3 Mise en oeuvre de la résolution. . . . . . . . . . . . . . . . . . . . . . . . . . . 125IV Langages, grammaires et automates127
15 Compilation, langages et grammaires128
I Introduction à la compilation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
I.1 Le problème posé est.... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 4 I.2 Les diverses phases d'une compilation. . . . . . . . . . . . . . . . . . . . . . . 128 II Les grammaires. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 II.1 Définition de la notion de grammaire. . . . . . . . . . . . . . . . . . . . . . . 129 II.2 Le formalisme BNF. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 II.3 Les symboles terminaux. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 II.4 Les symboles non terminaux. . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 II.5 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 III Un exemple complet. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 III.1 Principes généraux. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 III.2 La grammaire du langage. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 III.3 Analyseur syntaxique pur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 III.4 Analyseur syntaxique avec messages d'erreur. . . . . . . . . . . . . . . . . . . 132 III.5 Analyseur syntaxique avec interprétation sémantique. . . . . . . . . . . . . . . 13316 Introduction aux expressions rationnelles135
I Présentation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
II Règles de définition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
III Propriétés des opérateurs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
IV De nouvelles abréviations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
V Universalité des expressions rationnelles. . . . . . . . . . . . . . . . . . . . . . . . . . 137
17 Automates Finis138
I Automates finis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 I.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 I.2 Mécanismes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138II Automates finis à comportement déterminé. . . . . . . . . . . . . . . . . . . . . . . . 139
II.1 Définition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 II.2 Automates finis avec sorties (machines de Moore et de Mealy). . . . . . . . . . 141 II.3 Automates de Moore. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142III Langage associé à un automates de Moore. . . . . . . . . . . . . . . . . . . . . . . . . 142
III.1 Définition du langage. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 III.2 Exemple et exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142IV Automates finis à comportement non déterminé. . . . . . . . . . . . . . . . . . . . . . 144
IV.1 Définitions et exemples. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 IV.2 Utilité. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 V Détermination d'un AFND. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 V.1 Méthode de construction par sous-ensemble. . . . . . . . . . . . . . . . . . . . 145 V.2 En pratique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 VI Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147VI.1 Propriétés d'un automate àétats. . . . . . . . . . . . . . . . . . . . . . . . . 147
VI.2 Les palindromes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14718 Optimisation d'automates finis149
I Congruences d'automates. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 I.1 Quelques rappels. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 I.2 Définition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 I.3 Ensemble quotient. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150II Équivalence de Nérode. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
II.1 L'équivalence. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 II.2 L'algorithme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153III Méthode du dual. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
III.1 Dual d'un automate. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 5 III.2 Méthode du dual. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155IV Synthèse. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
IV.1 Outils. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 IV.2 Méthodes d'optimisation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15719 Construction d'automates finis à partir d'expressions rationnelles158
I Automates à transitions instantanées. . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
II Données et résultat. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
III Algorithme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 IV Exemple. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 V Finalisation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16020 Automates à pile162
I Automates à pile, déteministes ou pas.. . . . . . . . . . . . . . . . . . . . . . . . . . . 162
I.1 Automate à pile non déterministe. . . . . . . . . . . . . . . . . . . . . . . . . 162 I.2 Automate à pile déterministe. . . . . . . . . . . . . . . . . . . . . . . . . . . . 163II Calcul dans un automate à pile. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
II.1 Encore quelques définitions.... . . . . . . . . . . . . . . . . . . . . . . . . . . 164 II.2 Premiers exemples. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 II.3 Exemple plus complet : le langagennN. . . . . . . . . . . . . . . . 166III Construction d'un automate à pile. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
III.1 Introduction à la méthode. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 III.2 Utilisation d'un symbolisme. . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 III.3 Algorithme de construction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 III.4 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167