Remerciez-le!

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

1 Dr. M. AMAD Algorithmique et Structures de Données Cours et Travaux Dirigés S

1 Dr. M. AMAD Algorithmique et Structures de Données Cours et Travaux Dirigés Support destiné aux étudiants de niveau Première et deuxième année Licence Dr. Mourad AMAD Enseignant au Département d’Informatique Faculté des Sciences Exactes Université Abderrahmane Mira de Bejaia Année 2016 P O L Y C O P I E D E C O U R S 2 Dr. M. AMAD Avant Propos Ce polycopié est rédigé à l’intention des étudiants de première et de deuxième année du premier cycle universitaire (licence). Il constitue un manuel de cours et d’exercices sur une partie du domaine de programmation. Les lecteurs ne nécessitent aucun pré requis sur les l’algorithmique. Ce polycopié est structuré en huit chapitres comme suit : Dans le premier chapitre, des notions de base sur la structure globale d’un algorithme sont données, ainsi que les différentes parties qui le composent suivie par les instructions de base les plus élémentaires. Le deuxième chapitre décrit en détails les différentes structures de contrôles (boucles) qui peuvent être utilisées dans un algorithme (ex. Pour, tant que, ..). Le chapitre trois aborde l’utilisation des tableaux dans la programmation. Le quatrième chapitre est consacré aux sous programmes (fonctions et procédures). Dans le cinquième chapitre, l’utilisation des enregistrements et des fichiers dans le cadre de l’algorithmique est expliquée. Le sixième chapitre traite la récursivité afin de faciliter l’écriture des algorithmes qui peuvent être récursifs. Dans le septième chapitre, nous avons illustré comment calculer la complexité algorithmique de n’importe quel algorithme. Enfin, le chapitre huit est consacré à la programmation dynamique. La notion de pointeur est illustrée. Des modèles de programmation pour les listes linéaires chainée, les files, les piles ainsi que les arbres sont donnés. Une liste de références bibliographiques est donnée à la fin de ce manuscrit. 3 Dr. M. AMAD Sommaire Page Chapitre 1 : Généralités et Notions de Base 4 Chapitre 2 : Les Structures de Contrôle 11 Chapitre 3 : Les Tableaux 16 Chapitre 4 : Les Fonctions et les Procédures 20 Chapitre 5 : Les Enregistrements et les Fichiers 31 Chapitre 6 : La Récursivité 35 Chapitre 7 : La Complexité Algorithmique 40 Chapitre 8 : Les Pointeurs 43 Références bibliographiques 58 4 Dr. M. AMAD Chapitre 1 : Généralités et Notions de Base 1. Introduction L'algorithmique est l'étude des algorithmes. Un algorithme est une méthode permettant de résoudre un problème donne en un temps fini ; Un algorithme est une suite de raisonnements ou d'opérations qui fournit la solution d'un problème. Le programme ne sera que la traduction de l'algorithme dans un langage de programmation, c'est-à-dire, un langage plus simple que le français dans sa syntaxe, sans ambiguïtés, que la machine peut utiliser et transformer pour exécuter les actions qu'il peut décrire. Pascal, C, Java et Visual Basic sont des noms de langages de programmation LAROUSSE : « un ensemble de règles opératoires dont l’enchaînement permet de résoudre un problème au moyen d’un nombre fini d’opérations. » Réalisation d’un programme La résolution d’un problème donné passe par une succession d’étapes à savoir : La réalisation d'un programme passe par l'analyse descendante du problème : il faut réussir à trouver les actions élémentaires qui, en partant d'un environnement initial, nous conduisent à l'état final. Une fois ces actions déterminées, il suffit de les traduire dans le langage de programmation choisi. Durant l'écriture d'un programme, on peut être confronté à 2 types d'erreur : Problème Enoncé explicite Algorithme Programme 1 5 Dr. M. AMAD 1. Les erreurs syntaxiques : elles se remarquent à la compilation et sont le résultat d'une mauvaise écriture dans le langage de programmation. 2. Les erreurs sémantiques : elles se remarquent à l'exécution et sont le résultat d'une mauvaise analyse. Ces erreurs sont beaucoup plus graves car elles peuvent se déclencher en cours d'exploitation du programme. 2. Base d’un langage algorithmique Le langage algorithmique est un langage générique permettant de traiter tous type de problème par la concaténation des instructions. 2.1 Structure de Base La structure générale d’un algorithme (Programme) est la suivante : 1. Algorithme Nom-d’Algorithme ; 2. déclaration des variables et des constantes 3. Déclaration des fonctions 4. Début 5. ….. 6. Liste des instructions 7. ……….. 8. Fin. 2.2 Variables et constantes Une variable est un espace mémoire nommé de taille fixe, prenant au cours de déroulement de l’algorithme un nombre indéfini de valeurs différentes. Ce changement de valeur se fait par l’opération d’affectation notée (). La variable diffère de la notion de constante qui, comme son nom l’indique, ne prend qu’une valeur unique au cours de l’exécution de l’algorithme. La partie déclaration permet de spécifier quelles seront les variables utilisées au cours de l’algorithme ainsi que le type de valeur quelles doivent respectivement prendre. Parmi les types des variables les plus utilisés, on trouve : 2.2.1 Entier : (1,2, 3,….) Le type entier caractérise l’ensemble des nombres entiers. Les opérations arithmétiques possibles sur ce type sont : L’addition ‘+’, ‘-‘, ‘*’, ‘/’. Appliquées sur des opérandes de type entier, elles fournissent un résultat entier sauf l’opération ‘/’ qui fournit un résultat réel. Tandis que les opérations de relation notées par ‘<’, ‘>’, ‘>=’, ‘<=’, ‘<>’ fournissent un résultat logique. Exemples : Const x = 1 ; Var A : entier ; Var A, b : entier ; Var coefficient_module : entier ; 2.2.2 Réel : (flottant : 1.0, 1.35, 1E+12, …) Représente l’ensemble des nombres réels. Les opérations ‘+’,’-‘, ‘*’, ‘/’ appliqués sur des opérandes de type réel fournissent un résultat de type réel. 6 Dr. M. AMAD Exemples Var A : réel ; Var A, b : réel ; Var moyen_générale : réel ; 2.2.3 Caractère : (A, a, Z, …) Ce type englobe tout les caractères nécessaires à l’écriture de texte. Exemples : Const x = 1.1 ; Var A : Caractère ; Var A, b : Caractère ; Var xxxxxxxxxxxx : Caractère; 2.2.4 Booléen : (Vrai, Faux) Ce type de variable ne peut prendre que les valeurs vrai ou faux. Les operateurs logiques ET, OU, NON, appliqués à des opérandes de type booléen fournissent un résultat booléen. Exemples : Const x = ‘a’ ; Var A : Booléen ; Var A, b : Booléen; Var Admis : Booléen; 2.3 Identificateurs et mots clés Un identificateur est le nom d’une variable, d’une constante ou le nom d’un algorithme (programme), c’est un seul mot composé de chiffres et des caractères à l’exception de quelques uns. Un mot clé est un mot réservé, il a une utilisation spéciale dans un programme comme par exemple : program, begin, end, if, else, case, repeat, until, for, do, while, then, var, … Règles d’écriture des identificateurs 1. Un identificateur ne peut être un mot clé 2. Un identificateur doit commencer par un caractère alphanumérique 3. Un identificateur ne doit pas contenir des caractères spéciaux comme : ?, !, *, … Exemple Quels sont les identificateurs valides et ceux qui ne sont pas valides ? M, ax, 8b, s_m, farid, exo1, exo ?, 34, then, nom programme, …. 2.4 Instructions Une instruction est une action élémentaire commandant à l’ordinateur un calcul, une instruction de base peut être : A : Une affectation ou une opération arithmétique L’affectation est l’action élémentaire principale puisque c’est par son intermédiaire que l’on peut modifier la valeur d’une variable, elle a pour syntaxe : Variable valeur ou variable expression ; 7 Dr. M. AMAD Exemple Algorithme exemple-Affectation ; Var A, B : Entier ; Debut ……………….. A 10 ; B A+15 ; Fin. B : Cas d’utilisation d’une affectation Pour modifier la valeur d’une variable … A10 ; B5 ; AA+B ; … Pour affichage sur écran L’affichage est l’action élémentaire permettant à un algorithme de fournir des résultats à l’utilisateur, il se fait par l’intermédiaire de la commande (Fonction) Ecrire. … A10 ; B 5 ; CA+B ; Ecrire (« j’ai calculé la somme de A+B ») ; … Pour une lecture au clavier La lecture au clavier est une action élémentaire permettant de spécifier par une intervention humaine la valeur d’une variable. La saisie se fait par l’intermédiaire de la commande (Fonction) Lire. … A10 ; Lire (B) ; CA+B ; … Exercice 1 : (Savoir déchiffrer une séquence d’instructions) Dite que fait l’ensemble des instructions suivantes … A1 ; B10 ; CA*2+B-3 ; Ecrire (C) ; …. 2.5 Commentaires Un commentaire est un texte facultatif (des phrases) situé entre les symboles et { et } qui n’a aucun effet sur le fonctionnement du l’algorithme. Elle sert à expliquer le pourquoi de certaines instructions utilisés dans un programme. 8 Dr. M. AMAD Exemple Algorithme exo ; Var A : entier ; Debut /* ce programme calcul la somme de deux nombre*/ Lire (A) ; Lire (B) ; C :=A+B ; Ecrire (C) ; Fin. 2.6 Expressions Une expression est une combinaison de plusieurs opérandes (éventuellement des fonctions) et opérandes. Ils existent plusieurs types d’expressions : Les expressions arithmétiques Elles font intervenir les operateurs arithmétiques (+, -, /, *) ainsi que les deux operateurs DIV et uploads/Ingenierie_Lourd/ mi06-lessons-algo-str-donnees.pdf