Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Algo avnc 2 Algorithmique avancée suite Ahmed Harbaoui Harbaoui pro gmail com C 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éoriqu

Algorithmique avancée suite Ahmed Harbaoui Harbaoui pro gmail com C 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 - Ahmed HARBAOUI ISAMM C Autres modèles de calcul Machine de Turing à plusieurs rubans Une MT à plusieurs rubans est une machine de Turing à k rubans est un quintuplet M Q ? q t F O? Q q qn n ?? IN ? un ensemble ?ni d ? états q étant l ? état initial F ? Q F ensemble des états ?naux ? 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 - Ahmed HARBAOUI ISAMM C 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 con ?guration fondements des ordinateurs d'aujourd'hui Pas de MTU unique Mais sont toutes équivalentes à une constante près AU - Ahmed HARBAOUI ISAMM C 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 - Ahmed HARBAOUI ISAMM C 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 n pour une constante c nous dirons alors que la complexité en temps de cet algorithme est O n AU - Ahmed HARBAOUI ISAMM C Complexité en temps Pourquoi la complexité Dé ?nition 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 - Ahmed HARBAOUI ISAMM C Complexité en temps Pourquoi la complexité Loi de Moore empirique à coût constant la rapidité des processeurs double tous les 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 - Ahmed HARBAOUI ISAMM C Complexité en temps Exemple Algorithme A A Complexité en temps n n Pour N et pour une unité de temps de - s A s'exécute en ième de seconde A s'exécute en années AU - Ahmed HARBAOUI ISAMM C