Remerciez-le!

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

Complexite fst 2010 Théorie de la Complexité H Hasni Ecole Nationale des Sciences de l ?Informatique Université de Manouba Campus Universitaire ? Manouba E-mail hamadi hasni ensi rnu tn CPlan Qu est-ce que la complexité Modèles Abstraits de Calcul Machine

Théorie de la Complexité H Hasni Ecole Nationale des Sciences de l ?Informatique Université de Manouba Campus Universitaire ? Manouba E-mail hamadi hasni ensi rnu tn CPlan Qu est-ce que la complexité Modèles Abstraits de Calcul Machines de Turing Problèmes de Décision Classes de Complexité Réductions de Problèmes NP-Complétude Exemples de Problèmes NP-Complets Exemples de Réduction P NP Que faire devant un Problème NP Classe de Complexité co-NP C F Introduction La théorie de la complexité s intéresse à l étude formelle de F la di ?culté des problèmes en informatique G? del premier théorème d incomplétude toute théorie contient des énoncés non F démontrables Turing Church réponse négative au problème de la F décision cf machine de Turing et le problème de l arrêt Edmonds Distinction entre les problèmes P et NP Cook - Levin NP F Complétude Problème SAT Karp Liste de nouveaux problèmes F NP-Complet Aujourd hui la conjecture P NP fait partie des problèmes du millénaire C F Qu est ce que la complexité Question centrale de l Informatique F F théorique Limites des Ordinateurs Limites fondamentales indépendantes F de la technologie Peut-on identi ?er les problèmes de calcul qui sont hors de portée CQu est ce que la complexité Taille n Entrées Opérations élémentaires Algorithme Résultat Temps Ressources Espace C F F Qu est ce que la complexité Complexité En pratique un F algorithme consomme une quantité raisonnable de ressources de calcul F F F Nombre d opérations Temps de calcul Quantités de mémoire Complexité quantité minimale de ressources nécessaire à sa résolution C F Qu est ce que la complexité Les notions de temps de traitement F d espace sont dépendant de la machine physique utilisée Besoin d une F mesure absolue indépendante de toute implémentation Facteurs de temps F F F de calcul Taille de l entrée Ordinateur utilisé Langage de programmation utilisé C F Modèles Abstraits de Calcul Théorie robuste indépendante de la F F machine Nécessité de s entendre sur des modèles de calcul Dé ?nition F formelle de la notion d algorithme Modèles abstraits de Calcul F F F Machine de Turing Machine de Post Fonctions récursives de Kleene P- F calcul de Church Machine RAM Tous ces modèles sont équivalents Remarque Toutes les architectures de machines réelles sont équivalentes à la machine de Turing elles sont plus puissantes ? mais pas plus expressives ? C E E Modèles Abstraits de Calcul Théorie de la Complexité Classi ?cation des problèmes suivant le temps et l espace nécessaire à la résolution de l instance la plus dure ? du problème sur un modèle théorique machine de Turing C F Machines de Turing Alan Matheson Turing Inventeur de F la Machine de Turing Machine ENIGMA CMachines de Turing F Machines de Turing E Dé ?nition Une machine de TURING déterministe MTD est donnée E par M Q H q F o? Q est un ensemble ?ni d état E est un alphabet E E alphabet d entrée E E F Q est