Que retenir de l'algorithmique ?

En tant que développeur, comprendre comment utiliser les algorithmes et les structures de données est crucial pour concevoir des applications efficaces et performantes. Les bons algorithmes et les bonnes structures de données au bon endroit t'aideront à optimiser tes programmes, à améliorer leur vitesse et à économiser des ressources.

Dans cet article, nous allons explorer les principaux types d'algorithmes et de structures de données, ainsi que des exemples pratiques pour t'aider à comprendre.

Algorithmes

Les algorithmes sont des séquences d'instructions logiques et mathématiques utilisées pour résoudre des problèmes. Certains sont très simples, d'autres demandent plus de réflexion.

Les algorithmes itératifs sont des algorithmes qui répètent une série d'instructions jusqu'à ce qu'une condition de sortie soit remplie. Ils sont souvent utilisés pour résoudre des problèmes qui nécessitent une boucle de traitement.

def maximum(liste):
    max = liste[0]
    for nombre in liste:
        if nombre > max:
            max = nombre
    return max

Recherche linéaire de la valeur maximale dans une liste

Les algorithmes récursifs, quant à eux, sont des algorithmes qui se définissent en termes de solutions plus petites du même problème. Ils sont souvent utilisés pour résoudre des problèmes qui peuvent être divisés en sous-problèmes plus simples.

def est_palindrome(chaine):
    if len(chaine) <= 1:
        return True
    elif chaine[0] != chaine[-1]:
        return False
    else:
        return est_palindrome(chaine[1:-1])

Vérification récursive de palindrome

Les algorithmes diviser pour mieux régner se mettent aussi en œuvre en utilisant la récursivité. Ils résolvent un problème en le divisant en sous-problèmes plus petits, résolvent ces sous-problèmes de manière récursive, puis combinent les solutions pour obtenir la solution finale du problème initial.

def puissance(base, exposant):
    if exposant == 0:
        return 1

    if exposant % 2 == 0:
        resultat = puissance(base, exposant // 2)
        return resultat * resultat
    else:
        resultat = puissance(base, (exposant - 1) // 2)
        return base * resultat * resultat

Calcul de puissance avec l'approche diviser pour mieux régner

Les algorithmes de tri et de recherche peuvent être implémentés de différentes manières, en utilisant des approches itératives, récursives ou basées sur la technique de diviser pour mieux régner. Le tri par insertion (itératif) et le tri rapide sont des exemples d'algorithmes de tri, tandis que la recherche linéaire (itératif) et la recherche binaire (récursif) sont des exemples d'algorithmes de recherche.

def tri_rapide(liste):
    if len(liste) <= 1:
        return liste
    
    pivot = liste[0]
    plus_petits = [x for x in liste[1:] if x <= pivot]
    plus_grands = [x for x in liste[1:] if x > pivot]

    return tri_rapide(plus_petits) + [pivot] + tri_rapide(plus_grands)

Algorithme du tri rapide

La programmation dynamique consiste à résoudre des problèmes en décomposant le problème initial en sous-problèmes plus petits et en les résolvant de manière itérative. La clé de la programmation dynamique est de mémoriser les résultats des sous-problèmes résolus afin d'éviter de recalculer les mêmes solutions.

def plus_longue_sous_sequence_commune(chaine1, chaine2):
    m = len(chaine1)
    n = len(chaine2)

    dp = [[0] * (n+1) for _ in range(m+1)]

    for i in range(1, m+1):
        for j in range(1, n+1):
            if chaine1[i-1] == chaine2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[m][n]

Algorithme pour identifier la longueur de la plus longue sous-séquence commune

Enfin, les algorithmes gloutons sont une classe d'algorithmes qui résolvent les problèmes en faisant des choix localement optimaux à chaque étape. Mais les choix locaux effectués à chaque étape peuvent ne pas conduire à la solution globale optimale. Ce type d'algorithme est employé pour résoudre des problèmes d'optimisation où l'objectif est de trouver une solution acceptable en maximisant ou minimisant un certain critère.

def rendre_monnaie(montant, pieces):
    n = len(pieces)
    i = n - 1
    result = []
    while i >= 0 and montant > 0:
        if pieces[i] <= montant:
            montant -= pieces[i]
            result.append(pieces[i])
        else:
            i -= 1
    if montant != 0:
        return None
    return result

Algorithme glouton de rendu de monnaie

Structures de données

Les structures de données sont des méthodes de stockage et d'organisation des données pour faciliter leur utilisation et leur manipulation. Comme pour les algorithmes, il en existe une grande variété.

Les tableaux sont une structure de données linéaire qui stocke une collection d'éléments, accessibles par leur indice. Il est utilisé pour stocker des données ordonnées et permet un accès rapide aux éléments par leur position dans le tableau.

Dans les listes chaînées, chaque élément est lié au suivant, permettant ainsi des opérations d'ajout et de suppression efficaces à n'importe quelle position. Cette flexibilité en fait une structure idéale en cas de modifications fréquentes.

Un ensemble stocke une collection d'éléments uniques, sans ordre particulier. Il peut être utilisé lorsque l'on a besoin de vérifier rapidement la présence d'un élément dans une collection, sans se soucier de son ordre.

Bien qu'ils puissent différer légèrement dans leur implémentation spécifique, les tables de hachage, les tableaux associatifs ou les dictionnaires possèdent comment objectif principal de fournir une recherche efficace des éléments en fonction de leur clé.

mon_dict = {'pomme': 4, 'banane': 2, 'orange': 6, 'raisin': 8, 'kiwi': 3}

fruit = 'orange'
if fruit in mon_dict:
    quantite = mon_dict[fruit]
    print(f"La quantité de {fruit} est {quantite}.")
else:
    print(f"{fruit} n'est pas dans le dictionnaire.")

Recherche d'une valeur associée à une clé dans un dictionnaire

Basée sur le principe LIFO (Last In, First Out), la pile est utilisée pour les opérations d'empilement et de dépilement. Elle se révèle particulièrement utile lors de parcours en profondeur ou de l'évaluation d'expressions arithmétiques.

from collections import deque

class EditeurTexte:
    def __init__(self):
        self.texte = ""
        self.historique_actions = deque()

    def ajouter_texte(self, texte):
        self.texte += texte
        self.historique_actions.append(("ajout", texte))

    def supprimer_texte(self, longueur):
        texte_supprime = self.texte[-longueur:]
        self.texte = self.texte[:-longueur]
        self.historique_actions.append(("suppression", texte_supprime))

    def annuler_action(self):
        if self.historique_actions:
            action = self.historique_actions.pop()
            if action[0] == "ajout":
                self.texte = self.texte[:-len(action[1])]
            elif action[0] == "suppression":
                self.texte += action[1]

    def afficher_texte(self):
        print(self.texte)

editeur = EditeurTexte()
editeur.ajouter_texte("Hello")
editeur.ajouter_texte(" World!")
editeur.afficher_texte()  # Affiche "Hello World!"

editeur.supprimer_texte(6)
editeur.afficher_texte()  # Affiche "Hello"

editeur.annuler_action()
editeur.afficher_texte()  # Affiche "Hello World!"

Empilement et dépilement d'opérations en utilisant une pile

Quant à la file d'attente, elle se base sur le principe FIFO (First In, First Out). Elle trouve son utilité dans des situations telles que l'ordonnancement des processus ou la gestion des tâches en attente.

Un graphe est une structure de données non linéaire composée de nœuds (ou sommets) reliés par des arêtes. Il peut représenter des relations complexes entre des objets, tels que des réseaux sociaux, des itinéraires de transport ou des systèmes de recommandation. Les graphes permettent de modéliser et d'analyser les interactions et les dépendances entre les entités.

import networkx as nx
import matplotlib.pyplot as plt

graphe = nx.Graph()
graphe.add_nodes_from(['A', 'B', 'C', 'D', 'E'])
graph.add_edges_from([('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'E'), ('E', 'A')])

nx.draw(graph, with_labels=True)
plt.show()

Création d'un graphe avec les bibliothèques matplotlib et networkx

Les arbres, quant à eux, sont une forme spécifique de graphe, où chaque nœud a au plus un prédécesseur (à l'exception du nœud racine) et peut avoir plusieurs successeurs. Les arbres fournissent une structure hiérarchique pour organiser et hiérarchiser les données. Ils sont couramment utilisés dans les structures de fichiers, les bases de données et bien d'autres domaines.

import networkx as nx
import matplotlib.pyplot as plt


arbre = nx.DiGraph()

arbre.add_node('/', node_type='dossier')
arbre.add_node('/home', node_type='dossier')
arbre.add_node('/etc', node_type='dossier')
arbre.add_node('/dev', node_type='dossier')
arbre.add_node('/usr', node_type='dossier')
arbre.add_node('/var', node_type='dossier')
arbre.add_node('/home/user1', node_type='dossier')
arbre.add_node('/home/user2', node_type='dossier')
arbre.add_node('/etc/config.txt', node_type='fichier')
arbre.add_node('/etc/hosts', node_type='fichier')
arbre.add_node('/usr/bin', node_type='dossier')
arbre.add_node('/usr/lib', node_type='dossier')
arbre.add_node('/var/log.txt', node_type='fichier')

arbre.add_edges_from([
    ('/', '/home'),
    ('/', '/etc'),
    ('/', '/dev'),
    ('/', '/usr'),
    ('/', '/var'),
    ('/home', '/home/user1'),
    ('/home', '/home/user2'),
    ('/etc', '/etc/config.txt'),
    ('/etc', '/etc/hosts'),
    ('/usr', '/usr/bin'),
    ('/usr', '/usr/lib'),
    ('/var', '/var/log.txt')
])

node_labels = nx.get_node_attributes(arbre, 'node_type')
node_colors = ['lightblue' if node_type == 'dossier' else 'lightgreen' for node_type in node_labels.values()]

nx.draw_networkx(arbre, with_labels=True, node_color=node_colors)
plt.axis('off')
plt.show()

Création d'un arbre avec les bibliothèques matplotlib et networkx