TD1 Algorithmique Avancé et Complexité 2024/2025 PDF

Algorithmique Avancé et Complexité Master 1 informatique Université Sétif 1 Module : Algorithmique Avancé et Complexité Faculté des Sciences...

Algorithmique Avancé et Complexité Master 1 informatique Université Sétif 1 Module : Algorithmique Avancé et Complexité Faculté des Sciences Master 1 informatique Département d’informatique Année universitaire : 2024/2025 TD 1 Calculez la complexité des programmes suivants : def recherche_lineaire(tableau, cible): for i in range(len(tableau)): if tableau[i] == cible: return i # Retourne l'indice de l'élément trouvé return -1 # Retourne -1 si l'élément n'est pas trouvé # Exemple d'utilisation tableau = [3, 5, 2, 8, 1] cible = 2 indice = recherche_lineaire(tableau, cible) if indice != -1: print("Élément trouvé à l'indice :", indice) else: print("Élément non trouvé") def recherche_binaire_decroissante(tableau, cible): debut = 0 fin = len(tableau) - 1 while debut distances[sommet_actuel]: # Début de la condition continue # Passer à l'itération suivante # Fin de la condition # Mettre à jour les distances des voisins for voisin, poids in graphe[sommet_actuel].items(): # Début de la boucle pour les voisins nouvelle_distance = distances[sommet_actuel] + poids # Si la nouvelle distance est plus courte, mettre à jour la distance if nouvelle_distance < distances[voisin]: # Début de la condition distances[voisin] = nouvelle_distance précédent[voisin] = sommet_actuel # Mémoriser le prédécesseur heapq.heappush(file_priorite, (nouvelle_distance, voisin)) # Ajouter le voisin à la file # Fin de la condition # Fin de la boucle pour les voisins # Fin de la boucle principale # Afficher les distances et les chemins for sommet in graphe: # Début de la boucle pour afficher les résultats chemin = reconstruire_chemin(précédent, sommet) # Reconstruire le chemin pour sommet print(f"Distance à {sommet} : {distances[sommet]}, Chemin : {' -> '.join(chemin)}") # Fin de la boucle pour afficher les résultats return distances, précédent # Retourner les distances minimales et les prédécesseurs def reconstruire_chemin(précédent, destination): chemin = [ ] # Initialiser le chemin while destination is not None: # Début de la boucle pour reconstruire le chemin chemin.append(destination) destination = précédent[destination] # Fin de la boucle pour reconstruire le chemin chemin.reverse() # Inverser le chemin pour le montrer dans l'ordre return chemin # Exemple d'utilisation graphe = { 'A': {'B': 1, 'C': 2}, 'B': {'A': 1, 'D': 2, 'F': 3}, 'C': {'A': 2, 'E': 4, 'D': 3}, 'D': {'B': 2, 'C': 3,'F': 3, 'G': 3, 'E': 2}, 'E': {'C': 4, 'D': 2, 'G': 5}, 'F': {'B': 3, 'D': 3, 'G': 4}, 'G': {'D': 3, 'F': 4, 'E': 5}, } source = 'A' distances, précédents = dijkstra(graphe, source) Responsable du module : Dr Hadi F 2 Algorithmique Avancé et Complexité Master 1 informatique def bellman_ford(graphe, source): # Initialiser les distances distances = {sommet: float('inf') for sommet in graphe} # Distance initiale à chaque sommet est infinie distances[source] = 0 # La distance de la source à elle-même est 0 # Relaxation des arêtes for i in range(len(graphe) - 1): # Début de la boucle de relaxation for u in graphe: # Début de la boucle sur les sommets for v, poids in graphe[u].items(): # Début de la boucle sur les arêtes if distances[u] + poids < distances[v]: # Début de la condition distances[v] = distances[u] + poids # Mettre à jour la distance # Fin de la condition # Fin de la boucle sur les arêtes # Fin de la boucle sur les sommets # Fin de la boucle de relaxation # Détection de cycles négatifs for u in graphe: # Début de la boucle pour détecter les cycles for v, poids in graphe[u].items(): # Début de la boucle sur les arêtes if distances[u] + poids < distances[v]: # Début de la condition print("Le graphe contient un cycle négatif") return None # Retourner None si un cycle négatif est détecté # Fin de la condition # Fin de la boucle sur les arêtes # Fin de la boucle pour détecter les cycles return distances # Retourner les distances minimales # Exemple d'utilisation graphe = { 'A': {'B': 1, 'C': 2}, 'B': {'A': 1, 'D': 2, 'F': 3}, 'C': {'A': 2, 'E': 4, 'D': 3}, 'D': {'B': 2, 'C': 3,'F': 3, 'G': 3, 'E': 2}, 'E': {'C': 4, 'D': 2, 'G': 5}, 'F': {'B': 3, 'D': 3, 'G': 4}, 'G': {'D': 3, 'F': 4, 'E': 5}, } source = 'A' distances = bellman_ford(graphe, source) # Afficher les distances if distances is not None: print("Distances depuis le sommet", source, ":") for sommet, distance in distances.items(): print(f"Distance à {sommet} : {distance}") Responsable du module : Dr Hadi F 3 Algorithmique Avancé et Complexité Master 1 informatique import numpy as np def gauss_jordan(matrix): # Convertir la matrice en une matrice flottante A = np.array(matrix, dtype=float) n, m = A.shape for i in range(n): # Échanger les lignes pour avoir A[i][i] non nul if A[i][i] == 0: for j in range(i + 1, n): if A[j][i] != 0: A[[i, j]] = A[[j, i]] break # Normaliser la ligne i A[i] = A[i] / A[i][i] # Rendre zéro les autres éléments de la colonne i for j in range(n): if j != i: A[j] = A[j] - A[i] * A[j][i] return A[:, -1] # Retourner la dernière colonne qui contient les solutions # Exemple d'utilisation if __name__ == "__main__": # Système d'équations : 2x + 3y = 5, 4x + 9y = 15 matrix = [ [2, 3, 5], [4, 9, 15] ] solution = gauss_jordan(matrix) print("Les solutions sont :") for i, sol in enumerate(solution): print(f"x{i + 1} = {sol:.2f}") Responsable du module : Dr Hadi F 4 Algorithmique Avancé et Complexité Master 1 informatique def substitution(eq1, eq2): # Extraire les coefficients et les constantes des équations a1, b1, c1 = eq1 # a1*x + b1*y = c1 a2, b2, c2 = eq2 # a2*x + b2*y = c2 # Résoudre la première équation pour x if a1 != 0: x = (c1 - b1 * (c2 - a2 * a1) / a2) / a1 else: raise ValueError("L'équation 1 ne peut pas être utilisée pour isoler x.") # Substituer x dans la deuxième équation pour trouver y y = (c2 - a2 * x) / b2 return x, y # Exemple d'utilisation if __name__ == "__main__": # Équations : 2x + 3y = 5 et 4x + 6y = 10 eq1 = (2, 3, 5) # 2x + 3y = 5 eq2 = (4, 6, 10) # 4x + 6y = 10 (équation dépendante) try: x, y = substitution(eq1, eq2) print(f"La solution est : x = {x:.2f}, y = {y:.2f}") except ValueError as e: print(e) Responsable du module : Dr Hadi F 5 Algorithmique Avancé et Complexité Master 1 informatique def multiplication_naive(A, B): # Vérifier la compatibilité des dimensions if len(A) != len(B): raise ValueError("Le nombre de colonnes de A doit être égal au nombre de lignes de B.") # Dimensions des matrices n = len(A) # Nombre de lignes dans A m = len(B) # Nombre de colonnes dans B p = len(B) # Nombre de lignes dans B (égal au nombre de colonnes de A) # Initialiser la matrice résultante avec des zéros C = [[0 for _ in range(m)] for _ in range(n)] # Multiplication naïve for i in range(n): # Parcourir les lignes de A for j in range(m): # Parcourir les colonnes de B for k in range(p): # Parcourir les colonnes de A / lignes de B C[i][j] += A[i][k] * B[k][j] return C # Exemple d'utilisation if __name__ == "__main__": # Matrices A et B A=[ [1, 2, 3], [4, 5, 6] ] B=[ [7, 8], [9, 10], [11, 12] ] # Multiplication des matrices try: C = multiplication_naive(A, B) print("Résultat de la multiplication de A et B :") for row in C: print(row) except ValueError as e: print(e) Responsable du module : Dr Hadi F 6 Algorithmique Avancé et Complexité Master 1 informatique def karatsuba(x, y): # Convertir les nombres en chaînes pour obtenir leur longueur str_x = str(x) str_y = str(y) # Cas de base pour des nombres simples if len(str_x) == 1 or len(str_y) == 1: return x * y # Calculer la longueur maximale des deux nombres max_len = max(len(str_x), len(str_y)) half_len = max_len // 2 # Diviser les nombres en parties a = x // 10**half_len b = x % 10**half_len c = y // 10**half_len d = y % 10**half_len # Appliquer la méthode de Karatsuba ac = karatsuba(a, c) bd = karatsuba(b, d) ab_cd = karatsuba(a + b, c + d) # Calculer le produit selon la formule de Karatsuba return ac * 10**(2 * half_len) + (ab_cd - ac - bd) * 10**half_len + bd # Exemple d'utilisation if __name__ == "__main__": x = 1234 y = 5678 result = karatsuba(x, y) print(f"Le produit de {x} et {y} est : {result}") Responsable du module : Dr Hadi F 7