Leçon 4 : Exemples de structures de données. Applications.

(2021) 901

Dernier rapport du Jury :

(2019 : 901 - Structures de données. Exemples et applications.) Le mot algorithme ne figure pas dans l’intitulé de cette leçon, même si l’utilisation des structures de données est évidemment fortement liée à des questions algorithmiques. La leçon doit donc être orientée plutôt sur la question du choix d’une structure de données. Le jury attend du candidat qu’il présente différents types abstraits de structures de données en donnant quelques exemples de leur usage avant de s’intéresser au choix de la structure concrète. Le candidat ne peut se limiter à des structures linéaires simples comme des tableaux ou des listes, mais doit présenter également quelques structures plus complexes, reposant par exemple sur des implantations à l’aide d’arbres. Les notions de complexité des opérations usuelles sur la structure de données sont bien sûr essentielles dans cette leçon.

(2017 : 901 - Structures de données. Exemples et applications.) Le mot algorithme ne figure pas dans l’intitulé de cette leçon, même si l’utilisation des structures de données est évidemment fortement liée à des questions algorithmiques. La leçon doit donc être orientée plutôt sur la question du choix d’une structure de données. Le jury attend du candidat qu’il présente différents types abstraits de structures de données en donnant quelques exemples de leur usage avant de s’intéresser au choix de la structure concrète. Les notions de complexité des opérations usuelles sur la structure de données sont bien sûr essentielles dans cette leçon. Le candidat ne peut se limiter à des structures linéaires simples comme des tableaux ou des listes, mais doit présenter également quelques structures plus complexes, reposant par exemple sur des implantations à l’aide d’arbres.
(2015 : 901 - Structure de données : exemples et applications.) Le mot algorithme ne figure pas dans l'intitulé de cette leçon, même si l'utilisation des structures de données est évidemment fortement liée à des questions algorithmiques. La leçon doit donc être orientée plutôt sur la question du choix d'une structure de données que d'un algorithme. Le jury attend du candidat qu'il présente différents types abstraits de structures de données en donnant quelques exemples de leur usage avant de s'intéresser au choix de la structure concrète. Le candidat ne peut se limiter à des structures linéaires simples comme des tableaux ou des listes, mais doit présenter également quelques structures plus complexes, reposant par exemple sur des implantations à l'aide d'arbres.
(2014 : 901 - Structure de données : exemples et applications.) Le jury attend du candidat qu'il traite des exemples d'algorithmes récursifs et des exemples d'algorithmes itératifs. En particulier, le candidat doit présenter des exemples mettant en évidence l'intérêt de la notion d'invariant pour la correction partielle et celle de variant pour la terminaison des segments itératifs. Une formalisation comme la logique de Hoare pourra utilement être introduite dans cette leçon, à condition toutefois que le candidat en maîtrise le langage.

Développements :

Plans/remarques :

2018 : Leçon 901 - Structures de données. Exemples et applications.


2016 : Leçon 901 - Structure de données : exemples et applications.


2015 : Leçon 901 - Structure de données : 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 :

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)
Eléments d'algorithmique, Beauquier, Berstel et Chrétienne (utilisée dans 11 versions au total)