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 algorithmique Mr Radouane CHAHIN 1 Année Académique 2017-2018 Site web :h

Cours algorithmique Mr Radouane CHAHIN 1 Année Académique 2017-2018 Site web :https://sites.google.com/a/uca.ma/r-chahin Objectif • Objectif : • Apprendre les concepts de base de l'algorithmique et de la programmation • Être capable de mettre en œuvre ces concepts pour analyser des problèmes simples et écrire les programmes correspondants • Savoir expliciter et formaliser son raisonnement • obtenir de la «machine» qu’elle effectue un travail à notre place • On traite deux syntaxes pseudocode Logiciel Pratiquer l'Algorithmique 12 et python • Problème: expliquer à la «machine» comment elle doit s'y prendre Mais... comment le lui dire ? Comment le lui apprendre ? Comment s'assurer qu'elle fait ce travail aussi bien que nous ? Mieux que nous? Outils: Logiciel Pratiquer l'Algorithmique 12 : http://fr.lagache.free.fr/algo/telechargement.php 2 Plan du cours • Introduction à l’algorithmique et à la programmation • Généralités sur l’algorithmique et les langages de programmation • Introduction à la complexité des algorithmes • Algorithmique : Processus de développement • Méthode de recherche d'un algorithme • Notion de variable, affectation, lecture et écriture • Instructions conditionnels et instructions itératives • Les tableaux, les fonctions et procédures, la récursivité • Données structurées • Techniques Rusées 3 Définition : Programme informatique • Un programme correspond à la description d’une méthode de résolution pour un problème donné. • Cette description est effectuée par une suite d’instructions d’un langage de programmation • Ces instructions permettent de traiter et de transformer les données (entrées) du problème à résoudre pour aboutir à des résultats (sorties). • Un programme n’est pas une solution en soi mais une méthode à suivre pour trouver les solutions. 4 Langages informatiques • Un langage informatique est un code de communication, permettant à un être humain de dialoguer avec une machine en lui soumettant des instructions et en analysant les données matérielles fournies par le système. • Le langage informatique est l’intermédiaire entre le programmeur et la machine. • Il permet d’écrire des programmes (suite consécutive d’instructions) destinés à effectuer une tache donnée • exemple : un programme de résolution d’une équation du second degré • Programmation : ensemble des activités orientées vers la conception, la réalisation, le test et la maintenance de programmes. • Deux types de langages: • Langages procéduraux : Fortran, Cobol, Pascal, C, … • Langages orientés objets : C++, Java, C#,… • Le choix d'un langage de programmation n'est pas facile, chacun a ses spécificités et correspond mieux à certains types d'utilisations 5 L'algorithmique, vous la pratiquez tous les jours et depuis longtemps... 6 Notion d’algorithme • Un programme informatique permet à l’ordinateur de résoudre un problème • Avant de communiquer à l’ordinateur comment résoudre ce problème, il faut en premier lieu pouvoir le résoudre nous même • Un algorithme peut se comparer à une recette de cuisine • Le résultat c’est comme le plat à cuisiner • Les données sont l’analogues des ingrédients de la recette • Les règles de transformations se comparent aux directives ou instructions de la recette 7 Algorithme informatique • Un algorithme est une suite finie et non-ambiguë d’instructions ayant pour but de résoudre un problème donné. Ces instructions doivent être exécutées de façon automatique par un ordinateur. • Un algorithme est une méthode générale pour résoudre un ensemble de problèmes. Il est dit correct lorsque, pour chaque instance du problème, il se termine en produisant la bonne sortie, c'est-à-dire qu'il résout le problème posé • un algorithme doit donc contenir uniquement des instructions compréhensibles par celui qui devra l’exécuter 8 Algorithme informatique: propriété • Un algorithme doit: • avoir un nombre fini d’étapes, • avoir un nombre fini d’opérations par étape, • se terminer après un nombre fini d’opérations, • fournir un résultat. • Chaque opération doit être: • définie rigoureusement et sans ambiguïté • effective, c-à-d réalisable par une machine • Le comportement d'un algorithme est déterministe. 9 Analyse d’algorithmes Analyser un algorithme = évaluer son efficacité Efficacité ? • Temps d'exécution : complexité en temps • Espace mémoire occupé : complexité en espace • Qualité du résultat : • correction : si l’algorithme termine en donnant une proposition de solution, alors cette solution est correcte. • complétude : pour un espace de problèmes donné, l’algorithme, s’il termine, donnera toujours des propositions de solutions. • Simplicité …. 10 Théorie de la complexité (informatique théorique) • La théorie de la complexité est un domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement la quantité de ressources (en temps et en espace) nécessaire pour la résolution de problèmes au moyen de l'exécution d'un algorithme. Il s'agit donc d'étudier la difficulté intrinsèque de problèmes posés mathématiquement. • L'analyse de la complexité est étroitement associée à un modèle de calcul: • la machine de Turing, le modèle de calcul le plus utilisé • la machine RAM (Random Access Machine). • Mesure de la complexité : Les mesures les plus classiques de la complexité d'un algorithme sont le temps et l'espace utilisés. D'autre mesures existent, sur les communications par exemple. • Règle de calcul de la complexité (nombre d’opérations de base): est exprimée sous la forme du nombre d'opérations effectuées par celui-ci. En général, ce nombre dépend des données d'entrée. • Nous noterons dorénavant T nomalgo (d) est le nombre d’opérations élémentaires pour exécuter l’algorithme sur la donnée d’entrée d • Classes de complexité : • complexité en temps et en espace: TIME, NTIME, SPACE, NSPACE • Classes en temps: P, NP, EXPTIME, NEXPTIME • Classes en espace : L, NL, PSPACE, EXPSPACE 11 Théorie de la complexité : Fonction asymptotique La famille de notations de Landau O, o, Ω, Θ Notation Nom Description informelle Lorsque , à partir d'un certain rang... Grand O (Grand Omicron) La fonction |f | est bornée par la fonction |g| asymptotiquement, à un facteur près pour un k > 0 Définition rigoureuse Grand Omega En théorie des algorithmes : f est minorée par g (à un facteur près) En théorie des algorithmes : pour un k > 0 Définition rigoureuse Grand Theta f est dominée et soumise à g asymptotiquement pour un k1 > 0, et un k2 > 0 Définition rigoureuse Petit o f est négligeable devant g asymptotiquement , quel que soit > 0 (fixé). Définition rigoureuse 12 Exemple: la complexité en temps • La complexité en temps (temps d'exécution) d’un algorithme dépend de : • la taille des données d’entrée • Les valeur des données(diverses exécutions peuvent avoir temps d'exécutions diverses) • Considère touts les entrées est indépendant des environnements matériels et logiciels • Différentes approches calcul dans: • le pire des cas Tmax nomalgo (d) , • le moyenne Tmoy nomalgo (d), • le meilleur cas Tmin nomalgo (d), • Exemple: la recherche dans un dictionnaire 1. Recherche linéaire : parcourir les pages dans l'ordre (alphabétique) jusqu'à trouver le nom cherchépire le dernier mot, meilleur le premier mot de dictionnaire 2. Recherche dichotomique : ouvrir l'annuaire au milieu, si le nom qui s'y trouve est plus loin alphabétiquement que le nom cherché, regarder avant, sinon, regarder après. Refaire l'opération qui consiste à couper les demi- annuaires (puis les quarts d'annuaires, puis les huitièmes d'annuaires, etc.) jusqu'à trouver le nom cherché. 13 complexité : Ordre de grandeur • Ordre de grandeur du temps nécessaire à l'exécution d'un algorithme d'un type de complexité 14 Temps Type de complexité Temps pour n = 5 Temps pour n = 10 Temps pour n = 20 Temps pour n = 50 Temps pour n = 250 Temps pour n = 1 000 Temps pour n = 10 00 0 Temps pour n = 1 000 000 Problème exemple complexité logarithmique 10 ns 10 ns 10 ns 20 ns 30 ns 30 ns 40 ns 60 ns Dichotomie complexité linéaire 50 ns 100 ns 200 ns 500 ns 2.5 µs 10 µs 100 µs 10 ms Parcours de liste complexité quasi- linéaire 50 ns 100 ns 200 ns 501 ns 2.5 µs 10 µs 100,5 µs 10 050 µs Triangulation de Delaunay complexité linéarithmique 40 ns 100 ns 260 ns 850 ns 6 µs 30 µs 400 µs 60 ms Tris dont le Tri fusion ou le Tri par tas complexité quadratique (polynomiale) 250 ns 1 µs 4 µs 25 µs 625 µs 10 ms 1 s 2.8 heure s Parcours de tableaux 2D complexité cubique (polynomiale) 1.25 µs 10 µs 80 µs 1.25 ms 156 ms 10 s 2.7 heure s 316 ans Multiplication matricielle non- optimisée. complexité exponentielle 320 ns 10 µs 10 ms 130 jours ans ... ... ... Problème du sac à dos par force brute. complexité factorielle 1.2 µs 36 ms 770 ans an s ... ... ... ... Problème du voyageur de commerce (avec une approche naïve). Classes de complexité :Rappelle mathématique 1/2 • Dans ce cours on va utiliser que la fonction O (Fonction asymptotique la plus petite) de et à la complexité au pire de cas Tmax. 1. Rappelle mathématique: Propriétés fonction asymptotique • O(f(n))+O(g(n))=O(f(n)+ g(n)) • O(1)+O(1)+O(1)= O(1) • O(1)+……+O(1)= O(n) n fois • O(n3)>O(n2)>O(nlog(n))>O(n)>O(log(n)) • O(3n3+n2+5)=O(3n3)+O(n2)+O(5)=O(n3) • f(n) = nlog(n) + 12n uploads/Industriel/ cours-algorithmique-chahin.pdf