vendredi 5 janvier 2018

Lists in anki: desiderata and partial solution

In this text, I assume you are familiar with anki, and in particular know what is a field, a card, a card's type (aka template), a note and a note's type (aka a model), and that you have an idea of what are the rules used by anki to decide which cards should be generated or not.

There is one big limitation in anki, it concerns lists[1]. Here I list my trouble, the existing work arounds I know, their limits, and the functionnality I would really want. Sadly, this functionnality seems to require such a big modification of anki's underlying model that I fear that no add-on can answer my request. In particular if I want this request to also be satisfied in smartphone's application, which does not allows to add add-ons.

Learning a list of things is hard, but it's something I sometime want to do. A poem/song is just a list of line. Sometime, a mathematical notions have 4 distinct names. E.g. a pullback is also called a fiber product, a fibered product and a Cartesian square. In some othe case, a mathematical objects admits many distinct definitions[2]. E.g. I've got 5 definitions of left-trivial monoids. And I'd also wanted to see if I can learn the list of the prime number less than 100. Mostly to see how hard it is to learn an arbitrary list.

Work around

Creating a note by question

Currently, I used the add-on «imports lyrics/poetry» for lyrics of song I like. This add-on creates a note by line of the lyrics. The main trouble is that, if you have an error in a line, you need to correct many notes since the error is repeated. And it's hard to correct many notes from the smartphone, while it is easy to just correct the current note. The second problem with this method is that, since each lines correpsond to a distinct note, there is no way to ask Anki to bury the other notes(lines) related to the same song.

Furthermore, it is really inneficient in term of memory. Indeed, the first line of a 120-line lyrics is copied 120 times in memory.

A field by question

Concerning the definitions, I have in my note type «name», «name 2», «name 3» and «name 4». And my note's type contains 4 similar card's type, with similar templates. And I did the same thing for the four fields «notation». Normally, it means that when I do want to change a template, I'll need to change it - at least - 4 times. In order to avoid this, I created MetaTemplate, a template for card's type. But it's not really easy to learn how to use it and I have no idea of how to make it more user friendly. And anyway, having four fields works only because it is a small list.

Let us imagine I would like to have a single note for an entire song. And this song is 120 lines longs. The only solution I see would be to create a field by note, hence for a song with 120 lines, I would need a note type with 120 fields and 120 cards. Which is not technically impossible, but unreasonable. In particular because anki is already slow when I edit a note type with 30 cards.


The first thing I did to learn lyrics is to use cloze deletion. A single line would be deleted, and I have to remember it. The trouble is that, seeing the line after the deleted one is a really strong hint I'm not supposed to have when I recite the song. I would rearry prefer Anki to give me the start of the lyrics and asking for the next line. As is done by «imports lyrics/poetry».

My ideal world

I know explain what I would love to see when I use list. When I create a card type, I'd want to tell anki, «here is a list of thing» and maybe «its order matter» (for song) or «it order does not matter» (for list of names of an object). In the first case, I'd like to be able to ask Anki to randomize the order of the elements shown in a card. I don't think it'd be complicated, since we can use javascript.

The first option I want is to write in a card's type: «here, show every element of the list "name", separated by a "comma"» (of course, "name" and "comma" could be replaced by any other field and any other separator.) Thus, my card would show «name: fiber product, fibered product, Cartesian square». This is specially important if the question is «what is the name of "the limit of a product"». In this place, I should remember one of the name. Thus the answer need to show me every possible answer, and I would accept iff I remembered at least one of the name.

Similarly, I'd like to be able to tell anki to generate n cards, where n is the number of elements of the list. In card i I want the option to tell anki to shows only the ith element of the list. In my example above, each card would contains one of the name of the objects which admits multiple definitions, and each card would ask to give the other name. Hence the question would be «What is(are) the other name of "fibered product"» and the answer would be "fiber product, Cartesian square".

I also want the option to tell anki to show each elements appart from the i-th one. For example, this would let me tell to anki to ask me the i-th name given the n-1 other name. This would be especially usefull in order to learn lyrics. Assuming that you know the 10 first line, it makes sens to let you read them again in order to find the i-th line. By symmetry I probably want to see the n-i last line. (I don't yet see the usage I would have of it, but no reason not to do it too)

I'd also love the option to ask Anki for lines i-4 to i-1. For example, in the case of learing lyrics, you probably could remember the i-th line with only the four last lines, and not the entire beginning of the lyrics. That is what the add-ons «imports lyrics/poetry» does. But with this add-on, it is not possible do simply change the value of 4 to 10 if I realize that 10 would be better.


The main problem I see with this option is that some power-user may intend to put multiple lists l1, ..., lm into a type field. Assuming that the list lj has nj elements, the numbers of card to generate may be up to n1 times ... times nj elements. This may quickly be unreasonnable. This would mainly be a problem for the user, reviewing a lot of cards is not necessarily usefull. But it would also be a technical problem because each cards has a name. For clozed cards, the name depends on the card number. Here the name would depends of multiple number, it should be sure that we find a correct method to generate name, without ambiguity, and which does not vary if the content of a note vary. The name could be card_n1_..._nj but its not really beautiful nor practical when a card's type is changed. (Technical note: Actually, in the database, the card's number is used instead of its name. Here, I could state that the card n1 ... nj would be numbered as 2n1 times .... times pj^nj, with pj being the jth prime. But it would means that the length of the card number is linear in the number of card, which is technically ugly and innefficient.

Concerning the input, I think there should be at least two distinct kinds of input. The field should be either a text or a list. Nothing should be changed for the text field (what already exists). For a field F which is a list, the interface would have a button (+), stating to add a new text input for F.

Or maybe, each elements should be entered in a single text input area, with a special separator symbol. The separator should probably be a parameter, either in the add/edit window, or in the template. For example, it makes sens to consider that the separator of a lyric is the newline. But it would also makes sens to accept that the user just copy-paste the list of elements they want to learn, separated by a comma or a tab. (à la CSV)

I don't know enough about database to know the ideal way to obtain a column of a table which is a list of things. So I do hope that it would not be particularly complicated. I can imagine multiple solutions, but I don't know what is the best practice. But since, in the current database, a note is a list of field with a separator symbol, I guess it would not be really complicated to add a second separator.


[1] I assume here that sets are list, with an arbitrary order

[2] This is in general considered to be a proof that the object is really interesting

vendredi 18 novembre 2016

L'addition en virgule flottante est elle non commutative ou non associative

Lundi, on a lancé Trajectoires Podcast, «le podcast de la culture mathématique». Et Laura, chroniqueuse, dit que l'addition des floats, des représentations informatiques des nombres à virgules flottante, n'est pas associative. Il parait même que c'est ce qu'elle a toujours entendu dire dans son laboratoire.

J'aimerai revenir sur ce point précis, plus en détail que ce que j'ai dit à l'oral, quand je n'avais pas eu le temps d'y réfléchir. Mais d'abord je redonne un exemple.

Ainsi, la somme 1+0.000000000000000000000000000001+ (-1), calculé de gauche à droite, va donner 0, parce que le résultat intermédiaire 1+0.000000000000000000000000000001 aura été arrondi à 1. Par contre, si on inversait l'ordre des nombres, et qu'on prenait 1+(-1)+0.000000000000000000000000000001, ça donnera bien 0.000000000000000000000000000001. En effet le résultat intermédiaire 1+(-1)=0 a été arrondi à 0.

Et bien, je suis désolé, mais mathématiquement, c'est l'associativité qui est en cause. Pour le voir, il suffit de rajouter les parenthèse implicite. Notre deuxième calcul est (1+(-1))+0.000000000000000000000000000001. Mais si on avait fait le calcul 1+((-1)+0.000000000000000000000000000001), le résultat intermédiaire serait -1, et donc le résultat final serait 0. Et vous pouvez remarquer ici que seul l'associativité indique que les deux calculs donneraient le même résultat.

Mon explication

Je pense que ce qui est caché, quand on parle de la commutativé, c'est que les opérations ne sont pas commutatives. Remarquez que c'est trivial, si on commence par dire «bonjour $PRENOM» et seulement ensuite: «Quel est ton prénom ?
% :- »
Clairement, le programme va bugger.

Mais avec l'addition, cette intuition nous a été caché. Le bon moyen de donner du sens à ce qu'on appelle la commutativité de la somme, ici, se voit de la manière suivante. Prenons une liste L de nombre. Pour faire la somme des éléments de L, on initialise une variable V à 0, on fait une boucle sur les éléments E de L. Pour chaque élément E, on fait V:=V+E. Pour faire plus algébriste, on peut simplement dire que on considère que les floats sont un monoïde[1], et qu'on considère leur action à droite sur les floats. Et qu'on effectue toutes les actions à droites, successivement, à l'élément neutre du monoide, c'est à dire à 0.

Et c'est ces opérations informatiques de la forme V:=V+E qui ne commutent pas. Mathématiquement, c'est l'ordre dans lequel on effectue les actions à droite qui ne commute pas. Autrement dit, on ne peut pas commuter impunément les éléments de L. Mais tout ça n'a plus rien à voir avec la commutativité de l'opération binaire qu'est l'addition et tout à voir avec la commutativité des instructions informatique/application du monoïde.


Pour finir, si je me trompe et que effectivement l'addition des floats n'est pas commutative, ça sera super simple à montrer. Il suffit de donner deux floats x et y tel que x+y n'est pas égal à y+x. Et SEULEMENT deux nombres, montrer la commutativité n'a pas besoin de plus.

Comme me l'a signalé un-e ami-e, j'ai fait dans ma chronique exactement la même bêtise que celle que je signalais à Laura. En effet, quand je dis «commutativité», c'est faux, l'associativité était aussi nécessaire vu qu'il y a 4 personnes.

Wikipedia dit la même chose que moi.


[1] On a le droit, si l'on suppose que les floats sont associatif.

dimanche 7 août 2016

Wikipédia, ou le périple du purement fonctionnel

Durant ces vacances, je me suis décidé à créé et/ou compléter quelques pages Wikipédia en informatique. Et c'est pas totalement simple, surtout car je suis curieux et que je vais fouiner dans les arcanes wikipédiatesque. Donc voici quelques histoires qui, j'espère, ne nécessitent de connaître ni l'informatique ni le fonctionnement interne de Wikipédia pour pouvoir être comprise.

Plus précisément, j'ai voulu créer des pages sur les structures de données purement fonctionnelles. C'est un sujet que je trouve très joli, et j'ai justement profité des vacances pour lire Purely functional data structures de Chris Okasaki. Ce livre à 17 ans et mériterait bien une deuxième édition afin d'être mis à jour[1] puisque j'ai appris via Wikipédia que de nouvelles structures purement fonctionnelles plus efficaces ont été découvertes[2] depuis.

Le premier problème[3], c'est que la page purely functional existe. Sauf que, elle ne devrait pas. D'ailleurs, c'est ce qui est dit dans les discussions[4], cette page n'a pas de sens. On pourrait parler de langages purement fonctionnels. De structures de données purement fonctionnelles. De programmation purement fonctionnelle. Mais «purement fonctionnel» tout seul, ça ne veut rien dire. Et même si en 2009 et 2013 des gens ont dit que la page devrait être supprimé, personne n'a fait la demande formelle, ce qui dans leur jargon se nomme un AfD, Article for Deletion. Je m'en suis donc chargé. Les avis semblent être «on ne supprime pas, on va juste en faire autre chose», sans consensus sur ce qu'est cet autre chose. L'un propose de merger avec «transparence référentielle», un autre avec «programmation fonctionnelle». Et encore un propose de couper l'article en deux entre langage purement fonctionnel et structure de données purement fonctionnelle. Je trouve cette dernière proposition assez marrante. L'article «purely functional» est petit. Un tiers de l'article est un exemple, hors-sujet, et que des gens avaient déjà dit être mal choisi. Et un autre tiers contient juste des liens, qui sont d'ailleurs pas toujours pertinent.

Ce qui amène à un autre problème, la page programmation fonctionnel est déjà très longue, très documenté, et contient tout ce qu'il faut sur la programmation purement fonctionnelle. On dirait même que l'introduction parle plus de purement fonctionnel que de fonctionnel. Et j'ai AUCUNE envie de toucher à cette page, qui a déjà une longue page de discussion, avec quelques controverses, dont une assez fort pour qu'un éditeur dise qu'une phrase de l'article le fasse vomir (ce qui, sur un tel sujet, me semble très surprenant.) Bref, je ne vois pas ce qu'on pourrait prendre de «purement fonctionnel» pour mettre dans cette page.

Structures de données purement fonctionnelles

Je commence donc à prendre l'article «purement fonctionnel», et m'en inspirer pour en faire un article «structure de données purement fonctionnel». Sauf que je trouve triste qu'il y ait peu de telles structures à mettre en exemples. Pour l'instant, il n'y a presque des structures qui sont naturellement purement fonctionnelle, comme les piles ou les arbres binaires de recherches. C'est pas super intéressant d'avoir des exemples qui sont purement fonctionnel par hasard, le vrai intérêt de cette page, et du livre mentionné plus haut, c'est que parfois, choisir purement fonctionnel a des avantages ET des inconvénients. Bref, que ça demande au programmeur de vraiment faire un choix. Or, la seule structure listée sur la page actuellement est la VList.


Une petite note sur la VList. D'abord, elle a l'avantage de n'être effectivement pas une structure utilisé hors du monde purement fonctionnel, donc d'être un exemple potentiellement pertinent. Elle a par contre le désavantage de n'être pas non plus utilisé dans le monde purement fonctionnel. Et pour une raison toute simple, il n'est pas possible de créer cette structure dans le monde purement fonctionnel. Ce qui amené son découvreur, Phil Bagwell, à demander - arguments à l'appui - à ce qu'on rajoute ça comme brique de base des langages purement fonctionnels. Pour l'instant, ce n'est pas fait. À part dans le langage créé par M. Bagwell afin d'illustrer l'efficacité de cette structure.

Cette structure de donnée prétend être une liste, persistante, avec un accès en lecture en temps constant en moyenne à n'importe quel élément. Si vous comprenez pas, dites vous juste que c'est un truc souvent utilisé, avec des propriété sympathiques et qu'on sait pas avoir en général[5]. Je me demande donc pourquoi je n'en avais jamais entendu parler. Je vais alors lire l'article originale. Et là je réalise - si j'ai bien compris - que ce qui est passé sous silence, c'est que le temps constant en moyenne ne tient QUE SI la persistance n'est PAS utilisée. Autrement dit, il y a deux propriétés sympathiques, mais il faut choisir l'une ou l'autre. En tout cas, c'est ce que je crois comprendre, ce que les discussions de l'article Wikipédia semblent dire.

Notons en passant, à la décharge des VList, que ça ne serait pas la première structure de donnée persistante OU efficace. Les queue amorties, par exemple, en sont un exemple simple. Il se trouve que les queues temps-réel corrigent ce problème, mais, pour autant que je sache, il n'est pas corrigé pour les random-access list[6]. Bref, en soit, c'est un défaut qui n'est pas rédhibitoire, mais encore faut il le mentionner explicitement. Ici, l'article Wikipédia, et l'introduction de l'article original, ne mentionnent que les cotés positifs.

De toute façon, l'article original, de recherche, ne contient aucune preuve. Il contient des résultats d'expérience, mais sans expliquer quels expériences exactes sont faites, donc ce n'est pas très utile. Ce qui n'est pas grave d'un point de vue de recherche, puisque c'est un papier de conférence, et que c'est donc sensé être un travail en cours, pas un papier définitif. Bref, aucun article, ni Wikipédia, ni l'original, ne sont clair. Et il y a dans les discussions sur Wikipédia des questions à son sujets, posées en 2006, auxquels personne n'a répondu.

Les humains derrières tout ça.

Ça va être encore plus dur d'avoir des réponses que Phil Bagwell, le découvreur des VList, puisqu'il est mort il y a 4 ans. Non pas que s'il était mort plus récemment ça serait mieux. Et de toute façon, il est mort 12 après son article parlant des VList, donc je suppose que s'il n'a jamais publié à leurs sujets depuis, il y a d'autres raisons. Et pourtant, j'hésite à faire une demande de suppression de l'article VList, car j'ai quelque part l'impression bête que ça serait manqué de respect à un mort.

Une petite note en passant. Pour ceux qui seraient gêné(triggeré) par des histoires de chantages/de rumeur de sexe/et de mineur.... je ne mettrai pas sur ce blog le mot qui désigne l'union de ces deux derniers sujets ..., merci de passer au paragraphe suivant. J'ai voulu regarder le profil de l'auteur original de l'article et voir s'il pouvait améliorer l'article. Il a été banni de manière définitive de tout le projet commons (Wikipédia et tout ce qu'il y a autour), et il était admis de Wikipédia. Ma curiosité a voulu savoir pourquoi il était banni... Je sais que certains n'aiment pas Wikipédia, que Wikipédia a bien des défauts. Mais je n'imaginais pas que des sites entiers (au moins deux) étaient dévolu à dénoncer les abus et «crimes» de la direction de Wikipédia. Et ces sites sont totalement capable, et c'est leur but, de faire que quand on recherche un nom d'administrateur, on trouve d'immondes rumeurs. Je n'ai pas vu de preuve pour étayer ces accusation - ils disent que les admins les ont supprimés - et je n'ai rien lu qui me suggère que ceux qui écrivent ces rumeurs aient fait part de leurs soupçons/certitudes aux autorité judiciaires. J'ai trouvé ça effrayant parce que, même si je savais théoriquement que la réputation en ligne - c'est à dire la réputation aujourd'hui - était quelque chose de fragile, je n'avais jamais vu moi même ça en fonctionnement. Et je ne m'avais jamais vu moi même être convaincu par ces sites, au point qu'il me faille attendre au moins une heure pour qu'un déclic se fasse et que je me dise que je n'ai rien qui m'indique que ces accusations ont quoi que ce soit de véridiques. Me dire que, pour ce que je sais, il est plus probable qu'ils ont inventer les copies de logs IRC qu'ils nous montrent. Et qu'il restait, même avec ses logs, peu probable que les programmes créé pour aider les jeunes à éditer Wikipédia servent aux admins à rentrer en contact avec ses jeunes dans des buts non précisés.

Et c'est horrible, parce que ces accusations sont à coté de trucs crédible, et probablement vrai. Sur plus d'un millier d'admin, par exemple, ça serait mémé étonnant qu'il n'y en ai aucun qui ait cherché ce poste avant tout pour avoir un truc impressionnant à mettre sur un CV, et pas pour améliorer Wikipédia. (Et encore, vu le processus qu'il faut passer pour être et pour rester admin, ça ne me parait pas évident que ça soit une idée courante).

Des vrais structures de données purement fonctionnelles

Histoire qu'il y ait des structures de données purement fonctionnelles, qui soient reconnus par la communauté, et qui ne soient pas triviales, j'ai décidé de rajouter une description des queues temps-réel, des queues à deux bouts temps-réel. J'ai aussi voulu faire les listes à accès aléatoire. Sauf que les implémentation purement fonctionnelles efficaces de ces listes sont basée sur les représentations skew binaire des nombres. J'ignore comment cette représentation se nomme en français. Alors, pour une fois, l'article était déjà là, il a juste fallu l'améliorer, et rajouter des choses qui étaient absentes. En particulier, plutôt que de dire qu'il n'y a qu'un nombre a changer, il est plus pertinent de dire que le changement se fait en temps constant sur les représentations sparses[7]. Ce qui nécessite de créer un article sur les représentation sparse des nœuds.

Les représentations sparses des nombres.

Et là, encore un problème. Il est dur de trouver des sources sur les représentations sparses. D'abord, parce que google renvoie beaucoup plus de liens vers les matrices sparses, qui sont pour le coup un sujet très important du calcul numérique. Et que même quand j'obtiens des nombres au lieu d'obtenir des matrices, et bien j'obtiens des nombres sparses, alors que je veux des représentation sparses de nombres. Les nombres sparses, ceux dont la représentation binaire n'ont pas deux bits consécutifs à 1, n'ont d'ailleurs pas de page Wikipédia. Mais là, j'ai pas envie d'en faire, car je ne sais pas à quoi ça sert, à part à faire des jeux mathématiques. Et même si je soupçonne que c'est très pratique en théorie de l'information/théorie des codes, par exemple car représenter deux 1 d'affiler pourrait causer un bug, je n'en sais pas assez, je ne veux pas inventer, ni même passer du temps à chercher.

En même temps, c'est assez normal que je ne trouve pas grand chose sur les représentations sparses. Parce que même si la fonction successeur s'y fait en temps constant, cela n'est pas très utile en pratique, vu que la fonction successeur se fait aussi en temps constant en pratique sur les processeurs actuels. Je n'ai pas fait de test, mais je doute que la représentation sparse fasse vraiment gagner du temps, à moins de travailler sur des nombres qui font, au moins, des milliers de chiffre. Ce qui est assez rare il me semble. Et même si ça arrivait souvent, ça règle uniquement la question du successeur, l'addition se fait toujours en temps linéaire en la longueur des nombres, et quant à la multiplication, je n'ai rien trouvé, et pas osé y réfléchir.

Bref, tout ça pour dire, c'est un peu dur de justifier sur Wikipédia l'article des représentations de nombres sparses. Et si j'ai bien trouvé une source différente de Okasaki, j'ai un peu triché, puisque cette source citait Okasaki. Parce qu'il utilisait aussi les représentations des nombres comme guide pour implémenter une structure de donnée efficace. Notons en passant qu'une partie de mon ancien laboratoire s'occupe de représentation des nombres, il y a donc une solution simple: me renseigner la prochaine fois que j'y retourne.

Les articles généraux.

Puisqu'il y avait une majorité de gens proposant une page de redirection plutôt qu'un article «purement fonctionnelle», encore fallait-il avoir des choses vers quoi rediriger. Il est théoriquement possible, mais pas recommandé, de rediriger vers des articles qui n'existent pas. J'ai donc pris mon courage à deux main, suivi les recommandations Wikipédia de créer de manière audacieuse, et, malgré mon anglais, j'ai créé une page sur la programmation purement fonctionnelle, et un article sur les structures de données purement fonctionnelles. Dans ce dernier article, je pouvais d'ailleurs enfin y lier des exemples naturels et intéressants que j'avais créé plus tôt.

J'ai donc remplacé la page «purement fonctionnelle» par une page de désambiguiation. Et ça a été mon premier revert, la première fois que quelqu'un annule une modification que j'ai fait. Parce que, d'abord, la discussion n'était pas fini. Et de toute façon, il y a près d'une cinquantaine de page qui renvoyaient vers «purely functional», or les liens ne doivent pas renvoyer vers de la désambiguation, sauf exception[8]. Il fallait donc rediriger tout ces liens vers la bonne page, en fonction de si purement fonctionnel fait référence à un langage, une structure de donnée, un paradigme ou une fonction.

Et c'est pas si simple que ça, car parfois, je ne trouvai pas le lien vers l'article «purement fonctionnel». Parfois, c'était parce que le lien pointait vers une page qui, elle-même, redirige ait vers purely-functional. Ce problème disparaissant quand la redirection est corrigé, mais ce n'était pas évident. Parfois, le lien était dans un template, il fallait alors comprendre qu'il fallait aller regarder le code du-dit template au lieu de regarder le code de la page qui appelle le template. Et enfin, parfois, le lien était totalement introuvable. Et j'ai laissé tombé. J'ai finit par comprendre quand j'ai eu un conflit d'édition; c'est à dire quand, en validant, Wikipédia me dit qu'entre temps, quelqu'un avait modifié la page. Parce que nous étions en fait, au moins deux, et je soupçonne trois, à faire ça en parallèle.


Bon, ça n'a pas totalement arrêté le débat de la page de suppression. Parce que quelqu'un prétendait que, il y a quand même un lien entre programmation, langage, fonction et structure de donnée purement fonctionnelle, donc que si une page existe, il faut qu'elle résume ce qui lie tout ces sujets. Sauf que vu que, pour l'instant, aucun article/texte n'explique clairement ce qui relie tout ça, un tel résumé serait du travail original, ce qui est interdit dans Wikipédia ! Et puis, aucun des informaticiens de la discussion ne se sentait capable de faire un tel article, et le seul à défendre l'article général était le seul à dire ne pas connaître le sujet dont on parle.

Il n'est pas permis d'avoir une page de désambiguation pour un terme T si elle se contente de renvoyer vers toutes les expression qui contiennent T. La règle est qu'il faille que quelqu'un, sans contexte particulier, puisse appeler chacun des objets «T». C'est ce qui justifie sa place sur la page de désambiguation. Il y a donc eu un «débat», où certains tentaient de justifier que dans la phrase «Haskell est purement fonctionnel»/«les piles sont purement fonctionnelles», il n'y avait pas besoin de contexte, tandis que d'autres disaient que le contexte indiquait clairement qu'il s'agit d'un langage/d'une structure de donnée purement fonctionnel, donc qu'on est dans le cas du sous-terme.

Deux solutions magnifiques se sont offertes à ces deux problèmes. En loi des marques américaines «purely functional» fait référence à functionality doctrine, qui n'a rien à voir avec le schmilblick. Cela justifie donc la désambiguation et rend impossible la page générale.

Et une deuxième solution, encore plus jolie, s'est offerte. La discussion avait lieu sur la demande de suppression de la page. Or, presque tout le monde était d'accord sur le fait que la page ne doit pas être supprimée. La discussion pouvait donc être close, savoir si on faisait une page de désambiguation ou un résumé global était hors-sujet. Celui qui a fermé la discussion a quand même dit que si on voulait en parler on pouvait, dans la page de discussion de l'article «purement fonctionnel». Mais, personne l'a fait, et plus personne n'a contesté quand il a remplacé la page «purement fonctionnel» par une page de désambiguation !


On me demande parfois pourquoi je ne créé des pages que en anglais. Vous avez vu le boulot que ça m'a pris, pour faire les choses biens. J'ai vraiment pas le courage de faire ça deux fois. Et puis je me dis que quelqu'un qui s'intéresse à un sujet aussi technique n'a de toute façon pas le choix de parler anglais dans le monde académico-industriel actuel. Donc je doute que créer les même articles en français ne servirait à rien.


[1] Il y a bien un livre au titre similaire plus récent, mais le livre ne possède pas de description sur Amazon. L'unique revue indique qu'il manque des pages. L'éditeur m'est inconnu. Et l'auteur n'a pas de page académique - même si DBLP lui attribue quelques publications - ce qui me fait assez peu confiance pour tenter l'aventure de lire ce livre.

[2] Pour moi, on découvre les maths, on ne les crée pas. Et les algorithmes et structures de données, surtout les purement fonctionnelles, sont des maths !

[3] Le vrai premier problème, c'est que sur ce blog et sur Wikipédia, la création de lien se fait comme ça texte et sur Wikipédia ça se fait comme ça: [lien] ce qui est très perturbant.

[4] En haut de chaque page Wikipédia se trouve un lien discussion, où l'on peut discuter du contenu de la page, signaler les problème et dire comment l'améliorer.

[5] En tout cas dans le monde purement fonctionnel.

[6] pas de lien car je n'ai pas fini d'écrire cet article.

[7] encore une fois, j'ignore quel mot utiliser en français. La traduction littérale en «clairsemé» me laisse des doutes.

[8] par exemple, «purely-functional» redirige vers «purely functional», mais là l'exception est simple à justifier.

jeudi 21 juillet 2016

Un magnifique théorème, contre-intuitif, d'informatique fondamentale

Je me demande si j'arriverai à vulgariser un théorème que j'aime beaucoup. Je tente avec le théorème d'Abiteboul-Vianu. J'essaye d'abord en blog, puis j'essayerai peut-être sur arbital plus tard, dont j'adore le principe[1].

Je vous ai déjà parlé de P et de NP. Pour rappel, on définit un problème comme une question à laquelle on aimerait pouvoir répondre par oui ou non en fonction de l'entrée. Par exemple, si la question est: «est-ce que le nombre est premier», alors on veut répondre OUI pour 17 et NON pour 18. Même si en vrai, l'entrée serai 10001 et 10010 puisqu'on travaillera en binaire sur un ordinateur.

On s'intéresse au temps, mais aussi à l'espace mémoire. La mémoire, c'est le disque dur - parce qu'au bout d'un certain moment tout ne tient pas en mémoire vive, et qu'il faut bien utiliser des supports à plus long termes. Encore une fois, la question est de savoir, quand l'entrée grandit, à quel vitesse grandissent nos besoins de stockages. Ce n'est pas pareil d'avoir besoin de compter les éléments, d'avoir besoin de recopier l'entrée, ou carrément de recopier tous les sous-ensemble possible des éléments donné en entrée. On parle de PSPACE quand l'espace utilisé est assez petit - i.e. borné par un polynôme en la taille de l'entrée.

Il faut remarquer que tout problème qui peut se résoudre en temps polynomial peut se résoudre en espace polynomial - c'est normal puisque on ne peut juste pas écrire beaucoup de truc en peu de temps. On ne sait par contre pas si le contraire est vrai, si tout ce qui est faisable en espace polynomial l'est en temps polynomial. En fait, ça serait même extrêmement surprenant que ça soit le cas, la communauté informatique est à peu près unanimement[2] persuadé que PSPACE est beaucoup plus gros que P. Sauf qu'elle n'a aussi aucune idée de comment le montrer.

Il y a quand même une chose qu'on sait, c'est qu'on peut «simplifier» le problème. En tout cas on peut en faire un problème purement mathématique. Purement logique pour être plus précis. Tout ce qui peut se faire en temps polynomial peut se définir à l'aide d'un point fixe inflationnaire. C'est à dire, on prend un ensemble S, qui commence vide, et on rajoute dedans des listes de nombre. Ces listes sont de tailles fixé, et les nombres sont entre 0 et la taille de l'entrée. On rajoute des listes de nombres dans S tant qu'on peut, suivant certaines règles. Et on s'arrête quand on ne peut plus rien rajouter. On peut alors dire que notre problème est satisfait par l'entrée si et seulement si 0,...,0 appartient à cette ensemble.

Les règles pour décider ce qu'on ajoute sont créés à partir des objets suivants, les trois prédicats:

  • x<y: qui est vrai si la valeur de x est inférieure à la valeur de y,
  • bit(x,y) qui est vrai si le xième bit de y est 1, et
  • B(x), qui est vrai si le xième bit de l'entrée est 1,
  • S(x1,...,xn) qui est vrai si, en ce moment, la liste x1,...,xn appartient à S\\

et puis les connecteurs:

  • ... et ...
  • ... ou ...,
  • non ...,
  • pour toute nombre x (entre 0 et la taille de l'entrée), on a...
  • il existe un nombre x (entre 0 et la taille de l'entrée), tel que ...,

Ces connecteurs sont ceux de la logique du premier ordre (first-order), on écrit donc que c'est «FO(B,bit,<)». Quand on dit que ces règles sont appliqué pour générer un ensemble par point-fixe inflationnaire (PFI), on note ça «FO(PFI)(B,bit,<)». Il faut remarquer que la règle qui s'applique pour rajouter des éléments petits à petits va donc dépendre de ce qui se trouve, à un instant donné, dans l'ensemble S. C'est pour ça qu'on peut avoir plusieurs étapes, il peut y avoir des éléments que la règle ne dit pas de rajouter au départ, et puis qu'elle dit de rajouter plus tard quand S a grossi.

En gros, l'idée de ces règles est que B permet de lire l'entrée, < permet de compter les éléments (histoire de savoir où on en est dans l'entrée), et bit permet de simuler une étape du calcul. Avec le point fixe, on simule les étapes du calculs jusqu'à ce qu'on finisse le calcul. Et on rajoute 0 dans l'ensemble si à la fin du calcul, l'ordinateur dit qu'il faut accepter. On a donc P=FO(PFI)(B,bit,<).

Le point fixe inflationnaire consiste à ne faire que rajouter des listes de nombres dans l'ensemble. On rajoute des listes de nombres à chaque étape, tant qu'une règle nous disait dans rajouter. On peut aussi considérer un point fixe partiel(PFP), où les règles peuvent aussi demander de retirer des éléments. Il faut juste qu'à un moment, on s'arrête; on ne rajoute rien et on ne retire rien. Et bien avec le point fixe partiel, on peut définir tous les problèmes qui peuvent se résoudre dans PSPACE. On a donc P=FO(PFP)(B,bit,<).

Le fait de ne rajouter des éléments sans les retirer nous forçait a avoir un nombre polynomial d'étape, puisqu'il existe un nombre polynomial de liste d'entiers. En effet la taille de la liste est fixé et que les nombres sont bornés par la tailles de l'entrée. Puisqu'on peut maintenant retirer des objets de l'ensemble, alors on n'est plus contraint par un nombre polynomial d'étape. On est quand même en espace polynomiale, puisqu'on peut représenter tout l'ensemble en espace polynomial.

Ce qu'on peut en conclure, c'est que P=PSPACE si et seulement si le point fixe inflationnaire est équivalent au point fixe partiel quand on a comme prédicats B, < et bit. Autrement dit, P=PSPACE si et seulement si FO(PFI)(B,bit,<)=FO(PFP)(B,bit,<).

Le théorème d'Abiteboul-Vianu indique que FO(PFI)(B,bit,<)=FO(PFP)(B,bit,<) si et seulement si FO(PFI)(B,bit)=FO(PFP)(B,bit).

Bon, ok, écrit comme ça, c'est pas forcément super impressionnant, j'ai supprimé le symbole inférieur des deux côté du signe égal. Voyons donc ce que ça signifie. Si vous vous souvenez de ce que j'ai écrit plus haut, ce symbole, <, c'est ce qui nous permet de regarder les lettres individuellement[3]. Par exemple, x vaut 0 si et seulement si, il n'existe pas de nombre plus petit que lui, formellement «non(il existe y. y<x)». C'est comme ça qu'on pourra poser des question comme «est-ce que le premier bit de l'entrée est un 0 ou un 1», ou encore, étant donné un bit de l'entrée, regarder son bit successeur. Sans ce prédicat, l'ordre n'a plus d'importance; c'est comme si vous deveniez incapable de distingue 17 de 71. On peut encore faire des calculs, mais pas vraiment de calculs intéressants. Donc c'est très contre intuitif de se dire que l'équation FO(PFI)(B,bit)=FO(PFP)(B,bit) ait seulement du sens. Ou plutôt, même si mathématiquement ça a un sens bien défini, c'est surprenant qu'on puisse en tirer quoi que ce soit.

D'un autre côté, se forcer à ce genre d'algorithme pourrait avoir de vrais avantages. L'ordre est indispensable en informatique pour au minimum une raison: quand on boucle sur la totalité des objets d'un ensemble, on boucle dessus dans un certain ordre. Parfois on peut paralléliser le calcul, et lancer le contenu de la boucle sur autant de processeurs différents qu'il y a d'éléments dans l'ensemble, mais en général ce n'est pas le cas. Et l'ordre peut avoir un effet pervers, par exemple, si c'est l'ordre alphabétique, et que le processus s'arrête durant la boucle, les gens dont le nom de famille est en A seront systématiquement traité, et ceux dont le nom de famille est en Z ne le seront pas. S'interdire ce genre d'ordre éviterait ce problème. Bon, j'ignore à quel point le problème se pose dans les calculs, mais c'est un vrai problème dans la vrai vie académique.

Bref, ce magnifique théorème veut dire qu'on pourrait répondre à l'importante question P=PSPACE, à la question «est-ce que le temps et l'espace, c'est à peu près la même chose en informatique», en décidant d'ignorer totalement la notion d'ordre. Ce qui n'a a priori aucun sens intuitif, aucune raison d'être vrai, mais qui l'est !


[1] Je crois que j'aime tout ce que fait Eliezer Yudowsky, l'auteur de Harry Potter et les méthodes de la rationalités.

[2] enfin, quand on considère les gens qui connaissent ce problème.

[3] Notons qu'il n'est pas possible de définir < à partir du prédicat BIT, sinon ce théorème serait trivial.

jeudi 24 octobre 2013

Import dvd, a file by chapter

My goal is to import a lot of dvd, one file by chapter, in the folder ~/dvd/TITLE_OF_THE_DVD/ . Here is a command line I wrote which seems to do it perfectly. One just had to add it to its bash file

alias dvd='title=$(lsdvd | grep "Disc Title" |sed "s+Disc Title: ++"); cd /dvd/$title/\1-\$chapter\" -t \1 -c \$chapter; done +g" > output; chmod u+x output ; ./output; eject ;'

And then use the command dvd when a dvd is in the reader.

Of course, sed, lsdvd and HandBrakeCLI must be installed and working. (Which in my case, is not the case with every dvd, for some reason that I do not understand), and /dev/sr0 should be replaced by the path to the dvd if its something else.

Oh, and if you wonder why I'm suddenly writting in english, it's only that I hope that google will index me, and help new people who search for this.

If you want an explanation, this command read the title thanks to lsdvd and then grep/sed. Then it also use lsdvd to read the list of title, and the number of chapter in each title, creating the command it will need to execute in the file output. Then it exececute and delete this file. In this file, for each title, there is a command looping for each chapter, extracting them one by one, in the file titlenumber-chapternumber, finally it deletes its temporary file and eject the dvd (which is REALLY important, because its the best way to let me know it has ended his task, as I'm not always looking at the terminal)

Of course, this is not 100% secure. If two dvd have the same title (can happen for a dvd and its bonus file, or a long film in two parts, or a dvd called "MYDVD") then the second dvd will overwrite the first one. Furthermore, if there is already a dvd/TITLE folder, with an output file containing line of code, then this file will be executed. Or if the title of the dvd contains a command doing bad things to your computer it may also be executed... But I hardly think that anyone will send me a dvd with such a title, so I keep this method.

jeudi 12 août 2010

commentaires de commentaires

C'est assez marrant les commentaires du blogs de lipton:

les méta-commentaires:

  • ceux qui disent: c'est exceptionnel de voire tant de chercheurs travailler ensemble sur le net, j'espère que c'est le futur de la recherche
  • ceux qui disent que l'auteur a fait preuve de trop d'assurance en disant "j'ai prouvé"
  • ceux qui disent: c'est atroce de voir tant de grand scientifiques perdre leur temps sur une preuve clairement fausse(et la réponse: s'ils sont intelligents peut-être qu'ils savent mieux que toi si ça vaut le coup de regarder ou non)
  • ceux qui disent: pourquoi ma preuve n'a pas reçu autant d'attention...(l'alternative étant: j'ai prouvé que tel théorème bien connu est faux)
  • et enfin les méta^2 commentaires: ceux qui disent que ce n'est pas le bon billet pour faire des méta-commentaire

mardi 10 août 2010

C'est la gloire !

Tu es certainement au courant si tu ne l'ignores pas, un papier déclarant prouver que P est différent de NP circule actuellement et semble pris au sérieux par beaucoup de chercheurs sérieux. Pour le moment personne ne semble déclarer le comprendre entièrement, et ce n'est certainement pas mon cas.

Cependant, il y a une partie qui est mon domaine à moi et où je pense que mon avis est pertinent... Et je suis très fier, car ce billet semble le confirmer(et avoir son nom au milieu de tant de vrai chercheur, c'est pas rien pour l'égo) ! (Par contre, il s'est gouré dans le nom de famille la deuxième fois... )

Bon, ça fait pas avancer ma recherche à moi tout ça... mais si le point fixe minimale (LFP) sur la logique du premier ordre joue un rôle si important dans cette preuve, je suis drôlement content d'avoir justement étendu LFP sur les logique d'ordre supérieure ! (2 ça existait déjà)... avec un peu de chance, ça pourra servir à étendre P<NP, la hiérarchie polynomiale, aux classes k-EXP, les hiérarchies exponentielles, une question laissé ouverte dans l'article.

Sinon, je suis aussi tombé sur slash dot sur des commentaires hilarant. En dehors des classiques P=NP ssi N=1 ou P=0, et moins classiques P!=NP si N=(P-1)!, celui que j'ai adoré (en espérant qu'il est pas sérieux), c'est soupçonner qu'HP a sorti ce papier maintenant pour couvrir l'affaire de scandale sexuel dans sa direction !

samedi 31 juillet 2010

Méthode scientifique !

Dans mes 48 pages d'article[1], je parle de ce qui s'appelle la hiérarchie arithmétique. En anglais Arithmetical hierarchy. Mon maitre de stage me demande de vérifier, car il pense que le "al" est de trop. Je lui dis que j'ai regardé dans wikipédia, mais n'ait pas prix le temps de consulter la litérature [2]. Il me dit que, dans ce cas, pour faire un choix, j'aurai du googler les deux écritures, et voir qui rendait le plus de résultat ! (Pour information, après consultation d'un livre par le créateur du sujet, j'ai eu raison !)

Dans le même genre, parlant de probabilité, il m'expliquait que, si on sait qu'on a que des faux négatifs, on peut augmenter la probabilité de ne pas se tromper (c'est simple: il suffit de refaire l'expérience plusieurs fois !), et le meilleur exemple qu'il m'ait donné, c'est le vaisseau dans Hitchiker's guide to the galaxy, qui est une preuve que ce système peut fonctionner !

Sinon, j'ai encore écrit sur wikipédia ! Bounded alternating turing machine et padding argument, en plus de quelques autres modifications mineures. Ça me fait donc mon 10ème nouvel article en anglais, et ma troisième modification non triviale ! En plus, j'ai pensé à toi, Typhon, j'ai pensé à ton commentaire sur un dernier billet, j'ai pensé à mettre en bas des "catégories".

Et là ça m'énerve, car j'ai quelques résultats qui seraient surement intéressant à mettre dans ces deux sections... J'espère qu'ils sont nouveaux (comme ça je pourrai les publier), mais dans ce cas j'ai un conflit d'intérêt. Et s'ils ne sont pas nouveau alors je ne trouve pas de référence ! (cf page de discussion de l'alternation limité, si vous êtes curieux)


[1] ok, il y aura surement qu'une partie restreinte qui deviendra peut-être un article, mais bon

[2] Oui, c'est comme ça qu'on appelle les articles et livres publiés, je pense qu'on ferait frémir les vrais élèves littéraires

mercredi 19 mai 2010

Linear-Logic rules in Latex

I'm writting a paper and I needed to write down the rules of Linear Logic. Since I guess it may help other people working on linear logic who may want to copy paste and see how to do linear logic sequent proof, I share the .tex document with the rules. It uses the packages bussproof to show proof-tree and cmll for linear logic symbols.

You can see the rule on this pdf.

Even I I'm sure some people will need it, I really wonder if this people will find this document... and if you are here because that is what you wanted, please leave a comment, I would be really impressed !

dimanche 28 mars 2010


Encore une bonne blague qui n'entrera pas dans le one-man-show.

Comme dit un linuxien qui partage une machine qu'il ne contrôle pas avec une personne qui fait n'importe quoi:

Si seulement j'avais su.

jeudi 25 mars 2010

Problème informatique humain

Ceux qui ne l'ignorent pas savent que je suis un Idiot[1] vu que j'ai un Iphone... Mais par ailleurs je n'utilise presque plus que Linux, ce qui empêche d'avoir itunes directement dessus.

Après avoir cherché à utiliser des logiciels libre comme Rhythbmox, j'ai décidé d'installer Itunes sur un windows, offert aux élèves de mon école par Microsoft, en virtualisant. Je partage mon dossier de musique entre mon ordinateur et l'OS virtualisé afin qu'Itune puisse accéder aux chansons.

Itunes a pour une raison quelconque et inconnu choisi d'importer qu'un sous-ensemble des dossier de "musique" ... Et je n'ai dans la librairie qu'une partie des chanteurs, et disons 1/6 des chansons.

En même temps, avec Itunes de chez Apple, sur un windows 7 de chez Microsoft, via une VirtualBox de chez Sun, tournant sur un Ubuntu de chez Canonical, j'ai pas la moindre idée de qui blamer [2]. Je me demande si ce n'est pas ça le plus frustrant !


[1] ce bon mot est copyright Typhon

[2] à part moi, mais c'est pas drole

dimanche 7 mars 2010

nerd, alors ?

I am nerdier than 78% of all people. Are you a nerd? Click here to take the Nerd Test, get geeky images and jokes, and talk on the nerd forum! says I'm a Cool Light-Weight Nerd.  Click here to take the Nerd Test, get geeky images and jokes, and write on the nerd forum!

jeudi 4 mars 2010

Mon prochain article

Bon, après maintes difficultés[1] mes recherches m'ont permis de découvrir le théorème suivant, soit un graphe avec deux nœuds s et t, si le nœud s est de degré 0 alors les propriétés suivantes sont équivalente:
il y a un chemin de s à t

Je ne divulgue pas la preuve, je ne voudrai pas qu'on me la pique tant que je ne suis pas publié.


Arthur Rainbow[2], qui devrait commencer à chercher un journal à qui envoyer ça, et ses lunettes aussi[3].

Edit du6 mars 2011, je ne comprend plus moi même ce que j'ai voulu dire le 4 mars 2010.


[1] on ne rigole pas

[2] Oui bizarrement, je n'ai pas envie de signer avec mon vrai nom.

[3] non, pas envoyer mes lunettes, mais les chercher, car j'ignore où elles sont. D'ailleurs tant que j'y suis, si vous les croisez, dites leur que je les cherche.

jeudi 25 février 2010


Bon, maintenant qu'on m'a bien montré que j'avais faux, je peux vous révéler la preuve, que j'avais mis dans cet article et vous pouvez vous moquez de moi !

(N'empêche que j'ai réussi à tromper au moins une personne en lui faisant croire qu'elle était juste)

Bon, pour colmater ma preuve, personne aurait un oracle E EXPtime-complet tel que P^E<>NP^E ? Ou une fonction g asymptotiquement plus grande que tout polynôme, et une classe de fonction F tel que la classe de problème C={c est décidable en temps O(f(n)) pour f dans F} possède un problème complet c sous poly-time-reduction, tel que pour toute fonction f dans F f(g(n)) est encore dans F ?

Si vous me donnez ça, sachez que je saurai être généreux dès que l'institut Clay m'aura donné mon million de dollars !

Arthur, qui retourne à ses monoïdes.

mercredi 24 février 2010

P est différent de NP

Ou alors j'ai une faute dans mon raisonnement. (Mais rassurez vous, si mon raisonnement est juste, vous serez certainement mis au courant !)

Arthur, qui aimerait bien, comme ses machines de Turing, disposer d'oracle, pour savoir ce que penseront les gens de mon raisonnement.

mardi 26 janvier 2010

Complexitée calculatoire

Je vais aller faire un stage dans un laboratoire de "(computational) complexity", ou en français complexité (calculatoire). En premier lieu, j'ai envie d'essayer d'expliquer de manière simple pourquoi je trouve ce sujet passionnant. L'explication sera peut-être un peu mystique, car je suis de ceux qui pensent qu'on découvre les mathématiques, mais qu'on ne les invente pas. Cela n'a pas forcément beaucoup d'importance.

Je vais vous donner un exemple à partir d'un problème classique en informatique, transposé dans la vie de tous les jours.

Vous invitez un tas d'amis à diner et pour l'occasion avez mis le couvert sur une grande table ronde. Vous avez plusieurs cercles d'amis qui ne se connaissent pas nécessairement tous entre eux, d'ailleurs vous avez envie de permettre à des gens de se découvrir et pour cela vous allez assignez des places à vos invités, avec un petit carton avec leur noms sur leurs assiettes de manière à ce que que toute personne soit assise entre deux personnes qu'elle ne connait pas. Eh bien, en supposant que vous savez exactement qui connait qui, le simple fait de savoir s'il est possible de placer tout le monde autour de la table de manière à respecter cette contrainte est, en général, extrêmement dur !

On appelle "Algorithme" une méthode qui permet de systématiquement résoudre un problème. Un algorithme peut être d'essayer toutes les manières possible de placer les gens autour de la table, et voir si il y en a une qui est correcte. Faire comme cela va prendre un temps exponentiel, c'est à dire que pour chaque invité supplémentaire, le temps de calcul va doubler ! Malheureusement, il n'existe pas (encore ?) d'algorithme fondamentalement meilleur, au point qu'on dit que celui qui saurait résoudre ce problème aurait à la fois le prix Turing et la médaille Fields, qui sont les équivalents des prix Nobel d'informatique et de mathématique respectivement.

On ne sait pas faire ça, mais on peut se poser tout un tas de question, en premier lieu, chercher dans quels cas particulier on sait faire le calcul facilement. Par exemple, si une personne connait tous le monde, il est évident que c'est raté. Si personne ne connait personne c'est évident: on place tout le monde n'importe comment ! Mais entre les deux, qu'est-ce qu'on peut dire ? Par exemple, si chaque personne ne connait pas plus que la moitié des personnes, on sait qu'il est toujours possible de placer les gens autour de la table, et on sait même trouver assez rapidement comment placer les gens, quand le nombre d'invité double, le temps qu'on met à chercher la solution est multiplié seulement par 25[1], ce qui est un net progrès par rapport au cas général. Mais on peut aussi réfléchir à d'autres moyens de calculer, je ne connais pas les réponses dans le cas général, et je ne crois pas qu'elles soient toutes connues:

-Et si je laissais les invités se débrouiller entre eux[2], est-ce qu'ils réussiraient rapidement, est-ce qu'il faudrait que tous parlent à tout le monde, ou est-ce qu'ils peuvent se débrouiller juste en parlant avec ceux avec qui ils sont amis/ne sont pas amis [3]?

-Et si je jetais les cartons aux hasard en espérant avoir un bon résultat [4], combien de fois je dois réessayer avant de me dire que ça doit être impossible ? Combien d'essai je dois faire avant d'avoir une chance sur deux d'avoir bon ?

-Si je demandais à un génie[5] de me donner la solution, est-ce que je pourrais vérifier rapidement qu'il ne s'est pas moqué de moi. Eh bien oui, il suffit qu'il nous dise comment mettre les cartons sur les assiettes et de vérifier qu'effectivement personne ne connait son voisin.

Enfin, on peut choisir de changer légèrement de problème:

-Et si je permettais à un petit nombre de personne de s'asseoir à coté d'un ami à lui ? Voir carrément de deux amis à lui ? A partir de quel nombre de personne le problème devient simple à résoudre ? 10 personnes ? la moitié des personnes ?

-Et si finalement je décide de faire que tout le monde connaisse ses deux voisins, est-ce que ça va être plus simple ? Eh bien non. C'est en fait exactement le même problème[6]

-Imaginez des villes sur une cartes, certaines relié par des routes: vous voulez allez dans toutes les villes une fois et une seule en empruntant les routes de votre carte, est-ce que c'est possible ? Vous allez me dire, qu'est-ce que ça a à voir ? Eh bien c'est exactement le même problème en imaginant que les villes sont des personnes et que les routes existent si et seulement si les deux villes au bout de la route ne se connaissent pas[7]. Plus généralement le but du jeu est de voir quand un problème est identique à un autre problème, ce qui nous dit que si on sait résoudre l'un rapidement, on sait aussi résoudre l'autre.

Enfin, et c'est peut être la question la plus fondamentale de la complexité, pourquoi diantre est-ce qu'on n'arrive pas à faire ce calcul rapidement ? Est-ce vraiment intrinsèquement difficile, la nature même du problème nous oblige-t-elle a y passer du temps, et n'y a t-il aucun moyen d'y arriver ou est-ce que simplement jusqu'à aujourd'hui les humains ont été trop bête ? On sait, mathématiquement, que certains problèmes ne peuvent pas être résolu rapidement, mais pour celui là on ne sait pas grand chose.

Là où ça nous embête, c'est que si on ne sait pas grand chose, on sait quand même que des centaines d'autres problèmes sont aussi difficile que celui là, c'est à dire que si vous savez résoudre un de ces problèmes, vous savez résoudre tous les autres et, inversement, si vous savez qu'il est impossible d'en résoudre un rapidement, vous savez automatiquement que les autres ne peuvent pas non plus être résolus rapidement.

Pour dire ça autrement, on ne sait pas si, quand on sait résoudre rapidement un problème avec un génie auquel on ne fait pas confiance[8], on sait toujours le résoudre efficacement sans génie ? On suppose que le génie est indispensable, mais on ne sait pas non plus le prouver, et c'est ce qui est à la fois très frustrant et fait tout l'intérêt, si je peu dire, de la complexité: le graal, c'est de se débarrasser d'un génie.


[1] En temps O(n^5) avec l'algorithme de Dhardwadker

[2] Algorithme parallèle, utilisé sur les ordinateurs multi-processeurs et par internet

[3] Dans le cadre de calculs sur internet, pour la vitesse du réseau, il est important d'éviter que tout le monde parle à tout le monde

[4] algorithme probabiliste, qui peut s'effectuer avec une pièce non truqué, un dés, etc... en général c'est assez efficace, mais qu'est-ce qu'un dé dans l'ordinateur ?

[5] Je ne rigole pas, on utilise beaucoup des génies, qu'on appelle "non déterminisme"

[6] En supposant que les gens qui se connaissaient ne se connaissent plus, mais connaissent maintenant les gens qu'ils ne connaissaient pas, on voit qu'on a affaire deux fois au même problème.

[7] Par contre, ne cherchez pas ce que serait la table ou le morceau de carton, ça n'a pas d'intérêt.

[8] On sait par contre que si on peut faire confiance au génie, on est vraiment beaucoup plus efficace, vu qu'on peut faire des choses qu'on ne pouvais pas faire avant, même avec un temps illimité, il suffit de dire à ce bon génie de tout faire pour nous !

lundi 18 janvier 2010


Comme le savent tous ceux qui ne l'ignorent pas, je vais bientôt m'en aller dans un laboratoire informatique d'un pays non francophone pour un stage de 6 mois. Mon choix s'est arrêté dans un laboratoire de complexité, et après intense discussion avec un camarade de classe, je sais enfin sur quoi je veux travailler:

Des classes de machines de Turing probabiliste, donc une exécution reconnait un langage avec une probabilité supérieure à 3/2.

Je suis persuadé qu'il n'y a jamais rien eu d'écrit la dessus, et que ça doit être une classe très simple. Je propose de lui donner ce nom: {}.

Arthur, qui mine de rien, en profite pour dire au revoir à certains, bientôt bonjour à un autre, et que le blog de toute façon traverse les frontières.

mercredi 13 janvier 2010

Nombre de chemin hamiltonien avec des noeuds distingués

Étrangement, cette liste de nombre ne semble pas se trouver dans l'encyclopédie de Sloane. Il est malheureusement impossible de proposer des suites actuellement, le temps que cela devienne un wiki, je vous propose donc les premières valeurs.

the number of hamiltonian graph of size 2 is 1
the number of hamiltonian graph of size 3 is 4
the number of hamiltonian graph of size 4 is 34
the number of hamiltonian graph of size 5 is 620
the number of hamiltonian graph of size 6 is 22906
the number of hamiltonian graph of size 7 is 1666987
Sachant que j'aurai un problème si il y a plus de 4294967295 graphes (la plus grande valeur des unsigned int)

L'algorithme est relativement simple: puisque chaque graphe hamiltonien possède possède un chemin de longueur N, pour toute permutation sigma de 0,N-1 je prend un graphe en mettant une arête entre sigma(i) et sigma(i+1) pour i<N-1. Ensuite, récursivement, pour toutes les arêtes, si elles ne sont pas dans le graphe, je les rajoutes ou non. Cela me donne nécessairement un graphe hamiltonien.

Bien sur un graphe qui a m chemins hamiltoniens sera généré m fois, donc pour éviter de compter plusieurs fois, je stocke tout les résultat dans une table de hashage. La table vérifiant l'égalité entre ses éléments, les graphes ne seront rajouté qu'une fois.

Le nombre de graphe hamiltonien sera donc le nombre d'élément de la table !

Cela nécessite d'énumérer toutes les permutations, ce qui semble se faire en O(n^(n+1))[1], et pour chacune des n! permutations, on génère tout en 2^O(n^2). Le temps de calcul est vraiment atroce ! Je suis donc encore à la recherche de moyen de l'améliorer. Par exemple, un algo pour les factoriel peut être exécuter en O(n n!) mais est plus dur et ne fournit pas un réel progrès.

Le code est ici compte.cpp, il doit être compilé avec -std=c0X car j'utilise des tables de hashage de la norme 0X. Il se compile sans problème avec g.

J'ai vérifié les 3 premières valeurs à la main, et elles sont bonnes, je suppose que mon algorithme est bon... Mine de rien, je suis sur ce code depuis dimanche (je n'ai pas fait que ça non plus).

Je mettrai les réponses suivante quand mon ordinateur me les auras craché. Pour le moment le calcul de la taille 8 ralentit trop mon ordinateur !


[1] Je n'ai pas trouvé d'algorithme plus rapide, si quelqu'un connait, je suis preneur

Droit des robots

Soit un membre du CNRS ou de l'INRIA a totalement débloqué, soit on est entré dans un univers de science-fiction et personne ne m'a prévenu. En effet, ces deux organismes préconisent la création d'un création d’un comité d’éthique sur la recherche dans les sciences et technologies du numérique.

Je cite:

Le groupe de travail ... a ainsi établi une cartographie des grands dossiers concernés : ... droits des robots

lundi 4 janvier 2010

Hasard sur en ligne

Pour choisir quelqu'un entre parmi un groupe de n personnes, attribuez un numéro à chaque personne (par exemple par ordre alphabétique) entre 0 et n-1.

Allez sur , choisissez un mot (pas nécessairement un vrai mot) et tapez le dans la première case, cliquez sur le bouton "Hash" et partagez le résultat de la ligne MD5 avec tout les joueurs sans avoir moyen de l'altérer[1].

Une fois que tout les joueurs ont notés le résultat, révélez le mot que vous aviez choisi. Comme le hash est publié, il est pratiquement impossible que vous mentiez ! Et les autres peuvent vérifier que vous n'avez pas menti en allant sur hash online et en essayant d'hasher votre mot.

Une fois que tous les mots sont connus, faite un très grand mot en mettant les mots cote à cotes dans l'ordre de vos numéros. (Par exemple si le joueur 0 a le mot "glace" et que le joueur 1 à le mot "chien" faites "glacechien"), et hasher le résultat. Cette fois, pour plus de faciliter, prenez le résultat de la ligne "adler-32", et tapez dans google 0xADLERRESULT%n où ADLERRESULT est le résultat donné par adler, et n est le nombre de participant. Google calculatrice vous rend alors le numéro du gagnant !


[1] par exemple un email, ou un commentaire sur un blog que vous ne pouvez pas éditer

- page 1 de 2