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

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

    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

  • Leçon choisie :

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

  • Autre leçon :

    903 : Exemples d’algorithmes de tri. Correction et complexité.

  • Développement choisi : (par le jury)

    Théorème de Rice

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

    Question sur le développement :
    - J'avais commencé par montrer l'indécidabilité du problème de l'acceptation en l'appelant problème de l'arrêt. Un jury m'a demandé si c'était vraiment ça le problème de l'arrêt, j'ai répondu que non, et il m'a demandé le lien entre problème de l'arrêt et problème de l'acceptation (ils sont équivalents). Ils m'ont demandé de prouver que tout langage reconnaissable se réduit au problème de l'acceptation et m'ont fait remarqué que le résultat que je prouvais montre en fait la complétude du problème de l'acceptation pour la reconnaissabilité.

    Question sur le plan :
    - J'avais mis une remarque sur l'impossibilité pour un compilateur de déterminer si un while termine en règle générale, ils m'ont demandé le rapport exact avec les problèmes décrits.
    - Le théorème de Rice est-il un résultat sur les machines de turing ou sur les langages ? Exemple d'applications ? (Langage du vide)

    Autres :
    - Langages de polynomes : le langage des polynomes à une variable à coefficients entiers admettant une racine entière est-il reconnaissable (oui), décidable (oui, j'ai mit longtemps à montrer qu'on peut borner l'espace sur lequel chercher les racines en fonction des coefficients). Que ce passe-t-il si on prend deux variables ? (C'est toujours reconnaissable, mais plus décidable).
    - Langages récursivement énumérable et reconnaissable est-ce la même chose ? Pourquoi ? Y-a-t il des langages non reconnaissables ? (oui, le complémentaire du langage de l'acceptation) ? Des langages non reconnaissable et non co-reconnaissables ? (Oui, par dénombrabilité, mais un exhiber un est compliqué) ? Un langage récursivement énumérable par ordre lexicographique est-il décidable, et réciproquement (oui, dans les deux sens).
    - existence de fonction non-calculable : est-ce qu'on a besoin d'exhiber le castor affairé ? (Non, par un argument de dénombrabilité) Exemple de fonction totale calculable non récursive primitive ? (Ackerman) Y-a-t il des fonctions récursives dont le graphe n'est pas décidable ? (Les fonctions partielles) Si on considère la réciproque du castor affairé, qu'est-ce qu'on calcule ? (Je n'ai pas su répondre, en fait c'est la compression optimale, i.e. la complexité de Komogorov, dont on prouve ainsi qu'elle n'est pas calculable).

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

    Jury souriant, mais fatigué. Ils m'ont aidé quand c'était nécessaire, mais ils ont surtout cherché à m'empêcher de partir dans des impasses. Par contre quand je rebondissais sur les questions pour chercher à aller plus loin ils me laissaient chercher un peu.

  • 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 de réponse fournie.

  • Note obtenue :

    Pas de réponse fournie.

  • Leçon choisie :

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

  • Autre leçon :

    927 : Exemples de preuve d’algorithme : correction, terminaisons.

  • Développement choisi : (par le jury)

    Théorie des ordres denses

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

    Il y a eu un long moment de questions sur le développement, où je comprenais pas vraiment où iels voulaient en venir... En fait iels me demandaient juste de dire un truc évident mais je suppose que ça me paraissait tellement clair que j'ai mis 10 minutes à le dire...

    J'ai eu pas mal de questions du type : "est-ce qu vous connaissez une autre théorie qui admet l'élimination des quantificateurs/je me souviens plus trop les autres", et à chaque fois j'ai dû répondre non parce que j'en savais clairement rien...

    Qu'est-ce qu'il se passe si on met "modèles finis" à la place de "modèles" dans le titre de la leçon ? Qu'est ce que cela change ?

    Une question sur la décidabilité : qu'est ce que ça veut dire in/décidable, et comment on peut le prouver ?

    J'ai aussi eu une question sur mon autre développement, en gros d'expliquer en deux mots comment on fait la preuve.

    Retour au développement, si on change les égalités et inégalités en rajoutant des trucs de la forme $x=y+c$ et $x

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

    Le jury était vraiment adorable, moi j'étais un peu en panique et vraiment extrêmement fatigué, du coup j'avais vraiment du mal à réfléchir, mais iels cherchaient tellement pas à me piéger qu'iels m'ont répété plusieurs fois que c'était pas du tout une question piège, c'était juste "pour s'assurer de notre compréhension commune de ce que je disais".

    Iels étaient assez vite à court de questions, je suppose que c'est parce que j'étais pas hyper à l'aise sur cette leçon donc iels osaient pas trop poser des questions trop difficiles (et je les en remercie !) mais du coup fallait se creuser la tête pour savoir de quoi on pouvait parler...

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

    Comme le premier jour, la préparation se passe comme sur des roulettes, le surveillant s'est même assuré qu'on avait toustes de l'eau et que ça allait ! Tout le monde te lâche des gros sourires dans les couloirs, ce qui est vraiment agréable quand tu sais que tu es en train de paniquer sur un de tes trois oraux.

    Sinon, le jury creuse creuse creuse vraiment jusqu'au fond des choses, ce qui, même en s'étant préparé au cours de l'année, est beaucoup plus intense qu'en oral blanc par exemple.

  • Note obtenue :

    15