Remerciez-le!

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

Université Mohammed V Faculté des Sciences Département d’informatique Cours de

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 2 Chap1: L’introduction à l’algorithmique 2014/2015 Algo1 /SMI 1 Cours d’Algorithmique 1 1ère année SMI Département d’Informatique, Université Mohammed V elbenani@hotmail.com 2014/2015 Algo1 /SMI 2 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édureset les fonctions qui permettent de structurer et de réutiliser les algorithmes. • Avoir une première notion de performance des algorithmes utilisés. 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 3 Galerie de portraits 2014/2015 Algo1 /SMI 4 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) John Von NEUMANN (1903-1957) 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 mathématique de la réaction en chaîne de la bombe A. Ses "machines IAS" sont à l'origine de "l'Architecture Von NEUMANN", c'est à dire celle des ordinateurs tels que nous les connaissons. Galerie de portraits 2014/2015 Algo1 /SMI 5 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, devenue une grande spécialise de la programmation des ordinateurs, elle sera l'une des principales créatrices du COBOL. Grace Murray HOPPER (1906 - 1992) 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 Bombe, première machine électromécanique de décryptage des messages codés avec l'Enigma Allemande. Alan TURING (1912 - 1954) Galerie de portraits 2014/2015 Algo1 /SMI 6 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 UNIX. Dennis 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 Society qui surveille les nouveaux standards d'Internet. Vinton G. CERF (1943 - ) 4 Galerie de portraits 2014/2015 Algo1 /SMI 7 Créateur du langage C++ basé sur le langage C mais en lui donnant une dimension de Langage Orienté Objet. Bjarne STROUSTRUP (1950 - ) James Gosling (1955 - ) 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. Galerie de portraits 2014/2015 Algo1 /SMI 8 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 - ) Steve JOBS (1955 - 2011) 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. Galerie de portraits 2014/2015 Algo1 /SMI 9 Richard STALLMAN (1953 - ) 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 contrôler les logiciels qu'ils utilisent. Il est également le créateur (entre autres) de l'éditeur Emacs et du 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 -) 5 Galerie de portraits 2014/2015 Algo1 /SMI 10 Larry Page (1973 - ) Sergey Brin (1973 - ) 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 chiffre, un 1 suivi de 100 zéros, traduisant l'exhaustivité du moteur de recherche. Mark Zuckerberg (1984 - ) 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. 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 6 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 2014/2015 Algo1 /SMI 15 Algorithmique L’algorithmiquedé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 7 2014/2015 Algo1 /SMI 16 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. 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 8 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 9 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 10 Les étapes de développement du logiciel 4) tests unitaires : effectuer les tests de chaque composant du logiciel en vue de son uploads/s3/ coursalgoprog2014-2018-p-pdf 1 .pdf