Remerciez-le!

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

Université Badji Mokhtar Annaba Département d’Informatique, Licence 2ième Année

Université Badji Mokhtar Annaba Département d’Informatique, Licence 2ième Année Polycopie du Cours Algorithmique et Structures de donnée Avancées Rédigé par Dr. Sabri GHAZI E-mail : sabri.ghazi@univ-annaba.dz Année universitaire 2020-2021 URL du cours : https://elearning.univ-annaba.dz/course/view.php?id=708 URL du fichier : https://elearning.univ-annaba.dz/mod/resource/view.php?id=33981 Université Badji Mokhtar , Annaba, Département d’Informatique, L2, ALGO-STD-2, sabri.ghazi@univ-annaba.dz Page2 Université Badji Mokhtar , Annaba, Département d’Informatique, L2, ALGO-STD-2, sabri.ghazi@univ-annaba.dz Page3 Liste des figures Figure 1, algorithme permet de trouver un élément dans un tableau. ................................................ 14 Figure 3, l’évolution des fonctions selon la taille d’entrée n ............................................................ 17 Figure : schéma d’une liste simplement chaînée ............................................................................... 21 Figure : schéma d’une liste doublement chaînée ............................................................................... 24 Figure : schéma d’une liste doublement chaînée circulaire ............................................................... 26 Figure : Schéma, algorithme de tri stable ......................................................................................... 28 Figure : Déroulement de l’algorithme bubble Sort ............................................................................ 29 Figure : déroulement de l’algorithme Insertion Sort .......................................................................... 30 Figure : Déroulement de l’algorithme Selection Sort ........................................................................ 31 Figure déroulement de l’algorithme Merge Sort ................................................................................ 32 Figure : Déroulement de l’algorithme Shell Sort ............................................................................... 33 Figure : Exemple de déroulement de l’algorithme Shell Sort ............................................................ 34 Figure : Déroulement de l’algorithme Quick Sort ............................................................................. 34 Figure : Déroulement de l’algorithme Quick Sort ............................................................................. 35 Figure : La structure arborescente du système de fichier. .................................................................. 37 Figure : exemple d’un arbre ............................................................................................................... 38 Figure : hauteur d’un arbre................................................................................................................. 38 Figure : La notions de fils père, frère dans un arbre .......................................................................... 39 Figure : exemple d’un arbre binaire de recherche. ............................................................................. 39 Le parcours d’un arbre peut se faire selon deux stratégies : en profondeur, ou bien en largeur. ....... 40 Figure : parcours d’un arbre en largeur .............................................................................................. 40 On peut parcourir un arbre selon trois façons : .................................................................................. 40 Figure :exemple d’un arbre binaire .................................................................................................... 41 Figure : Un TAS Max ( Max HEAP). ................................................................................................ 44 Figure : Exemple d’un Graphe ........................................................................................................... 47 Figure : exemple d’une représentation stattique d’un graphe ........................................................... 49 Figure : schéma d’une représentation d’un graphe en utilisant les listes ( dynamique) .................... 50 Figure : représentation d’un graphe en utilisant une stratégie dynamique ........................................ 50 Figure : Stratégie déclaration d’un arbre en dynamique .................................................................... 51 Figure : déroulement de l’algorithme En profondeur d’abord ( deep first). ...................................... 52 Figure , Déroulement d’un parcours largeur d’abord......................................................................... 55 Figure : Exemple d’un graphe orienté ................................................................................................ 57 Figure : Déroulement de l’algorithme de Dijkstra ............................................................................. 58 Université Badji Mokhtar , Annaba, Département d’Informatique, L2, ALGO-STD-2, sabri.ghazi@univ-annaba.dz Page4 Liste d’algorithmes: Figure 2, algorithme de permutation entre les case i et j du tableau A. ............................................. 17 Listing : Déclaration d’une liste en ALGO et en C ............................................................................ 21 Listing : Insertion d’un élément dans une liste simplement chaînée ................................................. 22 Listing parcourir une liste .................................................................................................................. 22 Listing suppression d’un élément d’une liste ..................................................................................... 23 Listing fonction de vérification de l’existence d’un élément dans une liste ...................................... 23 Listing procédure modifier un élément dans une liste ....................................................................... 24 Listing déclaration d’une liste doublement chaînée ........................................................................... 24 Listing Parcourir une liste doublement chaînée. ................................................................................ 24 Listing Parcourir une liste doublement chaînée. ................................................................................ 25 Listing d’insertion d’un élément dans une liste doublement chaînée, en tête. .................................. 25 Listing d’insertion d’un élément dans une liste doublement chaînée, en Queue. ............................. 25 Listing : Insertion dans une liste doublement chaînée circulaire ....................................................... 26 Listing : Bubble Sort algorithme ........................................................................................................ 29 Listing : L’algorithme Insertion Sort .................................................................................................. 30 Listing de l’algorithme Selection Sort ............................................................................................... 31 Listing : Code de L’algorithme Merging Sort .................................................................................... 32 Listing : L’algorithme Shell Sort ........................................................................................................ 34 Listing : Algorithme Quick Sort......................................................................................................... 35 Listing : Suite de l’algorithme Quick Sort ......................................................................................... 36 Listing : Déclaration d’un arbre binaire ............................................................................................. 39 Listing : Parcours en largeur d’un arbre binaire................................................................................. 40 Listing parcours en ordre préfixé ....................................................................................................... 41 Listing parcours en ordre postfixé ..................................................................................................... 41 Listing parcours en ordre infixé ......................................................................................................... 42 Listing : Chercher un élément dans un arbre binaire. ........................................................................ 42 Tableau : déroulement de la fonction Exist ....................................................................................... 43 Listing : Suppression d’un élément d’un TAS ................................................................................... 45 Listing, insertion d’un élément dans un tas........................................................................................ 45 Listing : Déclaration d’un graphe en utilisant un tableau .................................................................. 50 Listing : Déclaration d’un arbre en utilisant une stratégie dynamique ............................................. 51 Figure : Déroulement d’un exemple de parcours en largeur d’un graphe.......................................... 53 PListing algorithme de parcours d’un graphe en utilisant la stratégie Depth first ............................ 54 Listing suite de l’algorithme depth first ............................................................................................. 54 Listing : Parcours en largeur d’un graphe .......................................................................................... 54 Listing : Parcours d’un graphe breadth first ....................................................................................... 56 Listing Algorithme de Djikstra ......................................................................................................... 57 Université Badji Mokhtar , Annaba, Département d’Informatique, L2, ALGO-STD-2, sabri.ghazi@univ-annaba.dz Page5 Université Badji Mokhtar , Annaba, Département d’Informatique, L2, ALGO-STD-2, sabri.ghazi@univ-annaba.dz Page6 Sommaire Liste des figures ................................................................................................................................... 3 Liste d’algorithmes: ............................................................................................................................. 4 Sommaire ..................................................................................................................................... 6 Introduction .......................................................................................................................................... 9 Le programme détaillé du module Algorithmique et Structure des données avancée ................... 10 Chapitre 1 : La Complexité Algorithmique........................................................................................ 14 Comment peut-on comparer les algorithmes ? .............................................................................. 14 La notation asymptotique ............................................................................................................... 15 La notation thêta Θ ......................................................................................................................... 16 Complexité : ................................................................................................................................... 16 La notation Big O (appelée aussi la notation de Landau) : ............................................................ 16 La complexité constante O(1) : .................................................................................................. 17 Complexité linéaire O(n) : ......................................................................................................... 17 Complexité logarithmique O(log n) ........................................................................................... 17 Complexité linéaire logarithmique O( n log(n)) ........................................................................ 18 Complexité polynomiale O(nc) , ................................................................................................ 18 Complexité exponentielle O(cn), ................................................................................................ 18 Complexité factorielle O (n!) ..................................................................................................... 18 Chapitre 1 : les structures de données linéaires: ................................................................................ 20 Les stratégies de représentation d’une liste chaînée : .................................................................... 20 Définition : ................................................................................................................................. 20 Déclaration d’une liste simplement chaînée ( Simply Linked List)............................................... 21 Les opérations sur les listes :.......................................................................................................... 21 1- Création d’une liste : .............................................................................................................. 21 Parcourir une liste simplement chaînée ..................................................................................... 22 2-Supression d’un élément d’une liste : ..................................................................................... 22 3- Vérifier l’existence d’un élément dans la liste : .................................................................... 23 Liste doublement chaînée : ............................................................................................................ 24 Structure de données d’une liste doublement chaînée : ............................................................. 24 Parcours d’une liste doublement chainée : ................................................................................. 24 Les opérations de base sur une liste doublement chaînée : ........................................................ 25 Insertion d’un élément dans une liste doublement chainée circulaire. ...................................... 26 Chapitre Les algorithmes de tris ........................................................................................................ 27 Le tris (Sorting en anglais) : ........................................................................................................... 27 Les objectifs de tri ...................................................................................................................... 27 Les principales propriétés des algorithmes de tris ......................................................................... 27 In-place vs Not in-place: ............................................................................................................ 27 Stable vs Not Stable ................................................................................................................... 27 Université Badji Mokhtar , Annaba, Département d’Informatique, L2, ALGO-STD-2, sabri.ghazi@univ-annaba.dz Page7 Adaptative vs non-Adaptative: ................................................................................................... 28 Bubble Sort Algorithm ................................................................................................................... 28 Compléxite ............................................................................................................................. 28 Insertion Sort .................................................................................................................................. 30 Complexité O(N²) ...................................................................................................................... 30 Fonctionnement :........................................................................................................................ 30 Selection sort .................................................................................................................................. 31 Complexite ............................................................................................................................. 31 Fonctionnement ...................................................................................................................... 31 Fonctionnement du tri « selection sort » : .................................................................................. 31 Merge sort .................................................................................................................................. 32 Complexite O(N log(N)) ............................................................................................................. 32 Fonctionnement .......................................................................................................................... 32 Shell sort ........................................................................................................................................ 33 Fonctionnement de l’algorithme shell Sort ................................................................................ 33 Quick sort ................................................................................................................................... 34 Heap sort .................................................................................................................................... 36 Chapitre les structures de données hiérarchiques : Les arbres ........................................................... 37 Introduction : .............................................................................................................................. 37 Définition : ..................................................................................................................................... 38 Terminologie : ................................................................................................................................ 38 Les Arbres binaires......................................................................................................................... 39 Définitions .................................................................................................................................. 39 Parcours d’un arbre binaire : .......................................................................................................... 40 Parcours en largeur ou hiérarchique ........................................................................................... 40 Parcours en profondeur: ............................................................................................................. 40 Algorithme de parcours en pré-ordre : (ordre préfixé) .............................................................. 41 Algorithme de parcours en post-ordre : (ordre postfixé) ........................................................... 41 Algorithme de parcours en ordre symétrique : (ordre infixé) .................................................... 42 Les opérations de base sur un arbre binaire : ................................................................................. 42 Calculer la hauteur d’un arbre binaire ........................................................................................ 42 Chercher si un élément existe dans l’arbre ou non .................................................................... 42 Les TAS (Heap) .............................................................................................................................. 44 Définition : ................................................................................................................................. 44 Un autre exemple : ................................................................................................................. 44 Les opérations sur un Heap : ...................................................................................................... 45 Suppression d’un élément d’un Heap : ...................................................................................... 45 Insertion d’un élément dans un TAS : ........................................................................................ 45 Université Badji Mokhtar , Annaba, Département d’Informatique, L2, ALGO-STD-2, sabri.ghazi@univ-annaba.dz Page8 Chapitre : les graphes ......................................................................................................................... 46 Objectifs : ....................................................................................................................................... 46 Définitions .................................................................................................................................. 46 Utilisation ................................................................................................................................... 46 Graphe Orienté : ......................................................................................................................... 47 Terminologie : ............................................................................................................................ 48 Structure de données ...................................................................................................................... 49 Dynamique : En utilisant des listes chaînées. ............................................................................ 49 Stratégie statique ........................................................................................................................ 49 Stratégie dynamique ................................................................................................................... 50 Stratégie dynamique .................................................................................................................. 51 Opérations de base sur un graphe .................................................................................................. 51 Autres opérations: .......................................................................................................................... 51 Parcours d’un graphe ..................................................................................................................... 52 Parcours en profondeur ( deep first) .......................................................................................... 52 Parcours largeur d’abord(breadth first) ...................................................................................... 54 Graphe connexe .......................................................................................................................... 56 La recherche du plus court chemin. ........................................................................................... 56 Exemple de problème de plus court chemin .............................................................................. 57 Code de l’algorithme de Dijikstra .............................................................................................. 57 L’algorithme de Dijkstra ............................................................................................................ 58 Déroulement de l’Algorithme de Dijkstra ................................................................................. 58 Références .......................................................................................................................................... 59 Université Badji Mokhtar , Annaba, Département d’Informatique, L2, ALGO-STD-2, sabri.ghazi@univ-annaba.dz Page9 Introduction De son intitulé « Algorithmiques et Structures de données avancées », ce cours est axé sur le concept des structures de données et les algorithmes qu’on peut exploiter pour les traiter. L’étudiant apprendra les bonnes pratiques à adopter lorsqu’il fait face à un problème algorithmique. Comment les données peuvent être représentées et stockées dans la mémoire de la machine. Et quelles opérations uploads/Litterature/ 01-algo03-ghazi-intro.pdf