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 avance rappels complexite

Algorithmique Avancée Cours I Rappel Complexité Hadda CHERROUN Dépt d ? informatique Université Amar Telidji Laghouat hadda cherroun mail lagh-univ dz Septembre CPlan Vocabulaire et Dé ?nitions Complexité théorique Variantes complexité Vocabulaire et Dé ?nitions Complexité théorique Variantes complexité H CHERROUN Algorithmique Avancée CVocabulaire et Dé ?nitions Complexité théorique Variantes complexité Analyse d ? un l ? algorithme Correction Véri ?er sa correction vis-a-vis du problème c à d qu ? il donne bien la solution attendue Complexité s ? assurer que le temps d ? exécution et l ? espace mémoire qu ? il demande sont compatibles avec les performances demandés H CHERROUN Algorithmique Avancée CVocabulaire et Dé ?nitions Complexité théorique Variantes complexité Analyse d ? un l ? algorithme Correction Véri ?er sa correction vis-a-vis du problème c à d qu ? il donne bien la solution attendue Complexité s ? assurer que le temps d ? exécution et l ? espace mémoire qu ? il demande sont compatibles avec les performances demandés Intérêt de commencer par ces analyses Préciser les actions à entreprendre sans être encombrer des détails trop précis de l ? implémentation en machine H CHERROUN Algorithmique Avancée CProblème Vocabulaire et Dé ?nitions Complexité théorique Variantes complexité On désigne par Problème une Question comportant un ou plusieurs paramètres Exemple Tri d ? un tableau de n éléments Calcul de la somme des éléments d ? une matrice de n lignes et m colonnes Quel est le plus court chemin entre deux sommets données d ? un graphe Quel est le maximum d ? une liste L de t éléments H CHERROUN Algorithmique Avancée CVocabulaire et Dé ?nitions Complexité théorique Variantes complexité Taille d ? un problème Exemple Problème du tri d ? un tableau de n éléments ?? la taille c ? est n La Taille d ? un problème est une ou plusieurs variables exprimées en fonction des paramètres du problème Somme des éléments d ? une matrice ?? taille c ? est le couple n m Le Problème du plus court chemin entre deux sommets données d ? un graphe ?? Taille le couple n m n le nombre de sommets et m le nombre d ? arcs H CHERROUN Algorithmique Avancée CVocabulaire et Dé ?nitions Complexité théorique Variantes complexité Instance d ? un problème soit P un problème une instance de P serait alors caractérisée par un ensemble de données concret E e en Exemple Problème du tri d ? un tableau T de n éléments ?? une Instance I serait le problème avec ces données n et T Somme des éléments d ? une matrice A ?? un exemple d ? instance le couple n F EE F F F F F FB m A H CHERROUN Algorithmique Avancée CComplexité Vocabulaire et Dé ?nitions Complexité théorique Variantes complexité On cherche estimé ou comprendre le comportement de notre algorithme en fonction des variations de la taille du problème H CHERROUN Algorithmique Avancée CVocabulaire et Dé ?nitions Complexité théorique Variantes complexité Complexité Pratique