Comprendre les réseaux, exécuter les algorithmes et vérifier les réponses : dix chapitres détaillés, quarante exercices de cours et trente exercices de TD, tous corrigés.
Avant de commencer. Un graphe décrit des objets et leurs relations. Un algorithme est une suite d’étapes pour résoudre une question sur ces données. Il suffit de connaître les tableaux, les boucles et les comparaisons. Le pseudo-code évite de dépendre d’un langage particulier.
Une progression du modèle au certificat
Un petit réseau de livraison fictif permet de comparer les méthodes. Les coûts sont abstraits : ce ne sont pas des distances entre villes réelles. D’autres exemples ciblés montrent les poids négatifs, les dépendances et les capacités. Les tableaux et les schémas proviennent de calculs exécutés sur les mêmes données.
Lire la situation et la définition encadrée avant la notation.
Reproduire les étapes et comparer les états intermédiaires.
Chercher les exercices avant d’ouvrir les corrigés.
Vérifier les hypothèses, les ressources et les limites.
Des objectifs différents. BFS minimise les étapes ; Dijkstra les coûts non négatifs. Un arbre couvrant minimise une installation ; un flot maximise un transport soumis à des capacités. Le dernier chapitre aide à choisir.
