Retours d'oraux : Informatique

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

  • 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

  • Leçon choisie :

    927 : Exemples de preuve d'algorithme : correction, terminaison.

  • Autre leçon :

    924 : Théories et modèles en logique du premier ordre. Exemples.

  • Développement choisi : (par le jury)

    Preuve de la factorielle en logique de Hoare

  • Autre(s) développement(s) proposé(s) :
  • Liste des références utilisées pour le plan :
  • Résumé de l'échange avec le jury (questions/réponses/remarques) :

    Quelques questions sur le développement :
    - Une règle de conséquence que j'avais oublié d'appliquer, vite rectifié
    - La logique de Hoare est-elle adaptée pour l'automatisation (j'avais un peu parlé de ça en conclusion du développement). Je dis que le problème est surtout de deviner certaines assertions, pour ça on a les weakest prediconditions (wp).
    - Des exemples de wp ? Je parle de l'assignation, on m'a suggéré de regarder la séquence, et c'est aussi facile.
    - Est-ce que la logique de Hoare prouve la correction ? Non, seulement la correction partielle.

    Sur le plan :
    - Vous parlez d'ensemble bien fondé mais uniquement dans le cas des fonctions récursives... Non en fait pour les algos itératifs c'est pareil, juste un peu de maladresse dans mon plan. Exemple d'ensemble bien fondé ? (j'avais mis $\mathbb{N}^2$ muni de l'ordre lexicographique dans mon plan...) Un exemple de terminaison de programme itératif qui l'utilise ? Je dis qu'on peut réécrire un programme récursif que j'avais donné (Binôme de Newton) en mode itératif, j'ai un peu galéré alors que c'était assez con...
    - La terminaison de programme est un problème difficile (je donnais l'exemple de la conjecture de Syracuse). Est-ce que vous connaissez des problèmes dont la correction est arbitrairement difficile ? J'avoue que le "arbitrairement" m'a pas mal dérouté, j'avais aucune idée d'où il voulait m'emmener, du coup on est passé à autre chose.
    - Vous connaissez Dijkstra ? (sérieusement ?) Preuve de la correction ? J'explique qu'à l'étape $i$ on a la longueur du plus court chemin passant par au plus $i$ sommets, ça n'avait pas l'air d'avoir convaincu... Ils voulaient un invariant, c'est assez délicat et eux même n'étaient pas d'accord... On y réfléchit un peu ensemble.

    Exercices :
    - On définit une fonction $f$ de la façon suivante :
    $$f(x) =
    \begin{cases}
    x - 10 & \text{ si } x > 42 \\
    f(f(x+11)) & \text{ sinon}
    \end{cases}
    $$
    Montrer que $f$ termine. On me demande rapidement de calculer $f(42)$, $f(41)$, j'ai montré que si $x \leq 42$, $f(x) = 33$ en raisonnant par "tranches". A la fin, un des membres du jury m'a aussi suggéré une récurrence forte, qui aurait été plus simple c'est vraie...

    - On prend une matrice $n \times n$ triée par ligne et par colonne. Algorithme de recherche d'un élément $x$ en temps linéaire ? Comment le prouver ? Là j'ai expliqué quelle info on pouvait avoir en comparant $x$ à un élément de la matrice, mais il ne me restait plus beaucoup de temps.

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

    Jury très sympathique, bienveillant et sollicitant. Il y avait Laurent Cheno (Inspecteur Général), Judicaël Courant, et une femme (celle qui m'a acceuillie) dont j'ai oublié le nom.

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

    Je pense qu'ils ont apprécié que je parle de logique de Hoare (c'est assez suggéré dans le rapport) et surtout que je sois capable de discuter dessus après (j'avais pas mal potassé aussi pendant la préparation).

  • Note obtenue :

    20