Chapitre 1: Introduction a l'algorithmiqueBrice Mayagbrice.mayag@dauphine.frM1 SIEEBrice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 1 / 59Sommaire1Presentation du cours2Introduction et denitionsPourquoi l'etude des algorithmes?Denitions3Paradigmes et langages de programmation4Fondements des langages : la recursiviteAlgorithmes recursifs5Le langage PythonBrice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 2 / 59Presentation du coursSommaire1Presentation du cours2Introduction et denitionsPourquoi l'etude des algorithmes?Denitions3Paradigmes et langages de programmation4Fondements des langages : la recursiviteAlgorithmes recursifs5Le langage PythonBrice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 3 / 59Presentation du coursProgramme du coursLes grandes notionsLes bases de l'algorithmiqueLa recursivite et le paradigmeDiviser pour RegnerStructures de donnees basiques et avancees : listes, les, piles, tas,arbres de rechercheApplication au ltrage collaboratifEvaluationExamenBrice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 4 / 59Introduction et denitionsSommaire1Presentation du cours2Introduction et denitionsPourquoi l'etude des algorithmes?Denitions3Paradigmes et langages de programmation4Fondements des langages : la recursiviteAlgorithmes recursifs5Le langage PythonBrice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 5 / 59Introduction et denitionsPourquoi l'etude des algorithmes?L'algorithmique?Denition (informelle)Un algorithme est la composition d'un ensemble ni d'etapes, chaqueetape etant formee d'un nombre ni d'operations dont chacune est :denie de facon rigoureuse et non ambigue;eective (i.e. pouvant ^etre realisee en un temps ni).La notion d'algorithme est plus generale que celle de programme(independant du langage de programmation utilise).Un peu d'histoireLe mot algorithme vient du nom du mathematicien Al Khwarizmi (820) :introduction de la numerotation decimale et des calculs s'y rapportant.Brice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 6 / 59Introduction et denitionsPourquoi l'etude des algorithmes?Des besoins contradictoiresUn algorithme doit :^etre simple a comprendre, a mettre en oeuvre et a mettre au point;mettre intelligement a contribution les ressources de l'ordinateur, etplus precisement, il doit s'executer rapidement.Brice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 7 / 59Introduction et denitionsDenitionsUn algorithme : c'est quoi?Classiquement assimilable a une recette de cuisineBrice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 8 / 59Introduction et denitionsDenitionsAlgorithme : denitionsUn algorithme =Description precise des operations a faire pour resoudre un probleme (suited'instructions).Procedure de calcul bien denie qui prend en entree une valeur, ou un ensemble devaleurs et qui donne en sortie une valeur, ou un ensemble de valeurs.Unbonalgorithme =Un algorithmeco rrect: i.e. p ourchaqu ei nstanceen entr ee,l'alg orithmese termine en produisant la bonne sortie)Savoir prouver un algorithmeUn algorithmeecace : mesure de la dur eeque met un algo rithmep ourp roduireun resultat)Savoir analyser la complexite d'un algorithme : i.e. determination de l'espacememoire et du temps d'execution necessaire a la resolution du probleme.Pour un probleme donne,plusieurs algo rithmesou aucun sont p ossibles.Un algorithme se termine en untemps ni .Brice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 9 / 59Introduction et denitionsDenitionsUn exemple simpleProbleme de triDonnees : une suite de n nombres, (e0;e1;:::;en1)Resultat : permutation de la suite donnee en entree (e00;e01;:::;e0n1)de telle sorte quee00e01:::e0n1Principe du tri par insertionOn parcourt entierement la liste en appliquant a chaque iteration lastrategie suivante :Recherche de la place du ieme elementBrice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 10 / 59Introduction et denitionsDenitionsTri par insertionPrincipeOn veut trier la liste :327151On part du constat que liste[0 0] est triee327152On met l'element d'indice 1 a sa place dans la liste[0 1]237153liste[0 1] est maintenant triee.
On recommence a l'etape 2 avecl'element suivant.Exemple : Trier la liste de nombres[65;15;34;3;25;22;63;3;66;17].Brice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 11 / 59Introduction et denitionsDenitionsUn algorithme simpleConsiderons un tableauAcontenant une sequence a trier de longueurnAlgorithm 1TRI-INSERTION (A)1:forj 2 tondo2:key A[j]3:i j14:whilei>0 andA[i]>key do5:A[i+ 1] A[i]6:i i17:end while8:A[i+ 1] key9:end forOn verra comment implanter cet algorithme en PythonBrice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 12 / 59Introduction et denitionsDenitionsAnalyse d'un algorithmeSimplicite et intelligibilite de l'algorithmeEcacite de l'algorithme :Temps d'executionOccupation de la memoireQuantite de trac genere sur un reseauQuantite de donnees deplacees sur le disque Brice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 13 / 59Introduction et denitionsDenitionsComplexite d'un algorithmePermet de quantier les algorithmesDeux types de complexite :En espace: Quelle quantite de place en memoire va t-on utiliser?En temps: Combien d'operations va t-on eectuer?Inter^et :comparer deux algorithmesBrice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 14 / 59Introduction et denitionsDenitionsMesurer le temps d'executionLe temps d'execution depend de l'entree : par exemple dans le casd'un algorithme de tri, si le tableau est deja trie.On cherche une fonctionT(n) representant letemps d'executiond'un algorithme en fonction de lataille de l'entreen(nombred'elements constituant l'entree, nombre de bits necessaire a larepresentation de l'entree, )Le calcul exact etant souvent impossible a apprehender exactement,on s'interesse aux :Meilleur des casPire de casCas moyen : necessite d'avoir des connaissances sur la distributionstatistique des entreesBrice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 15 / 59Introduction et denitionsDenitionsMesurer le temps d'executionCas du tri par insertionAlgorithm 2TRI-INSERTION (A)1:forj 2 tondo2:key A[j]3:i j14:whilei>0 andA[i]>key do5:A[i+ 1] A[i]6:i i17:end while8:A[i+ 1] key9:end forSoitci, leco^uttemporel de chaque instruction.
On a alors :T(n) =c1n+c2(n1)+c3(n1)+c4Pnj=2tj+c5Pnj=2(tj1)+c6Pnj=2(tj1)+c7(n1)tjnombre de fois que le test de la boucleWhileest executee pour cette valeur dejBrice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 16 / 59Introduction et denitionsDenitionsMesurer le temps d'executionCas du tri par insertionCas le plus favorable: le tableau est deja trie et donc pour toutj= 2::non atj= 1.Temps d'execution :T(n) = (c1+c2+c3+c4+c7)n(c2+c3+c4+c7)Temps sous la formean+b:fonction lineaire de n.Cas le plus defavorable: la tableau est trie dans l'ordre decroissantdonctj=jpour toutj= 2::n.Temps d'execution :T(n) =c1n+c2(n1) +c3(n1) +c4(n(n+1)21) +c5(n(n1)2) +c6(n(n1)2) +c7(n1)Temps sous la formean2+bn+c:fonction quadratique de nBrice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 17 / 59Introduction et denitionsDenitionsClasses de complexiteAlgorithmessub-lin eaires: (log n)Algorithmeslin eaires: ( n) et (nlogn)Algorithmesp olynomiaux: ( nk)Algorithmesexp onentiels: (2 n)Brice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 18 / 59Paradigmes et langages de programmationSommaire1Presentation du cours2Introduction et denitionsPourquoi l'etude des algorithmes?Denitions3Paradigmes et langages de programmation4Fondements des langages : la recursiviteAlgorithmes recursifs5Le langage PythonBrice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 19 / 59Paradigmes et langages de programmationLangages de programmationEnsembles de mots clefs et de regles pour former des phrases pouvant ^etretraduites par la machine (binaire).Plusieurs niveauxLangages de bas niveau : instructions elementaires tresproches de lamachine(ex : Assembleur : V AX, [0110] signiecopier le contenu de0110 dans le registre AX; langage machine)Langages de haut niveau : instructions plus abstraites (C, C++, Perl,Java, Python).Brice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 20 / 59Paradigmes et langages de programmationParadigmes de programmationProcedural (imperatif)FonctionnelLogiqueOriente-objetHybrideBrice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 21 / 59Paradigmes et langages de programmationParadigmes de programmationProgrammation proceduraleDeclaration de procedures accomplissant des t^aches speciques necessairesau programme.
Les etapes sont expliquees ligne par ligne, et l'instructionatomique est l'aectationde va riables.Le p rogrammeest ex ecute.ExemplesFORTRAN,C,PASCALBrice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 22 / 59Paradigmes et langages de programmationParadigmes de programmationProgrammation fonctionnelleLangage d'utilisation et de developpement de fonctions.
Tout programmeest construit par fonctions, retournant un resultat en sortie et prenant enentree la sortie d'autres fonctions.
Le programme est evalue.Diviser un probleme complexe en sous problemesRecursiviteExemplesCAML, SCHEME, LISP, Brice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 23 / 59Paradigmes et langages de programmationParadigmes de programmationProgrammation logiqueLangage deductif utilisant des regles et des faits.
Un moteur d'inferencepermet de donner le resultat.
Le programme est une theorieaxiomatique apartir de laquelle on infere (demonstrations logiques/mathematiques) lesresultats.ExemplePROLOGBrice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 24 / 59Paradigmes et langages de programmationParadigmes de programmationCouche au-dessus des autres paradigmes de programmation.Programmation orientee-objetBasee sur le principe que des choses peuvent avoir des points communs,des similarites en elles-m^emes ou en leur facon d'agir.
On concoit desfabriques (classes) qui servent a construire des composants (objets).
Lesclasses contiennent des donnees(attributs) et des actions (methodes).ExemplesC++, JAVA, SMALLTALK, O-CAML Brice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 25 / 59Paradigmes et langages de programmationParadigmes de programmationProgrammation hybrideLangage combinant plusieurs paradigmes de programmation.ExemplesC++, JAVA, PYTHON,PERL,RUBY, Brice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 26 / 59Paradigmes et langages de programmationProduction de programmes : InterpretationInterpretationChaque ligne du code source est traduite au fur et a mesure eninstructions qui sont directement executees, i.e. l'interpreteur est utilise achaque execution.Brice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 27 / 59Paradigmes et langages de programmationProduction de programmes : CompilationCompilationCompilation = traduction du code ecrit dans un langage dit source enlangage objet ou cible (analyse lexicale, syntaxique, semantique etproduction du code objet).
L'edition de liens Brice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 28 / 59Fondements des langages : la recursiviteSommaire1Presentation du cours2Introduction et denitionsPourquoi l'etude des algorithmes?Denitions3Paradigmes et langages de programmation4Fondements des langages : la recursiviteAlgorithmes recursifs5Le langage PythonBrice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 29 / 59Fondements des langages : la recursiviteAlgorithmes recursifsAlgoritmes recursifsDenitionUn algorithme est ditr ecursifs'il s'app ellelui m ^eme.RecusivitePrincipe qui consiste a decrire les etapes necessaires a la resolution deproblemes en utilisant la resolution du m^eme probleme sur des entrees pluspetites.Brice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 30 / 59Fondements des langages : la recursiviteAlgorithmes recursifsAlgoritmes recursifs : exempleFactorielle d'un nombreOn peut denir la factorielle d'un nombre de la maniere suivante :n! =1sin1n(n1)!sinonBrice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 31 / 59Fondements des langages : la recursiviteAlgorithmes recursifsAlgoritmes recursifs : exempleFactorielle : algorithme iteratifAlgorithm 3FACTORIEL-ITERATIF (n : entier positif)1:x 12:fori 1 tondo3:x ix4:end for5:returnxBrice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 32 / 59Fondements des langages : la recursiviteAlgorithmes recursifsAlgoritmes recursifs : exempleFactorielle :algorithme recursifAlgorithm 4FACTORIEL-RECURSIF (n : entier positif)1:ifn= 1then2:return 13:else4:return n FACTORIEL-RECURSIF(n1)5:end ifBrice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 33 / 59Fondements des langages : la recursiviteAlgorithmes recursifsRegles de conceptionPremiere regleTout algorithme recursif doit distinguer plusieurs cas dont l'un au moins necomporte pas d'appel recursif : eviter lescalculs innis .Cas de baseLescas de base sont les cas non r ecursifsd'un algo rithmer ecursif.Conditions de terminaisonsLesconditions de terminaisons sont les conditions que doivent satisfaire le sdonnees dans les cas de base.Brice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 34 / 59Fondements des langages : la recursiviteAlgorithmes recursifsRegles de conceptionDeuxieme regleVerier que tous les appels recursifs eectues terminent bien sur unecondition de terminaison.TheoremeIl n'existe pas de suite innie strictement decroissante d'entiers positifs ounuls.Brice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 35 / 59Le langage PythonSommaire1Presentation du cours2Introduction et denitionsPourquoi l'etude des algorithmes?Denitions3Paradigmes et langages de programmation4Fondements des langages : la recursiviteAlgorithmes recursifs5Le langage PythonBrice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 36 / 59Le langage PythonLe langage PythonC'estUn langage de scripts (de petits programmes tres simples chargesd'une mission tres precise sur votre ordinateur);Un langage imperatif interprete (c'est-a-dire que les instructions quevous lui envoyez sont \transcrites" en langage machine au fur et amesure de leur lecture) contrairement a un langage compile (C/C++)Brice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 37 / 59Le langage PythonLe langage PythonPython est un langage de programmationCe qui denit un langage de programmationLa facon de representersymb oliquementles structures de donn ees.La facon de gerer lecontr^ oledes p rogrammes(qu efaire et dans quel ordre)Comme tout langage de programmation, Python fournit un certain nombrede types de donnees predenis (booleens, entiers, ottants, cha^ne decaracteres, listes) et de structure de contr^ole (les boucles for, while et lesconditions ifthenelse).Brice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 38 / 59Le langage PythonInstallation et Prise en mainPour installer Python sur votre machine personnelle, vous devez telecharger laderniere version du langage a l'adressehttps://www.Python.org/downloads/.L'installation de Python genere l'installation d'une interface, appelee IDLE(Python GUI).
Cette interface vous permet de saisir des instructions en ligne decommande mais egalement d'executer des programmes Python enregistres dansdes chiers.
L'acces a l'interface IDLE se fait a partir du repertoire ou Python aete installe.
Il sut alors de cliquer sur IDLE qui va vous ouvrir l'interfacegraphique ou vous pourrez taper vos instructions Python en ligne de commandes :Figure:Interface IDLE Brice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 39 / 59Le langage PythonInstallation et Prise en mainPour ecrire un programme dans un chier, dans le menuFile, selectionnezNewFile.
Une nouvelle fen^etre s'ouvre. Tapez votre programme Python dans cettefen^etre (attention aux indentations). Pour executer votre programme, allez dansle menu Run et faites Run Modules (ou F5).
Il va vous ^etre demande de faire unesauvegarde de votre chier (qui a generalement l'extension.py), puis votreprogramme s'executera (dans la fen^etre en ligne de commande precedemmentouverte).
Le debut de l'execution de votre programme est indique dans la fen^etreen ligne de commande par le mot cleRESTART.Brice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 40 / 59Le langage PythonInstallation et Prise en mainD'autres outils integrant un editeur de texte peuvent aussi ^etre utilises pourprogrammer en Python.
Exemples : Canopyhttps://www.enthought.com/products/canopy/et IEP (Interactive Editorfor Python)http://www.pyzo.org/iep.html.Brice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 41 / 59Le langage PythonLes structures de donneesStructure de donneesUnestructure de donn eesest d eniepa r3 choses : 1Untypequi est simplement un nom permettant de classier lesdonnees relevant de ce nom.
2) Unensemblequi denit avec precision les elements appartenant autype.3desoperationsutilisees par les programmes pour calculer sur cesdonneesOn parle destructures a lgebriques.Brice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 42 / 59Le langage PythonLes booleensCe type de donnees est predeni dans Python par :son nomb oolses valeursfTrue,Falsegses operationsnot: bool!bool,and: boolbool!bool, etor: boolbool!boolNom vient de George Boole [1815-1864] mathematicien anglais interessepar les proprietes algebriques des valeurs de verite.Brice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 43 / 59Le langage PythonLes entiers relatifsCe type de donnees est predeni dans Python par :son nomint son ensemble de valeurs est theoriquementZmais est en fait borneselon la machine utilisee.ses operations+,- ,* ,/ ,% ,** : intint!int,==,>,<,>=,<=,! = : intint!boolLes operations de calcul (+,-,** ) sont prioritaires sur les operateurs decomparaison (==,<=, ).Brice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 44 / 59Le langage PythonQuelques exemples d'utilisation des entiers>>> type(46) #type : fonction pr\'{e}d\'{e}finie fournissanttype 'int' #le type d'une expression>>> print 5 * 7 #print : fonction pr\'{e}d\'{e}finie d'impression35>>> 5 / 2 # / quotient de la division euclidienne2>>> 5 % 2 # % reste de la division euclidienne1>>> 5 ** 3 # fonction d'exponentation125>>> 5 < 3 # pr\'{e}dicat de comparaison "strictement inf\'{e}rieur"False>>> 5 == 3 + 2 # op\'{e}ration + est prioritaire sur ==True>>> 5 = 3 + 2SyntaxError: can't assign to literalBrice Mayagbrice.mayag@dauphine.frChapitre 1: Introduction a l'algorithmiqueM1 SIEE 45 / 59Le langage PythonLes nombres reelsEn fait, les nombres reels ne sont pas representables en machine.
On lesapproxime par des nombres rationnels (i.e. avec des virgules).Ce type de donnees est predeni dans Python par :son nomoat son ensemble de valeurs est theoriquementRmais est en fait uns
