Chapitre 03 - Structures de données linéaires. Dans ce troisième chapitre, nous allons présenter des structures de données linéaires optimisées, que l'on implémentera ensuite dans un langage à pointeur, typiquement le C++.
La notion d'optimisation portera sur la complexité algorithmique des opérations de traitement, comme l'insertion d'éléments, la suppression, la recherche, etc. On commencera par le concept général de liste chaînée, que l'on particularisera ensuite aux structures de pile et file. Cette partie sera consacrée à l'étude des listes chaînées, structures de données où l'on passe d'un élément à un autre grâce à un pointeur. En C et C++ on a présenté une structure de données nommée tableau permettant de stocker des valeurs de même type au sein d’une seule variable.
Le principal défaut d'un tableau est qu'une fois déclaré on ne peut pas modifier simplement sa taille. On va maintenant introduire une structure plus souple, celle de liste chaînée. Un maillon sera un objet composé de deux attributs : Listes simplement chaînées. Chapitre 04 - Structures de données arborescentes. Nous reviendrons dans cette première partie sur le concept d'arbre tel qu'on l'a introduit dans le cours de théorie des graphes.
Après quelques rappels, nous apporterons les compléments nécessaires pour définir la notion d'arbre binaire. Commençons de façon naturelle par rappeler la définition d'un arbre. Soit G un graphe orienté ou non. On dit que G est un arbre si et seulement si G est connexe et ne possède pas de cycles simples. Il existe une définition équivalente à la précédente, parfois plus utile selon le contexte. On dit que G est un arbre si et seulement si pour toute paire {x,y} de sommets de G, il existe une unique chaîne simple d’extrémités x et y. Nous renvoyons le lecteur au cours de théorie des graphes pour la preuve de cette équivalence.
Comme nous allors le voir sur des exemples, la représentation saggitale d'un arbre est intuitive et justifie d'ailleurs la terminologie. Example 1.1. Ces deux graphes vérifient bien les contraintes de la définition d'arbre : Chapitre 05 - Programmation dynamique. Le but de ce chapitre va être de présenter un paradigme de programmation alternatif à celui diviser pour régner. Nous allons en effet mettre en évidence l'une des faiblesses de celui-ci, en un mot des appels récursifs redondants, et voir comment y remédier. Cette nouvelle technique s'appellera programmation dynamique, et l'on verra qu'elle prend deux formes, l'une récursive et l'autre itérative. Après en avoir exposé le principe général, nous la mettrons en application sur deux grands problèmes classiques, celui du rendu de monnaie et celui du sac à dos. Nous allons dans cette partie pointer du doigt l'un des grands problèmes de la récursivité, puis proposer deux solutions pour y pallier.
La récursivité a ses limites Commençons par rappeler une fois de plus les trois étapes du paradigme "diviser pour régner" : Le problème est que dans certaines situations, les sous-problèmes ne sont pas indépendants. Chapitre 01 - Notion de complexité algorithmique. Rappelons, voir cours 1ADS, que le tri par sélection est un algorithme itératif réalisant le tri par ordre croissant d'une liste. Il consiste dans un premier temps à mettre à la première place le plus petit élément de la liste, puis à la seconde place le deuxième plus petit élément, etc. Sa description est la suivante : Rechercher dans la liste la plus petite valeur et la permuter avec le premier élément de la liste.Rechercher ensuite la plus petite valeur à partir de la deuxième case et la permuter avec le second élément de la liste.Et ainsi de suite jusqu’à avoir parcouru toute la liste.
En voici son implémentation en Python : def triSelection(l): for i in range(len(l)-1): indMini=i for j in range(i+1,len(l)): if l[j]<l[indMini]: indMini=j l[i],l[indMini]=l[indMini],l[i] Ici aussi la complexité sera fonction de la longueur n de la liste. Le pire des cas correspond à une liste triée par ordre décroissant. Conclusion, la complexité dans le pire des cas du tri par sélection est T(n)=2n2+3n-5. Chapitre 02 - Complexité des algorithmes récursifs. Le but est de déplacer nn disques de diamètres différents, d’une tour initiale (celle de gauche) à une tour finale (celle de droite) en passant par une tour intermédiaire (celle du milieu).
Initialement, tous les disques sont empilés sur la tour initiale, du plus grand au plus petit. Les règles de déplacement sont les suivantes : On ne peut bouger qu’un seul disque à la fois.On ne peut déplacer un disque que vers une tour vide, ou sur un disque plus grand. Etudions "à la main" le cas n=3n=3. Voici la position initiale : Effectuons ces trois premiers mouvements : Chapitre 06 - Algorithmes gloutons.