Cours d'algorithmique et programmation PDF 2014-2018

Université Mohammed V Faculté des Sciences Département d’informatique Cours de l’algorithmique et programmation: Licence SMI- S2 (Accréditation : 2014-2018) Pr. Y. EL BENANI Année de production : 2014 Chap1: L’introduction à l’algorithmique Cours d...

Université Mohammed V Faculté des Sciences Département d’informatique Cours de l’algorithmique et programmation: Licence SMI- S2 (Accréditation : 2014-2018) Pr. Y. EL BENANI Année de production : 2014 Chap1: L’introduction à l’algorithmique Cours d’Algorithmique 1 1ère année SMI Département d’Informatique, Université Mohammed V [email protected] 2014/2015 Algo1 /SMI 1 Objectif du cours  Objectifs : Apprendre les concepts de base de l'algorithmique. S’initier à l’analyse et la résolution de problèmes et écrire les algorithmes correspondants. Étudier les procédures et les fonctions qui permettent de structurer et de réutiliser les algorithmes. Avoir une première notion de performance des algorithmes utilisés. 2014/2015 Algo1 /SMI 2 Plan du cours  Chap1: L’introduction à l’algorithmique  Chap2: Notion de variables et d’affectation  Chap3: La lecture et l’écriture  Chap4: Les instructions conditionnelles  Chap5: Les instructions itératives (les boucles)  Chap6: Les tableaux  Chap7: Les fonctions et les procédures  Chap8: La récursivité  Chap9: L’introduction à la complexité des algorithmes  Chap10: Les algorithmes de recherche et tri 2014/2015 Algo1 /SMI 3 2  Galerie de portraits Mathématicien anglais, il publie en 1854 les Lois de la pensée. Dans ce livre, il décrit comment toute la logique peut être définie par un principe simple: le binaire. George BOOLE (1815-1864) L'un des personnages clés des débuts de l'informatique. Il publia de nombreux articles sur l'algèbre et la mécanique quantique avant de se consacrer à la construction d'ordinateurs et à la modélisation John mathématique de la réaction en chaîne de la bombe A. Von NEUMANNSes "machines IAS" sont à l'origine de "l'Architecture (1903-1957) Von NEUMANN", c'est à dire celle des ordinateurs tels que nous les connaissons. 2014/2015 Algo1 /SMI 4 Galerie de portraits Cette américaine, mobilisée comme auxiliaire dans la marine américaine fut affectée aux travaux de programmation et d'exploitation de l'ENIAC. Puis, Grace Murray devenue une grande spécialise de la programmation des HOPPER ordinateurs, elle sera l'une des principales créatrices du (1906 - 1992) COBOL. Mathématicien anglais, maître-assistant à Cambridge dès 23 ans. Il a conçu en 1936 une machine logique capable de résoudre tous les problèmes que l'on peut formuler en termes d'algorithmes. Pendant la guerre, il participera à la réalisation de la Alan TURING Bombe, première machine électromécanique de (1912 - 1954) décryptage des messages codés avec l'Enigma Allemande. 2014/2015 Algo1 /SMI 5 Galerie de portraits Cet ingénieur des laboratoires Bell, est l'auteur du langage C. En 1973, avec K. THOMPSON, il réécrira dans ce nouveau langage le système d'exploitation Dennis UNIX. RITCHIE (1941) C'est l'un des pères de l'Internet. Encore étudiant de l'université de Los Angeles, il fut l'un des auteurs du protocole TCP/IP et développa avec une équipe de chercheurs les premiers outils utilisant ce mode de communication. Il est aujourd'hui président de l'Internet Vinton G. Society qui surveille les nouveaux standards d'Internet. CERF (1943 - ) 2014/2015 Algo1 /SMI 6 3  Galerie de portraits Créateur du langage C++ basé sur le langage C mais en lui donnant une dimension de Langage Orienté Bjarne Objet. STROUSTRUP (1950 - ) Créateur du langage Java basé sur le langage C++. La particularité principale de Java est que les logiciels écrits dans ce langage sont trè s facilement portables sur plusieurs systèmes d’exploitation. James Gosling (1955 - ) 2014/2015 Algo1 /SMI 7 Galerie de portraits Ancien président (et fondateur avec P. ALLEN) de Microsoft. Cette société est à l'origine du MS-DOS, de Windows, du Basic-Microsoft puis de Visual Basic. Bill GATES (1951 - ) L’un des fondateurs de la société Apple. Après son éviction d'Apple S. JOBS créera la société Next avant d'être rappelé pour redresser Apple. Steve JOBS (1955 - 2011) 2014/2015 Algo1 /SMI 8 Galerie de portraits Fondateur du projet GNU, lancé en 1984 pour développer le système d'exploitation libre GNU et donner ainsi aux utilisateurs des ordinateurs la liberté de coopérer et de Richard contrôler les logiciels qu'ils utilisent. Il est également le STALLMAN créateur (entre autres) de l'éditeur Emacs et du (1953 - ) compilateur gcc. Finlandais d'origine, il a construit en 1991 un nouveau système d'exploitation de type UNIX appelé Linux. Ayant choisi de le diffuser suivant le principe des logiciels libres, Linus TORVALDS ne retire aucune royaltie de son travail sur le noyau Linux. Linus TORVALDS (1969 -) 2014/2015 Algo1 /SMI 9 4  Galerie de portraits Créateurs du moteur de recherche Google. Ces deux jeunes brillants nord-américains ont lancé leur moteur de recherche en 1999. Ce mot vient du terme "googol" qui désigne un Larry Page Sergey Brin chiffre, un 1 suivi de 100 zéros, traduisant (1973 - ) (1973 - ) l'exhaustivité du moteur de recherche. Créateur de Facebook C'est en 2004 que la première version de Facebook voit le jour pour mettre en relation les étudiants de Harvard. Mark Zuckerberg (1984 - ) 2014/2015 Algo1 /SMI 10 Pourquoi un cours d’algorithmique  Pour proposer à la « machine» d’effectuer un travail à notre place.  Problème : expliquer à la machine comment elle doit le faire.  Besoins : savoir expliquer et formaliser son problème Concevoir et écrire des algorithmes (séquence d’instructions qui décrit comment résoudre un problème particulier). 2014/2015 Algo1 /SMI 11 Les algorithmes sont anciens !  Les algorithmes ne sont pas nés avec l’informatique :  L’algorithme d’Euclide pour calculer le PGCD de deux entiers est vieux de plus de 2000 ans !  Des descriptions précises d’algorithmes sont présents dans la Chine ancienne. (Par exemple, pour extraire des racines carrées à partir de divisions effectuées sur une « surface à calculer »). 2014/2015 Algo1 /SMI 12 5  Les origines de l’algorithmique  Mohammed Al-Khwarizmi (780 - 850) 

ou  Mathématicien, géographe, astrologue et astronome musulman arabe dont les écrits ont permis l'introduction de l'algèbre en Europe.  L’ origine du mot « algorithme » est lié au nom d’Al- Khwarizmi. Ce savant arabe a publié plusieurs méthodes pour le calcul effectif de racines d’une équation du second degré et grâce à lui les chiffres arabes ont pu se diffuser en occident. 2014/2015 Algo1 /SMI 13 Algorithme  Savoir expliquer comment faire un travail sans la moindre ambiguïté.  Un algorithme : est une suite finie d’instructions que l’on applique à un nombre fini de données dans un ordre précis pour arriver à un résultat.  L’écriture algorithmique : un travail de programmation ayant une vision universelle : Un algorithme ne dépend pas du langage dans lequel il est implanté, ni de la machine qui va exécuter le programme correspondant. 2014/2015 Algo1 /SMI 14 Algorithmique  L’algorithmique désigne la discipline qui étudie les algorithmes et leurs applications en informatique  Une bonne connaissance de l’algorithmique permet d’écrire des algorithmes exacts et efficaces 2014/2015 Algo1 /SMI 15 6  Propriétés d’un algorithme  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. 2014/2015 Algo1 /SMI 16 Les 3 étapes d’un algorithme Les entrées (les données du problème) Le traitement Les sorties (l’affichage des résultats)  Les entrées : Il s’agit de repérer les données nécessaires à la résolution du problème.  Le traitement : Il s’agit de déterminer toutes les étapes des traitements à faire et donc des "instructions" à développer pour arriver aux résultats. 2014/2015 Algo1 /SMI 17 Les 3 étapes d’un algorithme  Les sorties : les résultats obtenus peuvent être affichés sur l’écran, ou imprimés sur papier, ou bien encore conservés dans un fichier. 2014/2015 Algo1 /SMI 18 7  Exemple d’algorithme : recette de cuisine 2014/2015 Algo1 /SMI 19 Exemple d’un algorithme  On se donne deux points A et B du plan. 1. Tracer le cercle de centre A passant par B. 2. Tracer le cercle de centre B passant par A. 3. Nommer C et D les points d’intersection de ces cercles.  Construire le polygone ADBC.  Cet algorithme décrit la construction d’un losange dont une diagonale est [AB].  Les entrées sont : les points A et B.  Le traitement de la construction est décrit dans les phases 1. 2. et 3.  La sortie est : le polygone ADBC. 2014/2015 Algo1 /SMI 20 Algorithme de calcul  2014/2015 Algo1 /SMI 21 8  Génie logiciel  Définition: le génie logiciel regroupe les sciences et les technologies qui permettent la production et la maintenance de logiciels de qualité  Le cycle de vie d’un logiciel regroupe les étapes de production du logiciel, ainsi que leur ordonnancement. 2014/2015 Algo1 /SMI 22 Les étapes de développement du logiciel 2014/2015 Algo1 /SMI 23 Les étapes de développement du logiciel  1) Analyse des besoins : que fait le système ? On définit les fonctionnalités du système à développer.  2) conception : comment faire le système ? décomposition du système en modules logiciels et matériel.  3) Implémentation (codage) : Réalisation des programmes dans un langage de programmation 2014/2015 Algo1 /SMI 24 9  Les étapes de développement du logiciel  4) tests unitaires : effectuer les tests de chaque composant du logiciel en vue de son intégration.  5) intégration : Intégration des modules et test de tout le système  6) Livraison et maintenance: Livraison du produit final à l'utilisateur, Le suivi, les modifications, les améliorations après livraison. 2014/2015 Algo1 /SMI 25 Modèles de développement  Objectifs : Organiser les différentes phases du cycle de vie pour l'obtention d'un logiciel fiable, adaptable et efficace. Guider le développeur dans ses activités techniques Fournir des moyens pour gérer le développement et la maintenance (ressources, délais, avancement, etc.).  Il existe plusieurs types de modèles : en cascade, en V, en spirale… 2014/2015 Algo1 /SMI 26 Modèle en cascade 2014/2015 Algo1 /SMI 27 10  Modèle en V 2014/2015 Algo1 /SMI 28 Modèle en spirale 2014/2015 Algo1 /SMI 29 Les langages de programmation  Le langage de programmation est l'intermédiaire entre l'humain (anglais) et la machine (binaire).  Il existe des milliers de langages de niveau élevé, pour tous les goûts et toutes les applications.  Quelques uns des plus connus: C, C++, Java, PHP,… 2014/2015 Algo1 /SMI 30 11  Les langages de programmation  Haut niveau : proche de l’homme, vocabulaire et syntaxe plus riches C++, Java, PHP,… C, Fortran,… Assembleur Langage machine  Bas niveau : proche de la machine, instructions élémentaires 2014/2015 Algo1 /SMI 31 Compilation et interpréteur  Compilation : permet de traduire le code source du programme vers le langage natif (objet) de la machine (ou parfois vers du code intermédiaire).  Interpréteur : permet de traduire et d’exécuter chaque instruction du programme. Ce mécanisme est utilisé pour le passage d’un programme précompilé à un pseudo-code (cas de Java). 2014/2015 Algo1 /SMI 32 2014/2015 Algo1 /SMI 33 12  Représentation d’un algorithme  Un algorithme, pour être lu par tous, est écrit en langage naturel (pseudo-code) ou représenté par un organigramme.  Un programme est la traduction d’un algorithme pour être compris par une machine (ordinateur, calculatrice, téléphone,…). 2014/2015 Algo1 /SMI 34 Représentation d’un algorithme  L’organigramme: représentation graphique avec des symboles (réctangles, losanges, etc.)  offre une vue d’ensemble de l’algorithme.  Représentation presque abandonnée aujourd’hui. 2014/2015 Algo1 /SMI 35 Représentation d’un algorithme  Le pseudo-code: représentation textuelle avec une série de conventions ressemblant à un langage de programmation.  plus pratique pour écrire un algorithme.  représentation largement utilisée.  Un algorithme écrit en pseudo-code est composé de trois parties suivantes : L’en-tête, la partie déclarative et le corps 2014/2015 Algo1 /SMI 36 13  Les instructions de base  Un programme informatique est formé de quatre types d’instructions considérées comme des briques de base : Les affectations de variables Les lectures et/ou les écritures Les tests Les boucles 2014/2015 Algo1 /SMI 37 Formalisme d’un algorithme  Un algorithme informatique doit suivre les règles suivantes : Il est composé d’une entête et d’un corps : l’entête, qui spécifie : le nom de l’algorithme (Nom :) son utilité (Rôle :) Les données “en entrée”, c.-à-d. les éléments qui sont indispensables à son bon fonctionnement (Entrée :) 2014/2015 Algo1 /SMI 38 Formalisme d’un algorithme les données “en sortie”, c.-à-d. les éléments calculés, produits, par l’algorithme (Sortie :) les données locales à l’algorithme et indispensables (Déclaration :)  le corps, qui est composé : du mot clé début d’une suite d’instructions du mot clé fin 2014/2015 Algo1 /SMI 39 14  Formalisme d’un algorithme : exemple Nom : addDeuxEntiers Rôle : Additionner deux entiers a et b et mettre le résultat dans c Entrée : a, b deux entiers Sortie : c un entier Déclaration : a, b, c : entier début c←a+b; ecrire (ʺla somme de a et b est =ʺ, c); fin 2014/2015 Algo1 /SMI 40 15