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
