Remerciez-le!

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

Algorithmique (objet) et Structure de données Licence 2ème année Faculté des Sc

Algorithmique (objet) et Structure de données Licence 2ème année Faculté des Sciences USTM Dr. Bienvenu FASSINUT-MOMBOT Algorithmique et Structure de données Dr. Bienvenu FASSINUT-MOMBOT 2 / 232 Remerciements & Copyright Certains transparents sont basés sur des supports trouvés sur : Web Et d’autres trouvés dans des Livres et cours sur le sujet Copyright © 2009-2012 Bienvenu Fassinut-Mombot; all rights reserved Ce support de cours est soumis aux droits d’auteur et n’est donc pas dans le domaine public. Sa reproduction est cependant autorisée à condition de respecter les conditions suivantes : Si ce document est reproduit pour les besoins personnels du reproducteur, toute forme de reproduction (totale ou partielle) est autorisée à la condition de citer l’auteur. Si ce document est reproduit dans le but d’être distribué à des tierces personnes, il devra être reproduit dans son intégralité sans aucune modification. Cette notice de copyright devra donc être présente. De plus, il ne devra pas être vendu. Cependant, dans le seul cas d’un enseignement gratuit, une participation aux frais de reproduction pourra être demandée, mais elle ne pourra être supérieure au prix du papier et de l’encre composant le document. Toute reproduction sortant du cadre précisé ci-dessus est interdite sans accord préalable écrit de l’auteur. Algorithmique et Structure de données Dr. Bienvenu FASSINUT-MOMBOT 3 / 232 “ “Comment Organiser au Comment Organiser au Mieux Mieux l l’ ’Information Information dans dans un Programme ? un Programme ?” ” Un problème métaphysique ? Tableaux Tableaux int int tab[10]; tab[10]; struct struct Data_t Data_t { { int int index_; index_; char* value_; char* value_; } } Data_t Data_t; ; Structures Structures Structures de Structures de donn donné ées es Algorithmique et Structure de données Dr. Bienvenu FASSINUT-MOMBOT 4 / 232 Objectifs… Concevoir et réaliser un algorithme correct et efficace pour un problème donné. Sensibilisation aux problèmes algorithmiques et à leur performance, que ce soit sous la forme de complexité asymptotique ou à la performance sur des machines d’aujourd’hui en tenant compte de la performance du cache, et de la capacité multiprocesseur. Introduire des types abstraits, discuter leurs implémentations possibles Connaître les structures de données séquentielles simples, complexes et arborescentes : tableaux, listes chaînées, piles, files, arbres et graphes Faire un choix argumenté sur l'utilisation de telle ou telle structure de données ainsi que sur l'algorithme qui la manipule. Mettre en œuvre des structures de données et les algorithmes associés dans des programmes écrits en langage C/C++ dont l’aspect orienté objet sera réduit au minimum Il ne s'agit pas d'un cours de programmation pur et dur en C/C++ ! Algorithmique et Structure de données Dr. Bienvenu FASSINUT-MOMBOT 5 / 232 Contenu Notions de bases de l’algorithmique Algorithmique et Programmation Procédure de réalisation d’un programme Structures de données Structures de données élémentaires Tableaux Types composés ou structures Preuve et complexité algorithmique Notion de complexité algorithmique Notion de Récursivité Structures de données linéaires ou séquentielles Listes Piles et Files Structures de données non-linéaires ou arborescentes Arbres Graphes Programmation Notion de base du langage C/C++ Environnement de programmation Notions de bases de l’algorithmique Algorithmique et Structure de données Dr. Bienvenu FASSINUT-MOMBOT 7 / 232 Algorithmique et Programmation Qu’est-ce qu’un algorithme ? Vous avez déjà ouvert un livre de recettes de cuisine? Avez-vous déjà déchiffré un mode d’emploi traduit de l’anglais pour faire fonctionner un magnétoscope, un réveil, digicode…? Si oui? • Sans le savoir vous avez déjà exécuté des algorithmes. Encore plus fort : Avez-vous indiqué un chemin à un individu égaré? Avez-vous fait chercher un objet à quelqu’un par téléphone? Si oui? • Vous avez déjà fabriqué - et fait exécuter - des algorithmes Définition (selon l’Encyclopédia Universalis) améliorée : Un algorithme est la spécification d’un schéma de calcul, sous forme d’une suite [finie] d’opérations élémentaires [décrites dans un langage universel] obéissant à un enchaînement déterminé [représentant les calculs nécessaires à la production de la valeur d’une certaine fonction générale utilisant certaines données]. Algorithmique et Structure de données Dr. Bienvenu FASSINUT-MOMBOT 8 / 232 Algorithmique et Programmation Exemple : Algorithme de résolution d’une équation Un algorithme de résolution de l'équation ax+b = 0 données : a et b entiers Algorithme : ecrire("Résolution de l’équation : ax+b=0") lire(a), lire(b) Si a est non nul Alors, on obtient la solution : x = -b/a Sinon Si b est non nul Alors, l'équation est insoluble Sinon tout réel est solution Résultat : la solution de l’équation ax+b=0; si elle existe Algorithmique et Structure de données Dr. Bienvenu FASSINUT-MOMBOT 9 / 232 Algorithmique et Programmation Qu’est-ce qu’un programme ? Un programme est la description (traduction) d’un algorithme dans un langage de programmation obéissant à des règles très précises. Un langage de programmation est un langage commun entre machine et programmeur qui implante et réalise un algorithme.  Exemple: le langage C/C++ #include <stdio.h> #include <stdlib.h> int main (void) { int a,b; puts("Résolution de l’équation: ax+b=0\n"); printf("a?\n"); scanf("%d",&a); printf("b?\n"); scanf("%d",&b); if(a ≠ 0) printf("x=%f\n",-b/a); else if (b ≠ 0) puts("l’équation est insoluble\n"); else puts("tout réel est solution\n"); return EXIT_SUCCESS; } ALGORITHME: ecrire("Résolution de l’équation: ax+b=0") lire(a), lire(b) Si a est non nul Alors, on obtient la solution : x = -b/a Sinon Si b est non nul Alors, l'équation est insoluble Sinon tout réel est solution Structure de contrôle conditionnelle Algorithmique et Structure de données Dr. Bienvenu FASSINUT-MOMBOT 10 / 232 Algorithmique et Programmation Quelle est la différence ? En utilisant des images : • Si un programme était une construction, l’algorithme serait le plan • Si un programme était une toile de peinture, l’algorithme serait l’esquisse Algorithme : Algorithmique et Structure de données Dr. Bienvenu FASSINUT-MOMBOT 11 / 232 Algorithmique et Programmation Quelle est la différence ? En utilisant des images : • Si un programme était une construction, l’algorithme serait le plan • Si un programme était une toile de peinture, l’algorithme serait l’esquisse Programme : Algorithmique et Structure de données Dr. Bienvenu FASSINUT-MOMBOT 12 / 232 Un Langage Algorithmique : Comment faire? décrire l’algorithme dans une forme telle que la passage au programme ne pose plus aucun problème, pour que cette opération de codage devienne une simple mécanique de traduction du Langage Algorithmique vers le langage cible Historiquement, plusieurs types de notations ont été utilisées pour représenter des algorithmes Descriptions littéraires Organigrammes Pseudo-codes Les pseudo-codes Définition : un pseudo-code est une série de conventions qui ressemble à un langage de programmation authentique dont on aurait évacué la plupart des problèmes de syntaxe. Remarque : un pseudo-code est susceptible de varier d’une référence à une autre. En effet, un pseudo-code est purement conventionnel. Aucune machine n’est censée le reconnaître. Algorithmique et Structure de données Dr. Bienvenu FASSINUT-MOMBOT 13 / 232 Squelette d’un algorithme Spécifications de l’algorithme Déclaration des constantes et des variables Corps de l’algorithme (traitements) //BUT : cet algorithme effectue ... //ENTREE : une liste de M noms //SORTIE : une liste triée par ordre alphabétique // CONSTANTES : les constantes // l’initialisation est obligatoire obligatoire // au moment de leur déclaration CONST : pi <-- 3,1416 : REEL nom <-- "Bonjour" : CHAINE // VARIABLES : les variables (au sens strict) // l’initialisation est facultative facultative // au moment de leur déclaration VAR : prix, quantite : REEL prenom <-- "Bruno" : CHAINE DEBUT // instructions : suite de séquences // et ruptures de séquences FIN ALGORITHME : nom_algorithme Nom de l’algorithme Un Langage Algorithmique : Comment faire? Algorithmique et Structure de données Dr. Bienvenu FASSINUT-MOMBOT 14 / 232 Notion d’instruction 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 des variables constantes des valeurs littérales ("bonjour", 45, VRAI) des expressions complexes (combinaisons de variables, constantes et valeurs littérales avec des opérateurs) L’opérateur d’AFFECTATION, une "mise en mémoire" : L’opérateur d’affectation permet de donner (ou d’affecter) une valeur à une variable • Sa syntaxe est la suivante : nom_de_la_variable <-- valeur_à_affecter L’opérateur d’ÉGALITÉ le symbole du test d’égalié : = Algorithmique et Structure de données Dr. Bienvenu FASSINUT-MOMBOT 15 / 232 Notion d’instruction Opérateurs d'entrée/sortie Clavier et écran • LIRE(x) : données du problème (usercomputer) permet de lire au clavier la valeur de la variable x • ECRIRE(x) : affichage à l'écran (computeruser) permet d’afficher la valeur de la variable x Fichiers texte • Le type FICHIER permet de lire et d’écrire dans un fichier • lireF(x,file) : met dans x la première valeur lue dans le fichier • ecrireF(x,file) : permet d’écrire la valeur de x dans le fichier VAR : file : FICHIER File <-- ouvrir("nom.txt", "lect") "lect" : lecture seule "ecr" : écriture seule "lectEcr" : lecture-écriture Algorithmique et Structure de données Dr. Bienvenu FASSINUT-MOMBOT 16 / 232 Notion de séquence DEBUT FIN ACTION 1 : LIRE(valeur) Une séquence est une suite d'opérations élémentaires (ou ACTIONS) dont l'exécution est séquentielle. ACTION 2 : produit <-- valeur * valeur ACTION 3 : ECRIRE(produit) CORRESPONDANCE : Organigramme <--> Algorithmique ALGORITHME: carre //BUT : calcul le carré d’un nombre //ENTREE : entier saisi par l’utilisateur //SORTIE : valeur de l’entier uploads/Ingenierie_Lourd/ coursalgorithmique-et-structure-de-donnees-ustm.pdf