Tweet
Algorithmique
L'algorithmique est l'ensemble des règles qui sont impliquées dans la définition et la conception d'algorithmes, c'est-à-dire de processus systématiques de résolution par le calcul d'un problème permettant de décrire les étapes vers le résultat. En d'autres termes, un algorithme est une suite finie et non-ambiguë d'opérations permettant de résoudre un problème.
Vocabulaire basique :
Algorithme : suite de pas à suivre pour atteindre un objectif (forme schématique).
Implémentation : formulation concrète de l'algorithme, détails complexes, formule complète.
Problème paramétrique : problème dont toutes les variables ne sont pas spécifiées.
Instance du problème : apport des détails non fournis dans un problème paramétrique (forme schématique, plus complexe que l'algorithme et le problème paramétrique, mais moins que l'implémentation).
L'efficacité d'un algorithme : mesurée en fonction du nombre d'étapes qu'il contient pour résoudre un problème (moins il y en a, mieux c'est).
Le temps d'exécution : délai de temps d'exécution (dû à l'efficacité de l'algorithme).
Asymptotiquement : à partir d'une certaine valeur suffisamment grande, proche de l'infini.
Dichotomique : qui se sépare de deux en deux.
Paramètre formel : paramètre de la fonction (de l'algorithme), donnée d'entrée.
Récursion : un algorithme récursif est un algorithme qui fait appel à lui-même (dans la même fonction).
Itération : action de répéter plusieurs fois.
Induction : preuve par récurrence.
Algorithme de tri :
Tri par insertion : c'est le tri le plus couramment utilisé et un des plus simples. Il est par contre plus lent que les autres car sa complexité asymptotique est quadratique. Il est considéré comme le plus efficace sur des entrées de petite taille. La méthode est de parcourir le tableau à trier du début à la fin et d'insérer chaque élément à sa place parmi ceux qui précèdent. Il faut pour cela trouver où l'élément doit être inséré en le comparant aux autres, puis décaler les éléments afin de pouvoir effectuer l'insertion.
Tri par bulles : le tri à bulles (appelé aussi tri par propagation) consiste à faire remonter progressivement les plus grands éléments d'un tableau. Il n'est quasiment pas utilisé en pratique car il est considéré comme mauvais. Sa méthode consiste à parcourir le tableau en comparant les couples d'éléments successifs. Lorsque deux éléments successifs ne sont pas dans l'ordre croissant, ils sont échangés.
Tri par essais : il est considéré comme très peu efficace mais simple. Son principe est de parcourir le tableau en vérifiant, pour chaque permutation (façon de placer les nombres dans le tableau), si chaque nombre est plus grand que le précédent.
Tri par maximum : algorithme basé sur la recherche du nombre maximal contenu dans le tableau. Il vérifie ainsi tout le tableau pour en ressortir le chiffre le plus élevé.
Tri par fusion : diviser les problèmes en sous problèmes, les résoudre, rassembler les solutions des sous problème puis résoudre le problème général.
Tri rapide : fondé sur la méthode de "diviser pour régner". Il est optimal pour les tris par comparaison, mais la complexité dans le pire des cas est quadratique. C'est un des tris les plus rapides. La méthode consiste à placer un élément du tableau (appelé pivot) à sa place définitive, en permutant tous les éléments de telle sorte que tous ceux qui lui sont inférieurs soient à sa gauche et que tous ceux qui lui sont supérieurs soient à sa droite. Cette opération s'appelle le partitionnement. Pour chacun des sous-tableaux, on définit un nouveau pivot et on répète l'opération de partitionnement. Le processus est répété récursivement jusqu'à-ce que l'ensemble des données soient triées.
Tri par tas : on construit le tas dans le tableau, puis sachant que le maximum d'un tas ce trouve à la racine, on extrait ce maximum, on le remplace par la feuille la plus à droite du tas, et on entasse. On obtient un nouveau tas où le deuxième plus grand élément du tableau est la nouvelle racine. On continue jusqu'à avoir vidé le tas. Les éléments ont ainsi été prélevés dans l'ordre et placés dans un tableau. On peut ainsi même remplacer les données du tableau de départ par les nouvelles ce qui utilise moins de ressource mémoire vu que l'on travaille sur le même tableau. On parle dans ce cas d'un algorithme en place.
Fonctions :
Fonctions linéaires : fonctions du même ordre de grandeur de n.
Fonctions quadratiques : fonctions du même ordre de grandeur de n^2.
Fonctions polynomiales : fonctions du même ordre de grandeur de n^k (pour k >= 0).
Fonctions exponentielles : fonctions du même ordre de grandeur de 2^f(n) (pour une fonction polynomiale f).
Fonction surjective : fonction dont toutes les cases du tableau peuvent être utilisées.
Objets, pointeurs, listes chaînées :
Objet : tableau contenant plusieurs cases pouvant contenir des données de différents types ou de même type (tableau). Les cases d'un objet ne sont pas numérotées mais ont une étiquette. Les cases d'un objet s'appellent champs. (Lorsqu'il ne s'agit pas d'un tableau disposant de données de même types, un objet n'est pas indiqué comme ceci : O[cle] mais comme cela O.cle. ).
Pointeur : un pointeur redirige le contenu d'un objet (d'une variable) lui même contenu dans un autre objet (d'une autre variable).
Liste chaînée : une liste chaînée est un pointeur vers un élément. Celle-ci peut être récursive (lorsque son pointeur pointe vers nulle ou vers une valeur) ou circulaire (lorsque le dernier objet de celle-ci pointe vers le premier).
Liste doublement chaînée : c'est un objet avec des champs contenants des pointeurs vers d'autres champs dont les pointeur pointent vers un autre élément.
Objet liste doublement chaînée : c'est un objet avec un champ tête qui contient une liste doublement chaînée.
Structure FIFO : First In First Out, structure enlevant le premier élément inséré (le plus ancien). Cette structure s'appelle également file (queue, en anglais).
Structure LIFO : Last In First Out, structure enlevant le dernier élément inséré (le plus récent). Cette structure s'appelle également pile (stack, en anglais).
Arbres binaires :
Arbre binaire : pointeur vers un noeud qui s'appelle racine. La taille d'un arbre binaire est définie par le noeud le plus haut qu'il contient. Un arbre binaire est dit complet si toutes ses fleurs ont la même hauteur. Il est aussi dit équilibré.
Racine : base d'un arbre binaire. Sa hauteur est de 0. Sa valeur est null.
Sous-arbre : pointeurs fils pointant vers d'autres noeud.
Noeud : un noeud d'un arbre binaire est un objet contenant trois champs : sa valeur, et deux pointeurs pointants vers deux directions différentes (d'autres objets). La hauteur d'un noeud est définie par le nombre de noeuds qui le sépare de la racine (0+1 pour le premier noeud). Chaque noeud dispose d'un champ dénommé "par" qui pointe vers le noeud parent.
Parent : un noeud est un parent ayant des fils (pointeurs).
Fils : un fils un un pointeur situé dans un noeud parent.
Feuille : une feuille est un noeud sans fils (fleur).
Fleur : pointeur vers null. Sa hauteur est définie par celle du noeud auquel elle appartient.
Successeur : les successeurs d'un noeud N sont les noeuds qui contiennent une valeur plus petite que tous les noeuds qui ont une valeur plus grande que N.
Descendant : c'est le minimum du sous-arbre droit.
Ancêtre : lorsqu'un noeud n'a pas de fils droit, il est qualifié d'ancêtre du noeud parent.
Préfixe : voir les données d'un noeud d'un arbre binaire avant de visiter ses fils.
Infixe : voir les données d'un noeud d'un arbre binaire entre la visite de ses fils.
Postfixe : voir les données d'un noeud d'un arbre binaire après avoir visité ses fils.
Types d'arbres :
Arbre binaire de recherche : c'est un arbre binaire qui satisfait la propriété dichotomique suivante : pour tout noeud N contenu dans A, les valeurs des noeuds du sous-arbre gauche de N sont toutes plus petites ou égales à la valeur de N et les valeurs des noeuds du sous-arbre droit de N sont toutes plus grandes ou égales à la valeur de N. Le procédé de recherche d'un noeud ayant une certaine valeur dénommée K est le suivant : on commence par la racine, puis on suit le principe de la recherche dichotomique : si l'élément qu'on cherche est plus petit que la racine, on descend vers la gauche, sinon, on descend vers la droite. Pour insérer un nouvel élément dans un arbre binaire de recherche on suit le même principe : par recherche dichotomique ; on cherche l'endroit où l'élément est sensé se trouver et si cet endroit est libre on y insère l'élément. Effacer un élément d'un arbre binaire de recherche nécessite une discussion préliminaire ; car il faut à la fois préserver la structure de l'arbre et sa propriété dichotomique. Ainsi, tout d'abord, on recherche l'élément minimum dans la branche gauche, puis, pour trouver l'élément maximum on recherche dans la branche de droite. Si le noeud N à effacer est une feuille, on l'enlève directement. Si ce noeud à un seul fils, on le remplace par ce fils. Si ce noeud a deux fils, on ne peut le remplacer par les deux ; on échange alors la valeur du noeud droit de ce noeud N par la valeur de N puis on élimine cet ancien noeud. L'élimination se fait simplement car l'ancien noeud n'a plus qu'un fils, contrairement au nouveau qui lui en a deux.
Arbre parfait : un arbre parfait peut également aussi être représenté avec des tableaux, cependant, il n'est pas régi par des relation parents-fils mais par des relation arithmétiques entre les cases du tableau. Les noeuds de l'arbre sont ainsi stockés par niveaux. La première case contient la racine, les deux cases suivantes contiennent les fils gauche et droit du fils gauche, les deux cases suivantes les fils gauche et droit du fils droit, etc. Un arbre binaire parfait contient un champ dénommé "taille" permettant de le modifier (enlever des feuilles sans réduire le tableau en modifiant la variable "taille").
Arbres AVL : un arbre AVL un un arbre binaire de recherche automatiquement équilibré dont les hauteurs des deux sous-arbres d'un même noeud diffèrent au plus de un. Un noeud dont le facteur d'équilibrage est de 1, 0 ou -1 est donc considéré comme équilibré.
Arbres rouge et noir (ou arbre bicolore) : un arbre rouge et noir, ou arbre bicolore, est un arbre binaire de recherche qui, comme les arbres AVL, offre la meilleure garantie sur le temps d'insertion, de suppression et de recherche dans les cas défavorables. Ceci leur permet non seulement d'être utilisables dans des applications en temps réel, mais aussi de servir de fondement d'autres structures de données à temps d'exécution garanti dans les cas défavorables. Il dispose donc d'un attribut supplémentaire : sa couleur, qui est soit rouge, soit noire. La racine est noire. Le parent d'un noeud rouge est noir. Le chemin de chaque feuille à la racine contient le même nombre de noeuds noirs.
Tas, table de hachage :
Tas : un tas (heap, en anglais) est un arbre binaire parfait qui satisfait la propriété suivante : la valeur de chaque noeud est plus grande que la valeur de ses enfants. Pour construire un tas, il y a deux stratégie : la première consiste à aller du bas vers le haut, la seconde du haut vers le bas.
Situation de conflit : lorsqu'une donnée ne trouve pas de place disponible. Pour éviter cela, il est indiqué de stocker un pointeur dans chaque case du tableau renvoyant vers une liste chaînée.
Table de hachage : les données y sont mieux distribuées et évitent ainsi les situations de conflit. Chaque case ne contient pas plus de données qu'une autre. De plus, si le tableau contient M données, on souhaite que chaque noeud N de la table de hachage ne dépasse pas le ratio de N/M.
L'algorithmique est l'ensemble des règles qui sont impliquées dans la définition et la conception d'algorithmes, c'est-à-dire de processus systématiques de résolution par le calcul d'un problème permettant de décrire les étapes vers le résultat. En d'autres termes, un algorithme est une suite finie et non-ambiguë d'opérations permettant de résoudre un problème.
Vocabulaire basique :
Algorithme : suite de pas à suivre pour atteindre un objectif (forme schématique).
Implémentation : formulation concrète de l'algorithme, détails complexes, formule complète.
Problème paramétrique : problème dont toutes les variables ne sont pas spécifiées.
Instance du problème : apport des détails non fournis dans un problème paramétrique (forme schématique, plus complexe que l'algorithme et le problème paramétrique, mais moins que l'implémentation).
L'efficacité d'un algorithme : mesurée en fonction du nombre d'étapes qu'il contient pour résoudre un problème (moins il y en a, mieux c'est).
Le temps d'exécution : délai de temps d'exécution (dû à l'efficacité de l'algorithme).
Asymptotiquement : à partir d'une certaine valeur suffisamment grande, proche de l'infini.
Dichotomique : qui se sépare de deux en deux.
Paramètre formel : paramètre de la fonction (de l'algorithme), donnée d'entrée.
Récursion : un algorithme récursif est un algorithme qui fait appel à lui-même (dans la même fonction).
Itération : action de répéter plusieurs fois.
Induction : preuve par récurrence.
Algorithme de tri :
Tri par insertion : c'est le tri le plus couramment utilisé et un des plus simples. Il est par contre plus lent que les autres car sa complexité asymptotique est quadratique. Il est considéré comme le plus efficace sur des entrées de petite taille. La méthode est de parcourir le tableau à trier du début à la fin et d'insérer chaque élément à sa place parmi ceux qui précèdent. Il faut pour cela trouver où l'élément doit être inséré en le comparant aux autres, puis décaler les éléments afin de pouvoir effectuer l'insertion.
Tri par bulles : le tri à bulles (appelé aussi tri par propagation) consiste à faire remonter progressivement les plus grands éléments d'un tableau. Il n'est quasiment pas utilisé en pratique car il est considéré comme mauvais. Sa méthode consiste à parcourir le tableau en comparant les couples d'éléments successifs. Lorsque deux éléments successifs ne sont pas dans l'ordre croissant, ils sont échangés.
Tri par essais : il est considéré comme très peu efficace mais simple. Son principe est de parcourir le tableau en vérifiant, pour chaque permutation (façon de placer les nombres dans le tableau), si chaque nombre est plus grand que le précédent.
Tri par maximum : algorithme basé sur la recherche du nombre maximal contenu dans le tableau. Il vérifie ainsi tout le tableau pour en ressortir le chiffre le plus élevé.
Tri par fusion : diviser les problèmes en sous problèmes, les résoudre, rassembler les solutions des sous problème puis résoudre le problème général.
Tri rapide : fondé sur la méthode de "diviser pour régner". Il est optimal pour les tris par comparaison, mais la complexité dans le pire des cas est quadratique. C'est un des tris les plus rapides. La méthode consiste à placer un élément du tableau (appelé pivot) à sa place définitive, en permutant tous les éléments de telle sorte que tous ceux qui lui sont inférieurs soient à sa gauche et que tous ceux qui lui sont supérieurs soient à sa droite. Cette opération s'appelle le partitionnement. Pour chacun des sous-tableaux, on définit un nouveau pivot et on répète l'opération de partitionnement. Le processus est répété récursivement jusqu'à-ce que l'ensemble des données soient triées.
Tri par tas : on construit le tas dans le tableau, puis sachant que le maximum d'un tas ce trouve à la racine, on extrait ce maximum, on le remplace par la feuille la plus à droite du tas, et on entasse. On obtient un nouveau tas où le deuxième plus grand élément du tableau est la nouvelle racine. On continue jusqu'à avoir vidé le tas. Les éléments ont ainsi été prélevés dans l'ordre et placés dans un tableau. On peut ainsi même remplacer les données du tableau de départ par les nouvelles ce qui utilise moins de ressource mémoire vu que l'on travaille sur le même tableau. On parle dans ce cas d'un algorithme en place.
Fonctions :
Fonctions linéaires : fonctions du même ordre de grandeur de n.
Fonctions quadratiques : fonctions du même ordre de grandeur de n^2.
Fonctions polynomiales : fonctions du même ordre de grandeur de n^k (pour k >= 0).
Fonctions exponentielles : fonctions du même ordre de grandeur de 2^f(n) (pour une fonction polynomiale f).
Fonction surjective : fonction dont toutes les cases du tableau peuvent être utilisées.
Objets, pointeurs, listes chaînées :
Objet : tableau contenant plusieurs cases pouvant contenir des données de différents types ou de même type (tableau). Les cases d'un objet ne sont pas numérotées mais ont une étiquette. Les cases d'un objet s'appellent champs. (Lorsqu'il ne s'agit pas d'un tableau disposant de données de même types, un objet n'est pas indiqué comme ceci : O[cle] mais comme cela O.cle. ).
Pointeur : un pointeur redirige le contenu d'un objet (d'une variable) lui même contenu dans un autre objet (d'une autre variable).
Liste chaînée : une liste chaînée est un pointeur vers un élément. Celle-ci peut être récursive (lorsque son pointeur pointe vers nulle ou vers une valeur) ou circulaire (lorsque le dernier objet de celle-ci pointe vers le premier).
Liste doublement chaînée : c'est un objet avec des champs contenants des pointeurs vers d'autres champs dont les pointeur pointent vers un autre élément.
Objet liste doublement chaînée : c'est un objet avec un champ tête qui contient une liste doublement chaînée.
Structure FIFO : First In First Out, structure enlevant le premier élément inséré (le plus ancien). Cette structure s'appelle également file (queue, en anglais).
Structure LIFO : Last In First Out, structure enlevant le dernier élément inséré (le plus récent). Cette structure s'appelle également pile (stack, en anglais).
Arbres binaires :
Arbre binaire : pointeur vers un noeud qui s'appelle racine. La taille d'un arbre binaire est définie par le noeud le plus haut qu'il contient. Un arbre binaire est dit complet si toutes ses fleurs ont la même hauteur. Il est aussi dit équilibré.
Racine : base d'un arbre binaire. Sa hauteur est de 0. Sa valeur est null.
Sous-arbre : pointeurs fils pointant vers d'autres noeud.
Noeud : un noeud d'un arbre binaire est un objet contenant trois champs : sa valeur, et deux pointeurs pointants vers deux directions différentes (d'autres objets). La hauteur d'un noeud est définie par le nombre de noeuds qui le sépare de la racine (0+1 pour le premier noeud). Chaque noeud dispose d'un champ dénommé "par" qui pointe vers le noeud parent.
Parent : un noeud est un parent ayant des fils (pointeurs).
Fils : un fils un un pointeur situé dans un noeud parent.
Feuille : une feuille est un noeud sans fils (fleur).
Fleur : pointeur vers null. Sa hauteur est définie par celle du noeud auquel elle appartient.
Successeur : les successeurs d'un noeud N sont les noeuds qui contiennent une valeur plus petite que tous les noeuds qui ont une valeur plus grande que N.
Descendant : c'est le minimum du sous-arbre droit.
Ancêtre : lorsqu'un noeud n'a pas de fils droit, il est qualifié d'ancêtre du noeud parent.
Préfixe : voir les données d'un noeud d'un arbre binaire avant de visiter ses fils.
Infixe : voir les données d'un noeud d'un arbre binaire entre la visite de ses fils.
Postfixe : voir les données d'un noeud d'un arbre binaire après avoir visité ses fils.
Types d'arbres :
Arbre binaire de recherche : c'est un arbre binaire qui satisfait la propriété dichotomique suivante : pour tout noeud N contenu dans A, les valeurs des noeuds du sous-arbre gauche de N sont toutes plus petites ou égales à la valeur de N et les valeurs des noeuds du sous-arbre droit de N sont toutes plus grandes ou égales à la valeur de N. Le procédé de recherche d'un noeud ayant une certaine valeur dénommée K est le suivant : on commence par la racine, puis on suit le principe de la recherche dichotomique : si l'élément qu'on cherche est plus petit que la racine, on descend vers la gauche, sinon, on descend vers la droite. Pour insérer un nouvel élément dans un arbre binaire de recherche on suit le même principe : par recherche dichotomique ; on cherche l'endroit où l'élément est sensé se trouver et si cet endroit est libre on y insère l'élément. Effacer un élément d'un arbre binaire de recherche nécessite une discussion préliminaire ; car il faut à la fois préserver la structure de l'arbre et sa propriété dichotomique. Ainsi, tout d'abord, on recherche l'élément minimum dans la branche gauche, puis, pour trouver l'élément maximum on recherche dans la branche de droite. Si le noeud N à effacer est une feuille, on l'enlève directement. Si ce noeud à un seul fils, on le remplace par ce fils. Si ce noeud a deux fils, on ne peut le remplacer par les deux ; on échange alors la valeur du noeud droit de ce noeud N par la valeur de N puis on élimine cet ancien noeud. L'élimination se fait simplement car l'ancien noeud n'a plus qu'un fils, contrairement au nouveau qui lui en a deux.
Arbre parfait : un arbre parfait peut également aussi être représenté avec des tableaux, cependant, il n'est pas régi par des relation parents-fils mais par des relation arithmétiques entre les cases du tableau. Les noeuds de l'arbre sont ainsi stockés par niveaux. La première case contient la racine, les deux cases suivantes contiennent les fils gauche et droit du fils gauche, les deux cases suivantes les fils gauche et droit du fils droit, etc. Un arbre binaire parfait contient un champ dénommé "taille" permettant de le modifier (enlever des feuilles sans réduire le tableau en modifiant la variable "taille").
Arbres AVL : un arbre AVL un un arbre binaire de recherche automatiquement équilibré dont les hauteurs des deux sous-arbres d'un même noeud diffèrent au plus de un. Un noeud dont le facteur d'équilibrage est de 1, 0 ou -1 est donc considéré comme équilibré.
Arbres rouge et noir (ou arbre bicolore) : un arbre rouge et noir, ou arbre bicolore, est un arbre binaire de recherche qui, comme les arbres AVL, offre la meilleure garantie sur le temps d'insertion, de suppression et de recherche dans les cas défavorables. Ceci leur permet non seulement d'être utilisables dans des applications en temps réel, mais aussi de servir de fondement d'autres structures de données à temps d'exécution garanti dans les cas défavorables. Il dispose donc d'un attribut supplémentaire : sa couleur, qui est soit rouge, soit noire. La racine est noire. Le parent d'un noeud rouge est noir. Le chemin de chaque feuille à la racine contient le même nombre de noeuds noirs.
Tas, table de hachage :
Tas : un tas (heap, en anglais) est un arbre binaire parfait qui satisfait la propriété suivante : la valeur de chaque noeud est plus grande que la valeur de ses enfants. Pour construire un tas, il y a deux stratégie : la première consiste à aller du bas vers le haut, la seconde du haut vers le bas.
Situation de conflit : lorsqu'une donnée ne trouve pas de place disponible. Pour éviter cela, il est indiqué de stocker un pointeur dans chaque case du tableau renvoyant vers une liste chaînée.
Table de hachage : les données y sont mieux distribuées et évitent ainsi les situations de conflit. Chaque case ne contient pas plus de données qu'une autre. De plus, si le tableau contient M données, on souhaite que chaque noeud N de la table de hachage ne dépasse pas le ratio de N/M.