Leçon 907 : Algorithme du texte.

(2016) 907
(2018) 907

Dernier rapport du Jury :

(2017 : 907 - Algorithme du texte.) Cette leçon devrait permettre au candidat de présenter une grande variété d’algorithmes et de paradigmes de programmation, et ne devrait pas se limiter au seul problème de la recherche d’un motif dans un texte, surtout si le candidat ne sait présenter que la méthode naïve. De même, des structures de données plus riches que les tableaux de caractères peuvent montrer leur utilité dans certains algorithmes, qu’il s’agisse d’automates ou d’arbres par exemple. Cependant, cette leçon ne doit pas être confondue avec la 909, «Langages rationnels et Automates finis. Exemples et applications.». La compression de texte peut faire partie de cette leçon si les algorithmes présentés contiennent effectivement des opérations comme les comparaisons de chaînes : la compression LZW, par exemple, est plus pertinente dans cette leçon que la compression de Huffman.

(2015 : 907 - Algorithmique du texte : exemples et applications.) Cette leçon devrait permettre au candidat de présenter une grande variété d'algorithmes et de paradigmes de programmation, et ne devrait pas se limiter au seul problème de la recherche d'un motif dans un texte, surtout si le candidat ne sait présenter que la méthode naïve. De même, des structures de données plus riches que les tableaux de caractères peuvent montrer leur utilité dans certains algorithmes, qu'il s'agisse d'automates ou d'arbres par exemple. Cependant, cette leçon ne doit pas être confondue avec la 909 : Langages rationnels. Exemples et applications ni avec la 910 : Langages algébriques. Exemples et applications . La compression de texte peut faire partie de cette leçon si les algorithmes présentés contiennent effectivement des opérations comme les comparaisons de chaînes : la compression LZW, par exemple, ressortit davantage à cette leçon que la compression de Huffman.

Développements :

Plans/remarques :

2016 : Leçon 907 - Algorithmique du texte : exemples et applications.


2015 : Leçon 907 - Algorithmique du texte : exemples et applications.


Retours d'oraux :

2015 : Leçon 907 - Algorithmique du texte : exemples et applications.

  • Leçon choisie :

    907 : Algorithmique du texte : exemples et applications.

  • Autre leçon :

    914 : Décidabilité et indécidabilité. Exemples.

  • Développement choisi : (par le jury)

    Pas de réponse fournie.

  • Autre(s) développement(s) proposé(s) :

    Pas de réponse fournie.

  • Liste des références utilisées pour le plan :

    Pas de réponse fournie.

  • Résumé de l'échange avec le jury (questions/réponses/remarques) :

    Uniquement des questions sur le plan et le développement, pas d'exercice.

    - Preuve de la complexité pour le calcul des bords ? Comment se sert-on des bords ? Sur un exemple ?

    - Des questions sur comment (et pourquoi) le développement fonctionne

    - D'autres codes que Huffman ? Comment on chiffre et déchiffre avec Huffman ?

    - KMP, quelle autre structure (automates) ?

  • Quelle a été l'attitude du jury (muet/aide/cassant) ?

    Jury sur l'offensive mais pas méchant non plus. Il m'a coincé sur deux ou trois choses. Membres : Claude Marché et Judicaël Courant. Malheureusement je n'ai pas retenu le nom de celui qui parlait le plus (90%)

  • L'oral s'est-il passé comme vous l'imaginiez ou avez-vous été surpris par certains points ? Cette question concerne aussi la préparation.

    Pas vraiment de surprises, juste une petite déception sur l'absence de questions sur les lemmes admis dans le développement (qui sont en fait d'autres développements).

  • Note obtenue :

    Pas de réponse fournie.


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)
Text algorithms , Crochemore (utilisée dans 2 versions au total)
Algorithms on string, Crochemore, Hancart et Lecroq (utilisée dans 5 versions au total)
Eléments d'algorithmique, Beauquier, Berstel et Chrétienne (utilisée dans 11 versions au total)
Flexible Pattern Matching in Strings, Gonzalo Navarro (utilisée dans 1 versions au total)