Je suis sûre que vous avez besoin de voir un bébé oie installé sur le dos de sa maman
Remote
Dr Pyviv
@pyviv@social.sciences.re
mastodon 4.6.8Maîtresse de conférences en informatique -- Associate professor in Computer sciences
About research, math, progamming, feminism and whatever I feel like talking about...
1568 Followers
241 Following
50 Posts
Joined November 12, 2022
Blog:
"oui mais quand même parfois, c'est juste que les filles aiment pas l'informatique"
Il y a 2 postes et je suis 3ème
Donc c'est trop la classe en vrai mais moins la classe que si j'avais vraiment le poste. Et maintenant mon destin dépend de choix qui n'ont plus rien à voir avec moi. Donc on verra 🤷🏼♀️
L'enfant : Chacun sa route 🎶
La dame qu'on croise dans la rue : Chacun son chemin !
Le monsieur derrière : Chacun son rêve !
Moi : Chacun son destin !
L'enfant : 😯
"oui allo Viviane de la semaine dernière ? C'est Viviane du présent, je crois qu'il y a un PROBLÈME dans le planning, c'est noté : préparer et donner un keynote à une rencontre internationale, clôturer Parcoursup ET préparer UNE AUTRE audition. Il y a que 3 jours ouvrés, ça rentre pas !
Viviane de la semaine dernière : ouais euh déso pas déso, moi ma mission c'était l'audition de Jussieu, j'ai tout donné, le reste bon c'était après quoi, je pouvais pas m'en occuper.. Râle plutôt sur Viviane d'il y a 3 semaines
Viviane d'il y a 3 semaines : vous avez la mémoire courte, j'étais H24 sur le cours de Bristol + l'exam à préparer, c'est pas comme si j'avais eu du temps
Viviane d'il y a 2 semaines : et pensez même pas à venir me saouler vu que c'est moi qui me suit tapée la correction de l'exam en même pas 1 journée. J'ai été ultra efficace et c'est chacune pour soi, débrouillez vous !
Mardi j'ai l'honneur d'être invitée à parler au "International Day of Women in Mathematics" par l'association "African Women in Mathematics Association"
Je dois parler de "Global Collaboration and the Role of Networks in Advancing Women in Mathematics". Mais je commence par parler du sexisme et je parle de la phrase qu'on entend souvent "bah oui, elle a eu le poste parce que c'est une femme" et donc je peux donner un témoignage direct que ça marche pas top top
Présentation : 24 minutes 59
Nombre d'heures de préparation : 24h 45 minutes
J'ai fait ma part, je l'ai bien faite. Je sais qu'il y a d'autres candidat-es qui sont aussi très bien. Alea jacta est
Bon j'ai vu les Star Wars I, II et III et ma conclusion, c'est que les jedi sont vraiment très nuls et se font avoir comme des bleus. Et en plus, leur philosophie est toute pourrie
Replying to
Et comme on aime découper en triangle, il y a des gens qui étudient toutes les façons de découper en triangle (genre moi je fais ça parfois).
Car oui, il y a plusieurs façons de faire ce découpage. Pour l'octogone de tout à l'heure, je vous ai montré un exemple mais il y a 132 façons différentes. On sait compter ça en combinatoire, ça s'appelle les nombres de Catalan, c'est mes nombres préférés
https://fr.wikipedia.org/wiki/Nombre_de_Catalan
Malgré la pluie, elle décida de sortir un dimanche après-midi. C'est ainsi qu'elle découvrit que sa semelle droite était fendue
-- t'as pas fini ton œuf !
-- j'aime pas
-- Depuis quand t'aimes pas les œufs sur le plat ?
-- j'aime pas cet œuf là
😑😑
Bon par contre, faut que je me concentre là. J'ai attendu bien 5 ou 10 minutes en gare de Robinson en attendant qu'on reparte avant de réaliser que : j'étais à Robinson, Donc dans le mauvais train, et qu'on était arrivé au terminus donc clairement on allait pas aller vers Saint-Remy-les-Chevreuses
Replying to
Et Joseph Dorfer a démontré que le calcul de la distance de flip est NP-complet donc en gros, il est équivalent à tous les autres problèmes relous qu'on a déjà. Ça veut dire que c'est PAS LA PEINE d'essayer de se prendre la tête à trouver un algorithme efficace parce qu'on VA PAS Y ARRIVER
Mais c'est pas grave hein ! Ça veut dire qu'on peut mettre son énergie ailleurs, par exemple calculer des solutions approchées
Replying to
Bon et je peux pas m'empêcher de remarquer : parité au niveau des auditionné-es mais les 2 classés premiers sont des hommes (et les 2-3-4 sont des femmes), c'est très section 25
Et évidemment bravo aux 2 premiers, évidemment qu'ils sont super forts, mes critiques ne sont pas nominatives. Ça dit juste quelque chose des inégalités structurelles auxquelles on fait face
Je rappelle que le pourcentage de PR femmes en section 25 c'est genre 6 ou 7 %
(section 25 = maths pures)
Le filleul écoutait Bella de Gims et je lui ai montré la parodie des @lesgoguettes sur Bardella et il a trouvé ça drôle. Je prends toutes les petites victoires
Replying to
@MonniauxD@social.sciences.re donc en vrai, même "que" 3ème et sans poste, ça reste vachement la classe
Replying to
Donc voilà, je vous ai résumé le résultat. Je ne sais pas du tout comment il le démontre car je n'ai pas encore lu l'article. Assez récemment, un autre article démontrait la NP-complétude de la distance de flip pour les polygones non convexe
https://arxiv.org/abs/1209.0579
Replying to
On peut se demander pourquoi on veut savoir ça. Donc déjà je vous ai dit que les triangles et les triangulations, on aimait bien ça mais peut-être ça vous convainc pas assez. Mais il se trouve qu'en plus, les triangulations peuvent être transformées en plein d'autres choses !!
Par exemple, si je mets un point dans chaque triangle et que je relis ensemble les points qui sont dans des triangles qui se touchent, j'obtiens une autre structure qu'on appelle un arbre binaire
Replying to
@MonniauxD@social.sciences.re c'est un profil ouvert sur tout le labo (et ils avaient un 3ème poste en vrai, et ça fait 3 ans de suite qu'ils ont des postes, ils devaient avoir que des grabataires dans leurs équipes je sais pas 🤷🏼♀️)
Replying to
En gros, en théorie de la complexité, on range les problèmes en fonction de à quel point on peut les résoudre de façon efficace ou non. Et en gros, on a des problèmes qu'on sait résoudre pas trop mal et d'autres pas du tout
Ceux qu'on sait pas résoudre, on a jamais réussi à démonter que c'était vraiment pas possible de le faire de façon efficace, mais on pense que c'est une impossibilité structurelle inhérente au problème lui même, c'est la conjoncture que "P est différent de NP"
Mais on a mis tous les problèmes irrésolubles ensemble et on a démontré qu'ils étaient équivalent entre eux (en gros, si on sait en résoudre un, on sait résoudre les autres _ si je sais calculer un certain bidule dans un graphe, je vais réussir à calculer une solution d'une certaine équation)
Replying to
Et ce qu'on peut démontrer assez facilement, c'est que sur un polygone : on peut passer de n'importe quelle triangulation à n'importe quelle autre juste en faisant une série de "flip".
Voyez par exemple sur cette page le "graphe de flip" des 14 triangulations d'un hexagone
https://www.researchgate.net/figure/The-flip-graph-of-a-convex-hexagon-the-graph-of-the-3-dimensional-associahedron_fig4_365369610
Replying to
Et là le gros résultat de Joseph Dorfer c'est que : eh bah non ! Si on n'a pas réussi à trouver un algo sympa pour calculer cette distance c'est pas parce qu'on est nul, c'est parce que c'est très certainement pas possible !
Replying to
Pourquoi on fait ça ? Heu.. Parce qu'on a envie ?
En vrai, le triangle est la forme "la plus simple" et donc qu'on fasse de l'informatique graphique ou de la géométrie des polytopes, on va souvent découper les trucs en triangle car en math et info, on aime bien simplifier les choses
Replying to
Maintenant qu'on sait ça, on se pose une question toute simple : voilà 2 triangulations de mon polygone, c'est quoi la façon la plus rapide de passer de l'une à l'autre en faisant des flips? (c'est à dire le moins de flip possible)
Replying to
L'un des auteurs est le directeur de thèse de Joseph Dorfer avec qui j'ai beaucoup discuté de ce problème. Une triangulation d'un polygone non convexe ça peut ressembler à ça
La preuve fabriquait des espèces de "tunnels" comme sur l'image donc, une chose est sûre, la nouvelle démonstration de Joseph Dorfer doit être très différente. En tout cas, c'est un magnifique résultat et je vais devoir mettre à jour tous mes projets de recherche !!
Les enfants : oh regarde on s'installe là !!
(petit coin ombragé juste au bord de l'étang)
Moi : euh.. Ok mais vous allez pas dans l'eau !!
Les enfants avec un air ultra blasé : baah non enfin !! Pff
(vraiment ils comprennent pas pourquoi je leur dis de telles évidences)
....
....
Moi un peu plus tard : bah écoute maintenant tu REMETS TON SHORT et tu continues la balade avec des chaussures mouillées c'est tout c'est comme ça !
Replying to
Et là, C'EST LE DRAME !! On ne sait pas !! Évidemment, on peut calculer le graphe complet de toutes les triangulations, mais heu il y en a beaucoup, plus précisément le nombre de triangulations augmente de façon exponentielle par rapport au nombre de sommets.
Pour un polygone de 50 sommets, j'ai déjà plusieurs milliards de milliards de milliards de triangulations possibles. Donc no way de calculer le graphe complet 🤷🏼♀️
Replying to
Et les arbres binaires, c'est un truc très très courant en informatique, en particulier en algorithmique parce que ça permet de représenter tout un tas de donnés en les séparant à chaque fois en 2 groupes.
Par exemple je vais mettre tous les mots qui commencent pat une lettre entre A et M à gauche, et tous les mots qui commencent par N... Z à droite. Puis je vais redécouper à gauche et à droite en 2 nouveaux groupes etc.
Replying to
Voilà le (vrai) dodecaèdre après correction
Et pour m'occuper l'esprit et ne pas stresser pour rien, je dois faire passer 14 exposés de L1 😜
(ça fait 2 auditions / 2 passées où j'ai des soutenances de L1 le même jour)
"Chef, avec tout le respect que je vous dois, ce n’est pas avec les couilles qu’on tranche une langue."
Cabale @Sandg@piaille.fr
Replying to
Et tous ces problèmes "équivalents" et qu'on sait pas résoudre mieux, on les appelle des problèmes "NP complet" (c'est très résumé hein, mais c'est l'idée générale)
Replying to
Donc là, on va parler un "tout petit peu" de théorie de la complexité. Un truc qui prend la tête de toute la communauté informatique c'est le problème "P = NP"
https://fr.wikipedia.org/wiki/Probl%C3%A8me_P_%E2%89%9F_NP
Replying to
Et ce qui va nous intéresser aujourd'hui, c'est qu'on peut passer d'une triangulation à l'autre en modifiant juste une diagonale. Ça s'appelle un "flip" on choisit une diagonale, on la supprime et on la remplace par la seule autre diagonale possible qui forme une triangulation
Voilà un exemple
Replying to
Ah non j'ai zoome sur la photo et il y a une erreur 😱
Replying to
Il est toujours là, je crois que c'est mon pote maintenant (il y a une mare au pied de mon bâtiment, je pense que ça l'intéresse pas mal _ ça ou mon audition PR, on sait pas)
Replying to
Donc la question qui était ouverte jusqu'à présent, c'est étant donné 2 triangulations d'un polygone, quelle est la complexité du calcul de la "distance de flip", c'est à dire le plus court chemin entre les deux.
"complexité" en gros ça veut dire le temps théorique en fonction du nombre de sommets dans mon polygone
Replying to
Donc l'arbre binaire modélise plein de trucs intéressant et se retrouve dans plein d'algo. Et en plus, le "flip" sur la triangulation correspond à ce qu'on appelle la "rotation" sur l'arbre binaire qui permet de faire pencher l'arbre sur la gauche ou sur la droite.
C'est une opération très courante et utile. Ce qui fait qu'on aimerait bien savoir comment on calcule la "distance de rotation" entre deux arbres, aka la "distance de flip" entre les triangulations et surtout savoir si on peut le faire de façon efficace
Replying to
@dantheclamman agreed, I love it when some of the tools I built are used in papers I don't fully understand, it feels like progress has been made and science is working
Replying to
@lienrag@mastodon.tedomum.net il a pas démontré que P different de NP hein, il a juste démontré que notre problème à nous était NP complet, ce dont on n'était pas sûr du tout !
Replying to
Convexe signifie qu'aucun des points n'est "au milieu" des autres : je ne peux pas entourer un point avec des segments entre les autres points
Par exemple, cet autre polygone n'est pas convexe
Replying to
On va "trianguler" notre polygone convexe : c'est à dire qu'on va former des triangles en reliant les points entre eux. C'est ce qu'on va appeler une "triangulation"
Replying to
@Troggie it was absolutely awful the first time. The two times after that were ok. But I had some of the worst pain to remove it last time as it was somehow "stuck". Anyway even if the act itself is painful, I have had very little inconvenience afterwards and it's totally worth it (it's just good to know in advance that it can be very painful)
Replying to
@villapirorum@indieweb.social c'est bien la preuve qu'il me faut un poste DANS PARIS qui ne m'oblige pas à prendre le RER B ! (vu que je vis moi-même à Paris)