Remerciez-le!

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

Institut Supérieur Arts et Multimédia Université de la Manouba Algorithme et St

Institut Supérieur Arts et Multimédia Université de la Manouba Algorithme et Structures de Données 1 Support de Cours Mohamed Mohsen Gammoudi, Professeur en informatique, ISAMM, Université de la Manouba gammoudimomo@gmail.com Farah HARRATHI Maître Assistant en Informatique E-mail : harrathi.farah@gmail.com Année universitaire 2015-2016 Préface -i- Préface Objectifs du cours : Ce cours permettra aux étudiants de première année Licence fondamentale informatique d’analyser un problème donné et de définir l’algorithme traduisant la solution du problème d’une manière rigoureuse et optimisée et prête à être traduite en utilisant un langage de programmation quelconque, comme ça était demandé dans le programme du LMD. De plus, l’étudiant sera capable de définir la structure de données adéquate au problème à résoudre et par conséquent celle qui permettra d’optimiser l’algorithme. Il servira aussi aux étudiants cycle ingénieur comme support pour une mise au point des connaissances acquises en algorithmique durant le premier cycle ou en classes préparatoires avant d’entamer l’algorithmique niveau II. Nous attirons l’attention que ce support de cours est inspiré de plusieurs références bibliographiques (livres et ressources disponibles sur le web). Prérequis : Aucun Bibliographie : FABER. (2009). FABER F. INTRODUCTION A LA PROGRAMMATION EN ANSI-C, http://www.ltam.lu/cours-c/, Date de consultation : 28 Juin 2009 . HARDOUIN. (2009). HARDOUIN L. http://www.istia.univ- angers.fr/~hardouin/cours_c.pdf, Date de constation : 19 Mai 2009 . La Page de l'algorithmique. ( 2008). La Page de l'algorithmique. http://algor.chez.com/index.html, . LAPORTE. (2009). LAPORTE S. http://btsig972.free.fr/cours/Algorithme/1e_annee/07.pdf, Date de consultation : 09 Mai 2009 . REBAINE. (1, 2009). REBAINE D. http://wwwens.uqac.ca/~rebaine/8INF805/courslistespilesetfiles.pdf, Date de consultation : 20 Mai 2009 . REBAINE. (2,2009). REBAINE D. http://wwwens.uqac.ca/~rebaine/8SIF109/Les%20arbres.pdf, Date de consultation : 10 Septembre 2009 . Préface -ii- Shaffer. (2001). Shaffer C A. Practical Introduction to Data Structures and Algorithm Analysis (C++ Edition) (2nd Edition) (chapitre2) . TThomas et al. (2002). Thomas H. Cormen, Charles E. Leireson, Ronald L Rivest et Clifford Stein, . «Introduction à l’algorithmique», cours et exercices 2ème cycle Ecoles d’ingénieurs » , Edition Dunod, 2ème dition, Paris 2002. Table des matières -iii- Table des matières 1. Préface ................................................................................................................................... i 2. Table des matières............................................................................................................ 3 3. Table des figures ............................................................................................................... 7 4. Table des tableaux ............................................................................................................ 8 5. Introduction à l’algorithmique ..................................................................................... 1 1.1. Démarche pour la résolution d’un problème .............................................................. 1 1.2. De l’algorithmique à la programmation ........................................................................ 1 1.3. Définition d’un Algorithme ................................................................................................. 2 1.4. Exemple...................................................................................................................................... 2 1.5. Structure d’un algorithme .................................................................................................. 3 1.6. Conclusion ................................................................................................................................. 3 6. Introduction aux Structures de Données .................................................................. 4 2.1. Introduction ............................................................................................................................. 4 2.2. Constante et variable ............................................................................................................ 4 2.3. Identificateur ........................................................................................................................... 4 2.4. Type ............................................................................................................................................. 5 2.4.1. Le type entier .............................................................................................................................. 5 2.4.2. Le type réel ................................................................................................................................... 5 2.4.2.1. Les opérateurs réels ........................................................................................................................... 5 2.4.2.2. Les fonctions sur les réels ................................................................................................................ 6 2.4.3. Le type booléen .......................................................................................................................... 6 2.4.3.1. Les opérateurs booléens................................................................................................................... 6 2.4.3.2. Propriétés des opérateurs logiques ............................................................................................ 6 2.4.3.3. Les opérateurs de comparaison .................................................................................................... 7 2.4.4. Le type caractère........................................................................................................................ 7 2.4.5. Le type chaîne de caractères ................................................................................................. 8 2.5. Les expressions ....................................................................................................................... 8 2.6. Hiérarchie entre les opérateurs ....................................................................................... 9 7. Instructions élémentaires et structure d’un algorithme ................................. 10 3.1. Structure d’un algorithme ............................................................................................... 10 3.2. Déclaration de variables ................................................................................................... 10 3.3. Déclaration de constantes................................................................................................ 10 Table des matières -iv- 3.4. L’affectation ........................................................................................................................... 11 3.5. Fonctions d’entrées/sorties ............................................................................................ 11 3.6. Les commentaires ............................................................................................................... 12 3.7. Les instructions .................................................................................................................... 12 3.8. Exemple d’algorithme ....................................................................................................... 12 8. Les instructions conditionnelles .............................................................................. 14 4.1.1. L’instruction conditionnelle simple ................................................................................ 14 4.1.2. Structures alternatives complètes ................................................................................... 14 4.1.3. Structure conditionnelle à choix multiple .................................................................... 16 9. Les structures itératives .............................................................................................. 17 5.1. La boucle Pour ...................................................................................................................... 17 5.2. La boucle Répéter ............................................................................................................... 18 5.3. La boucle Tant que .............................................................................................................. 19 10. Les tableaux ..................................................................................................................... 21 6.1. Tableaux simples ................................................................................................................. 21 6.1.1. Définition ................................................................................................................................... 21 6.1.2. Notations et déclarations .................................................................................................... 21 6.1.3. Accès à un élément du tableau .......................................................................................... 22 6.1.4. Opérations sur les tableaux ................................................................................................ 22 6.1.4.1. Affectation ............................................................................................................................................ 22 6.1.4.2. Comparaison ....................................................................................................................................... 22 6.2. Lecture d'un tableau : ........................................................................................................ 22 6.3. Ecriture d'un tableau : ....................................................................................................... 23 6.4. Tableaux à deux dimensions ........................................................................................... 23 6.4.1. Définition ................................................................................................................................... 23 6.4.2. Déclaration ................................................................................................................................ 23 6.4.3. Accès à un élément du tableau à deux dimensions ................................................... 23 6.5. Définition d’un nouveau type ......................................................................................... 24 11. Les sous-programmes : les procédures et les fonctions ................................... 26 7.1. Les sous-programmes ....................................................................................................... 26 7.2. Les variables globales et locales .................................................................................... 27 7.2.1. Variables Globales .................................................................................................................. 27 7.2.2. Variables locales...................................................................................................................... 27 7.3. Les procédures ..................................................................................................................... 28 7.3.1. Définition ................................................................................................................................... 28 Table des matières -v- 7.3.2. Déclaration d’une procédure ............................................................................................. 28 7.3.3. Les paramètres formels et effectifs ................................................................................. 28 7.4. Les fonctions ......................................................................................................................... 30 7.4.1. Définition ................................................................................................................................... 30 7.4.2. Déclaration d’une fonction ................................................................................................. 30 7.4.3. Appel d’une fonction ............................................................................................................. 30 7.5. Les paramètres d’appel ..................................................................................................... 31 7.5.1. Procédure sans paramètres d’appel ............................................................................... 31 7.5.2. Procédure avec paramètres d’appel ............................................................................... 31 7.5.2.1. Passage par valeur ............................................................................................................................ 32 7.5.2.2. Passage par adresse (ou variable) ............................................................................................ 32 12. Les enregistrements ...................................................................................................... 34 8.1. Introduction .......................................................................................................................... 34 8.2. Déclaration d'un type structuré .................................................................................... 34 8.3. Déclaration des variables à partir d'un type structuré ........................................ 35 8.4. Manipulation d'un enregistrement .............................................................................. 35 8.4.1. Accès aux champs d'un enregistrement ........................................................................ 35 8.4.2. Passage d’un enregistrement en paramètre d’une fonction ou d’une procédure 36 8.4.3. L'imbrication d'enregistrements ..................................................................................... 37 8.5. Les tableaux d'enregistrement ...................................................................................... 38 13. Les fichiers ........................................................................................................................ 40 9.1. Généralités sur les fichiers .............................................................................................. 40 9.2. Définition ................................................................................................................................ 40 9.2.1. Les types de fichiers .............................................................................................................. 40 9.2.2. Mode d'accès ............................................................................................................................. 40 9.3. Les fichiers à accès séquentiel ....................................................................................... 41 9.3.1. Déclaration ................................................................................................................................ 41 9.3.2. Ouverture et fermeture ........................................................................................................ 41 9.3.3. Lecture et Ecriture ................................................................................................................. 42 9.3.4. Fonction de test de fin de fichier ...................................................................................... 42 9.4. Exemple................................................................................................................................... 42 14. Les algorithmes de recherche .................................................................................... 45 10.1. Définition d’un tableau trié .................................................................................. 45 10.2. Recherche séquentielle .......................................................................................... 45 10.3. Recherche dichotomique ...................................................................................... 46 Table des matières -vi- 15. Les algorithmes de tri ................................................................................................... 49 11.1. Le tri à bulles ............................................................................................................. 49 11.2. Le tri par sélection ................................................................................................... 51 11.3. Le tri par insertion .................................................................................................. 52 16. La récursivité ................................................................................................................... 54 12.1. Définition .................................................................................................................... 54 12.2. Principe de la récursivité ...................................................................................... 54 12.3. Récursivité simple ................................................................................................... 54 12.3.1. La fonction factorielle............................................................................................ 54 12.3.2. La fonction exponentielle .................................................................................... 55 12.4. Récursivité multiple ................................................................................................ 55 12.4.1. La fonction combinaison ...................................................................................... 55 12.5. Récursivité mutuelle (ou indirecte).................................................................. 56 12.5.1. La fonction paire et la fonction impaire......................................................... 56 12.6. Récursivité imbriquée ............................................................................................ 57 12.6.1. La fonction d’Ackermann ..................................................................................... 57 17. Notion de pointeur ......................................................................................................... 58 13.1. Introduction ............................................................................................................... 58 13.2. Définition .................................................................................................................... 58 13.3. Déclaration ................................................................................................................. 58 13.4. Opérations sur les pointeurs ............................................................................... 59 13.4.1. Affectation, addition, soustraction et différence ........................................ 59 13.4.2. Allocation et destruction ou libération .......................................................... 59 Table des figures -vii- Table des figures Figure ‎ 1.1 : Démarche de résolution d’un problème ....................................................... 2 Figure ‎ 1.2 : Les trois parties d’un algorithme ................................................................... 3 Figure ‎ 1.3 : Structured’un algorithme .............................................................................. 3 Figure ‎ 2.1 : Les trois qualificatifs d’un objet ..................................................................... 4 Figure ‎ 7.1 : Algorithme appelant et d’algorithme appelé .............................................. 27 Table des tableaux -viii- Table des tableaux Tableau ‎ 2.1 : Table de vérité de l’opérateur NOT ............................................................ 6 Tableau ‎ 2.2 : Table de vérité de l’opérateur OR et de l’opérateur AND .......................... 6 Tableau ‎ 2.3 : Exemple d’évaluation d’expressions booléennes ....................................... 8 Tableau ‎ 2.4 : Hiérarchie entre les opérateurs .................................................................. 9 ‎ Chapitre 1 : Introduction à l’algorithmique -1- Chapitre 1 Introduction à l’algorithmique 1.1. Démarche pour la résolution d’un problème Pour résoudre un problème, en informatique, plusieurs étapes sont nécessaires : 1. Environnement : la connaissance précise de l’environnement (machine utilisée, processeur,...) 2. Problème : la définition précise du problème. 3. Analyse : l’analyse du problème et sa décomposition en sous-problèmes simples et distinctes. 4. Algorithme : la formulation de la solution sous une forme textuelle. Description des opérations à mettre en œuvre expliquant comment obtenir un résultat à partir de données. Il s'agit d'une description compréhensible par un être humain de la suite des opérations à effectuer pour résoudre le problème. 1.2. De l’algorithmique à la programmation Pour automatiser la résolution d’un problème, nous devons traduire un algorithme en un programme. En effet, un programme ce n’est que la traduction d’un algorithme dans un langage de programmation compréhensible par la machine utilisée. Ainsi, pour obtenir un programme exécutable, nous devons passer par les étapes suivantes : ‎ Chapitre 1 : Introduction à l’algorithmique -2- Figure ‎ 1.1 : Démarche de résolution d’un problème 1.3. Définition d’un Algorithme Un algorithme peut être définit comme suit : « Un algorithme est une suite finie d'opérations ou 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 (La Page de l'algorithmique, 2008)». A noter que le mot algorithme vient du nom du mathématicien arabe El Khawarizmi, originaire de la ville de Khawarizmi (La Page de l'algorithmique, 2008) 1.4. Exemple Pour déterminer le PGCD (Plus Grand Commun Diviseur) de deux entiers naturels a et b nous suivons la uploads/Ingenierie_Lourd/ coursasdiversion-etudiant-corrigee.pdf