Please enable JavaScript.

Coggle requires JavaScript to display documents.

Algo & Structure de données - Coggle Diagram

- - - - Array
        
        =Tableau de données
        Avantage principal : Accès direct aux éléments par index
        Opération la plus lente : Insérer un élément au début
        
        Avantages
        
        Les éléments sont numérotés à partir de 0
        
        Multi-dimensionnel
        
        Accès rapide par index : array[i]
        
        Taille fixe ou dynamique
        
        Inconvénients
        
        Ajouter/suppression un item au début
        
        Taille non redimensionnable
        
        Moins de flexibilité dans la taille et les types
        
        Non idéal pour les gros jeux de données
        
        O(n) quand il faut redimmensionner/ajouter un élément à la fin (quand il est plein)
      - List
        
        Slices
        
        Avec des opérations (+ ; - ; * ; etc.) Liste[5-2:5]
        
        Avec des valeurs négatives Liste[-3:-5]
        
        Avec [len(Liste)-3:5] (où len() compte la taille de la liste)
        
        Simple Liste[3:5] (Index 3 à 5)
        
        Avec 'Pas' Liste [1:5:2] = [1,3,5]
      - Stack
        
        =Pile (fr) : Last in First out (LiFo)
        push() : Ajouter un item
        pop() : sortir un item
      - Queue
        
        =File (fr) : FiFo (First in First out)
        Operation qui retire un élément d’une queue = dequeue.
        Ajouter avec : enqueue.
      - Linked List
        
        =liste chaînée (fr) : Chaque noeud = 1 poiteur.
        Opération la plus rapide = insérer au début
        Comment savoir si la fin de la liste est atteinte = quand le pointeur suivant est nul.
        
        Rq : Accéder rapidement au 100e élément = Array
        
        Liste simplement chaînée
        
        Structure de données linéaire où chaque nœud contient :
        • Une valeur (la donnée)
        • Un pointeur vers le nœud suivant
        
        Liste doublement chaînée
        
        Structure de données linéaire où chaque nœud contient :
        • Une valeur (la donnée)
        • Un pointeur vers le nœud suivant
        • Un pointeur vers le nœud précédent
        
        Liste circulaire
        
        Variante où le dernier nœud pointe vers le premier, formant une boucle.
        Chaque nœud pointe vers le suivant, et le dernier pointe vers la tête.
        
        Liste doublement circulaire
        
        Variante où le dernier nœud pointe vers le premier, formant une boucle.
        Chaque nœud pointe vers le suivant et le précédent, avec la tête et la queue reliées entre elles.
      - Liste Double
        
         Implémenter un système « annuler » (Ctrl + Z) = liste bidirectionnelle
    - - Tree
        
        Full Binary Tree
        
        Règle : Avoir 0 ou 2 enfants (pas un seul enfant)
        
        Est TOUJOURS un Complete Binary Tree
        
        Complete Binary Tree
        
        Règles :
        
        Chaque niveau est plein sauf le dernier niveau.
        
        Ou le denier nœud doit être à gauche.
        
        Remarque : Peut être facilement stocké dans un tableau
        
        Perfect Binary Tree
        
        Règles :
        
        Tous les nœuds ont 2 enfants
        
        Toutes les feuilles sont au même niveau
        
        Propriétés Mathématiques
        Hauteur : h
        Nombre total de nœuds : 2^(h+1) - 1
        Nombre de feuilles : 2^h
        Nombre de nœuds internes : 2^h - 1
        
        Exercices
        
        5 more items...
        
        Balanced Binary Tree
        
        Règle : Si pour chaque nœud, la différence de hauteur entre ses sous-arbres gauche et droit est au maximum 1.
        [h(Left subTree) - h(Right subTree)] <= 1
        
        Degenerate Tree
        
        Règle :
        Avoir un seul enfant au max
        
        Propriétés Mathématiques
        Hauteur : h = n - 1 (Maximum possible)
        Feuilles : 1 (Une seule feuille au bout)
        Noeuds internes : n - 1 (Tout sauf la feuille)
        Time Complexity : O(n) (Comme une liste chaînée)
        
        Binary Tree Traversal
        
        • Pre-order : root left right
        • In-order : left root right
        • Post-order : left right root
        
        Exercices
        
        Question 1 : Calculer Pré-order
        
        Réponse
        
        1 more item...
        
        Question 2 : Calculer In-Order
        
        Réponse
        
        1 more item...
        
        Question 3 : Calculer Post-Order
        
        Réponse
        
        1 more item...
        
        Binary Search Tree (BST)
        
        Règles :
        
        Tous les nœuds du sous-arbre GAUCHE ont des valeurs
        INFÉRIEURES au nœud
        
        Tous les nœuds du sous-arbre DROIT ont des valeurs
        SUPÉRIEURES au nœud
        
        Les sous-arbres gauche et droit sont eux-mêmes des
        BST
        
        Remarque : Il n'y a généralement pas de doublon dans un BST
        
        Avantages :
        • Recherche rapide : O(log n) en moyenne.
        • Insertion/Suppression efficaces.
        • Parcours in-ordre donne les éléments triés
        
        Exercices
        
        Question 1 : Ajouter 16
        
        Réponse
        
        1 more item...
        
        Question 2 : Ajouter 21
        
        Réponse
        
        1 more item...
        
        Question 3 : Ajouter 40
        
        Réponse
        
        1 more item...
        
        Dans cet arbre
        
        Time complexity :
        • Best case : O(log n)
        • Average case : O(log n)
        • Worst case : O(n)
        
        Règles du Delete :
        
        Si sous-arbre et enfants à droite : Minimum du sous-arbre droit.
        
        Sinon si Enfant de droite alors remonter au 1er plus grand sinon enfant de gauche alors remonter de 1.
        
        Exercice
        
        AVL Tree
        
        Arbre BST auto-équilibré. Equilibré si entre -1 et 1.
        
        Equilibré
        
        Types de rotation
        
        LL : Left-left
        
        1 more item...
        
        2 more items...
        
        LR : Left-Right
        
        2 more items...
        
        RR : Right-Right
        
        2 more items...
        
        RL : Right-Left
        
        2 more items...
        
        Breadth-first traversal
        
        Level-order : niveau par niveau et de gauche à droite
        
        Binary Heap
        
        Est une structure de données arborescente complète (ou presque complète) qui satisfait la propriété de tas : :arrow_right:
        Il est stocké dans un tableau
        
        Min-Heap : La valeur d’un nœud est ≤ à celles de ses enfants
        
        Max-Heap : La valeur d’un nœud est ≥ à celles de ses enfants.
        
        Règle :
        
        Tous les niveaux sont complets sauf potentiellement le dernier et sont remplis de gauche à droite.
        
        Indices :
        Parent(i) = [(i-1)/2]
        Left(i) = 2i+1
        Right(i) = 2i+2
        
        Deapth-First Traversal
        
        Processus de visiter chaque nœud d'un arbre binaire exactement une fois dans un ordre spécifique.
        
        Méthodes :
        Afficher tous les éléments
        Rechercher une valeur
        Copier l'arbre
        Calculer une propriété (hauteur, taille, etc.)
      - Graph
        
        Graphe Non-Orienté
        
        Graphe Orienté
        
        Graphe Pondéré
        
        Graphe Cyclique / Acyclique
        
        Graphe Non-Connecté
        
        Graphe Connecté
        
        Graphe Simple
        
        Complete graph
        
        Weakly connected
        
        Weakly not connected
        
        Graphe représenté sous forme de matrice
      - Trie (Sort)
        
        Selection Sort
        
        Méthode :
        
        Cherche le plus petit
        
        Echange (swap)
        
        Avance
        
        Time Complexity : O(n²)
        
        Bubble Sort
        
        Compare les éléments 2 à 2 et les échange immédiatement s’ils ne sont pas dans le bon ordre.
        Remonte le plus grand élément vers la fin du tableau
        
        Time Complexity :
        
        Insertion Sort
        
        Construit progressivement un sous-tableau trié et y insère les éléments à leur place.
        
        Merge Sort
        
        Appelé aussi « Tri par Fusion ».
        Divide and conquer
        Méthodes :
        
        Couper en deux l'array niveau par niveau jusqu'à avoir une pair ou 1 valeur afin de les comparées entre elles.
        
        Trier et merger les valeurs dans un tableau trié
        
        Time Cmplexity : O(log n)
        
        Quick Sorting
        
        Tri Rapide
        
        Time Complexity : O(n log n)
        
        Heap Sort
        
        Ou tri par tas,
        Est un algo de tri qui s’appuie sur la structure de données « Heap » (tas binaire), en général un Max-Heap.
        Méthodes :
        
        **Transformer** le tableau en Max Heap (la plus grande valeur est à la racine)
        
        **Retirer** la racine (le maimum) et la **placer à la fin** du tableau
        
        **Réajuster le tas** pour que le suivant plus grand **remonte** à la racine
        
        **Répéter** jusqu’à ce que tout soit trié
        
        Résultat final : le tableau est trié en ordre croissant.
      - Hash Table
        
        Une table de hachage est une Structure de données qui associe des clés a des valeurs pour permettre un accès extrêmement rapide
        
        Opérations :
        
        Search
        
        Insert
        
        Delete
        
        Access
      - Search
        
        Linear Search
        
        Le plus simple algo de recherche
        Parcourir une liste élément par élément, du début à la fin jusqu’à trouver la valeur recherchée.
        Méthodes :
        
        Commencer au 1er élément du tableau
        
        Comparer chaque élément à la valeur recherchée
        
        Si un élément correspond, retourner son indice (index)
        
        Si la fin du tableau est atteinte sans correspondance, retourner -1 (ou « Non trouvé »)
        
        Binary Search
        
        Ou recherche Dichotomique,
        Est un algo très efficace pour trouver une valeur dans une liste triée.
        Méthodes :
        
        Il fonctionne ne **divisant** la liste en 2 parties à **chaque étape**.
        
        A chaque **comparaison**, on **élimine** la moitié des éléments restants.
  - - - le Slice fonctionne également avec les chaîne str
- - - - 3 principes fondamentaux pour faire fonctionner l’automate
        
        Algorithme
        
        Langage (Python, R, etc.)
        
        Une structure de données
  - - - Une structure de données = Une information
      - Elle intervient dans
        
        Les algorithmes
        
        Le stockage de données
        
        L’échange des données
  - - - Juger l’algorithme par rapport à
        
        Accès
        
        Insertion
        
        Suppression
        
        Recherche