Algorithme

Exercices Corrigés sur les Algorithmes

Les algorithmes sont au cœur de l’informatique et des mathématiques appliquées. Comprendre leur fonctionnement et savoir les concevoir est essentiel pour résoudre efficacement des problèmes complexes. Cet article présente une série d’exercices sur les algorithmes, accompagnés de leurs solutions détaillées. Ces exercices couvrent divers aspects des algorithmes, incluant les structures de données, les méthodes de tri et de recherche, et l’analyse de complexité.

Exercice 1 : Tri à Bulles

Énoncé :
Implémentez un algorithme de tri à bulles pour trier un tableau d’entiers en ordre croissant.

Solution :
Le tri à bulles fonctionne en parcourant le tableau à plusieurs reprises, en comparant des éléments adjacents et en les échangeant s’ils sont dans le mauvais ordre. Ce processus est répété jusqu’à ce que le tableau soit trié.

def tri_a_bulles(tab):
    n = len(tab)
    for i in range(n):
        for j in range(0, n-i-1):
            if tab[j] > tab[j+1]:
                tab[j], tab[j+1] = tab[j+1], tab[j]
    return tab

# Exemple d'utilisation
tab = [64, 34, 25, 12, 22, 11, 90]
print(tri_a_bulles(tab))

Exercice 2 : Recherche Dichotomique

Énoncé :
Implémentez un algorithme de recherche dichotomique (ou binaire) pour trouver un élément dans un tableau trié.

Solution :
La recherche dichotomique divise le tableau en deux parties égales à chaque étape et compare l’élément cherché avec l’élément du milieu pour déterminer dans quelle moitié continuer la recherche.

def recherche_dichotomique(tab, x):
    gauche, droite = 0, len(tab) - 1
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if tab[milieu] == x:
            return milieu
        elif tab[milieu] < x:
            gauche = milieu + 1
        else:
            droite = milieu - 1
    return -1

# Exemple d'utilisation
tab = [2, 3, 4, 10, 40]
x = 10
print(recherche_dichotomique(tab, x))

Exercice 3 : Algorithme de Dijkstra

Énoncé :
Implémentez l’algorithme de Dijkstra pour trouver le plus court chemin dans un graphe pondéré depuis un sommet source.

Solution :
L’algorithme de Dijkstra utilise une file de priorité pour explorer les chemins les plus courts en partant du sommet source et en mettant à jour les distances les plus courtes vers chaque nœud.

import heapq

def dijkstra(graphe, source):
    distances = {vertex: float('infinity') for vertex in graphe}
    distances[source] = 0
    priority_queue = [(0, source)]

    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)

        if current_distance > distances[current_vertex]:
            continue

        for neighbor, weight in graphe[current_vertex].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

# Exemple d'utilisation
graphe = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}
source = 'A'
print(dijkstra(graphe, source))

Ces exercices illustrent différents types d’algorithmes et leurs applications pratiques. En les résolvant, vous renforcez votre compréhension des concepts fondamentaux de l’algorithmique. La pratique régulière et l’analyse détaillée des solutions vous permettront de développer des compétences solides en conception et en optimisation d’algorithmes.

Série d’Exercices Avancés sur les Algorithmes

Exercice 1 : Algorithme de Prim

Énoncé :
Implémentez l’algorithme de Prim pour trouver l’arbre couvrant minimal d’un graphe pondéré non orienté.

Solution :
L’algorithme de Prim construit l’arbre couvrant minimal en ajoutant successivement les arêtes les moins coûteuses qui n’introduisent pas de cycles.

import heapq

def prim(graphe, start):
    mst = []
    visited = set([start])
    edges = [(cost, start, to) for to, cost in graphe[start].items()]
    heapq.heapify(edges)

    while edges:
        cost, frm, to = heapq.heappop(edges)
        if to not in visited:
            visited.add(to)
            mst.append((frm, to, cost))
            for to_next, cost in graphe[to].items():
                if to_next not in visited:
                    heapq.heappush(edges, (cost, to, to_next))

    return mst

# Exemple d'utilisation
graphe = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}
print(prim(graphe, 'A'))

Exercice 2 : Algorithme de KMP (Knuth-Morris-Pratt)

Énoncé :
Implémentez l’algorithme de Knuth-Morris-Pratt (KMP) pour rechercher un motif dans une chaîne de caractères.

Solution :
L’algorithme de KMP utilise un tableau de préfixes pour éviter de re-vérifier les caractères déjà appariés, ce qui améliore l’efficacité de la recherche.

def kmp(pattern, text):
    def build_prefix_table(pattern):
        prefix_table = [0] * len(pattern)
        j = 0
        for i in range(1, len(pattern)):
            if pattern[i] == pattern[j]:
                j += 1
                prefix_table[i] = j
            else:
                if j != 0:
                    j = prefix_table[j-1]
                    i -= 1
                else:
                    prefix_table[i] = 0
        return prefix_table

    prefix_table = build_prefix_table(pattern)
    i = j = 0
    matches = []

    while i < len(text):
        if pattern[j] == text[i]:
            i += 1
            j += 1
        if j == len(pattern):
            matches.append(i-j)
            j = prefix_table[j-1]
        elif i < len(text) and pattern[j] != text[i]:
            if j != 0:
                j = prefix_table[j-1]
            else:
                i += 1
    return matches

# Exemple d'utilisation
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
print(kmp(pattern, text))

Exercice 3 : Algorithme de Ford-Fulkerson

Énoncé :
Implémentez l’algorithme de Ford-Fulkerson pour trouver le flux maximal dans un réseau de transport.

Solution :
L’algorithme de Ford-Fulkerson utilise une approche de recherche en profondeur pour trouver des chemins augmentants dans le réseau de transport jusqu’à ce que plus aucun chemin augmentant ne soit trouvé.

def bfs(rGraph, s, t, parent):
    visited = [False] * len(rGraph)
    queue = []
    queue.append(s)
    visited[s] = True

    while queue:
        u = queue.pop(0)
        for ind, val in enumerate(rGraph[u]):
            if visited[ind] == False and val > 0:
                queue.append(ind)
                visited[ind] = True
                parent[ind] = u
                if ind == t:
                    return True
    return False

def ford_fulkerson(graph, source, sink):
    parent = [-1] * len(graph)
    max_flow = 0
    rGraph = [row[:] for row in graph]

    while bfs(rGraph, source, sink, parent):
        path_flow = float("Inf")
        s = sink
        while s != source:
            path_flow = min(path_flow, rGraph[parent[s]][s])
            s = parent[s]

        v = sink
        while v != source:
            u = parent[v]
            rGraph[u][v] -= path_flow
            rGraph[v][u] += path_flow
            v = parent[v]

        max_flow += path_flow
    return max_flow

# Exemple d'utilisation
graph = [[0, 16, 13, 0, 0, 0],
         [0, 0, 10, 12, 0, 0],
         [0, 4, 0, 0, 14, 0],
         [0, 0, 9, 0, 0, 20],
         [0, 0, 0, 7, 0, 4],
         [0, 0, 0, 0, 0, 0]]
source = 0
sink = 5
print(ford_fulkerson(graph, source, sink))

Ces exercices avancés mettent en lumière des algorithmes fondamentaux utilisés pour résoudre des problèmes complexes en informatique et en mathématiques appliquées. En les résolvant, vous pourrez non seulement renforcer vos compétences en algorithmique mais aussi comprendre les concepts sous-jacents qui rendent ces algorithmes efficaces et puissants. La pratique régulière et l’analyse approfondie de ces exercices vous aideront à maîtriser l’art de concevoir et d’optimiser des algorithmes.

Cas Particuliers des Algorithmes Avancés

Les cas particuliers dans les algorithmes avancés sont des scénarios spécifiques où les algorithmes peuvent se comporter différemment ou nécessiter des ajustements particuliers. Voici quelques cas particuliers pour chaque algorithme précédemment présenté.

Exercice 1 : Algorithme de Prim

Cas Particulier :
Graphe avec des arêtes de poids égal.

Description :
Lorsque toutes les arêtes ont le même poids, l’algorithme de Prim peut choisir n’importe quelle arête de manière arbitraire. Cependant, cela n’affecte pas le résultat final car tous les chemins ont le même coût.

graphe_egal = {
    'A': {'B': 1, 'C': 1},
    'B': {'A': 1, 'C': 1, 'D': 1},
    'C': {'A': 1, 'B': 1, 'D': 1},
    'D': {'B': 1, 'C': 1}
}
print(prim(graphe_egal, 'A'))

Exercice 2 : Algorithme de KMP (Knuth-Morris-Pratt)

Cas Particulier :
Motif avec des répétitions.

Description :
L’algorithme KMP est particulièrement efficace lorsque le motif contient des sous-motifs répétitifs. Le tableau de préfixes aide à éviter de réexaminer les caractères déjà comparés, optimisant ainsi la recherche.

text_repetition = "ABABABABABABABABABAB"
pattern_repetition = "ABAB"
print(kmp(pattern_repetition, text_repetition))

Exercice 3 : Algorithme de Ford-Fulkerson

Cas Particulier :
Graphe avec cycles.

Description :
Lorsque le graphe contient des cycles, l’algorithme de Ford-Fulkerson peut nécessiter plusieurs itérations pour trouver le chemin augmentant optimal. Les cycles peuvent introduire des complexités supplémentaires, mais l’algorithme est conçu pour les gérer.

graph_cycle = [[0, 10, 10, 0, 0, 0],
               [0, 0, 2, 4, 8, 0],
               [0, 0, 0, 0, 9, 0],
               [0, 0, 0, 0, 0, 10],
               [0, 0, 0, 6, 0, 10],
               [0, 0, 0, 0, 0, 0]]
source = 0
sink = 5
print(ford_fulkerson(graph_cycle, source, sink))

Autres Cas Particuliers Intéressants

Cas Particulier 1 : Algorithme de Dijkstra avec des Arêtes Négatives

Description :
L’algorithme de Dijkstra ne fonctionne pas correctement si le graphe contient des arêtes avec des poids négatifs. Il peut retourner des résultats incorrects ou entrer dans une boucle infinie. Dans ce cas, il est recommandé d’utiliser l’algorithme de Bellman-Ford.

def bellman_ford(graph, source):
    distance = {vertex: float('inf') for vertex in graph}
    distance[source] = 0

    for _ in range(len(graph) - 1):
        for u in graph:
            for v, weight in graph[u].items():
                if distance[u] != float('inf') and distance[u] + weight < distance[v]:
                    distance[v] = distance[u] + weight

    for u in graph:
        for v, weight in graph[u].items():
            if distance[u] != float('inf') and distance[u] + weight < distance[v]:
                return "Graph contains a negative-weight cycle"

    return distance

# Exemple d'utilisation
graph_negative = {
    'A': {'B': 1, 'C': 4},
    'B': {'C': -3, 'D': 2},
    'C': {'D': 3},
    'D': {}
}
print(bellman_ford(graph_negative, 'A'))

Cas Particulier 2 : Tri à Bulles avec un Tableau Déjà Trié

Description :
Le tri à bulles est inefficace pour les grands tableaux, mais il peut détecter un tableau déjà trié en une seule passe. En ajoutant un drapeau pour vérifier si des échanges ont été effectués, on peut optimiser le tri.

def tri_a_bulles_optimise(tab):
    n = len(tab)
    for i in range(n):
        echangé = False
        for j in range(0, n-i-1):
            if tab[j] > tab[j+1]:
                tab[j], tab[j+1] = tab[j+1], tab[j]
                echangé = True
        if not échangé:
            break
    return tab

# Exemple d'utilisation
tab_trie = [1, 2, 3, 4, 5]
print(tri_a_bulles_optimise(tab_trie))

Conclusion

Ces cas particuliers montrent comment les algorithmes peuvent être adaptés ou comment leur comportement peut changer dans des situations spécifiques. Comprendre ces cas aide à anticiper et à résoudre des problèmes potentiels lors de l’application des algorithmes dans des scénarios réels. La pratique de ces cas particuliers améliore la compréhension et la maîtrise des algorithmes avancés.


Exercices Avancés sur les Algorithmes

Exercice 1 : Algorithme de Floyd-Warshall

Énoncé :
Implémentez l’algorithme de Floyd-Warshall pour trouver les plus courts chemins entre toutes les paires de sommets dans un graphe pondéré. Vous devez également gérer les arêtes avec des poids négatifs, mais sans cycles de poids négatif.

Solution :
L’algorithme de Floyd-Warshall est une méthode dynamique pour trouver les plus courts chemins entre toutes les paires de sommets. Il fonctionne en mettant à jour les distances entre les sommets de manière itérative.

def floyd_warshall(graph):
    dist = [[float('inf')] * len(graph) for _ in range(len(graph))]

    for i in range(len(graph)):
        dist[i][i] = 0

    for u in range(len(graph)):
        for v, weight in graph[u].items():
            dist[u][v] = weight

    for k in range(len(graph)):
        for i in range(len(graph)):
            for j in range(len(graph)):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

# Exemple d'utilisation
graph = [
    {1: 3, 2: 8, 3: -4},
    {0: 3, 3: 1},
    {1: 4},
    {2: 7}
]

distances = floyd_warshall(graph)
for row in distances:
    print(row)

Exercice 2 : Algorithme de Branch-and-Bound pour le Problème du Sac à Dos

Énoncé :
Implémentez l’algorithme de Branch-and-Bound pour résoudre le problème du sac à dos (Knapsack problem). Donnez une solution optimale pour un ensemble donné d’objets avec des valeurs et des poids, et une capacité maximale du sac.

Solution :
L’algorithme de Branch-and-Bound explore les solutions possibles de manière hiérarchique en utilisant une approche de division et d’évaluation, en rejetant les branches non prometteuses en fonction des bornes calculées.

class Node:
    def __init__(self, level, profit, weight, bound):
        self.level = level
        self.profit = profit
        self.weight = weight
        self.bound = bound

def bound(node, n, W, profits, weights):
    if node.weight >= W:
        return 0
    profit_bound = node.profit
    j = node.level + 1
    total_weight = node.weight
    while j < n and total_weight + weights[j] <= W:
        total_weight += weights[j]
        profit_bound += profits[j]
        j += 1
    if j < n:
        profit_bound += (W - total_weight) * profits[j] / weights[j]
    return profit_bound

def knapsack(profits, weights, W):
    n = len(profits)
    Q = []
    u = Node(-1, 0, 0, 0)
    v = Node(-1, 0, 0, 0)
    max_profit = 0
    u.bound = bound(u, n, W, profits, weights)
    Q.append(u)

    while Q:
        Q.sort(key=lambda x: x.bound, reverse=True)
        u = Q.pop(0)

        if u.level == -1:
            v.level = 0
        if u.level == n-1:
            continue
        v.level = u.level + 1

        v.weight = u.weight + weights[v.level]
        v.profit = u.profit + profits[v.level]

        if v.weight <= W and v.profit > max_profit:
            max_profit = v.profit

        v.bound = bound(v, n, W, profits, weights)

        if v.bound > max_profit:
            Q.append(v)

        v = Node(v.level, u.profit, u.weight, 0)
        v.bound = bound(v, n, W, profits, weights)

        if v.bound > max_profit:
            Q.append(v)

    return max_profit

# Exemple d'utilisation
profits = [60, 100, 120]
weights = [10, 20, 30]
W = 50
print(knapsack(profits, weights, W))

Autres articles

Cours Algorithme PDF : la base de...
Dans ce cours algorithme, nous présentons différentes notions d'algorithme afin...
Read more
Tutos algorithme : des exemples d'algorithmes pour...
Dans ce tutoirel algorithme, nous exposons des exemples des algorithmes...
Read more
cours algorithme : les variables dimensionnes /...
Dans ce cours Algorithme, nous voyons la notion des tableaux.cours...
Read more

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *