Outils pour utilisateurs
formations:licence:2024-2025:ue:l3:al5
Différences
Ci-dessous, les différences entre deux révisions de la page.
| Les deux révisions précédentesRévision précédente | |||
| formations:licence:2024-2025:ue:l3:al5 [2025/01/29 10:45] – supprimée - modification externe (Date inconnue) 127.0.0.1 | formations:licence:2024-2025:ue:l3:al5 [2025/01/29 10:45] (Version actuelle) – ↷ Page déplacée de formations:licence:ue:l3:al5 à formations:licence:2024-2025:ue:l3:al5 admin | ||
|---|---|---|---|
| Ligne 1: | Ligne 1: | ||
| + | ~~NOTOC~~ | ||
| + | ====== Algorithmique (AL5) ====== | ||
| + | |||
| + | |||
| + | ===== Description ===== | ||
| + | |||
| + | De nombreux problèmes pratiques peuvent être modélisés à l'aide de graphes, et leur résolution nécessite des algorithmes de graphes. Ce cours explore les algorithmes pour les problèmes les plus classiques, tels que les parcours de graphes, le plus court chemin, les arbres couvrants de poids minimum, et le flot maximum. | ||
| + | |||
| + | ===== Syllabus ===== | ||
| + | ==== Sujets centraux ==== | ||
| + | |||
| + | - Introduction | ||
| + | * Graphes : définitions de base | ||
| + | * Représentation matricielle et par listes | ||
| + | * Lemme de la poignée de main | ||
| + | * Connexité | ||
| + | * Arbres | ||
| + | * Rappels sur la complexité algorithmique, | ||
| + | - Parcours de graphes | ||
| + | * Parcours en largeur (BFS) | ||
| + | * Parcours en profondeur (DFS) | ||
| + | * Graphes orientés acycliques (DAG) | ||
| + | * Tri topologique | ||
| + | * Composantes fortement connexes | ||
| + | - Plus court chemin | ||
| + | * Algorithme de Dijkstra | ||
| + | * Algorithme de Bellman--Ford | ||
| + | * Algorithme de Floyd--Warshall | ||
| + | * Algorithme de Johnson | ||
| + | - Arbres couvrants de poids minimum | ||
| + | * Algorithme de Kruskal | ||
| + | * Implementation de l' | ||
| + | * Algorithme de Prim | ||
| + | * Implementation de l' | ||
| + | - Flot max, coupe min | ||
| + | * Algorithme de Ford--Fulkerson | ||
| + | * Algorithme de Edmonds--Karp | ||
| + | * Couplages dans les graphes bipartis : théorèmes de König et de Hall | ||
| + | - Algorithme d' | ||
| + | * Algorithme d' | ||
| + | * Graphes eulériens, algorithme de Hierholzer | ||
| + | * Problème du voyageur de commerce (TSP) : algorithme de Christofides | ||
| + | |||
| + | ==== Sujets potentiellement traités ==== | ||
| + | |||
| + | -- Coloration | ||
| + | * Algorithme glouton de coloration | ||
| + | * Graphes d' | ||
| + | ===== Pré-requis ===== | ||
| + | |||
Outils de la page
Sauf mention contraire, le contenu de ce wiki est placé sous les termes de la licence suivante : CC Attribution-Noncommercial-Share Alike 4.0 International
