Leçon 921 : Algorithmes de recherche et structures de données associées.

(2018) 921

Dernier rapport du Jury :

(2017 : 921 - Algorithmes de recherche et structures de données associées.) Le sujet de la leçon concerne les algorithmes de recherche : les structures de données proposées doivent répondre à une problématique liée aux algorithmes, et la leçon ne peut donc être structurée sur la base d’un catalogue de structures de données. La recherche d’une clé dans un dictionnaire sera ainsi par exemple l’occasion de définir la structure de données abstraite « dictionnaire », et d’en proposer plusieurs implantations concrètes. De la même façon, on peut évoquer la recherche d’un mot dans un lexique : les arbres préfixes (ou digital tries) peuvent alors être présentés. Mais on peut aussi s’intéresser à des domaines plus variés, comme la recherche d’un point dans un nuage (et les quad-trees), et bien d’autres encore.

Retours d'oraux :

2015 : Leçon 921 - Algorithmes de recherche et structures de données associées.

  • Leçon choisie :

    921 : Algorithmes de recherche et structures de données associées.

  • Autre leçon :

    913 : Machines de Turing. Applications.

  • Développement choisi : (par le jury)

    Arbres Splay

  • 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) :

    Pas trop d'exercices en info, donc surtout des questions sur des détails du plan ou des notions générales.
    Le niveau était complètement naze, la plupart des questions étaient un niveau basique L3, et pourtant ça avait l'air compliqué pour le jury... Un des 3 membres était un vieux grincheux qui comprenait pas grand chose et qui était du coup pas très sympathique...
    Apparemment, ils ont pas digéré le fait que je parle pas des arbre rouges noirs et que je mette les arbres splay à la place, parce que pour eux c'est beaucoup plus compliqué les arbres splays que les ARN, donc les questions visaient à me faire dire que c'était de la merde mon développement...

    Des détails sur mon développement :
    - sur les différents cas que vous avez dessiné (zig, zig-zag, zig-zig), ça recouvre pas tout, c'est beaucoup plus compliqué, non ? Les autres cas sont symétriques, tocard.
    - comment ça se code splay(x,S) ? Du coup je montre comment ça s'écrit de manière récursive, que c'est pas trop compliqué à faire mais apparemment le but de la question était de montrer que "c'est quand même trop compliqué à coder !" =\textgreater WTF ?!!
    - c'est quoi les crédits dans la preuve ? J'essaye de lui expliquer ce que c'est l'analyse amortie, mais apparemment il a pas l'air de connaitre. J'en vient même à lui citer l'exemple du tableau dynamique pour essayer de lui faire comprendre, et à ce moment là un des autres membres du jury lui dit à l'oreille un truc du style : "Oui oui, ça je connais, c'est vrai ce qu'il dit" -\textgreater WTF ?!!!! Y'a une leçon entière qui s'appelle analyse de complexité, le jury est sensé s'y connaitre, merde !!!
    - Non mais je comprends pas, c'est quoi un crédit ? Bah on peut voir ça comme des opérations élémentaires qu'on a payé en avance pour analyser la complexité de manière plus fine...
    - (Un autre membre) Et c'est équilibré ces arbres ? Bah en pire cas non, mais si on les utilise sur un ensemble de données, ça tends à donner le meilleur arbre (style Huffman) pour ce set de données, et puis en moyenne ça se rééquilibre tout seul.
    - Qu'est ce qui se passe si on insère 1,2,3, ... ? Oui ca créé un peigne donc c'est pas équilibré, mais il suffit d'appeler une fois find(1,S) pour que l'arbre se rééquilibre tout bien.
    - Mais vous connaissez pas des arbres qui sont équilibrés tout le temps ? Bah les arbres rouges noirs, mais c'est relou à utiliser. Je donne quand même les différentes contraintes que doit vérifier un arbre rouge noir, et j'explique que c'est ça qui est casse-pied à maintenir.

    Questions sur le plan :
    - (Retour au grincheux) Vous dites que la profondeur moyenne est O(log n), qu'est ce que ça veut dire ? J'explique que c'est l'ordre qui est pris de manière aléatoire, et comment on insère les éléments.
    - Vous pouvez nous faire la preuve ? C'est un développement en entier c**nnard ! Je commence à faire la preuve, en montrant que les racines sont équiprobables, puis qu'à une racine fixée, les arbres gauches et droits sont uniquement déterminés par l'ordre des éléments plus petits (resp plus grands) que la racine, et donc on aboutit à une inégalité de récurrence, et j'ai pas le temps de la résoudre.
    - Vous dites qu'on peut supprimer dans une liste triée en O(1), comment on fait ça ? Bah on change les pointeurs de celui d'avant et de celui d'après.
    - Mais c'est quoi vos listes ?!! Bah des listes doublement chainées (je l'avais écris dans le plan...)
    - Et comment vous faites pour trouver le maximum d'une liste triée en O(1) ?!! Mais c'est une liste doublement chainée, boulet ! J'ai un accès sur le début et la fin de la liste !
    - Et puis, dans le cas d'une liste normale, comment vous faites pour supprimer en O(1) ?! Toujours pareil, c'est doublement chainée ! Là je commence à comprendre qu'il a un blocage sur les listes, et qu'il a pas l'air très à l'aise avec la notion de liste doublement chainée, donc je développe : bah j'ai mis les complexités que dans le cas des listes doublement chainées, parce que elles ont une meilleure complexité que les listes pour toutes les requêtes, donc les listes simplement chainées n'ont aucun intérêt algorithmique dans cette leçon.

    Question pédagogique :
    - Comment vous introduirez cette leçon à des lycéens ? Je leur parlerai de Google. Détaillez. Bah il faut indexer donc ça ressemble un peu à ma partie sur l'indexation. Puis je me corrige en disant que l'algo de Google est trop compliqué et que du coup je parlerai plutôt de la fonction recherche dans un document texte, qui utilise fortement l'indexation.

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

    Pas de réponse fournie.

  • 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.

    J'ai volontairement pas choisi Machines de Turing parce que j'avais peur de faire des trucs trop théoriques et trop compliqués, donc je me suis dis qu'en prenant de l'algo, ça devrait passer. Et beh non ! Jury avec un niveau de connaissance très très décevant, c'était vraiment triste...
    J'ai pas du tout eu de question sur la partie d'algorithmique du texte (1/3 de mon plan), et je soupçonne que c'est parce que le jury n'était pas non plus à l'aise sur ces notions...

    Du coup, au lieu de discuter sur toutes les pistes de notions un peu plus complexes que je proposais dans le plan, le jury a essayé de ramener les questions à un niveau prépa qu'il maitrisait mieux, enfin du moins en apparence...

    [Oui je suis un gros rageux, ils sont peut être pas si mauvais que ça en vrai...]
    EDIT: Vu la note reçu, c'était bien un gros rageux....

  • Note obtenue :

    5.25