Qu'est-ce que la complexité en informatique ?
Réponse algorithmique
Pour mesurer le temps d'exécution d'un algorithme, on définit la complexité en temps qui représente le nombre d'étapes qui sont nécessaires pour résoudre le problème pour une entrée de taille donnée.Quelle est la complexité de l'algorithme ?
Qu'est-ce que la complexité algorithmique ? La complexité algorithmique est un concept très important qui permet de comparer les algorithmes afin de trouver celui qui est le plus efficace.
Il existe une notation standard qui s'appelle big O et qui permet de mesurer la performance d'un algorithme.Comment mesurer la complexité d'un algorithme ?
On mesure alors la complexité en temps d'un algorithme comme le nombre de ces opérations élémentaires.
Par exemple, en considérant élémentaire l'addition de 2 chiffres, poser l'addition de deux nombres de n chiffres nous fera effectuer n additions à 1 chiffre, la complexité sera donc de n.- La complexité d'un algorithme est une mesure du temps[1] requis par l'algorithme pour accomplir sa tâche, en fonction de la taille[2] de l'échantillon à traiter.
On dira d'un problème qu'il est aussi complexe que le meilleur algorithme connu pour le résoudre.
MICROSOFT WORD 2016
PDF Formation Office 2016
Formation continue informatique
Aéronautique Aérospatial
L'AÉROSPATIALE
L'aéronautique et l'espace
Les industries aéronautiques et spatiales de la Communauté
Aéronautique Aérospatial
De l'industrie aéronautique et spatiale
Calculabilité et complexitéCours & exercices corrigés9 782311 014006LICENCE3&MASTERMATHÉMATIQUES&INFORMATIQUEAGRÉGATION MATHÉMATIQUESOlivier CartonLangages formelsCalculabilité et complexitéLangagesformelsLICENCE3& MASTERMATHÉMATIQUES& INFORMATIQUEAGRÉGATIONMATHÉMATIQUESOlivier CartonCours completExercices d'applicationTous les corrigés détaillésCalculabilité et complexitéCe manuel est une introduction à l'informatique fondamentaleprésentanttous les grands domaines de la théorie des langages formels aux notions decalculabilité et de complexité.
Le coursest complété par de nombreuxexercices dont les corrigés, très détaillés,assurent une mise en applicationefficace des différentes notions.
Il s'adresse aux étudiants en Licence 3 et enMaster de Mathématiques ou d'informatique ainsi qu'aux candidats àl'Agrégation de mathématiques, option informatique, dont il couvrel'essentiel du programme.Professeur d'informatique à l'université Paris Diderot (Paris 7), Olivier Cartonenseigne à tous lesniveaux, depuis le L1 jusqu'au M2, les différentes disciplines de l'informatique: programmation,algorithmique Spécialiste des automates et des langages formels, il a également enseigné durantplusieurs années à l'École normale supérieure de Paris (ENS Ulm).SommaireI.
Langages formels1. Langages rationnels2. Langages algébriquesII. Calculabilité et complexité3. Calculabilité4.ComplexitéAu fil de chaque chapitre, on trouvera des exercices suivis de leurs corrigés.CV_LangagesFormels:EP 20/05/14 11:24 Page 1iilfcc 2014/5/15 15:32 page 8 #6iiiiiiiilfcc 2014/5/15 15:32 page 3 #1iiiiiiTable des matièresPréface7Introduction9Remerciements11I Langages formels131 Langages rationnels151.
1) Premières définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151. 2) Opérations rationnelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171. 3) Combinatoire des mots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181.3. 1) Périodicités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181.3. 2) Mots infinis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231.3. 3) Motifs inévitables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231.3. 4) Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271. 4) Un peu d"ordre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301.4. 1) Quasi-ordres sur les mots . . . . . . . . . . . . . . . . . . . . . . . . . . . 331.4. 2) Ordres sur les mots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341.4. 3) Quasi-ordres sur les arbres . . . . . . . . . . . . . . . . . . . . . . . . . . . 341. 5) Langages rationnels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381.5. 1) Expressions rationnelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381.5. 2) Automates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391. 6) Automates déterministes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461. 7) Automate minimal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491.7. 1) Quotients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491.7. 2) Congruence de Nerode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 521.7. 3) Calcul de l"automate minimal . . . . . . . . . . . . . . . . . . . . . . . . . 541.8) Propriétés de clôture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 571.8.
1) Opérations booléennes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 581.8. 2) Morphisme et morphisme inverse . . . . . . . . . . . . . . . . . . . . . . . 581.9) Lemme de l"étoile et ses variantes . . . . . . . . . . . . . . . . . . . . . . . . . . . 611.10 Hauteur d"étoile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 651.11 Reconnaissance par morphisme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 661.12 Langages sans étoile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 731.13 Compléments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 791.13.
1) Conjecture de ƒerný . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 791.13.2) Rationnels d"un monoïde quelconque . . . . . . . . . . . . . . . . . . . . . 80iilfcc 2014/5/15 15:32 page 4 #2iiiiii4Table des matières4Table des matières4Table des matières2 Langages algébriques832.
1) Grammaires algébriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 832.1. 1) Définitions et exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . 832.1. 2) Grammaires réduites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 872.1. 3) Grammaires propres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 882.1. 4) Forme normale quadratique . . . . . . . . . . . . . . . . . . . . . . . . . . 902. 2) Systèmes d"équations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 912.2. 1) Substitutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 912.2. 2) Système d"équations associé à une grammaire . . . . . . . . . . . . . . . . 922.2. 3) Existence d"une solution pourS(G) . . . . . . . . . . . . . . . . . . . . . 932.2. 4) Unicité des solutions propres . . . . . . . . . . . . . . . . . . . . . . . . . 942.2. 5) Théorème de Parikh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 952.2. 6) Systèmes d"équations en commutatifs . . . . . . . . . . . . . . . . . . . . 952.2. 7) Solutions rationnelles des systèmes commutatifs . . . . . . . . . . . . . . . 962. 3) Arbres de dérivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 982.3. 1) Ambiguïté . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 992.3. 2) Lemme d"itération . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1002.3. 3) Applications du lemme d"itération . . . . . . . . . . . . . . . . . . . . . . 1032.3. 4) Ambiguïté inhérente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1052.4) Propriétés de clôture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1062.4.
1) Opérations rationnelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1062.4. 2) Substitution algébrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1062.4. 3) Intersection avec un rationnel . . . . . . . . . . . . . . . . . . . . . . . . . 1072.4. 4) Morphisme inverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1092.4. 5) Théorème de Chomsky et Schützenberger . . . . . . . . . . . . . . . . . . 1102. 5) Forme normale de Greibach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1122. 6) Automates à pile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1142.6. 1) Définitions et exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1142.6.2) Différents modes d"acceptation . . . . . . . . . . . . . . . . . . . . . . . . 1162.6.3 Équivalence avec les grammaires . . . . . . . . . . . . . . . . . . . . . . . 1192.6.
4) Automates à pile déterministes . . . . . . . . . . . . . . . . . . . . . . . . 1232. 7) Compléments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1262.7. 1) Réécriture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1262.7. 2) Contenus de pile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1282.7.3) Groupe libre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130II Calculabilité et complexité1333 Calculabilité1353.
1) Préliminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1353.1.
1) Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1353.1. 2) Logique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1373.2) Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1383.2.
1) Notion de problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1393.2. 2) Notion de codage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1393.2. 3) Machines de Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1403.2. 4) Graphe des configurations . . . . . . . . . . . . . . . . . . . . . . . . . . . 1453.2. 5) Normalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1463.2. 6) Variantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1483.3) Langages récursivement énumérables . . . . . . . . . . . . . . . . . . . . . . . . . 155iilfcc 2014/5/15 15:32 page 5 #3iiiiiiTable des matières5Table des matières5Table des matières53.
4) Langages décidables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1583. 5) Problème de correspondance de Post . . . . . . . . . . . . . . . . . . . . . . . . . 1633.5. 1) Présentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1633.5. 2) Indécidabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1643.5. 3) Application aux grammaires algébriques . . . . . . . . . . . . . . . . . . . 1663. 6) Théorème de récursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1683. 7) Machines linéairement bornées . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1713.7. 1) Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1713.7. 2) Grammaires contextuelles . . . . . . . . . . . . . . . . . . . . . . . . . . . 1713.7. 3) Décidabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1743.7. 4) Complémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1743.8) Décidabilité de théories logiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1773.
9) Fonctions récursives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1803.9. 1) Fonctions primitives récursives . . . . . . . . . . . . . . . . . . . . . . . . 1803.9.2) Fonctions récursives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1843.9.3 Équivalence avec les machines de Turing . . . . . . . . . . . . . . . . . . . 1853.9.
4) Thèse de Church . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1863.10 Compléments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1873.10.1 Écritures des entiers dans une base . . . . . . . . . . . . . . . . . . . . . . 1873.10.
2) Machines de Turing sans écriture sur l'entrée . . . . . . . . . . . . . . . . 1894 Complexité1934.
1) Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1934.1.
1) Objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1934.1. 2) Définition des complexités . . . . . . . . . . . . . . . . . . . . . . . . . . . 1934. 2) Complexité en temps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1944.2. 1) Théorème d'accélération . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1954.2. 2) Changements de modèles . . . . . . . . . . . . . . . . . . . . . . . . . . . 1954.2. 3) Classes de complexité en temps . . . . . . . . . . . . . . . . . . . . . . . . 1964.2. 4) NP-complétude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2014.2. 5) NP-complétude deSatet3Sat. . . . . . . . . . . . . . . . . . . . . . . . 2034.2. 6) Exemples de problèmesNP-complets . . . . . . . . . . . . . . . . . . . . . 2064. 3) Complexité en espace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2184.3. 1) Changement de modèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2184.3. 2) Classes de complexité en espace . . . . . . . . . . . . . . . . . . . . . . . . 2214.3. 3) Complexités en temps et en espace . . . . . . . . . . . . . . . . . . . . . . 2214.3. 4) Exemples de problèmes dansPSpace. . . . . . . . . . . . . . . . . . . . 2224.3. 5) PSpace-complétude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2234.3. 6) Espace logarithmique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2254.3. 7) NL-complétude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2304. 4) Théorèmes de hiérarchie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2334. 5) Machines alternantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2344.5. 1) Définitions et exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2344.5. 2) Complémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2364.5. 3) Automates alternants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2374.5. 4) Classes de complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2404.6) Compléments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242Bibliographie251Index253iilfcc 2014/5/15 15:32 page 12 #10iiiiiiiilfcc 2014/5/15 15:32 page 7 #5iiiiiiPréfaceVoiciun nouveau livre d'introduction à la théorie des langages, de la calculabilité et dela complexité.
Un de plus? non, car il s'inscrit dans l'évolution et l'enrichissementcontinuel de ce ce sujet et qu'il témoigne de sa vitalité et de son mûrissement.
Loin d'êtreencore un domaine standardisé, il n'est plus non plus à ses débuts et son exposition s'estenrichie au fur et à mesure de l'exp