Leçon 925 : Graphes : représentations et algorithmes.

(2019) 925
(2021) 925

Dernier rapport du Jury :

(2019 : 925 - Graphes : représentations et algorithmes.) Cette leçon offre une grande liberté de choix au candidat, qui peut choisir de présenter des algorithmes sur des problèmes variés : connexité, diamètre, arbre couvrant, flot maximal, plus court chemin, cycle eulérien, etc. mais aussi des problèmes plus difficiles, comme la couverture de sommets ou la recherche d’un cycle hamiltonien, pour lesquels il pourra proposer des algorithmes d’approximation ou des heuristiques usuelles. Une preuve de correction des algorithmes proposés est évidemment appréciée. Il est attendu que diverses représentations des graphes soient présentées et comparées, en particulier en termes de complexité.

(2017 : 925 - Graphes : représentations et algorithmes.) Cette leçon offre une grande liberté de choix au candidat, qui peut décider de présenter des algorithmes sur des problèmes variés : connexité, diamètre, arbre couvrant, flot maximal, plus court chemin, cycle eulérien, etc. mais aussi des problèmes plus difficiles, comme la couverture de sommets ou la recherche d’un cycle hamiltonien, pour lesquels il pourra proposer des algorithmes d’approximation ou des heuristiques usuelles. Une preuve de correction des algorithmes proposés sera évidemment appréciée. Il est attendu que diverses représentations des graphes soient présentées et comparées, en particulier en termes de complexité.

Développements :

Plans/remarques :

2018 : Leçon 925 - Graphes : représentations et algorithmes.


2017 : Leçon 925 - Graphes : représentations et algorithmes.


2016 : Leçon 925 - Graphes : représentations et algorithmes.


2015 : Leçon 925 - Graphes : représentations et algorithmes.


Retours d'oraux :

Pas de retours pour cette leçon.

Références utilisées dans les versions de cette leçon :

Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest (utilisée dans 49 versions au total)
Eléments d'algorithmique, Beauquier, Berstel et Chrétienne (utilisée dans 11 versions au total)
Types de données et algorithmes, Christine Froidevaux, Marie-Claude Gaudel, Michèle Soria (utilisée dans 9 versions au total)
Algebraic graph theory , Biggs (utilisée dans 1 versions au total)