Leçon 931 : Schémas algorithmiques. Exemples et applications.

(2018) 902
(2018) 906
(2020) 931

Dernier rapport du Jury :

(2019 : 931 - Schémas algorithmiques. Exemples et applications.) Cette leçon permet au candidat de présenter différents schémas algorithmiques, en particulier « diviser pour régner », programmation dynamique et approche gloutonne. Le candidat pourra choisir de se concentrer plus particulièrement sur un ou deux de ces paradigmes. Le jury attend du candidat qu’il illustre sa leçon par des exemples variés, touchant des domaines différents et qu’il puisse discuter les intérêts et limites respectifs des méthodes. Le jury ne manque pas d’interroger plus particulièrement le candidat sur la question de la correction des algorithmes proposés et sur la question de leur complexité, en temps comme en espace.

(2017 : 902 - Diviser pour régner. Exemples et applications.) Cette leçon permet au candidat de proposer différents algorithmes utilisant le paradigme diviser pour régner. Le jury attend du candidat que ces exemples soient variés et touchent des domaines différents. Un calcul de complexité ne peut se limiter au cas où la taille du problème est une puissance exacte de 2, ni à une application directe d’un théorème très général recopié approximativement d’un ouvrage de la bibliothèque de l’agrégation.
(2017 : 906 - Progammation dynamique. Exemples et applications.) Même s’il s’agit d’une leçon d’exemples et d’applications, le jury attend des candidats qu’ils présentent les idées générales de la programmation dynamique et en particulier qu’ils aient compris le caractère générique de la technique de mémoïsation. Le jury appréciera que les exemples choisis par le candidat couvrent des domaines variés, et ne se limitent pas au calcul de la longueur de la plus grande sous-séquence commune à deux chaînes de caractères. Le jury ne manquera pas d’interroger plus particulièrement le candidat sur la question de la correction des algorithmes proposés et sur la question de leur complexité en espace.
(2015 : 902 - Diviser pour régner : exemples et applications.) Cette leçon permet au candidat de proposer différents algorithmes utilisant le paradigme diviser pour régner . Le jury attend du candidat que ces exemples soient variés et touchent des domaines différents. Un calcul de complexité ne peut se limiter au cas où la taille du problème est une puissance exacte de 2, ni à une application directe d'un théorème très général recopié approximativement d'un ouvrage de la bibliothèque de l'agrégation.
(2015 : 906 - Programmation dynamique : exemples et applications.) Même s'il s'agit d'une leçon d'exemples et d'applications, le jury attend des candidats qu'ils présentent les idées générales de la programmation dynamique et en particulier qu'ils aient compris le caractère générique de la technique de mémoïsation. Le jury appréciera que les exemples choisis par le candidat couvrent des domaines variés, et ne se limitent pas au calcul de la longueur de la plus grande sous-séquence commune à deux chaînes de caractères. Le jury ne manquera pas d'interroger plus particulièrement le candidat sur la question de la correction des algorithmes proposés et sur la question de leur complexité en espace.

Développements :

Plans/remarques :

2018 : Leçon 902 - Diviser pour régner. Exemples et applications.


2016 : Leçon 902 - Diviser pour régner : exemples et applications.


2015 : Leçon 902 - Diviser pour régner : exemples et applications.


2018 : Leçon 906 - Programmation dynamique. Exemples et applications.


2016 : Leçon 906 - Programmation dynamique : exemples et applications.


2015 : Leçon 906 - Programmation dynamique : exemples et applications.


Retours d'oraux :

Pas de retours pour cette leçon.

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

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)
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)
Algorithms from P to NP , Moret (utilisée dans 1 versions au total)
An Introduction to the Analysis of Algorithms, Robert Sedgewick, Phillipe Flajolet (utilisée dans 2 versions au total)
Le Langage des machines, Floyd, Beigel (utilisée dans 7 versions au total)
Analyse numérique et équation différentielle , Demailly (utilisée dans 74 versions au total)
Algorithm Design , Kleinberg (utilisée dans 1 versions au total)
Optimisation combinatoire , Rasches (utilisée dans 1 versions au total)