Retours d'oraux : Option C

Un truc sur le cardinal de groupes abéliens finis à ordre fixé

Un truc sur Lotka-Volterra

Pas de réponse fournie.

Pas de réponse fournie.

Pendant ma présentation j'ai foiré mon calcul de complexité, du coup 90% DES PUTERELLES DE QUESTION ONT ETE SUR DES CALCULS DE COMPLEXITE DE SCHEISS.
Quelques questions sur des trucs que j'ai dit un peu vite dans ma présentation (et qui étaient faux)

Donner la comlpexité du calcul de $\prod_{k=1}^{+\infty}\frac{1}{1-X^k}~~mod~X^{e+1}$ et trouver que ça fait $O(e^2)$ (c'est franchement super rigolo comme calcul, je vous conseille chaudement ça comme une activité à faire en famille le samedi soir pour égayer vos veillées funèbres)

Pas de réponse fournie.

Le niveau était plutôt bas, j'ai l'impression que le jury a pris pitié quand il m'a vu m'empêtrer dans mes calculs de complexité du coup il m'aidait bien.
Un des membres du jury avait une longue vue pour voir ce que j'écrivais au tableau :D #cool #incongru #pirate
Pour une fois, un membre du jury hochait de la tête quand je disais des trucs. Ça doit être l'attitude de jury la plus humaine que j'aie vue pendants mes oraux.

Tout s'est passé aussi moyennement que prévu.
P'tite cace-dédi à Michel qu'a eu la présence d'esprit de reposer le manuel de Sage dans la malle avant de passer en oral de manière à ce que je puisse commencer avec.

14.25

Cryptage à clef publique dans GLn(Fq)

Des séries formelles, me rappelle plus trop..

Pas de réponse fournie.

Pas de réponse fournie.

Questions principalement sur l'exposé, mais mon intro était assez solide et recouvrait déjà les thématiques adjacentes au texte (logarithme dans les corps finis, stratégie des cryptages à clef publique..)

un peu stressé et fatigué pendant ma présentation (commencer à 6h30 c'est dur..), j'ai fait une démo fausse dans mon exposé, du coup j'ai du la refaire (heureusement, elle était correcte dans mes notes, juste fausse telle qu'écrite au tableau).
On m'a demandé de réfléchir aux points que j'avais admis dans ma présentation, notamment le calcul d'un polynome minimal, et une partie de l'algo que j'avais pas implémentée.
Pas vraiment d'exercices, mais on a un peu discuté de réduction de Jordan dans les corps finis, notamment pour des questions d'ordres de blocs de Jordan.

Pas de réponse fournie.

les questions étaient relativement faciles, j'y répondais généralement entre quelques phrases. Le jury était le même que celui de dosso, mention spécial au vieillard joufflu dont le nez rouge et les jumelles rétractables m'ont fait craindre l'arrêt cardiaque à chaque fois qu'il esquissait un geste.

oral assez sympathique, même si le tableau est assez dur à gérer vu qu'on ne choisit pas trop comment / quand utiliser l'ordinateur.

Tkt dosso jte lache pas buddy

17.5

Multiplication rapide de polynômes en caractéristique 2.

Équivalence de nuages de points.

Pas de réponse fournie.

Pas de réponse fournie.

Pas mal de questions sur l'exposé et mon informatique, quelques questions sur la partie du texte que je n'ai pas eu le temps d'aborder.

Réexpliquer un bout de mon informatique sur lequel j'étais allé un peu vite.

Corriger une remarque où j'avais indiqué une équivalence alors que seule une implication était vraie.

Justifier des calculs de complexité et quelques calculs que je n'avais pas eu le temps de détailler.

Essayer de justifier un théorème que j'avais laissé de côté (je n'ai pas réussi faire quoi que ce soit là-dessus).

Comment construit-on une clôture algébrique de $\mathbb{F}_2$ (évoquée dans mon exposé pour justifier le fait qu'il n'y a qu'une racine $2^k$-ème de l'unité dans un corps de caractéristique $2$) ?

Pas de réponse fournie.

Questions plutôt faciles à mon avis. Jury plus agréable et (car ?) plus jeune que ceux d'algèbre et d'analyse.

Pas de réponse fournie.

17.25

C47 : Usinage de de courbes

C37 : un truc de cryptographie (cf Nicolas ?)

On a une courbe

$$ \alpha(t) = (x(t), y(t))$$

définie sur un segment. On a une fraiseuse avec laquelle on aimerait tracer la courbe. La fraiseuse est circulaire de rayon $r$ et passe par une courbe décalée à $\alpha$ :

$$ \beta = \alpha + r \vec{n} $$

où $n= (-y', x')/ ||\alpha'||$ est la normale. Pour avoir des trucs faciles à calculer on suppose que $||\alpha'||$ est polynomiale ainsi que $x'$ et $y'$. On en déduit une condition sur $x,y$.

De là il y a des problèmes d'intersection qui apparaissent : si $r$ est trop grand (la fraise est trop grosse) on va manger trop de matière. Il faut donc regarder les points d'auto-intersection de la courbe décalée. De même si on définie une courbe par morceaux il y a des risques d'intersection entre deux courbes décalées. D'où on cherche les points d'intersection de deux courbes pour éviter les détériorations.

Pour tout ça on utilise en gros la multiplicité d'un point d'une courbe et le résultant avec lequel on arrive à détecter ces points.

Pas de réponse fournie.

Pas vraiment des questions de mathématiques fondamentales. Surtout des questions pour voir si j'arrive à mettre en contexte les mathématiques. Les détails des preuves étaient facultatives. Les questions étaient plutôt 'évasives' (?)

Questions :

Q : éclairer un point du début

Q : Est ce qu'il y a des courbes qui poseront forcément un problème ?
R : Oui, genre un point de rebroussement.

Q : Pour toute courbe le $r$ est minoré nan ?
R : Par le rayon de courbure

Q : Et la complexité de tout ça ?
R : Pgcd c'est polynomial, division tout ça, ... multiplication de poly en $n\ln(n)$ avec Transformée de Fourier Rapide. Résultant c'est du déterminant ou par méthode du pgcd donc polynomial.

Q : Les courbes de Béziers vous connaissez ?
R : C'est des courbes polynomiales qui interpolent le passage en des points de manière lisse $C^1$.

Q : Yep et c'est quoi le degré de ces polynômes ?
R : Bah il y a quatre conditions donc de degré $4$.

Q : Est ce que vous vu la suite ?
R : nan ça partait trop en lattes + quelque chose de politiquement correct

Q : Si le déterminant d'une matrice est très petit. Genre 0 normalement mais à cause des arrondis ça marche pas. Est ce que vous savez calculer un élément du noyau ? [j'avais soulevé ce problème dans ma présentation]
R : pas trop

Q : [un truc chelou du genre : qu'est ce qu'on obtient avec la fraiseuse ? ils me demandaient des propriétés mathématiques]

Pas de réponse fournie.

Pas de réponse fournie.

L'ordinateur et Sage ont été pas mal coopératifs. Je les remercie. Par contre la touche espace ...

19.5

cryptosystème à clef secrète

Un truc avec du résultant

on fait un cryptosysteme a clef secrète affine (en gros on code en faisant $M*(m +k)$ avec $m,k$ des scalaires étant le message et la clefs secrète et $M$ une matrice de permutation.) On regarde une attaque possible et du coup on code en faisant plusieir fois le codage précédent avec des $k$ différents, puis on choisit bien $M$.

J'ai fait un truc un peu original en partant d'une phrase de l'intro et ça a fait un flop total (en gros j'ai essayer de partitionner mon message et de le coder morceau par morceaux mais finalement c'est un peu plus rapide mais niveau sécurité ça change que dalle). Sinon j'ai suivi le texte, j'ai pas fait assez de maths à leur goût je pense.

Je me suis un peu fait démonté même si ils essayaient d'être gentils. Il faut savoir que comparer la complexité à RSA demande de bien comparer des valeurs comparables (ici prendre n (taille du message en nombre de bit) = N). Aussi, on doit savoir combien d'opération un ordi fait par seconde (en ordre de grandeur)

Bien faire des maths ET de l'info. Pas partir sur des trucs totalement originaux

En fait, ils ont rigolé entre eux pendant la présentation et ça m'a pas mal perturbé. Je ne sais pas si ils rigolaient entre eux ou si c'était àcause de ce que je disait et écrivait (peut être que j'ai fait trop de fautes d'orthographes au tableau)

Je pensais vraiment que ça serait plus facile que ça. Certaines parties du texte étaient dur à comprendre

20

De la cryptographie avec de l'algèbre linéaire sur des corps finis

Un truc de combinatoire

A et B veulent créer un secret, pour cela ils choisissent un groupe G et un élément $\mu$ de ce groupe. Ensuite A choisit un entier a, B choisit un entier b, A calcule $S_A=\mu^a$ et B calcule $S_B=\mu^b$, puis ils échangent leurs résultat, A calcule donc ensuite $S_B^a$ et B calcule $S_A^b$, ils connaissent donc le même secret $\mu^{ab}$.
Ensuite le texte s'intéresse à comment un méchant hackeur peut découvrir le secret. Dans tout le texte G était $GL_n(\mathbb{F}_q)$. Il y avait trois grandes parties à part l'introduction, deux d'entre elle concernaient des méthodes d'attaques du secret, et la troisième je ne l'ai pas du tout traité car il y avait déjà de quoi faire, mais il y avait des matrices circulantes dedans et ça ne me tentait pas trop.

J'ai redémontré quasiment toutes les affirmations du texte dans les deux première parties, et présenté des bouts de codes qui marchaient moyennement pour illustrer les méthodes d'attaques décrites dans le texte. (environ une page et demi de code sur Sage)

Ils m'ont posé beaucoup de questions sur mon exposé, j'ai fait pas mal de démonstration donc je suis allé un peu vite et ils m'ont demandé de reprendre plusieurs arguments, du coup ça paraissait facile vu que c'était des trucs que j'avais dit (ou pensé) pendant l'exposé. Les questions plus générales ne m'ont paru facile qu'après coup, j'ai hésité sur des questions un peu bêtes à cause de la fatigue. Le niveau des questions m'a paru inégal, entre facile et moyen, j'avais l'impression de bien répondre puisque plusieurs membres du jury avaient une attitude très encourageante, par exemple des hochements de tête approbateurs ou des sourires quand je répondais vite. En revanche vers la fin ils m'ont posé des questions de complexité, et ils m'ont demandé comment j'aurais fait pour aborder le problème de façon naïve avec telle ou telle donnée, et là j'ai eu du mal

J'ai eu l'impression de mal parler de ce que j'avais fait comme code, en gros je disais à la fin d'une partie "bon bah voilà ce que j'ai fait" sans mettre vraiment en lien avec le texte. Pour le temps de préparation j'ai trouvé que 4h c'était assez large pour faire un truc bien et je met la plupart de mes erreurs sur le compte de la fatigue.

Pas de réponse fournie.

L'oral en lui même s'est passé à peu près comme je l'imaginais, le jury était plutôt gentil, sauf quand j'ai hésité sur des questions bêtes ils ont semblé s'impatienter un peu mais je les comprends!

Pas de réponse fournie.

Fonctions de hachage

Courbe de fraiseuses (résultants, élimination)

Le texte étudiait des fonctions de hachage définies par deux éléments d'un groupe fini. L'objectif était d'étudier les relations entre ces deux éléments, que l'on voulait les moins courtes possibles, et de vérifier qu'ils engendraient le groupe. Il y avait deux exemples traités dans le texte

Plusieurs procédures sur les permutations, un plan préparé, et deux preuves claires de points du texte

jury très agréable et intéressé, les questions étaient intéressantes, et plutôt abordables, donc l'échange était plutôt fluide

Pas de réponse fournie.

Pas de réponse fournie.

Pas de réponse fournie.

Pas de réponse fournie.

Groupes abéliens finis

Un truc de crypto pas beau

Soit $G$ un groupe abélien fini de cardinal $n$. On s'en sert pour encoder des données sécurisées du style carte bancaire ou informatiques. On veut garder secrète la structure du groupe : par exemple, si $n = 4$, on ne sait pas si $G = \mathbb{Z}/ 2\mathbb{Z} \times \mathbb{Z}/ 2\mathbb{Z}$ ou si $G = \mathbb{Z}/ 4\mathbb{Z}$. Dans un premier temps, le texte propose de déterminer le nombre de groupes abéliens d'ordre $n$ pour tout $n\in \mathbb{N}$. On fait le lien avec le nombre de partitions de $n$ ({\it i.e} le nombre de manières d'écrire $n = n_1 + \ldots + n_r$ avec $n_1 \geqslant n_2 \geqslant \ldots \geqslant n_r$) et on détermine deux algorithmes pour calculer ce nombre (l'un à base de séries formelles, l'autre par récurrence).

Dans une deuxième partie, on s'intéresse à la manière de déterminer la structure d'un groupe abélien fini dont on connaît l'ordre en supposant que l'on peut tirer au hasard des éléments et que l'on peut déterminer l'addition de deux éléments, ainsi que si cette addition vaut l'élément neutre. On trouve donc un algorithme qui détermine la structure du groupe à partir de ce que l'on nomme \og un système canonique de générateurs \fg{}.

Il y avait une troisième partie qui modélisait la retenue dans les additions (genre quand on compte avec nos doigts) mais je n'y au pas touché je sais pas de quoi ça parlait.

'ai fait un plan en trois parties qui suivaient de manière assez linéaire le plan tout en détaillant les aspects mathématiques cachés derrière le truc (théorème de classification des groupes abéliens finis, donc prolongement des caractères, produit de Cauchy de séries formelles, etc.). J'ai proposé plusieurs algorithmes qui à la fin aboutissaient à la détermination du nombre de groupes abéliens d'ordre $n$ fixé. J'ai aussi déterminé, pour une borne $N$ fixée, quel était le cardinal $n$ maximisant ce nombre (c'est forcément une puissance de $2$) et j'ai aussi comparé la complexité algorithmique de quelques uns de mes algorithmes avec ceux déjà présents dans la bibliothèque de Sage. J'ai aussi montré quels étaient les $n$ pour lesquels on dispose d'un unique groupe abélien d'ordre $n$ (ceux qui sont sans facteur carré).

Q : vous pouvez détailler un peu plus le théorème de structure des groupes abéliens finis que vous avez annoncés ?
R : oui bien sûr (j'ai fait exprès d'être allusif sur ce point pour qu'on vienne me pêcher sur cette question et ça a marché). Alors là on prolonge le caractère comme ça, on a $G = \left(x\right) \times G/\left(x\right)$ par tel isomorphisme etc. (voir dans les développements).

Q : d'accord très bien mais quel rapport avec celui annoncé dans le document ? (c'était que avec des nombres premiers)
R : beh en fait c'est le lemme chinois parce que\ldots (là il m'interrompt parce qu'il a vu que je savais)

Q : pourquoi pour $p$ premier il y a exactement $q(e)$ groupes abéliens distincts d'ordre $p^e$ si $q$ est la fonction " nombre de partitions "
R : c'est car en écrivant toujours avec le théorème chinois qui est une caractérisation (donc un {\it ssi}) que...

Q : ok on peut revenir sur les séries formelles que vous avez peu traitées ? (j'ai tenté un code mais ça marchait pas là dessus donc j'ai fait d'autres trucs plutôt bien pour me rattraper)
R : alors (je baragouine en écrivant en cherchant une preuve que j'obtiens au bout de quelques minutes de griffonnage) et voilà.

Q : (la question qui tue) ok et la complexité ?
R : naaaan pas ça stp :(:( Bon alors j'essaie... La multiplication c'est en $n log\left(n\right)$

Q : quoi?????
R : beh avec la transformée de Fourier rapide

Q : Lol fais le en naïf petit
R : ok... beh je crois que c'est du tant...

[quelques galères plus tard un autre membre du jury intervient]

Q : bon on va faire autre chose genre des maths tu peux me démontrer ça ?
R : ouai ok j'fais ça plutpot j'préfère !

La gestion du temps : j'ai dû faire ma troisième partie en 5 minutes

Le jury était super sympa, ils étaient quatre (deux femmes et deux hommes) et seuls deux ont vraiment interagit durant l'oral. Ils avaient l'air intéressés et me testaient sur des trucs difficiles (thm de structure) puis quand ils ont vu qu'ils m'avaient pas eu sur les maths ils se sont dit que sur l'info ils y arriveraient peut-être et ils se sont pas trompés (mais ça va y a pire).

J'ai l'impression d'avoir agacé la membre du jury qui me posait des questions sur les séries formelles et la complexité de l'algorithme d'Euclide étendu sur les polynômes. Les autres ont bien aimé. J'suis juste passé pour un gland car j'ai oublié ma montre dans la salle alors je suis revenu dedans après.

Pas de réponse fournie.

18

C88 : Polynômes à plusieurs variables, géométrie, résultant.

C17 : Arithmétique des entiers.

Conception de courbes d'usinage pour la découpe à la fraiseuse d'un profil dans un matériau, étude des problèmes de conception : détection des points singuliers et des auto-intersections des courbes. On se restreint au cas où les courbes d'usinages sont unicursales et à hodographe pythogaricien. On utilise massivement la théorie de l'élimination et du résultant de deux polynômes.

Contenu mathématique : Caractérisation des triplets pythagoriciens de polynômes d'une variable à coefficients dans un corps, calcul explicite du noyau de la matrice de Sylvester de deux polynômes d'une variable à coefficients dans un corps.

Contenu informatique : Représentation de plusieurs courbes d'usinages présentant des points singuliers de différente nature, implémentation d'une procédure calculant la matrice de Sylvester de deux polynômes d'une variable à coefficients dans un corps et calcul de la dimension de son noyau.

1. Quelle est l'expression de la normale en un point d'une courbe paramétrée régulière ?
2. Donner et prouver une paramétrisation rationnelle du cercle ?
3. Quel est le lien avec le résultat que vous avez prouvé sur les triplets pythagoriciens de polynômes ?
4. Existe-t'il une paramétrisation polynômiale du cercle sur les réels ? Les complexes ? Un corps quelconque de caractéristique différente de 2 ?

Pas de réponse fournie.

Sur les quatre membres du jury, trois étaient majoritairement muets, mais ils restaient souriants et surtout attentifs à mes propos. Le quatrième juré me posait de nombreuses questions et était disposé à me guider lorsque je rencontrais des difficultés à lui répondre.

Aucune surprise.

15.75

Arithmétique et traitement du signal

Un truc sur les codes correcteurs

Pas de réponse fournie.

Pas de réponse fournie.

Pas de réponse fournie.

Pas de réponse fournie.

Pas de réponse fournie.

Pas de réponse fournie.

Pas de réponse fournie.

Algorithmes permettant de déterminer le nombre d'isomères de n-alcoos. Arithmétique des polynômes, équations différentielles.

Un sujet de crypto basique avec du résultant.

On présente dans un premier temps des notions de chimie organique liée à la représentation d'alcools. On s'intéresse ensuite à la détermination du nombre d'isomères pour les différentes valeurs de n avant de généraliser le problème à celui des arbres 1,2,3,4.

L'essentiel du travail informatique a été réalisé sous xcas. J'ai produit divers programme liés à des problématiques explicités dans le texte.

Echange très riche qui ressemblait plus à une discussion. Beaucoup de questions afin de préciser quelques erreurs dans mes démonstrations puis beaucoup de questions de complexité de mes algorithmes (une chance dans mon cas, il faut y être préparé). Dans un dernier temps, nous avons discutés de prolongements aux cas d'autres arbres particuliers tels que les arbres binaires par exemple.

La structure du plan probablement afin de mieux mettre en jeu les articulations entre les différentes parties. Egalement approfondir davantage la partie compliquée du document que j'ai simplement survolée et qui m'a probablement coûtée quelques points.

Jury très bienveillant, sympathique et attentif (bravo !) durant l'intégralité de ma présentation.

35 minutes c'est long, je n'avais rien préparé par rapport au temps, il faut donc être capable d'allonger ou raccourcir son discours pour s'adapter au cours de la présentation.

15

C87 - (Session 2019)

C42 ?

On cherche à obtenir l'évolution asymptotique d'une population animale en modélisant les naissances et morts sur différents âges avec un modèle linéaire. Le texte pointe qu'à partir de certaines hypothèses (assez forte) on peut avoir une convergence prévisible.

Plan et notes de l'oral que je comptais produire.
Un peu de code pour illustrer mon propos. Principalement des calculs et graphiques pour montrer qu'on a une asymptote exponentielle à l'infini et qu'en dehors des hypothèses formulées en début de texte on obtient des résultats peu contrôlés.

Le jury s'est montré très intéressé par les hypothèses du modèle et ce qu'elles impliquent sur les calculs, ce que provoque leur absence, etc. En partie parce que j'ai beaucoup appuyé sur le côté "hypothèses lourdes" pendant ma présentation. Il m'a également demandé la complexité pour calculer un certain vecteur (Le vecteur V* du texte, connaissance lambda et A). La complexité standard était O(n^3), car pivot de Gauss. Mais la matrice A étant très gentille, on peut en fait descendre en O(n).

Je m'en voulais un peu de m'être emmêlé les pinceaux dans certaines de mes démonstrations, par refus de recopier bêtement mes notes. Le jury est revenu sur la démonstration problématique pour me donner l'occasion de la refaire tranquillement.

Un jury très intéressé et vraiment souriant et sympathique.

Voir mon retour sur la leçon 152 pour un retour général.
Pour cet oral précis, je ne m'attendais à un jury aussi entraînant.

8.25

C30 : Algebre linéaire, corps finis, groupes de permutations

Algèbre linéaire et géométrie

On cherchait à sécuriser un échange entre deux individus Alice et Bob et pour cela on avait ne permutation connue de tous permettant de définir des fonctions de chiffrement et de déchiffrement, le texte évoluait et proposait au fur et à mesure des solutions réglant le problème que générait celle d'avant.
Par exemple, la première méthode était toute bête, donc il n'y avait aucune sécurité. La deuxième était un poil plus complexe et faisait intervenir les matrices compagnons. Mais encore une fois la sécurité n'était pas optimale. La troisième indroduisait la notion de polynôme de permutation, et la sécurité était bien meilleure, cependant ça nécessitait un calcul de résultant de taille très grand de l'ordre de 2^n.
Enfin la dernière partie du texte traitait une optimisation du cout et de la sécurité via les actions de groupes (je ne l'ai pas abordée)

Un plan en trois parties expliquant le concept général puis les améliorations apportées ainsi que leurs faiblesses.

Questions :
- Retour sur certains de mes programmes pour les détailler
- vérifier que les fonctions chiffrement et déchiffrement que vous énoncez sont bien réciproques
- Corriger votre erreur dans la preuve (j'avais juste écrit un ensemble privé de 0 alors qu'il fallait laisser 0 pour garder une structure d'espace vectoriel)
- Comment on effectue le calcul d'un déterminant (J'avais énoncé le coût du calcul du résultant énoncé) ? Algorithme de Gauss
- complexité de l'algorithme de Gauss et preuve ? De l'ordre de n^2 transvections qui coutent chacune n donc n^3
- On peut toujours procéder comme ça ? Non il faut des pivots non nuls
- Et donc par exemple pour une matrice compagnon ? On permute des lignes pour avoir un pivot non nul
- Quelle influence sur le déterminant ? ça ne change rien au signe (-1) près
- Comment procéder pour obtenir une relation de Bezout ? Euclide étendu
- Écrire le principe de l'algorithme d'Euclide étendu
- Dans le texte il était écrite que les X^t étaient des polynomes de permutation si t était premier avec 2^n - 1 (un polynome de permutation c'est un polynome qui pour tout x dans F2^n vérifiait P(x) = sigma(x) avec sigma une permutation) donc on m'a demandé de prouver ce point : Bézout puis injectif surjectif
- Combien y'a t'il de polynomes de permutation de cette forme dans F256 ? Il faut calculer phi(255) ou phi est l'indicatrice d'euler, on trouve 128
- De quel résultat provient le résultat utilisé pour votre calcul de phi(255) ? Theoreme chinois

J'ai carrément oublié après une partie de présenter un exemple que j'avais modélisé sur ordianteur. Donc pendant ma troisieme partie, je suis revenu sur un résultat de la deuxieme partie.. Bref à part ça je pense qu'une meillleure compréhension du texte m'aurait été très bénéfique mais j'ai donc préféré présenté une moitié de texte seulement mais relativement bien traitée..
Si je devais changer quelque chose, je pense que je structurerais plus mes idées avant le passage devant le jury.

Une femme et trois hommes.
La seule femme a dormi, ou du moins fermé les yeux pendant plus de 5 minutes, ce qui est relativement destabilisant surtout quand c'est elle qui gère le rétroprojecteur.
Malgré tout elle a posé des questions à la fin !
Un des 4 était totalement muet, et les 3 autres posaient des questions un peu tour à tour.

RAS

12.25

Arithmétique des entiers, arithmétique des polynômes

Algèbre linéaire, corps finis

Il s'agissait de faire une étude arithmétique des canons musicaux. On se donne une mélodie "modèle" (ie à chaque temps on joue soit une noire soit un soupir) sur un nombre fini de temps et on se donne ensuite un décalage (mettons : je lance la mélodie au temps 0 puis je la relance en canon au temps 2 et idem au temps 3).

On se demande ensuite si, ayant une mélodie, il existe un décalage qui permette de faire en sorte qu'à chaque temps, une et une seule note soit jouée.

Pour cela, au départ, on voit une mélodie et un décalage comme des tableaux de nombres représentant respectivement les temps sur lesquels on joue et les temps auxquels on lance la mélodie en canon.

Ensuite on remplace les tableaux par des polynômes.

J'ai globalement suivi les trois premières parties du texte. J'ai passé un certain temps à définir les notions un peu originales de canon et de décalage en les illustrant par de magnifiques graphiques.

J'ai codé les caractérisations proposées dans le texte, je les ai illustrées sur des exemples et j'ai calculé une complexité.

J'ai prouvé à peu près tout ce qui était prouvable. Il y a tout de même un théorème que je n'ai pas su démontrer : je l'ai dit à l'oral puisque c'était un théorème que l'on utilisait pas mal par la suite.

- J'ai dû expliciter deux ou trois points de l'exposé qui n'étaient pas très clairs (j'y reviens plus loin).

- On m'a fait calculer une autre complexité.

- Un des membres du jury a voulu revoir une partie de mon code parce qu'il n'avait pas suivi cette partie-là de mon exposé. J'ai réexpliqué ce qu'il faisait et quels résultats du texte/de l'exposé étaient sous-jacents.

- On m'a demandé s'il n'était pas possible de trouver une caractérisation "à la main" de l'une des propriétés présentées. J'ai avancé sur le sujet avec un peu d'aide mais je n'ai pas réussi à le mener jusqu'au bout : l'oral était terminé.

J'ai été extrêmement brouillon lors de mon exposé. Je n'ai pas songé à relire attentivement mon plan avant de passer et ça m'a clairement porté préjudice : je ne l'avais plus tout à fait en tête une fois face au jury. En dehors de ça, j'étais plutôt content de ce que j'ai produit.

Les membres du jury étaient soit neutres soit gentils. L'une des membres est restée complètement immobile du début à la fin, je ne suis même pas certain que ses yeux me suivaient lorsque je bougeais. Les autres se sont répartis les questions de manière assez uniforme. Ils m'ont plutôt mis à l'aise.

Je rajouterais qu'une fois l'oral terminé, après la question à laquelle je n'ai pas eu le temps de répondre, l'un des membres m'a dit de ne pas m'inquiéter pour cette question-là et qu'ils savaient que j'aurais pu la terminer. Je ne sais pas si ça signifiait quelque chose quant à la note finale, mais en tout cas c'était sympa de le dire.

Pas de surprise, tout est plutôt bien expliqué.

Une remarque de bon sens mais qui m'aurait servi : prenez des choses à manger, quitte à en prendre trop. Je n'en avais pas assez et je l'ai bien senti sur la fin de la préparation et pendant l'oral.

13.5

C86 Traitement des images vectorielles

Géolocalisation par GPS

Le texte (C86) traite de l'affichage d'images vectorielles (à opposer aux images matricielles, faites de tableaux de pixels), qui sont affichés grâce à des courbes (du plan affine R^2) paramétrées par des équations.
On nous fait d'abord montrer que la famille de polynômes B_k = (k parmi n) X^k (1-X)^(n-k) est une base de R_n[X], puis à l'aide de ces polynômes, on construit une courbe dans le plan à partir de n+1 points A_0,...,A_n du plan affine appelés "points de contrôle", courbe définie par
Gamma(t) = somme_k B_k(t) * A_k, 0 où la courbe est dans l'enveloppe convexe des points car somme_k B_k(t) = 1 (les points de la courbe sont des barycentres des A_k). La courbe peut alors être exprimée comme (x(t), y(t)) où x,y sont polynomiales en t. S'en suit un exemple avec une figure.
Le texte affirme sans le justifier qu'on peut ainsi à partir d'une courbe paramétrée (x(t), y(t)) polynomiale former une courbe ; et même à partir d'une paramétrisation pas forcément polynomiale.
Tout une partie du texte explique ensuite comment afficher une courbe (lisse) à partir d'une ligne brisée (c'est-à-dire une succession de segments), à l'aide de résultats calculatoires de barycentres. Partie que j'ai évité, pour m'intéresser à une dernière partie qui traite du calcul de l'intersection d'une courbe avec une droite. Pouvoir calculer ces intersections permet de délimiter les zones de l'images pour ensuite les colorer. Calculer ces intersections revient à trouver des racines de polynômes sur un segment, ce qui est fait grâce à une proposition qui donne un critère disant si un polynôme n'a aucune racine sur [0,1], et un autre critère concluant à la présence d'une unique racine sur [0,1]. Ces deux critères reposent sur le comptage de changements de signes sur une suite finie (ça ressemble donc aux suites de Sturm), qui est tout simplement la suite (p_k) des coordonnées du polynôme P dans la base (B_k). La démonstration de ces deux critères semble plutôt détaillée de premier abord, mais est en fait truffée d'implicites qui m'ont fait perdre un temps certain à la comprendre ("Soit a une racine de P" sans avoir montré son existence ; "par supposition on a " sans avoir précisé avant ce qui était supposé (??)). Il est ensuite expliqué comment faire si aucun des critères n'est véirfié (c'est-à-dire s'il y plusieurs racines : on regarde les racines de P(X/2) et P( X+1 / 2) etc..)

Lors de ma préparation, pour la partie mathématique j'ai principalement redémontré ou justifié des affirmations du texte; et pour la partie informatique j'ai codé des petites fonctions qui retournaient des objets définis dans le texte.

J'ai divisé ma présentation en 3 parties :
1 Les polynômes B_k
2 Les courbes paramétrées
3 L'intersection d'une courbe et d'une droite
En 1 j'ai montré que B_k formait bien une base, en montrant que B_k est dans l'espace engendré par Vect(X^i, i>=k) mais hors de Vect(X^i, i>k) (la suite de ces sous-espaces forme un drapeau de R_n[X]), ce qui se manifeste ensuite par le fait que la matrice des B_k dans la base canonique (X^k) (matrice de passage) est triangulaire inférieure. J'ai illustré ça par un petit code qui renvoie les B_k, ainsi que la matrice de passage, est j'ai utilisé linear_transformation pour obtenir l'application linéaire Phi associée.
En 2 j'ai justifié que la courbe Gamma était dans l'enveloppe convexe des points (mal), puis j'ai justifié que les courbes polynomiales pouvaient être affichées ainsi, en décomposant les polynôme x(t) = x_k B_k(t) , y(t) = y_k B_k(t) dansl a base B_k (de R_n[t] où n est le degré max de x et y), ce qui fournit les n+1 points de contrôle (x_k,y_k) et on vérifie que ça coïncide. Pour les courbes polynomiales mais continues, j'ai dit qu'on peut les approcher par des courbes polynomiales grâce au théorème de Weierstrass, et en pratique par les polynômes de Bernstein qui sont définis grâce aux B_k. J'ai ensuite coder la fonction Gamma, et montré que ça marche avec l'exemple donné.
En 3 j'ai essayé de redémontrer la proposition, mais je n'ai pas eu le temps de la présenter lors de l'oral. J'ai codé une fonction renvoyant la suite (p_k) grâce à l'appliation linéaire Phi définie plus haut (en fait son inverse par la procédure Phi.inverse() ).

Le jury était composé de 4 personnes qui avaient plus l'air de vouloir faire la sieste que de m'écouter. L'un d'entre eux est venu me chercher sur de la géométrie affine, car en fait je ne connaissais pas bien la définition de barycentre. Seul un des membres m'a posé plein de questions et avait l'air intéressé.Il m'a posé quelques questions sur le code, pour voir si j'avais bien compris ce que je manipulais (notamment sur la matrice de passage renvoyée). Il m'a posé des questions de complexité, en prenant des exemples dans mon code ou dans le texte, comme :
quelle complexité pour inverser une matrice triangulaire inférieure ? (O(n^2))
quelle complexité pour la méthode de Hörner ? (il me donne la réponse O(degré du polynôme))
quelle complexité pour l'expo rapide ? (O(log n))
Ensuite quelques questions sur les lignes brisées, puis enfin la question : peut-on paramétriser le cercle par des polynômes ? à laquelle je n'ai pas eu le temps de répondre (mais je crois que la réponse est négative car une paramétrisation est (cos t, sin t) que j'aurais du mal à écrire polynomialement).

Je n'ai pas eu le temps de finir alors qu'il me semblait avoir fini par comprendre la preuve, ce qui est un peu dommage.

À part un des membres qui posait beaucoup de questions, les autres n'avaient pas l'air très intéréssés. Il étaient plutôt bienveillants.

Pas de réponse fournie.

Pas de réponse fournie.

C35, ça partait sur la recherche du nombre d'isomères connaissant la formule brute d'une molécule et on en vient après à devoir dénombrer des arbres ayant certaines contraintes.

C25, des codes correcteurs classiques.

Le texte proposait plusieurs techniques toujours plus efficaces pour dénombrer les arbres 2-3-4.

J'ai touché en gros aux 4/5 du texte, j'ai démontré les résultats principaux en essayant de mettre l'accent sur le côté modélisation/complexité. J'ai implémenté deux des algorithmes proposés dans le texte.

Pas mal de questions sur la modélisation (pourquoi les algorithmes ont telles complexités, est-ce qu'on peut faire mieux, pourquoi pouvait-on s'attendre à certain résultats...). Un long retour sur la définition de taille d'un arbre 2-3-4 que je n'avais pas bien comprise (ça la fout mal pour un texte sur les arbres). Puis pas mal de petites questions mathématiques en lien avec les méthodes que j'ai abordé plus superficiellement.

Je pense avoir bien choisi les résultats que j'ai présenté (je n'ai pas touché à une partie immonde se basant sur des séries form- pardon des séries entières).

Ils étaient à l'écoute et très gentils. Tout le jury a participé à l'échange, c'était très agréable. Je crois aussi les avoir mis de bonne humeur quand ils ont vu que j'étais trop petit pour pouvoir descendre l'écran même en sautant :-)

À peu près oui, je ne m'attendais pas à voir ce genre de texte extrêmement éloigné du programme.

17

Algèbre linéaire, polynômes

Codes correcteurs, polynômes

On s'intéressait à une dune sur laquelle marchent des passants. Lors du passage d'une personne sur la dune cette dernière s'aplatit. On modélise le phénomène en disant que cela revient à multiplier un vecteur par une certaine matrice et à ajouter un vecteur "déformation". Cela nous ramène donc à l'étude à l'étude d'une suite arithmético-géométrique et à l'étude du spectre de la matrice...

Plan : I. Modélisation du problème
II. Une suite de matrices
III. Localisation du spectre

Code : quelque chose de très élémentaire, il s'agissait de montrer les matrices qui interviennent (construction par bloc). Il y avait plusieurs graphiques : 1 pour visualiser la localisation de le seconde plus grande valeur propre de la matrice, 1 pour visualiser la dune au début VS la dune après multiplication par une puissance de la matrice.

J'ai essentiellement touché à les 2/3 du texte en me concentrant sur la proposition 2. Le III. illustrait les résultat de la partie suivante. Je n'ai même pas regardé le dernier tier du texte.

- D'après vous comment fonctionne la fonction "eigenvalue" ?
- Vous montrez que cette droite admet un supplémentaire orthogonal stable : est-ce vrai en général ?
- Quelques questions sur comment lire certaines infos sur la matrice (qui était naturellement échelonnée)
- A votre avis : aurait-on pu faire mieux pour calculer cette matrice ? (ils attendaient que je calcule les coefficients un à un plutot que d'obtenir la matrice comme produit de matrices élémentaires)
- Vous avez parlé du théorème de Courant Fischer : pouvez vous l'énoncer et expliciter le lien avec le texte ?
- Quelques questions qualitatives sur les hypothèses qu'on faisait (symétrie etc) et que je ne suis pas sûr d'avoir compris (il restait très peu de temps, je n'ai pas eu le temps de vraiment répondre).

Je ne pense pas que j'aurais pu mieux faire étant donné mon peu de virtuosité en informatique mais j'aurais bien voulu prendre plus le temps de discuter des hypothèses qu'on faisait dans le texte.

Jury neutre, cependant très aimable.

C'était l'oral que je redoutait le plus : il s'est bien passé ! Un peu surpris du fait que le texte nous faisait au final faire pas mal d'analyse matricielle.

16.75

Chiffrement par des polynômes.

Aucune idée, il y avait des matrices et des polynômes.

Mise en place d'un protocole ayant pour but de faire une requête et d'obtenir un résultat sur un moteur de recherche sans que celui-ci n'ait accès ni à la requête ni au résultat.

I/ Mise en place du protocole
II/ Commutativité
III/ Attaque naïve, sécurité du protocole
IV/ Conclusion

Pas mal de code assez basique

Pas de réponse fournie.

Tout

Neutre

J'avais assez pour ma présentation au bout de 3h15 de préparation je dirais, c'est assez perturbant.

Pas de réponse fournie.