vendredi 23 juillet 2021

Conseiller des jeunes étudiant·e·s en informatique

Des étudiants en informatiques, contributeur à AnkiDroid, m'ont demandés des conseils. Sans préciser de sujet, mais j'imaginai, vu le context, que c'était en rapport avec le fait d'être développeur professionellement. J'imagine que, ayant été engagé par deux GAFAM, j'obtiens un bonus crédibilité et c'est effrayant, parce que je n'ai aucune idée. Je peux répéter les conseils que j'ai reçu et ignore s'ils sont bons

Lire la suite...

mardi 19 février 2019

Expliquer l'open-source au moment Meurice

Au Paris Open Source Summit, j'ai croisé Guillaume Meurice. Un humoriste, qui s'est fait connaître en étant chroniqueur au Coq des bruyères(connaître de moi, j'entend), puis sur France Inter dans l'émission Par Jupiter (connu du grand public ici). Dans ses chronique, il interview des gens, personnage public ou non, tente avec beaucoup de mauvaise foi de trouver des contradiction, garde des petits extraits de phrase et rigole avec ses comparses. Bon, dis comme ça, ça a pas l'air top, mais en réalité, j'aime beaucoup.

J'ai donc réfléchi à ce que je dirai si je devais expliquer ma présence au salon. En essayant de trouver un truc qui soit assez cours pour son micro, et qui sonne bien vu le style de pensée qu'il défend.

Lire la suite...

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.

Lire la suite...

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.

Lire la suite...

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

Note

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

Lire la suite...

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)

Notes

[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

su

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 !

Notes

[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! NerdTests.com 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
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.

Notes

[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

NP=?P

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.

Notes

[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

Complexité

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 !

Note

[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

- page 1 de 2