D88 - Théorie des jeux via satisfiabilité
D85 - Codes correcteurs
Pas de réponse fournie.
Pas de réponse fournie.
Beaucoup de questions sur l'exposé, le modèle présenté et ses hypothèses. Sur le code aussi et les mécanismes derrière les primitives utilisées.
- List.hd et List.tl sont-elles des fonctions totales ?
- pourquoi telle ou telle hypothèse ? Quelles conséquences si on la change ?
- une remarque sur une erreur de style dans mon code (vu la taille du fichier que j'ai pondu, ça n'est pas étonnant d'avoir quelques petites maladresses par-ci par-là)
Le texte portait sur la modélisation de procédés automatiques par un jeu : une machine doit réaliser une chose sans être mise en échec par les actions de son environnement. On voit ça comme un jeu à deux joueurs représenté par un graphe (les sommets où A joue et ceux où B joue plus les transitions entre les sommets selon les règles du jeu). On voit deux types de jeux : le joueur A veut atteindre l'un des sommets d'un ensemble donné, ou il veut l'atteindre une infinité de fois.
- questions sur un exemple basé sur un problème de réseaux (l'instanciation sous forme de jeu est un peu complexe) : on doit envoyer 9 messages d'un noeud à un autre au travers d'un petit réseau, sachant qu'à chaque instant un seul lien peut être cassé et à chaque instant au plus un message transite sur chaque lien.
Pour calculer l'ensemble des sommets d'où A a une stratégie gagnante, on modélise le jeu par un ensemble de clauses de Horn dont on vérifie la satisfiabilité par un petit programme (exercice de programmation).
- est-on certain d'avoir produit assez de clauses pour tout avoir ?
Pas de réponse fournie.
Pas de réponse fournie.
Très petit tableau, j'ai du demander à effacer une partie et j'ai fini à l'oral (pour les remarques du genre intérêt et faiblesses du modèle et l'ouverture à la fin).
Pas de réponse fournie.
Triangulation parfaite
Un truc sur les réseaux sociaux
On s'intéressait ici au problème de triangulation parfaite (le nom du sujet donné à la triangulation de Delaunay...). Une partie était plutôt théorique : on définissait mathématiquement une triangulation, celle de Delaunay et l'équivalence entre Delaunay (tous les disques ouverts circonscrits aux triangles ne contiennent aucun point) et un critère d'optimalité (on maximisait l'ensemble des angles des triangles triés avec l'ordre lexicographique). Dans la deuxième partie, on étudiait l'aspect algorithmique avec l'algorithme incrémental classique, où quand on insère un point, on supprime les triangles qui ne respectent pas la règle de Delaunay puis on retriangularise.
Mon plan :
Introduction
I] Définitions et étude mathématique
a) Triangulation
b) Triangulation optimale
c) Quelques propriétés (i.e. nombre d'arètes et de triangles)
II] Aspect algorithmique
a) Borne inférieure
b) Algorithme incrémental
MODELISATION
c) Complexité (évaluation du nombre de triangles ajoutés et du nombre de tests d'appartenance d'un point au disque circonscrit)
d) Structure de données (là je parle de comment on peut faire en pratique pour supprimer un triangle, et plus généralement pour représenter une triangulation)
Par rapport au texte, j'ai expliqué l'existance et l'unicité d'une triangulation de Delaunay, j'ai démontré la formule donnant le nombre d'arêtes et de triangles dans une triangulation quelconque, je montre la borne inférieure en $n \cdot \text{log}(n)$ (l'idée de l'exemple était donné) et la complexité pire cas de l'algo incrémental.
Ma dernière sous-partie n'apparaissait pas dans le texte, j'y parle d'halfedge (une structure pour pouvoir représenter et parcourir une triangulation de façon compacte et simple).
- Vous n'avez pas traité exactement l'exercice de modélisation". En effet, j'avais commencé dans la bonne direction, mais j'ai zappé le but de l'exo de modélisation (on voulait un algo qui dit si un polygone est convexe). Du coup j'explique un algo auquel j'avais pensé (on regarde les orientations successives), on me fait demander la complexité (linéaire), alors qu'une indication suggérait un algo quadratique. Du coup j'exibe un contre exemple ou ce que je voulais faire ne marchait pas.
- Une question sur l'utilisation des float en Caml (je faisais notamment une comparaison par rapport à 0.). Le but était de discuter sur les problèmes d'arrondis, si on multiplie deux nombres petits on peut avoir un problème sur le représentation en machine, et quand on fait petit fois grand on peut avoir des soucis si le nombre trop petit à des erreurs d'arrondis, amplifiée quand on multiplie.
- Evidemment la question qui suit.... Comment on peut éviter ça ? Bah comme on ne fait pas que des opérations type multiplication/divisions, on peut représenter les entiers sur lesquels on travaille par des fractions, du coup on peut faire du calcul exact. L'inconvénient est que pareil, quand on fait des opérations sur deux nombres rationnels, le dénominateur peut doubler de taille à chaque opération, et du coup sortir de la précision de l'ordinateur si on fait trop d'opérations. La personne du jury qui m'a posé cette question était visiblement satisfaite.
- On discute longuement autour d'un argument que j'ai proposé à l'oral pour une preuve qui ne convenait pas ici (pour l'unicité j'utilisais un argument du type "Si on a deux solutions différentes, on peut s'arranger pour transformer l'une vers l'autre" alors que ce n'était pas possible ici). Du coup ici, il fallait utiliser l'autre caractérisation de Delaunay sur les angles triés dont je n'ai pas parlé, qui là fournit un critère d'optimisation. J'ai eu une autre question du même genre mais je ne m'en souviens plus.
- Dans l'exemple pour la complexité pire cas, on place des points sur une parabole. Vous devinez la question... "Bah pourquoiiiii ?" Là j'ai dit que ce qui était important, c'est d'avoir une courbe telle que la triangulation de Delaunay permettait d'obtenir la liste des éléments triés facilement, et du coup comme on sait que le tri c'est au moins $n \cdot \text{log}(n)$, c'est gagné.
* Ensuite : "Mais pourquoi c'est au moins $n \cdot \text{log}(n)$ le tri?" Déjà c'est le tri par comparaison, ensuite le truc classique : arbre de décision, lien feuille/ordre des éléments, la hauteur c'est le pire cas de l'algo, et le lien entre hauteur et feuilles nous donne le résultat.
- Un des jurys voulait que je réexplique les halfedges, et surtout comment on obtient les triangles. Je dis que voir les somets d'un triangle c'est facile si on a une halfedge de ce triangle, par contre comment on la trouve... j'y avais pas pensé. Du coup je dis que j'avais vu cette structure dans un stage, et que je voulais montrer les idées essentielles.
J'aurai du faire plus attention à l'exercice de modélisation demandé, surtout que ce n'était pas bien dur et il y avait une indication ! Après c'était le dernier jour et j'étais pas mal fatigué. Mais des points vraiment perdus pour rien, alors que c'était un sujet que je dominais suffisamment je pense...
Peut-être aussi faire une "vraie" démonstration mathématique, mais question temps j'étais tout juste et je voulais pas raccourcir davantage.
Un des membres du jury monopolisait plus la parole, un autre dormait les 3/4 du temps, le troisième était grognon parce que je n'ai pas fait de démonstration mathématique "pure et dure" (c'est le seul dont je me souvienne du nom : Hubert Comon, ses thèmes de recherche sont réécriture et vérification... tu n'étonnes qu'il aime bien les démonstrations !). Enfin le dernier était sympathique et visiblement très content de mes réponses.
Pas de réponse fournie.
15.25
D80 : Codes correcteurs linéaires (algorithmique, complexité, matrices)
D67 : Séquençage ADN (programmation dynamique, arbres, grammaires)
Le texte traitait des codes correcteurs linéaires pour communiquer sur un canal bruité. L'idée est d'utiliser une matrice G de $M_{k,n}(F_2)$ pour envoyer un message m de $F_2^k$ dans $F_2^n$ en introduisant de la redondance. À partir de là, le texte donnait des propriétés sur ces codes, proposait deux algorithmes pour le décodage (exhaustif, par syndrome), et s'intéressait aux propriétés du code pour G choisie aléatoirement.
Code :
Ce qui était demandé par le sujet, à savoir l'algorithme de décodage par syndrome dans un cas particulier, en python
Plan :
I. Codage de Hamming (Exemple plus code)
II. Cadre théorique (Propriétés des codes correcteurs linéaires)
III. Code correcteur aléatoire (Probabilité que le taux de bruit admissible soit plus faible qu'un certain seuil)
Preuve :
J'ai prouvé quelques propriétés proposées par le texte sur la distance minimale d'un code correcteur, la possibilité d'un décodage unique s'il y a peu d'erreur, et le fait que la probabilité que la distance minimale d'un code aléatoire soit inférieure à un certain seuil tend vers 0 quand n tend vers l'infini.
Le jury a commencé par revenir sur mon code avec des questions sur la complexité de mes algorithmes et la pertinence de mes choix en terme de structure de données (je représentais les mots binaires par des tableaux de 0 et de 1, ils m'ont demandé pourquoi cette représentation, le coût de l'allocation, etc...).
Ensuite, j'ai eu une série de question sur les aspects théoriques, avec notamment un petit moment pour me faire corriger les tailles des vecteurs et matrices que je multipliais (je les avais écrit dans le mauvais sens) puis sur la complexité de l'inversion d'une matrice par le pivot de Gauss. Ils m'ont aussi posé des questions sur la complexité temporelle et spatiale des autres algorithmes proposés dans le texte, en fonction de la représentation des mots sur $F_2^n$.
Pendant la présentation, j'ai eu l'impression de ne pas être très clair dés le début même si ça s'est amélioré ensuite. Il faut garder en tête que le jury ne connaît pas forcément le détail du texte et faire attention à introduire tout ce dont on parle. Au niveau de la gestion du temps, je n'ai pas pu présenter tout ce que je voulais, donc j'aurais sans doute pu aller plus vite sur la première partie qui est conceptuellement simple.
Jury très sympathique pendant les questions, ils avaient le sourire (ça détend l'atmosphère). Ils ne m'ont pas forcément beaucoup aidé, plutôt encouragé à poser les choses proprement au tableau à certains moments.
L'oral en lui même m'a surpris positivement, l'ambiance était beaucoup plus détendue que ce à quoi je m'attendais. Peut-être même plus que pendant les oraux blancs :) Au niveau de la préparation, j'ai fini de préparer ce que je voulais présenter avec 30mn d'avance (et je n'ai pas eu le temps de tout présenter), j'ai essayer de coder un peu plus que demandé dans le texte, mais je n'ai pas eu le temps d'aboutir à quelque chose d'intéressant.
Pas de réponse fournie.