Algorithmique et Structures de Données

1 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.

2 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.

3 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.

4 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.

5 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. 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. 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 ( ).

6 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 : 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 ; R el : (flottant : , , 1E+12.)

7 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 ; Caract re : (A, a, Z, ..) Ce type englobe tout les caract res n cessaires l criture de texte. Exemples : Const x = ; Var A : Caract re ; Var A, b : Caract re ; Var xxxxxxxxxxxx : Caract re; 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; 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.

8 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, .. 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.

9 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 .. A 10 ; B 5 ; A A+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.. A 10 ; B 5 ; C A+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.. A 10 ; Lire (B) ; C A+B ; .. Exercice 1 : (Savoir d chiffrer une s quence d instructions) Dite que fait l ensemble des instructions suivantes .. A 1 ; B 10 ; C A*2+B-3 ; Ecrire (C).

10 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. 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 MOD. Exemple : a + b c/d est une expression arithm tique Les expressions bool ennes (logiques) Elles font intervenir les operateurs logiques (and, or, not.)