Remerciez-le!

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

ZIDANE N . Page 1 ALGORITHMIQUE ET STRUCTURES DE DONNEES PREAMBULE L’essentiel

ZIDANE N . Page 1 ALGORITHMIQUE ET STRUCTURES DE DONNEES PREAMBULE L’essentiel du cours d’algorithmique est noté dans ce document. Composé de 12 chapitres principaux, celui-ci est accompagné d’une partie complémentaire nommé Chapitre 0 qui concerne une (pseudo) convention d’écriture algorithmique retenue pour ce cours. L’écriture des langages informatiques est normalisée, mais l’écriture algorithmique ne dispose pas d’une convention officielle, et chaque auteur de publications du domaine opte pour telle ou telle formalisme. Les enseignants en font autant, nous vous présentons un formalisme dans ce chapitre 0, accompagné des arguments explicites qui nous ont amenés à prendre ces décisions, tant sur le fond que sur la forme. Il est, par conséquent, vivement recommandé de commencer la lecture de ce chapitre avant même de débuter le cours par le chapitre 1. Les enseignants ne le présenteront pas en cours, mais celui-ci pourra servir de support à des explications complémentaires ou bien pour répondre à des questions complémentaires. Ensuite, au fur et à mesure de l’avancé du cours, sera intéressant de revenir sur ce chapitre 0 afin de compléter les informations acquises. Pour les élèves qui ont déjà des connaissances en programmation, qui maîtrisent un langage, … ou qui ne désirent pas programmer plus tard, ce cours est malgré tout un concentré de connaissances fondamentales pour un informaticien, quelle que soit sa spécialité. Bon courage … Généralités sur l’Algorithmique Définitions Algorithmique 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 (sources : E. Universalis). Suite d’opérations nécessaires et suffisantes à l’accomplissement d’une tâche. Ces opérations se nomment en informatique des « INSTRUCTIONS ». Algorithme d’assemblage d’un produit fini ZIDANE N . Page 2 ALGORITHMIQUE ET STRUCTURES DE DONNEES Algorithme d’Euclide (calcul du PGCD) Algorithme de résolution d’une équation … Historique Historiquement, les langages font parties des sciences très anciennes visant à transmettre des moyens efficaces pour obtenir des résultats en partant d’éléments donnés. Par la suite, cela représentait tout procédé de calcul systématique. Inventé par le grand mathématicien Abu Ja'far Muhammad ibn Musa al-Khawarizmi. Vraisemblablement né en 780 à Bagdad, il est mort vers 850, D'autres sources voient son lieu de naissance en Ouzbékistan, au sud de la mer d'Aral, dans la ville de Khawarizm En informatique moderne : on le désigne par un procédé automatique (autonome) et effectif, comportant une description (finie) des entrées, des sorties, et des tâches élémentaires à réaliser. Réalisation d’un programme PROCEDURE de REALISATION d'un PROGRAMME INFORMATIQUE : L'écriture algorithmique est une phase intermédiaire et indispensable pour réaliser un programme. La qualité du développement final dépend aussi de cette phase cruciale. La suppression de celle-ci, perçue comme un “gain de temps" est généralement la cause d’un accroissement de la durée de développement, du fait de la non prise en compte de la complexité du problème au bon moment. [La taille des « pavés » permet de connaître le niveau d’importance (le volume) des phases de développement. Il faut aussi noter l’ordre des phases, l’incidence des premières phases sur les suivantes montre bien que tout projet doit être engagé en ne négligeant aucune phase. ] Notion d’instruction Notion d'instruction et notion de donnée Une instruction est un ordre élémentaire - au sens algorithmique -, que peut exécuter un programme. Les données manipulées par les instructions sont : des variables proprement dites (x, y, …) des « variables » constantes (pi, …) des valeurs littérales ("bonjour", 45, VRAI) des expressions booléennes ou complexes (combinaisons de variables, constantes et valeurs littérales avec des opérateurs) Notion de PRIMITIVE, ou fonction élémentaire ZIDANE N . Page 3 ALGORITHMIQUE ET STRUCTURES DE DONNEES Deux primitives d'entrée-sortie : LIRE() : lecture de la frappe au clavier ECRIRE() : affichage à l'écran L'AFFECTATION, pour une "mise en mémoire" : le symbole d'affectation : <-- Notion de séquences Suite d'opérations élémentaires (ou ACTIONS) dont l'exécution est séquentielle. Chaque pavé représente ici une instruction. La lecture d'un algorithme s'effectue de haut en bas. Attention, les représentations graphiques du type “organigramme” sont limitées aux seules structures algorithmiques et ne sont pas employées pour modéliser des ensembles modulaires (programmes). Notion de ruptures de séquences L'exécution des opérations élémentaires ACTIONS 2a et ACTIONS 2b n'est pas systématique. Chacune d’elle dépend de la "condition" de la rupture de séquence. La réalisation des ruptures de séquence s'effectue en fonction des éléments transmis à la "condition". L'exécution de l’opération élémentaire ACTION 2 peut éventuellement faire l’objet d’une répétition. L’action 2 peut avoir une occurrence nulle, égale à 1 ou encore une occurrence n. Elle dépend d'une "condition" qui permet ou non la répétition. Conventions d’écriture Les commentaires sont précédés de : // ou /* */ Les mots clés et Primitives sont écrits en majuscule : VAR: Les chaînes de caractères sont encadrés par : " Les caractères uniques sont encadrés par : ' Les accents sont seulement autorisés : dans les lignes de commentaire dans les chaînes de caractères : "élève" pour les caractères uniques : 'à' Présentation ZIDANE N . Page 4 ALGORITHMIQUE ET STRUCTURES DE DONNEES Concevoir un programme, c’est mettre en œuvre des mécanismes intellectuels complexes qui nécessitent la maîtrise des concepts intégrés à l’utilisation de l’ordinateur sur lequel le logiciel doit fonctionner. Ces concepts sont nombreux et situés à différents niveaux : du plus concret au plus abstrait. Mais, c’est aussi : appliquer avec rigueur un nombre important de règles essentielles pour parvenir à notre fin ; un logiciel qui fonctionne dans tous les cas de figure, et qui répond le plus justement au problème posé. Pour cela, il faudra structurer la technique de résolution en fonction de trois éléments de base en informatique … Les trois structures La structuration des données Un programme nécessite l’emploi systématique de données ou d’ensembles de données : Des données élémentaires (structures les plus basiques) [Modules 2] Des structures évoluées (structures complexes) [Modules 4 - 6 - 7 - 9] La structuration algorithmique La suite d’opérations à réaliser pour résoudre un problème nécessite un minimum d’organisation : Des séquences (suite successive d’opérations réalisées sans condition) [Module 3] Des ruptures de séquences (opérations conditionnées réalisées ou non suivant un contexte inconnu lors de la programmation) [Module 3 - 5] La structuration du programme [Module 8] Module 0: Convention d'écriture algorithmique Intérêt d’une convention Conventions de mise en forme Conventions liées à la sémantique des programmes Conventions liées aux concepts avancés Module 1: Généralités sur l’Algorithmique ZIDANE N . Page 5 ALGORITHMIQUE ET STRUCTURES DE DONNEES Présentation Les trois structures Présentation des modules Objectifs du cours Module 2: Données et Structures de données Types de données Opérations élémentaires Opérateurs associés à chaque type Accès aux données en mémoire Module 3: Structures algorithmiques élémentaires Présentation Structures séquentielles Structures de sélection Structures de répétition Module 4: Structures linéaires de données I Présentation Structures indexées à une dimension Structures indexées à plusieurs dimensions Structures indexées dynamiques Module 5: Structures algorithmiques imbriquées Présentation Structures de sélection imbriquées Structures de répétition imbriquées Module 6: Structures non linéaires de données I Présentation Structure abstraite de données: Enregistrement simple Structure abstraite de données: Enregistrement imbriqué Module 7: Structures linéaires de données II Présentation Structure abstraite de données: Liste Structure abstraite de données: Pile Structure abstraite de données: File Module 8: Structure de programme Présentation Programme principal, fonction et procédure Récursivité ZIDANE N . Page 6 ALGORITHMIQUE ET STRUCTURES DE DONNEES Module 9: Structures non linéaires de données II Présentation Structure abstraite de données: Graphe Structure abstraite de données: Arbre Module 10: Programme et Système d'exploitation Présentation Flux d'entrées/sorties Structures de données: Fichiers Système d'exploitation: Gestion des erreurs Module 11: Complexité Algorithmique: Introduction Complexité d'un algorithme Ecriture en O() Classes de complexité Module 12: Résolution d'un problème Approche de résolution globale d’un problème Résoudre un problème en informatique Qualités d'un programme informatique Données et structures de données Présentation Les structures de données élémentaires sont des informations de base dont on a besoin en informatique, et qui seront stockées en mémoire, et traitées par des algorithmes. Il faudra distinguer : les structures élémentaires qui sont des types concrets de données, des structures avancées (simples ou complexes) qui sont de véritables structures de données (suite organisées de données élémentaires) ou types abstraits de données. Correspondances de type Les types élémentaires de données ont une définition proche de celle étudiée en mathématique. En algorithmique, on limite volontairement les types élémentaires à la liste suivante : R : Le type réel, noté :REEL ZIDANE N . Page 7 ALGORITHMIQUE ET STRUCTURES DE DONNEES Z : Le type entier (relatif), noté :ENTIER Le type booléen, noté :BOOLEEN Le type caractère (unique), noté :CARACTERE Dans les langages, on retrouve les types correspondants : float, real, double, int, integer, bool, char, … Cinq types élémentaires Lors de l’emploi de ces différents types de données, au coeur des algorithmes, on ne se préoccupera pas : Du domaine des valeurs affectées aux données, contrairement aux langages, pour lesquels il est possible de définir si une donnée ne sera que uploads/Ingenierie_Lourd/ algorithmique-et-structures-de-donnees-cours.pdf