Leçon 926 : Analyse des algorithmes : complexité. Exemples.

(2018) 926
(2020) 926

Dernier rapport du Jury :

(2019 : 926 - Analyse des algorithmes : complexité. Exemples.) Il s’agit ici d’une leçon d’exemples. Le candidat doit prendre soin de proposer l’analyse d’algorithmes portant sur des domaines variés, avec des méthodes d’analyse également variées : approche combinatoire ou probabiliste, analyse en moyenne ou dans le pire cas. $\\$ Si la complexité en temps est centrale dans la leçon, la complexité en espace ne doit pas être négligée. La notion de complexité amortie a également toute sa place dans cette leçon, sur un exemple bien choisi, comme union find (ce n’est qu’un exemple).

(2017 : 926 - Analyse des algorithmes, complexité. Exemples.) Il s’agit ici d’une leçon d’exemples. Le candidat prendra soin de proposer l’analyse d’algorithmes portant sur des domaines variés, avec des méthodes d’analyse également variées : approche combinatoire ou probabiliste, analyse en moyenne ou dans le cas le pire. Si la complexité en temps est centrale dans la leçon, la complexité en espace ne doit pas être négligée. La notion de complexité amortie a également toute sa place dans cette leçon, sur un exemple bien choisi, comme union find (ce n’est qu’un exemple).

Développements :

Plans/remarques :

2018 : Leçon 926 - Analyse des algorithmes : complexité. Exemples.


2016 : Leçon 926 - Analyse des algorithmes : complexité. Exemples.


2015 : Leçon 926 - Analyse des algorithmes : complexité. Exemples.


Retours d'oraux :

Pas de retours pour cette leçon.

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

Types de données et algorithmes, Christine Froidevaux, Marie-Claude Gaudel, Michèle Soria (utilisée dans 9 versions au total)
Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest (utilisée dans 49 versions au total)
A Guide to Algorithm Design: Paradigms, Methods, and Complexity Analysis, Anne Benoît, Yves Robert, Frédéric Vivien (utilisée dans 5 versions au total)
Eléments d'algorithmique, Beauquier, Berstel et Chrétienne (utilisée dans 11 versions au total)
An Introduction to the Analysis of Algorithms, Robert Sedgewick, Phillipe Flajolet (utilisée dans 2 versions au total)
The Design and Analysis of Algorithms, Kozen (utilisée dans 1 versions au total)
Algorithms and complexity, Wilf (utilisée dans 2 versions au total)
Invitation to Fixed Parameter Algorithms, Niedermeier (utilisée dans 1 versions au total)