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 d’Informatique Initiation à l’informatique, à l’algorithmique et à la pro

Cours d’Informatique Initiation à l’informatique, à l’algorithmique et à la programmation Licence fondamentale et professionnelle Pr. Rachid SEHAQUI Université Hassan II Casablanca Faculté des sciences Aïn Chck r.sehaqui@fsac.ac.ma www.goodprepa.tech ALGORITHMIQUE POUR L'INGENIEUR Pr. Rachid SEHAQUI Université Hassan II Casablanca Faculté des sciences Aïn Chck r.sehaqui@fsac.ac.ma Université Hassan II- Faculté des Sciences - P. R. EHAQUI 3 Objectif Familiariser les étudiants avec les techniques et outils permettant de concevoir et de comprendre, de réaliser puis traduire, d’implémenter et enfin d’obtenir un programme produisant par son exécution sur un ordinateur, le résultat attendu. rigueur de la démarche scientifique Chapitre 1 : Introduction à l’algorithmique Université Hassan II- Faculté des Sciences - P. R. EHAQUI 5 1.1 - Introduction Matériel / Logiciel Domaine du logiciel (software) instructions expliquant à l’ordinateur comment traiter un problème algorithmes et représentation informatiques de ces instructions programme Université Hassan II- Faculté des Sciences - P. R. EHAQUI 6 1.1 - Introduction Les programmeurs sont amenés à concevoir des logiciels de plus en plus complexes pour répondre aux besoins des utilisateurs (applications en réseau, base de données réparties, …) maîtriser le développement des logiciels est très important Université Hassan II- Faculté des Sciences - P. R. EHAQUI 7 1.2 - Algorithmes et programmes Notion précise d’algorithme a été découverte en 825 par le mathématicien arabe Muhammmad ibn Musa al-Kharezmi Moyen d’automatisation et d’économie de la pensée Petit Larousse : suite d’opérations élémentaires constituant un schéma de calcul ou de résolution de problème. Université Hassan II- Faculté des Sciences - P. R. EHAQUI 8 1.2 - Algorithmes et programmes Pour nous : Un algorithme est une séquence précise et non ambiguë d’une suite d’étapes pouvant être exécutées de façon automatique par un ordinateur pour résoudre un problème Spécification du schéma de calcul sous forme d’une suite finie d’opérations élémentaires obéissant à un enchaînement déterminé. Université Hassan II- Faculté des Sciences - P. R. EHAQUI 9 1.2 - Algorithmes et programmes Informations en entrée Informations en sortie Algorithme informatique = schéma de calcul Un algorithme est une suite finie de règles à appliquer dans un ordre déterminé à un nombre fini de données, pour arriver en un nombre fini d’étapes, à un certain résultat, et cela indépendamment des données. Université Hassan II- Faculté des Sciences - P. R. EHAQUI 10 1.2 - Algorithmes et programmes Programme : codage d’un algorithme afin que l’ordinateur puisse exécuter les actions décrites doit être écrit dans un langage compréhensible par l’ordinateur langage de programmation Un programme est donc une suite ordonnée d’instructions élémentaires codifiées dans un langage de programmation Université Hassan II- Faculté des Sciences - P. R. EHAQUI 11 1.3 - Langages de programmation RAPPEL: Langage machine langage binaire ses opérations sont directement compréhensibles par l’ordinateur propre à chaque famille d’ordinateur Ecriture des premiers programme en langage machine Université Hassan II- Faculté des Sciences - P. R. EHAQUI 12 1.4 - Importance des algorithmes  Pour mener à bien un traitement sur un ordinateur il faut : 1. Concevoir un algorithme qui décrit comment le traitement doit être fait 2. Exprimer l’algorithme sous la forme d’un programme dans un langage de programmation adéquat 3. Faire en sorte que l’ordinateur exécute le programme : compilation Université Hassan II- Faculté des Sciences - P. R. EHAQUI 13 Algorithme Programme en langage évolué Programme en langage machine programmation traduction Interprétation par l’Unité Centrale de traitement le traitement souhaité est réalisé Université Hassan II- Faculté des Sciences - P. R. EHAQUI 14 1.4 - Importance des algorithmes  Quels sont les aspects et propriétés des algorithmes qu’il est nécessaire d’étudier ? 1. La calculabilité des algorithmes (convergence de l’algorithme et existence de l’algorithme) la méthode existe t elle ? 2. La complexité des algorithmes (nombre d’opérations nécessaires) 3. L’efficacité des algorithmes (vitesse des algorithmes: raisonnable) TEMPS D'EXÉCUTION - MÉMOIRE OCCUPÉE Université Hassan II- Faculté des Sciences - P. R. EHAQUI 15 1.5 – Affinement des algorithmes Un algorithme doit décrire précisément le traitement qu’il doit exécuter et s’assurer que tous les cas de figures possible ont bien été prévus. Exemple : algorithme permettant de calculer la durée d’un voyage à partir du tableau d’affichage des aéroports 1. Consulter l’heure de départ 2. Consulter l’heure d’arrivé 3. Soustraire l’heure de départ de celle d’arrivée Université Hassan II- Faculté des Sciences - P. R. EHAQUI 16 1.5 – Affinement des algorithmes Problèmes : fuseaux horaires différents Si un point applique l’heure d’Été et pas l’autre Pour éviter de telles erreurs le concepteur doit suivre une démarche rigoureuse et méthodique : Affinement progressive de l’algorithme Démarche descendant, top down Technique du « diviser pour mieux régner » Université Hassan II- Faculté des Sciences - P. R. EHAQUI 17 1.5 – Affinement des algorithmes  Exemple : robot domestique avec un algorithme de préparation d’une tasse de café soluble 1. Faire bouillir l’eau 2. Mettre le café 3. Ajouter l’eau dans les tasses Université Hassan II- Faculté des Sciences - P. R. EHAQUI 18 1.5 – Affinement des algorithmes 1. faire bouillir l'eau peut être affinée en 1.1. remplir la bouilloire d'eau 1.2. brancher la bouilloire sur le secteur 1.3. attendre l'ébullition 1.4. débrancher la bouilloire Université Hassan II- Faculté des Sciences - P. R. EHAQUI 19 1.5 – Affinement des algorithmes 2. mettre le café dans la tasse pourrait être affiné en 2.1. ouvrir le pot à café 2.2. prendre une cuiller à café 2.3. plonger la cuiller dans le pot 2.4. verser le contenu de la cuiller dans la tasse 2.5. fermer le pot à café Université Hassan II- Faculté des Sciences - P. R. EHAQUI 20 1.5 – Affinement des algorithmes 3. ajouter de l'eau dans la tasse pourrait être affinée en 3.1. verser de l'eau dans la tasse jusqu'à ce que celle-ci soit pleine Université Hassan II- Faculté des Sciences - P. R. EHAQUI 21 1.5 – Affinement des algorithmes  1.1. remplir la bouilloire d'eau peut nécessiter les affinements suivants: 1.1.1. mettre la bouilloire sous le robinet 1.1.2. ouvrir le robinet 1.1.3. attendre que la bouilloire soit pleine 1.1.4. fermer le robinet Université Hassan II- Faculté des Sciences - P. R. EHAQUI 22 1.5 – Affinement des algorithmes Affinement ne se fait pas dans le vide Savoir où s’arrêter Connaître les capacités du processeur Exemple : Brancher la bouilloire, activité interprétable Remplir la bouilloire, activité non interprétable affinement Université Hassan II- Faculté des Sciences - P. R. EHAQUI 23 1.6 – Ecrire un algorithme Processeur informatique : ordinateur, capacités d’interprétation connues Le concepteur d’un algorithme doit donc affiner ce dernier jusqu’à ce que les étapes puissent être écrites à l’aide d’un langage de programmation Université Hassan II- Faculté des Sciences - P. R. EHAQUI 24 1.7 – Exemple Calcul de l'intérêt et de la valeur acquise par une somme placée pendant un an L'énoncé du problème indique Les données fournies: deux nombres représentant les valeurs de la somme placée et du taux d'intérêt les résultats désirés: deux nombres représentant l'intérêt fourni par la somme placée ainsi que la valeur obtenue après placement d'un an. Université Hassan II- Faculté des Sciences - P. R. EHAQUI 25 1.7 - Exemple  Formalisation de l’algorithme: En français 1. prendre connaissance de la somme initiale et du taux d'intérêt 2. multiplier la somme par le taux; diviser ce produit par 100; le quotient obtenu est l'intérêt de la somme 3. additionner ce montant et la somme initiale; cette somme est la valeur acquise 4. afficher les valeurs de l'intérêt et de la valeur acquise. 1.7 - Exemple 26 • SI=somme initiale • T=taux d’intérêt (ex: 3 pour 3%) • I=intérets=S*T/100 • SF=somme finale=S+I Université Hassan II- Faculté des Sciences - P. R. EHAQUI 1.8 – Environnement de l’algorithme Un algorithme utilise un certain nombre d’objets pour fonctionner appelé : environnement de l’algorithme, Cet environnement est constitué : - Des objets d’entrée (OE) qui représentent l’ensemble de données que l’utilisateur doit introduire à l’algorithme. - - Des objets de sortie (OS) qui représentent l’ensemble des résultats produits par l’algorithme. - - Des objets constants (OC) qui représente l’ensemble des objets dont les valeurs ne changent pas au cours de toute l’exécution de l’algorithme. Université Hassan II- Faculté des Sciences - P. R. EHAQUI 27 1.8 – Environnement de l’algorithme - Des objets Intermédiaires (OI) qui représentent l’ensemble des objets de traitement internes, ils ne sont ni entrés, ni sortis, ni constants mais ils sont soit des compteurs, soit calculés à partir des objets d’entrée et des objets constants et serviront pour produire les objets de sortie. Université Hassan II- Faculté des Sciences - P. R. EHAQUI 28 Objet d’Entrée(OE) Objet de Sortie (OS) Objet Constants (OC) Objet Intermédiaire (OI) 1. 9 Exemples  Université Hassan II- Faculté des Sciences - P. R. EHAQUI 29 1. 10- Qu’est ce qu’un bon algorithme?  Université Hassan II- Faculté des Sciences - P. R. EHAQUI 30 Chapitre 2 : Outils de base de l’algorithmique 2. 1- Introduction 1. INTRODUCTION - Vie quotidienne : - se préparer pour aller au travail le matin . - Conduire uploads/Science et Technologie/ algo-etudiants.pdf