Remerciez-le!

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

Csi2514 4x conception et analyse des algorithmes

ANALYSE D ? ALGORITHMES ? Révision mathématique rapide ? Temps d ? exécution ? Pseudo-code ? Analyse d ? algorithmes ? Notation asymptotique ? Analyse asymptotique T n n Entrée Algorithme Sortie Analyse d ? algorithmes Cas moyen vs Pire des cas Temps d ? exécution d ? un algorithme ? Un algorithme peut être plus performant avec certains ensembles de données qu ? avec d ? autres ? Trouver le cas moyen peut s ? avérer di ?cile alors les algorithmes sont mesurés typiquement selon la complexité temporelle du pire des cas ? De plus pour certain domaines d ? application par ex contrôle aérien chirurgie gestion de réseau conna? tre la complexité temporelle du pire des cas est d ? importance cruciale Temps ms pire des cas ms cas moyen ms meilleur des cas ms ms ABCDE F G Entrée Analyse d ? algorithmes Mesurer le temps d ? exécution ? Comment devrions-nous mesurer le temps d ? exécution d ? un algorithme ? Étude expérimentale - Écrivez un programme qui réalise l ? algorithme - Exécutez le programme avec des ensembles de données de taille et de contenu variés - Utilisez une méthode System currentTimeMillis pour mesurer précisément le temps d ? exécution - Les mesures résultantes devraient ressembler à t ms Analyse d ? algorithmes n Au-delà des études expérimentales ? Les études expérimentales ont quelques restrictions - Il est nécessaire de réaliser et de tester l ? algorithme a ?n de déterminer son temps d ? exécution - Les essais peuvent être faits seulement sur un ensemble limité d ? entrées et ils peuvent ne pas être indicatifs du temps d ? exécution d ? autres entrées non considérées - A ?n de comparer deux algorithmes les mêmes environnements matériel et logiciel devraient être utilisés ? Nous développerons maintenant une méthodologie générale pour analyser le temps d ? exécution d ? algorithmes qui - Utilise une description de haut niveau de l ? algorithme au lieu de tester sa réalisation - Considère toutes les entrées possibles - Permet d ? évaluer l ? e ?cacité d ? un algorithme indépendamment des environnements matériels et logiciels Analyse d ? algorithmes CPseudo-code ? Le pseudo-code est une description d ? algorithme qui est plus structurée que la prose ordinaire mais moins formelle qu ? un langage de programmation ? Exemple trouver l ? élément maximal d ? un vecteur array Algorithm arrayMax A n Entrée Un vecteur A contenant n entiers Sortie L ? élément maximal de A currentMax A for i to n ?? do if currentMax A i then currentMax A i return currentMax ? Le pseudo- code est notre notation de choix pour la description d ? algorithmes ? Cependant le pseudo-code cache plusieurs problèmes liés à la conception de programmes Qu ? est-ce que le pseudo-code ? Un mélange de langage naturel et de concepts de programmation de haut niveau qui décrit les idées générales derrière la réalisation générique d ? une structure