Algorithmique avancée (suite) Ahmed Harbaoui Harbaoui.pro@gmail.com 1.3 Autres

Algorithmique avancée (suite) Ahmed Harbaoui Harbaoui.pro@gmail.com 1.3 Autres modèles de calcul Il existe d'autres modèles de calcul permettant d’aborder sous un autre angle les problèmes de décision et plus généralement l'informatique théorique : - Automates de Markov, - Circuits booléens ou digitaux, - Machine de Turing à plusieurs rubans AU 2015-2016 Ahmed HARBAOUI @ ISAMM 2 1.3 Autres modèles de calcul Une MT à plusieurs rubans est une machine de Turing à k rubans est un quintuplet M=< Q, Σ, q0, t, F > Où : Q = {q0, ..., qn}, n ∈ IN∗ : un ensemble fini d’états q0 étant l’état initial; F ⊆ Q , F : ensemble des états finaux, Σ : alphabet extérieur, un ensemble de symboles / Q et Σ sont totalement disjoints et Σ contient toujours le symbole vide Λ t est la fonction de transition; t : Q × Σk → Q × Σk × {G,D,N} AU 2015-2016 Ahmed HARBAOUI @ ISAMM 3 Machine de Turing à plusieurs rubans 1.4 Complexité et Machine de Turing Historiquement, c’est la Machine de Turing qui est le modèle théorique ayant permis de refondre le concept d’algorithme : Registre, Programme, Cycle d'instruction, configuration => fondements des ordinateurs d'aujourd'hui Pas de MTU unique ! Mais sont toutes équivalentes à une constante près. AU 2015-2016 Ahmed HARBAOUI @ ISAMM 4 1.4 Complexité et Machine de Turing Thèse de Church-Turing N’importe quel modèle raisonnable de calcul est de puissance équivalente aux machines de Turing Remarque : Sans grande perte de généralité, on peut utiliser des langages de programmation évolués à la place des MT. AU 2015-2016 Ahmed HARBAOUI @ ISAMM 5 1.4 Complexité en temps Pourquoi la complexité ? C’est la complexité intrinsèque d’un algorithme ou d’un problème qui est déterminante, et non comme on pourrait le penser en première approche, la rapidité de la machine sur laquelle il est exécuté, ou l’espace mémoire dont elle dispose. Si un algorithme «exécute» un problème de taille n en un temps c.n2 pour une constante c, nous dirons alors que la complexité en temps de cet algorithme est O(n2) AU 2015-2016 Ahmed HARBAOUI @ ISAMM 6 1.4 Complexité en temps Pourquoi la complexité ? Définition: une fonction g(n) est dite en O(f(n)) s’il existe une constante c telle que Question: Quel est le facteur déterminant: la vitesse de l'ordinateurs (vitesse dû aux progrès technologiques) ou la complexité d'un algorithme ? AU 2015-2016 Ahmed HARBAOUI @ ISAMM 7 1.4 Complexité en temps Pourquoi la complexité ? Loi de Moore (empirique) : à coût constant, la rapidité des processeurs double tous les 18 mois (les capacités de stockage suivent la même loi). Constat : le volume des données stockées dans les systèmes d'informations augmente de façon exponentielle. AU 2015-2016 Ahmed HARBAOUI @ ISAMM 8 1.4 Complexité en temps Exemple : Pour N=100 et pour une unité de temps de 10-3 s A1 s'exécute en 1/10 ième de seconde A2 s'exécute en 3,2 * 1019 années AU 2015-2016 Ahmed HARBAOUI @ ISAMM 9 Algorithme Complexité en temps A1 n A2 2n 1.4 Complexité en temps Définition: On appelle temps pour un programme M d’une MT sur une donnée x, le nombre d’étapes du calcul jusqu’à l’état final, c’est à dire l’arrêt de la machine. On peut aussi dire que c’est le nombre de fois où la MT a lu ou écrit sur le ruban. AU 2015-2016 Ahmed HARBAOUI @ ISAMM 10 1.4 Complexité en temps Définition: Pour un programme M d’une MT qui s’arrête en un temps fini pour toute donnée x de , sa fonction de complexité en temps TM : IN* −> IN* est donnée par : TM(n) = max {m : ∃ Zx ∈ ZΣ* ; |x| = n | le calcul de M sur la donnée x prend un temps m} 1.4 Complexité en temps Classe de Complexité en temps: Soit t : IN −> IN On définit la classe de complexité en temps TEMPS(t) comme étant la classe des langages décidés (i.e. décidés) par une MT Travaillant en temps t(n). 1.5 Complexité en espace Quel est l’espace occupé durant le calcul effectué par la MT ? - L’espace utilisé pendant un calcul est égal au nombre de cellules visitées sur le ou les ruban(s). Définition (Complexité spatiale) Pour un programme M d’une MT qui s’arrête en temps fini pour toute donnée x de Σ*, on définit sa complexité en espace EM : IN* −> IN* Par : EM(n) = max {m : ∃ Zx ∈ ZΣ* ; |x| = n | le calcul de M sur la donnée x utilise m cellules.} 1.5 Complexité en espace Définition (Classe de complexité en espace) Soit e : IN −> IN On définit la classe de complexité en espace ESPACE(m) comme étant la classe des langages décidés (i.e. reconnus) par une MT utilisant m cellules de rubans pour son calcul. AU 2015-2016 Ahmed HARBAOUI @ ISAMM 14 1.6 Relation entre les complexités Les complexités spatiale et temporelle sont liées par le théorème suivant : Théorème (complexités spatiale vs temporelle) Exemple : Permutation des deux valeurs entières (2 solutions) Intuitivement : pour gagner du temps de calcul, on doit utiliser d'avantage d'espace mémoire AU 2015-2016 Ahmed HARBAOUI @ ISAMM 15 Règles pratiques de calculer de la complexité • Règle 1: la complexité d’un ensemble d’instructions est la somme des complexités de chacune d’elles. • Règle 2: Les opérations élémentaires telle que l’affectation, test, accès à un tableau, opérations logiques et arithmétiques, lecture ou écriture d’une variable simple ... etc, sont en O(1) Règle 3: Instruction if: maximum entre le then et le else switch: maximum parmi les différents cas Règle 4: Instructions de répétition 1. La complexité de la boucle for est calculée par la complexité du corps de cette boucle multipliée par le nombre de répétition. 2. La complexité d’une boucle while, il faudra avant tout déterminer le nombre de fois que cette boucle est répétée, ensuite le multiplier par la complexité du corps de cette boucle. Règle 5: Procédure et fonction: leur complexité est déterminée par celui de leur corps. L’appel à une fonction est supposé prendre un temps constant en O(1) Notons qu’on fait la distinction entre les fonctions récursive et celles qui ne le sont pas: • Dans le cas de la récursivité, le temps de calcul est exprimé comme une relation de récurrence. Exemples Exemple 1: a = b; Temps constant: O(1). Exemple 2: somme = 0; for (i=1; i<=n; i++) somme += n; Temps: O(n) Exemple 3: somme = 0; for (j=1; j<=n; j++) for (i=1; i<=n; i++) somme++; for (k=0; k<n; k++) A[k] = k; Temps: O(1) + O(n2) + O(n) = O(n2) Exemple 4: somme = 0; for (i=1; i<=n; i++) for (j=1; j<=i; j++) somme++; Temps: O(1) + O(n2) = O(n2) Exemple 5: somme = 0; for (k=1; k<=n; k*=2) for (j=1; j<=n; j++) somme++; Temps: O(nlog n) O(1) : complexité constante, pas d'augmentation du temps d'exécution quand le paramètre croit O(log(n)) : complexité logarithmique, augmentation très faible du temps d'exécution quand le paramètre croit. Exemple : algorithmes qui décomposent un problème en un ensemble de problèmes plus petits (dichotomie). O(n) : complexité linéaire, augmentation linéaire du temps d'exécution quand le paramètre croit (si le paramètre double, le temps double). Exemple : algorithmes qui parcourent séquentiellement des structures linéaires. O(nlog(n)) : complexité quasi-linéaire, augmentation un peu supérieure . O(n). Exemple : algorithmes qui décomposent un problème en d'autres plus simples, traités indépendaments et qui combinent les solutions partielles pour calculer la solution générale. Exemples : Résumé Exemples : Résumé O(n2) : complexité quadratique, quand le paramètre double, le temps d'exécution est multiplié par 4. Exemple : algorithmes avec deux boucles imbriquées. O(ni) : complexité polynomiale, quand le paramètre double, le temps d'exécution est multiplié par 2i. Exemple : algorithme utilisant i boucles imbriquées. O(in) : complexité exponentielle, quand le paramètre double, le temps d'exécution est élevé à la puissance 2. O(n!) : complexité factorielle, asymptotiquement équivalente à nn 1.7 La classe P - Un programme de MT est dit programme polynomial en temps s’il existe un polynôme p tel que : PZoZuZrZ ZtZoZuZtZ ZnZ Z∈ ZIZNZ*Z Z,ZTZMZ(ZnZ)Z Z≤ ZpZ(ZnZ)Z -Z ZLZ’aZpZpZaZrZtZeZnZaZnZcZeZ Zà ZlZaZ ZcZlZaZsZsZeZ ZPZ ZpZoZuZrZ ZuZnZ ZpZrZoZbZlZèmZeZ ZsZuZpZpZoZsZeZ ZlZ’eZxZiZsZtZeZnZcZeZ ZdZ’uZnZ ZaZlZgZoZrZiZtZhZmZeZ ZpZoZlZyZnZoZmZiZaZlZ ZeZnZ ZtZeZmZpZsZ ZpZoZuZrZ ZrZésZoZuZdZrZeZ ZcZeZ ZpZrZoZbZlZèmZeZ.Z ZLZeZ ZpZlZuZsZ ZsZoZuZvZeZnZtZ ZlZ’aZlZgZoZrZiZtZhZmZeZ ZeZsZtZ ZcZoZnZnZuZ.Z -Z ZLZaZ ZcZlZaZsZsZeZ ZNZPZ ZeZsZtZ ZfZoZrZmZéeZ ZdZeZsZ ZlZaZnZgZaZgZeZsZ ZrZeZcZoZnZnZuZsZ Z(ZoZuZ ZaZcZcZeZpZtZésZ)Z ZpZaZrZ ZlZeZsZ ZmZaZcZhZiZnZeZsZ ZdZeZ ZTZuZrZiZnZgZ ZdZétZeZrZmZiZnZiZsZtZeZ 1.8 La classe NP l - La classe NP est formée des langages reconnus (ou acceptés) par les machines de Turing Non déterministe polynomiale l - Machine de Turing non-déterministe pour chaque pair état-symbole il peut y avoir une, plusieurs ou aucune possibilité de transition, correspondant a un choix l - Un algorithme non polynomiale et vérifiable d'une façon polynomiale appartient à la classe NP AU 2015-2016 Ahmed HARBAOUI @ ISAMM 27 1.8 La classe NP Comment mesurer le temps de calcul d'un tel algorithme ? Pour le temps de calcul, on convient, conformément au principe "envisager le pire", que c'est celui de uploads/Industriel/ algo-avnc-2.pdf

  • 12
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager