Remerciez-le!

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

Cours complexite algo 3lfiag 2020 2021 drmounajouini

Cours Complexité Algorithmique Dr Mouna Jouini Mail jouini mouna yahoo fr A U - CPlan du cours ? Chap- Eléments de base de la complexité algorithmique ? Chap- Complexité optimalité ? Chap- Complexité des classes CObjectifs du cours ? Ma? triser la démarche diviser pour régner ? ? Savoir estimer la complexité d ? un algorithme itératif ou récursif pouvant conduire à des récurrences linéaires d ? ordre d ? ordre et des récurrences de type diviser régner ? ? Conna? tre les di ?érents algorithmes et estimer leur complexité CChapitre ??Eléments de base de la complexité algorithméque CIntroduction ? Un algorithme une suite ordonnée d'instruction écrites pour la résolution d'un problème donné ? Algorithme une suite d ? actions que devra e ?ectuer un automate pour arriver à partir d ? un état initial en un temps ?ni à un résultat ? Une structure de données indique la manière d'organisation des données dans la mémoire CIntroduction ? Le choix d'une structure de données adéquate dépend généralement du problème à résoudre ? Deux types de structures de données ? Statiques Les données peuvent être manipulées dans la mémoire dans un espace statique alloué dès le début de résolution du problème Ex les tableaux ? Dynamiques On peut allouer de la mémoire pour y stocker des données au fur et à mesure des besoins de la résolution du problème Ex liste chainée pile ?le ? CIntroduction Qu ? est-ce qu ? un problème ? Commençons par donner quelques exemples de problèmes ? déterminer si un nombre naturel n est pair ou impair ? calculer le PGCD de deux nombres naturels m et n ? étant donné un graph G et deux sommets m et n de ce graphe déterminer s ? il existe un chemin menant de m à n dans ce graphe CIntroduction Problèmes de décision ? Un problème est dit de décision si la réponse aux instances du problème est soit oui soit non Exemples ? Déterminer si oui ou non un nombre entier n est pair est un problème de décision ? Par contre déterminer la longueur minimale du circuit qui passe par tous les sommets d ? un graphe n ? est pas un problème de décision mais un problème d ? optimisation CCaractéristiques d ? un algorithme ? Simplicité et intelligibilité de l ? algorithme ? E ?cacité de l ? algorithme ? Temps d ? exécution ? Quantité d ? espace disque occupée par les variables ? Quantité de tra ?c généré sur un réseau ? Quantité de données déplacées sur le disque ? Temps d ? exécution versus place mémoire occupée CCaractéristiques d ? un algorithme ? Pour résoudre un problème donné on veut un algorithme ?? correct Trouver une solution exacte ou approchée ?? e ?cace Analyser la complexité d ? un algorithme CRésolution d ? un problème ? Pour résoudre un problème ? Connaitre les notions de calculabilité et de décidabilité ? Le problème est il classique tri recherche dans des graphes