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é de la Manouba Institut Supérieur des Arts et Multimédias de la Manou

Université de la Manouba Institut Supérieur des Arts et Multimédias de la Manouba Support de cours : Algorithmique et complexité (partie 1) Cours M. Mohamed Mohsen Gammoudi, Professeur en Informatique et M. Farah HARRATHI, Maître Assistant en Informatique Année universitaire 2019-2020 -i- Préface Objectifs du cours : Ce cours s'adresse aux élèves ingénieurs informatique Multimédia. Les élèves sélectionnés sont hétérogènes et sont de plusieurs institutions, (ISET, Instituts et facultés). D'après notre petite expérience, nous avons constaté qu'il y'a un grand nombre de problèmes du type (différentes manières pour écrire un algorithme, confusion entre écriture d'algorithme et écriture de programmes, etc.). Ce cours permettra aux élèves de première année Ingénieur en informatique Multimédia 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. De plus, l'élève 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 sera également capable de calculer sa complexité. 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 Volume horaire : cours :21h, TD : 21h 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 . -ii- REBAINE. (2,2009). REBAINE D. http://wwwens.uqac.ca/~rebaine/8SIF109/Les%20arbres.pdf, Date de consultation : 10 Septembre 2009 . 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. -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. Comment exploiter nos algorithmes par la machine : 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 -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. Structures conditionnelles imbriquées .............................................................................. 16 4.1.4. Structure conditionnelle à choix multiple ........................................................................ 16 9. Les structures itératives ........................................................................................... 18 5.1. La boucle Pour............................................................................................................................. 18 5.2. La boucle Répéter ...................................................................................................................... 19 5.3. La boucle Tant que .................................................................................................................... 20 10. Les tableaux ................................................................................................................. 22 6.1. Tableaux simples ....................................................................................................................... 22 6.1.1. Définition ........................................................................................................................................... 22 6.1.2. Notations et déclarations .......................................................................................................... 22 6.1.3. Accès à un élément du tableau ............................................................................................... 23 6.1.4. Opérations sur les tableaux ...................................................................................................... 23 6.1.4.1. Affectation ............................................................................................................................................ 23 6.1.4.2. Comparaison ....................................................................................................................................... 23 6.2. Lecture d'un tableau : .............................................................................................................. 24 6.3. Ecriture d'un tableau : ............................................................................................................. 24 6.4. Tableaux à deux dimensions ................................................................................................ 24 6.4.1. Définition ........................................................................................................................................... 24 6.4.2. Déclaration ........................................................................................................................................ 24 6.4.3. Accès à un élément du tableau à deux dimensions ...................................................... 25 6.5. Définition d’un nouveau type .............................................................................................. 26 11. Les sous-programmes : les procédures et les fonctions .................................. 27 7.1. Les sous-programmes ............................................................................................................. 27 7.2. Les procédures ............................................................................................................................ 28 7.2.1. Définition ........................................................................................................................................... 28 7.2.2. Déclaration d’une procédure ................................................................................................... 28 7.2.3. Les paramètres formels et effectifs ...................................................................................... 28 -v- 7.3. Les fonctions ................................................................................................................................ 30 7.3.1. Définition ........................................................................................................................................... 30 7.3.2. Déclaration d’une fonction ....................................................................................................... 30 7.3.3. Appel d’une fonction .................................................................................................................... 31 7.4. Les variables globales et locales ......................................................................................... 32 7.4.1. Variables Globales ......................................................................................................................... 32 7.4.2. Variables locales............................................................................................................................. 32 7.5. Les paramètres d’appel........................................................................................................... 32 7.5.1. Procédure sans paramètres d’appel .................................................................................... 32 7.5.2. Procédure avec paramètres d’appel .................................................................................... 32 7.5.2.1. Passage par valeur ........................................................................................................................... 32 7.5.2.2. Passage par adresse (ou variable) ............................................................................................ 33 12. Les enregistrements .................................................................................................. 35 8.1. Introduction ................................................................................................................................. 35 8.2. Déclaration d'un type structuré ......................................................................................... 35 8.3. Déclaration des variables à partir d'un type structuré ........................................... 36 8.4. Manipulation d'un enregistrement ................................................................................... 36 8.4.1. Accès aux champs d'un enregistrement ............................................................................ 36 8.4.2. Passage d’un enregistrement en paramètre d’une fonction ou d’une procédure 37 8.4.3. L'imbrication d'enregistrements ........................................................................................... 38 8.5. Les tableaux d'enregistrement ............................................................................................ 39 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 -vi- 10.3. Recherche dichotomique ........................................................................................... 46 15. La récursivité ............................................................................................................... 50 11.1. Définition ........................................................................................................................... 50 11.2. Principe de la récursivité ........................................................................................... 50 11.3. Récursivité simple ......................................................................................................... 50 11.3.1. La fonction factorielle ................................................................................................. 50 11.3.2. La fonction exponentielle.......................................................................................... 51 11.4. Récursivité multiple ..................................................................................................... 51 11.4.1. La fonction combinaison ........................................................................................... 51 11.5. Récursivité mutuelle (ou indirecte) ...................................................................... 52 11.5.1. La fonction paire et la fonction impaire ............................................................ 52 11.6. Récursivité imbriquée ................................................................................................. 53 11.6.1. La fonction d’Ackermann .......................................................................................... 53 16. Notion de pointeur ..................................................................................................... 54 12.1. Introduction ..................................................................................................................... 54 12.2. Définition ........................................................................................................................... 54 12.3. Déclaration ........................................................................................................................ 54 12.3.1. Allocation........................................................................................................................... 55 12.3.2. Destruction ....................................................................................................................... 55 17. Introduction à la complexité ................................................................................... 56 13.1. Introduction ..................................................................................................................... 56 13.2. Les opérations élémentaires et notion d’instance ......................................... 56 13.3. Définition ........................................................................................................................... 57 13.4. Calculs élémentaires de complexité ...................................................................... 57 13.4.1. Si...Sinon ............................................................................................................................. 57 13.4.2. La boucle pour ................................................................................................................ 58 13.4.3. La boucle tantque .......................................................................................................... 58 13.5. Exemple : le tri par insertion .................................................................................... 58 -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.1Algorithme appelant et d’algorithme appelé ................................................28 -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 -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, etc. ) 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 (langage pseudo naturel). 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. Comment exploiter nos algorithmes par la machine : 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 quelconque, compréhensible par la machine utilisée. Ainsi, pour obtenir un programme exécutable, nous devons passer par les étapes suivantes : -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 uploads/Ingenierie_Lourd/ coursasdi-partie-1-finale-revisee.pdf