Next PDF List

Ecole Supérieure en Génie Electrique et Energétique d'OranAlgorithmique2et Structures deDonnées AvancéesSUPPORT DE COURSClassesPréparatoires(AncienProgramme)parFatima Zohra LEBBAHÀ ma mèreTABLE DES MATIÈRESIntroduction générale 71 rappel de cours 81.

1) Introduction81. 2) Types81. 3) Algorithme91.3. 1) Structure générale de l"algorithme101.3. 2) Alternatives101.3. 3) Boucles111. 4) Types structurés121.4. 1) Implémentation des vecteurs121.4. 2) Implémentation des matrices151.4. 3) Implémentation des enregistrements/articles171. 5) Procédures et fonctions171.5. 1) Procédures181.5. 2) Fonctions211. 6) Passage vers le C/C++231.6. 1) Boucles231.6. 2) Instructions de contrôle241.6. 3) Types prédéfinis261.6. 4) Opérateurs262 techniques de programmation c++282. 1) Introduction282. 2) Pointeurs282.2. 1) Définitions282.2. 2) Opérateurs associés aux pointeurs302. 3) Allocation de la mémoire322.3. 1) Allocation dynamique322.3. 2) Pointeurs et tableaux332.3. 3) Arithmétique des pointeurs362.3. 4) Tableaux et allocation dynamique372. 4) Portée des fonctions et des variables402.4. 1) Passage des arguments402.4. 2) Portée des variables462.4. 3) Variable globale/locale462.4. 4) Règles de résolution de portée463 récursivité 493. 1) Introduction493. 2) Construction d"un algorithme récursif493. 3) Environnement d"une fonction récursive503.3. 1) Environnement local5023.3. 2) Environnement global513. 4) Fonctionnement de la récursivité523. 5) Le passage algorithme récursif-algorithme itératif543.5. 1) Un seul appel récursif terminal553.5. 2) Un seul appel récursif non-terminal563. 6) Exemples d"application573.6. 1) Calcul du Plus Grand Commun Diviseur (PGCD)573.6. 2) La suite de Fibonacci584 complexité algorithmique 594. 1) Introduction594. 2) Analyse d"un algorithme594.2. 1) Déterminer les opérations fondamentales604.2. 2) Compter le nombre d"opérations (Calculer le coût)614. 3) Calcul de la complexité d"un algorithme624.3. 1) Taille d"une donnée624.3. 2) Ordre d"une fonction624. 4) Types de complexité644.4. 1) Complexité dans le meilleur des cas644.4. 2) Complexité dans le pire des cas644.4. 3) Complexité en moyenne654. 5) Bons et mauvais algorithmes654.5. 1) Classification des algorithmes[Prins,1994]654.5. 2) Exemple illustratif675 structures de données complexes 695. 1) Introduction695. 2) Structures linéaires695.2. 1) Listes contiguës695.2. 2) Listes chaînées simples735.2. 3) Exemples d"applications sur les listes chaînées835.2. 4) Listes doublement chaînées845.2. 5) Piles965.2. 6) Files1005. 3) Structures arborescentes1045.3. 1) Arbres1045.3. 2) Graphes1155. 4) Fichiers1185.4. 1) Généralités sur les flots1185.4. 2) Ouverture et fermeture d"un fichier1195.4. 3) Manipulations sur les fichiers1215.4.

4) Exemple illustratif122TABLE DES FIGURESFigure 1Structure d"une variable de type tableau à une dimen-sion13Figure 2Structure de la matrice16Figure 3Paramètres d"entrée/sortie de la procédurepermut20Figure 4Les variablesxetyen mémoire20Figure 5Paramètre d"entrée et résultat de la fonctionsomme22Figure 6Application de la fonctionsomme: le paramètre d"entrée etle résultat en mémoire23Figure 7Le pointeurpet la variable entierx29Figure 8Opérateur &(le pointeurpxpointe sur la variablex)30Figure 9Opérateurs & et30Figure 10Exemple de manipulation des pointeurs31Figure 11Le tableauvect34Figure 12Le tableautabet son illustration en mémoire36Figure 13Utilisation du pointeur référéptabsur le tableautab38Figure 14Allocation dynamique d"un tableau en mémoire39Figure 15La fonction " permut » avec passage par valeur42Figure 16Manipulation d"un pointeur-référence42Figure 17La fonction" permut » avec passage par adresse44Figure 18La fonction " permut » avec passage par référence45Figure 19Portée des variables47Figure 20Arbre d"exécution defact(3)51Figure 21Arbre d"exécution decmb(4,2)avecaetbvariables lo-cales52Figure 22Arbre d"exécution decmb(4,2)avec les variablesaetbglo-bales53Figure 23Pile d"exécution au cours d"exécution defact(3)54Figure 24Courbes respectives deCA1etCA262Figure 25Illustration de la liste contiguë en mémoire70Figure 26Liste contiguë de typecontig72Figure 27Liste contiguë de typecontig73Figure 28Liste chaînée74Figure 29Structure d"un maillon74Figure 30Structure d"une liste simplement chaînée75Figure 31Illustration d"une liste simplement chaînée en mémoire75Figure 32Insertion d"un maillon en tête de liste77Figure 33Insertion d"un maillon au milieu de la liste78Figure 34Insertion d"un maillon en queue de liste79Figure 35Suppression d"un maillon à l"entête de la liste80Figure 36Suppression d"un maillon au milieu de liste824Table des figures5Figure 37Suppression d"un maillon au milieu de liste83Figure 38Structure d"un maillon d"une liste doublement chaînée85Figure 39Structure d"une liste doublement chaînée85Figure 40Insertion d"un maillon à l"entête de la liste87Figure 41Insertion d"un maillon au milieu de la liste89Figure 42Insertion d"un maillon en tête de liste90Figure 43Suppression d"un maillon à l"entête de la liste92Figure 44Suppression d"un maillon au milieu d"une liste doublementchaînée94Figure 45Suppression du maillon en queue d"une liste doublementchaînée95Figure 46Structure d"une pile en utilisant une liste simplement chaî-née97Figure 47Insertion d"un élément dans une pile98Figure 48Suppression d"un élément dans une pile99Figure 49Structure d"une file en utilisant une liste simplement chaî-née101Figure 50Insertion d"un élément dans une file102Figure 51Suppression d"un élément dans une file103Figure 52Expression arithmétique(x(2y))+(x+(y/z)3)104Figure 53Structure d"un arbre binaire105Figure 54Arbre binaire d"entiers106Figure 55Représentation en mémoire de l"arbre de la figure54106Figure 56Niveaux de l"arbre binaire de la figure54 108Figure 57Arbre binaire correspondant à l"application de la fonctionajout_eltaprès insertion des valeurs5,6,12,3,11,4,2113Figure 58Arbre général d"entiers114Figure 59Arbre binaire correspondant à l"arbre général58 115Figure 60Exemple de graphes orienté et non-orienté115Figure 61Graphe orienté valué117Figure 62Liste d"adjacence correspondant au graphe de la sous-figure61 118Figure 63Flux d"E/S119LISTE DES TABLEAUXTable 1Types ordinaux9Table 2Types non-ordinaux9Table 3Types structurés : tableaux et enregistrements/articles12Table 4Types prédéfinis26Table 5Opérateurs utilisés en C++27Table 6Pile d"exécution defact(3)54Table 7Le temps d"exécution nécessaire pour une donnéen=20,50,100,200,500et1000et avec une complexité en fonc-tion den666INTRODUCTION GÉNÉRALELe présent support de cours est conforme à l"ancien programme enseigné à la2èmeannée des classes préparatoires au sein de notre école.

Ce document à pourbut l"étude de l"algorithmique et structures de données avancées en utilisant lestechniques du langage C++.L"algorithmique est une notion fondamentale pour proposer des méthodes derésolution des problèmes complexes issus de différents domaines. Éventuellement,la mise en place d"un algorithme induit la manipulation des données de typesappropriés.Dans ce présent support pédagogique, nous introduirons un ensemble de figures,avec le souci de toujours bien présenter et transmettre les différents conceptsalgorithmiques et de structures de données.

Nous couvrirons quatre aspects :les différents types de boucles et d"instructions de contrôle, les notions debase de la programmation structurée et la portée des variables,les principes de base et mathématique de récursivité en algorithmique.

Unaccent particulier est mis sur le comportement d"un algorithme récursifen mémoire, à savoir l"arbre et la pile d"exécution, à travers une variétéd"exemples d"application.

L"apport de la récursivité et ces inconvénients parrapport à sa version itérative,les notions fondamentales de la complexité algorithmique.

Nous mettons enavant son intérêt dans la conception des algorithmes.

Nous introduisons lestechniques de calculs de la complexité d"une manière simple et conforme auniveau de l"étudiant,la définition des structures de données linéaires et arborescentes et leursapplications.

Pour chaque type de structure, nous mettons en avant saposition et le comportement des primitives correspondants en mémoire.Outre leur importance intrinsèque, nous exposons l"apport d"un usagejudicieux de ces structures plus ou moins complexes.Ce support de cours s"organise en quatre chapitres :Le chapitre1les techniques d"évaluation de coûts d"algorithmes des basesalgorithmiques et de quelques notions du langage C++.Le chapitr e2porte sur les techniques de programmation C++.Le chapitr e3introduit les fondamentales de la récursivité algorithmique.Le chapitre4concerne la complexité algorithmique et les techniques d"éva-luation de coûts d"algorithmes.Le chapitre5consacré aux structures de données complexes, à savoir lesstructures linéaires, les structures arborescentes et les fichiers.71RAPPEL DE COURS1.1 introductionConcevoir un algorithme c"est comme monter une machine à calcul, sous formesd"une suite d"actions élémentaires conçue pour réaliser un traitement bien définisur des données (des entrées) et fournir en sortie des résultats bien précis.En d"autres termes, un algorithme est une méthode qui permet de résoudre unproblème issu d"un domaine donné.

Sa mise en oeuvre impose le passage par unlangage de programmation.Ce chapitre est un rappel, que nous jugeons indispensable, des notions de basede l"algorithmique enseigné en première année.

Afin de faciliter la compréhensiondes techniques de programmation enC++, nous mettons en avant la relation quiexiste entre le langage algorithmique et le langageC++, ainsi que les techniquesde passage d"une solution algorithmique vers un programme C++.1.2 typesL"application d"un algorithme sur un problème donné, fait appel à la manipula-tion d"un ensemble de variables.Une variable doit être définie, en lui attribuant unnomet untype.

En algorith-mique et dans tout langage de programmation, nous distinguons deux catégoriesde type, à savoir : les types standards1.2.1et les types personnels1.2.2.Définition1.2.1(type standard)Un type standard est un type de base prédéfini dansun langage bien défini.Définition1.2.2(type personnel)Un type personnel est un type qui n"est pas prédé-fini dans le langage de programmation.

Il est défini par le programmeur.Un type standard en algorithmique est caractérisé par :1.le domaine de définition: ensemble des valeurs que peut prendre une va-riable de ce type,2.les pr ésentationsinter neet exter ne:a)interne: présentation d"une variable de ce type en machine,b)externe: présentation d"une variable de ce type vis-à-vis le programmeuret l"utilisateur.81.3 algorithme 93.les opérateurs applicables sur ce type : ensemble des opérateurs que nouspouvons appliquer sur une variable de ce type,4.les fonctions standar dsou pr édéfinies: ensemble de fonctions propre aulangage, que nous pouvons appliquer sur une variable de ce type.Nous distinguons deux classes de types standards en algorithmique : ordinaux1.2.3et non-ordinaux1.2.4.Définition1.2.3(type ordinal)Un type ordinal est un type dont toute variable estcodée en machine par un entier qui précise son rang dans la suite des valeurs quidéfinissent ce type.Définition1.2.4(type non-ordinal)Un type non-ordinal est un type dont la variableest codée en machine par un entier qui ne précise en aucun cas, son rang par rapport auxvaleurs qui définissent ce type.Les tableaux1et2[Bensaoud-Senhadji,2005] représentent, respectivement lesdifférentes caractéristiques des deux classes typesordinauxetnon-ordinauxTable 1-T ypesor dinauxtypedomaineprésentationreprésentationopérateursfonctionsde valeursexterneinternebooléenfaux, vraifaux, vrai0,1et,ou,non,ord,pred,<,>,=,succ6=,,entiermin-entier max-entierDécimalcomplément à2+,-,*,ord,pred,(15ou -25)(16/32bits)<,>,=,6=,succ,,div,modcaractèrejeu fini("x", "?",code ASCII<,>,ord,pred,et ordonné"9", " " ")(1octet)6=,,succ,chrde caractèresTable 2-T ypesnon-or dinauxtypedomaineprésentationreprésentationopérateursfonctionsde valeursexterneinterneréelsous ensembleDécimalvirgule flottante+,-,*,/,sin,cos,abs,des réels(3.5ou -2.3)(32bits)<,>,=,sqrt,trunc,6=,,round,chaînesuite de"1chaîne"suite de<,>,length,caractères du"aujourd"hui"code ASCII=,6=,concatcode ASCII,1.3 algorithmeUn algorithme est une suite d"instructions qui doit respecter la syntaxe dulangage algorithmique.

Il permet la réalisation d"une suite de traitements sur une1.3 algorithme 10(des) donné(es), et fournir un(des) résultat(s).

Ce qui peut être illustré commesuit :Informations/données!Traitement!Informations/résultats1.3.

1) Structure générale de l"algorithmeLa structure générale d"un algorithme regroupe trois parties dans l"ordre,comme suit :1.Entête de l"algorithme: comporte le mot cléAlgorithme-principalsuivi dunom de l"algorithmeNom-algo, qui doit être de préférence conforme au rôlede l"algorithme.2.Envir onnementde l"algorithme : à ce niveau, nous devons :définir les types personnels, la syntaxe regroupe le mot cleftypesuividu nom du typenom-type, puis sa définition.déclar erles v ariableset les constantes.3.Cor psde l"algorithme: constitue une suite d"instructions, encadrée par lesdeux mots clés "début" et "fin" qui marquent, respectivement, le début et lafin de l"algorithme.

Ce qui donne le listing suivant :débutinstruction i-1;instruction i;instruction i+1;fin1.3.

2) AlternativesLes alternatives ou les structures conditionnelles servent à effectuer des vérifi-cations avant d"exécuter un bloc d"instructions.Nous distinguons deux types d"alternatives : complète et réduite.a.Alternatives complètes :la syntaxe de l"alternative se donne comme suit :si alorssinonfinsiElle comporte quatre mots cléssi,alors,sinonetfinsi.Si la conditionest vérifiée alors le bloc d"instructionssera exécuté, dans le cas contrairesera exécuté.Le mot cléfinsimarque la fin de l"alternative.1.3 algorithme 11b.Alternatives réduites :la syntaxe de l"alternative se donne comme suit :si alorsfinsiElle comporte trois mots cléssi,alorsetfinsi.Si la conditionest vérifiée alors le bloc d"instructionssera exécuté, sinon c"est l"instruction qui suitle mot cléfinsiqui sera exécutée.1.3.

3) BouclesUne boucle permet de boucler sur un bloc d"instructions et répéter son exécutionpour un nombre fini de fois.

L"itération s"arrête après avoir atteint laconditiond"arrêt, qui est exprimée soit par une expression booléenne, soit par le nombred"itération fixé au préalable.Nous distinguons trois types de boucles :tantque,pouretrépéter.a.La boucletant que:le schéma de la boucletantqueest le suivant :tantque fairefinfaireLe principe de la boucle est d"exécuter les instructionstant que la conditionest vérifiée.

Donc,est une condition de continuité pour la boucle.b.La bouclerépéter:le schéma de la bouclerépéterse donne comme suit :répéterjusquConditionElle permet d"exécuter les instructionsjusqu"à ce que la conditionsoit vérifiée.

Par conséquent,est une condition d"arrêt.c.La bouclepour:nous donnons le schéma de la bouclepourcomme suit :pour comp de ValInit à ValFinal pas fairefinfaire1.4 types structurés 12L"exécution de la bouclepoursuit le principe suivant :1.le compteur compest initialisé à la valeur initialeValInit,2.compest testé s"il ne dépasse pas la valeur finaleValFinal: sicomp>ValFinalalors on sort de la boucle sinon on passe à l"étape 3,3.le bloc d"instructions est exécuté,4.le compteur compest incrémentécomp comp+pas,5.aller à l"étape ( 2).NB :On peut omettre le pas dans le cas oùpas=1.1.4 types structurésUn type structuré est un type composé et basé sur les types prédéfinis oud"autres types personnels.

Nous avons deux types structurés : les tableaux et lesenregistrements(ou les articles).1.les tableaux : ils regroupent obligatoirement, plusieurs valeurs de mêmetype,2.les enregistrements(ou les articles) : il peuvent regrouper des valeurs detypes différents.Le tableau ci-dessous3[Bensaoud-Senhadji,2005] les différentes syntaxes quinous permettent de :définir le type,déclar erune v ariablede ce type,accéder à une v ariable(un champs ou un composant) de ce type.Table 3-T ypesstructur és: tableaux et enr egistrements/articlesTypeDéfinitionNom desAccès aux composantscomposantsvecteur outableau[typeindice]deT[expression]tableau à1type de basevariableT[23]dimensionT : tableau[210]deindicéecomposant dearrayentierrang9tableau à ntableauti,1,ti,2, ,ti,nvariableT[exp1,exp2, ,expn]dimensionsde type baseindicéeenregistrementarticlearticlefi1:t1;i2:t2; ;in:tngPar selecteurstructurechampsde champsrecordDate : articlefj: 1 31 ;m: 1 12;a: 2000 2010gDate.j1.4.

1) Implémentation des vecteursUn vecteur est un tableau à une dimension.

Il peut être illustré par la figureci-dessous1:1.4 types structurés 13a.Déclaration d"un v ecteur: la déclaration d"un vecteur de taillet=indnind1+1 se donne comme suit :nom-tab:tableau[ind1indn]detype-valeur;sachant que :nom-tabest le nom de la variable de type tableau,tableauest le mot clé qui désigne le type tableau en algorithmique,ind1etindnsont les indices début et fin des composants du tableau (voirla figure1),ind1ind2ind3indnFigure 1-Structur ed"une v ariablede type tableau à une dimensiontype-valeurest le type des valeurs qui vont être chargées dans le tableau.b.Accès à un composant du v ecteur: l"accès à laièmecase du vecteur se donnecomme suit :nom-tab[i],Exemple1.4.1(manipulation des boucles et des vecteurs)L"algorithme ci-dessouspermet de :saisir le nombr ede jours et la températur ede chaque jour ,calculer et afficher la moyenne des températur es.Par conséquent, nous avons à utiliser les variables :nbj,Setide type entier qui représentent respectivement, le nombre de jours, lasomme des températures et le compteur de la boucle "pour",Tde type tableau d"entiers, qui doit contenir les températures à saisir dans l"algo-rithme,moyennede type réel, qui doit contenir la moyenne calculée desnbjtempératures.La boucle "pour" :1.4 types structurés 14Algorithme-principal températurevar nbj,T : tableau[1 31] de entier;S,i : entier;moyenne : réel;débutécrire(lenombredejoursdumoislire(nbj);S 0;pour i de 1 à nbj faireécrire(tempéturedujour, i,lire(T[i]);S S+T[i];finfaire;moyenne S/nbj;écrire(Moyennedestempératures, moyenne);finLa boucle "répéter" :Algorithme-principal températurevar nbj,T : tableau[1 31] de entier;S,i : entier;moyenne : réel;débutécrire(lenombredejoursdumoislire(nbj);S 0;i 1;répéterécrire(tempéturedujour, i,lire(T[i]);S S+T[i];i i+1;jusqu0à i>nbj;moyenne S/nbj;écrire(Moyennedestempératures, moyenne);finLa boucle "tantque" :1.4 types structurés 15Algorithme-principal températurevar nbj,T : tableau[1 31] de entier;S,i : entier;moyenne : réel;débutécrire(lenombredejoursdumoislire(nbj);S 0;i 1;tantque i6nbj faireécrire(tempéturedujour, i,lire(T[i]);S S+T[i];finfaire;moyenne S/nbj;écrire(Moyennedestempératures, moyenne);fin1.4.

2) Implémentation des matricesUne matrice est un tableau à deux dimensions.

L"illustration de sa structure sedonne via la figure ci-dessous2:a.Déclaration de la matrice: la déclaration