Remerciez-le!

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

Support de cours Algorithmique avancé Page 1 sur 79 Algorithmique avancé Dr MAM

Support de cours Algorithmique avancé Page 1 sur 79 Algorithmique avancé Dr MAMBE Moïse Support de cours Algorithmique avancé Page 2 sur 79 Sommaire I Eléments de base du langage __________________________________________________ 4 I.1 Qualités d'un algorithme __________________________________________________________ 4 I.2 L’alphabet du langage _____________________________________________________________ 5 I.3 Les opérateurs ___________________________________________________________________ 5 I.4 Les identificateurs ________________________________________________________________ 5 I.5 Les mots réservés ________________________________________________________________ 6 I.6 Les nombres ____________________________________________________________________ 6 I.7 Les commentaires ________________________________________________________________ 6 II Structure d’un algorithme _____________________________________________________ 6 II.1 Exemple d’algorithme __________________________________________________________ 7 II.2 Tête de l’algorithme ____________________________________________________________ 7 II.3 Déclaration de constantes _______________________________________________________ 7 II.4 Déclaration de type ____________________________________________________________ 7 II.5 Les types simples ______________________________________________________________ 8 II.6 Le type tableau ________________________________________________________________ 9 II.7 Déclaration de variables ________________________________________________________ 11 II.8 Corps de l’algorithme __________________________________________________________ 11 III Les sous-algorithmes ________________________________________________________ 17 III.1 Définition ___________________________________________________________________ 17 III.2 Procédure ___________________________________________________________________ 18 III.3 Fonction ____________________________________________________________________ 20 III.4 Mode de passage des paramètres ________________________________________________ 21 IV Terminaison et correction des algorithmes itératifs _______________________________ 23 IV.1 Notation ____________________________________________________________________ 23 IV.2 Propriété de l’affectation _______________________________________________________ 23 IV.3 Propriété de l’enchaînement ____________________________________________________ 24 IV.4 Propriété de l’alternative _______________________________________________________ 25 IV.5 Propriété de la répétition _______________________________________________________ 26 IV.6 Terminaison de la boucle TANTQUE ______________________________________________ 27 V Analyse des algorithmes _____________________________________________________ 30 V.1 Complexité temporelle _________________________________________________________ 30 V.2 Complexité spatiale ___________________________________________________________ 38 VI Algorithmes récursifs________________________________________________________ 41 VI.1 Efficacité de la récursivité ? _____________________________________________________ 46 VI.2 Récursivité directe ____________________________________________________________ 41 Support de cours Algorithmique avancé Page 3 sur 79 VI.3 Analyse récursive _____________________________________________________________ 41 VI.4 Quelques algorithme récursifs simples ____________________________________________ 41 VI.5 Complexité des algorithmes récursifs _____________________________________________ 45 VI.6 Terminaison et correction des algorithmes récursifs _________________________________ 47 VI.7 Réalisation de la récursivité _____________________________________________________ 48 VI.8 Transformation des boucles en algorithmes récursifs ________________________________ 48 VI.9 Transformation des algorithmes récursifs en algorithmes itératifs ______________________ 48 VI.10 Récursivité est efficacité _______________________________________________________ 53 VII Méthode d’analyse des algorithmes _________________________________________ 55 VII.1 Analyse descendante __________________________________________________________ 55 VII.2 Analyse ascendante ___________________________________________________________ 57 VII.3 Critique des deux méthodes ____________________________________________________ 57 VIII Diviser pour régner _______________________________________________________ 60 VIII.1 Questions/Réponses _______________________________________ Erreur ! Signet non défini. VIII.2 Principe __________________________________________________ Erreur ! Signet non défini. VIII.3 Applications ______________________________________________ Erreur ! Signet non défini. VIII.4 Recommandations générales sur "Diviser pour Résoudre" ____________________________ 67 IX Programmation dynamique __________________________________________________ 68 X Algorithmes gloutons _______________________________________________________ 74 XI Heuristiques _____________________________________________ Erreur ! Signet non défini. XII Bibliographie ____________________________________________________________ 79 Support de cours Algorithmique avancé Page 4 sur 79 I Introduction Le but de l'algorithmique peut être résumé comme suit : Trouver un "bon" algorithme pour un problème donné. Cela nécessite souvent des connaissances. La plupart du temps, un algorithme connu peut être adapté au problème et il vaut mieux éviter de réinventer la roue du savoir-faire. Trouver un "bon" algorithme soulève pas mal de questions : • Existe-t-il un algorithme pour résoudre le problème en un temps fini ? (calculabilité, indécidabilité). • Le problème est-il un "classique"? (modélisation, connaissances) • Comment concevoir un algorithme? Il n'y a pas de méthode miracle mais on peut identifier quelques paradigmes, patrons d'algorithmes, classes d'algorithmes. • L'algorithme A apporte-t-il bien la réponse au problème donné? (correction des algorithmes) • Que dire des ressources utilisées par l'algorithme A? (analyse d'algorithmes) • L'algorithme A est-il "raisonnablement" efficace pour le problème donné? Pourrait-on faire beaucoup mieux? Que peut-on dire des ressources minima nécessaires pour résoudre le problème donné? (complexité des problèmes) L'objectif du cours est de vous donner quelques éléments de réponse. II Eléments de base du langage Pour écrire un algorithme, il faut un langage algorithmique constitué d’un vocabulaire et de règles syntaxiques. Ce langage doit être : • spécialisé : pour écrire des algorithmes, pas des poèmes ni des recettes de cuisine ; • de haut niveau : déchargé de détails techniques (ce n'est pas un langage de programmation) ; • concis :"si ça ne tient pas en une page, c'est que c'est trop long" ; • modulaire ; • typé. II.1 Qualités d'un algorithme • Qualité d'écriture : un algorithme doit être structuré, indenté, modulaire, avec des commentaires pertinents, etc. Il faut pouvoir comprendre la structure d'un coup d'œil rapide, et pouvoir aussi revenir dessus 6 mois plus tard et le comprendre encore ; • Terminaison : le résultat doit être atteint en un nombre fini d'étapes. Il ne faut donc pas de boucles infinies, il faut étudier tous les cas possibles de données, ... ; • Validité : le résultat doit répondre au problème demandé. Attention, un jeu d'essais ne prouve jamais qu'un programme est correct. Il peut seulement prouver qu'il est faux ; • Performance : étude du coût (complexité) en temps et en mémoire. La complexité en mémoire (c'est à dire la place mémoire prise par l'algorithme) est un problème de moins en moins primordial vu les capacités techniques actuelles. On sait que certains problèmes n'admettent pas de solutions, et que d'autres ont des solutions qui nécessitent beaucoup de temps d'exécution (et sont donc en fait irréalisables), même avec les ordinateurs actuels. Support de cours Algorithmique avancé Page 5 sur 79 On distingue la complexité en moyenne et la complexité dans le pire des cas (parfois on s'intéresse aussi au meilleur des cas mais). Ce n'est pas le même problème, mais les deux sont parlants. II.2 L’alphabet du langage L’alphabet du langage est constitué des caractères utilisables dans l’écriture d’un algorithme, ce sont : • les lettres de l’alphabet : a - z ou A - Z ; • les chiffres : 0 - 9 ; • les caractères spéciaux : #, $, ;. II.3 Les opérateurs On distingue 4 types d’opérateurs : II.3.1 Les opérateurs arithmétiques + Addition - Soustraction * Multiplication DIV Division entière / Division réelle % (modulo) reste d’une division entière II.3.2 Les opérateurs relationnels Opérateur égalité différence infériorité stricte infériorité large supériorité supériorité large Symbole = ≠ < ≤ > ≥ II.3.3 Les opérateurs logiques Opérateur Et logique Ou logique Non logique Symbole ET OU NON II.3.4 Les opérateurs de manipulation de chaînes de caractères Opérateur Concaténation Symbole & ou + II.4 Les identificateurs Ce sont des mots choisis par le concepteur de l’algorithme pour représenter les objets de l’algorithme (ex. nom de l’algorithme, nom de variable, …). Un identificateur est constitué d’une suite de caractères alphanumériques dont le premier est obligatoirement une lettre de l’alphabet ou le caractère de soulignement. Priorité - + Support de cours Algorithmique avancé Page 6 sur 79 Un identificateur doit être expressif c’est-à-dire, choisi de telle sorte qu’il désigne bien l’objet qu’il représente. Exemple : prix_TTC, valeur_max, deuxPI Contre exemple : 2PI Il n’y a pas de distinction entre minuscule et majuscule. Par exemple les identificateurs Prix_TTC, PRIX_TTC, prix_ttc désignent le même objet. II.5 Les mots réservés Ce sont des identificateurs prédéfinis du langage algorithmique ; ils ne doivent pas être utilisés comme identificateur dans un algorithme. Exemple : ALGORITHME, FONCTION, TANTQUE, POUR Remarque : Par convention, les mots réservés seront écrits en majuscules ainsi que le premier caractère des constantes. II.6 Les nombres On distingue deux types de nombre : les entiers et les réels. Ex. 125 (entier), 3.1459, 15 E-3 (réels). II.7 Les commentaires Un commentaire peut être inséré dans un algorithme afin de faciliter sa lecture et sa maintenance. Il commence par une parenthèse ouvrante accolé au caractère *, suivi du texte du commentaire. Il se termine par le caractère * accolé à une parenthèse fermante. Exemple : (* prix_TTC désigne le prix Toute Taxe Comprise *) Remarque : Il ne peut pas avoir d’imbrication de commentaire. III Structure d’un algorithme Support de cours Algorithmique avancé Page 7 sur 79 III.1 Exemple d’algorithme FONCTION fact(D n :ENTIER) :ENTIER VAR i, f: ENTIER DEBUT SI (n = 0) OU (n = 1) ALORS f ← 1 SINON DEBUT f ← 1 POUR i ← 2, n f ← f * i FIN fact ← f FIN ALGORITHME factoriele VAR m, res : ENTIER DEBUT ECRIRE('Entrer un entier positif :' ) LIRE(m) res ← fac(m) ECRIRE(m, ' ! = ', res) FIN Un algorithme comprend 4 parties : • déclaration de sous-algorithme (facultative) • tête de l’algorithme • déclaration des objets (facultative) • corps de l’algorithme III.2 Tête de l’algorithme Il s’agit de donner un nom (ayant une relation avec le but de l’algorithme) à l’algorithme précédé du mot réservé ALGORITHME. Ex. : ALGORITHME factorielle Tout objet manipulé par l’algorithme devra avoir été déclaré avant son utilisation dans le corps de l’algorithme. Les différents objets sont : les types, les constantes et les variables. III.3 Déclaration de constantes Une constante est un espace mémoire désigné par un identificateur et utilisé pour désigner une valeur fixe d’un ensemble donnée. Cette valeur reste inchangée tout au long de l’exécution de l’algorithme. Syntaxe : CONST identificateur = expression Exemples : CONST Pi = 3.1459 Nbre_mois = 12 Ecole = ‘INP-HB’ Omega = 100 * Pi III.4 Déclaration de type Un type est constitué par un ensemble de valeurs et par des opérateurs définis sur cet ensemble. Support de cours Algorithmique avancé Page 8 sur 79 Syntaxe TYPE Identificateur = nom du type La figure présente les différentes sortes de type uploads/Management/ algorithmique-avance.pdf