samedi 10 juillet 2010

Fin d'article

Voilà, j'ai écrit mon premier vrai article avec des vrai résultats nouveaux et de la vraie recherche dedans !

Une caractérisation logique des programmes prenant un temps/un espace mémoire borné par une tour d'exponentiel de hauteur donnée [1]; et par extension, ceux borné par des tours d'exponentiels de hauteur quelconque. Par ailleurs, une simplification d'un formalisme, et la preuve que en gros, ça ne présente aucun intérêt [2].

Comme conclusion, j'ai envie de dire que c'est étonnant le temps que ça prend d'écrire 24 pages; 2 semaines ! Alors que la plupart des preuves sont [facile][3], et que dès que je me suis posé la question, j'ai vu rapidement quel serait la preuve. Moins de 2 pages par jour, c'est pas spécialement rapide.

Si vous êtes curieux, le document (avant relecture par mon maitre de stage) est [ici]. Amusez vous bien !

--

Arthur, qui ne sait plus quoi faire, maintenant que ce qui l'a occupé pendant 2 semaine entière est fini.

Notes

[1] Une extension de [High Order], article que j'ai rédigé sur wikipédia

[2] Variable-Order (pas de lien, je ne veux pas faire d'article wikipédia sur un truc si inutile) est égal à la [Hiérarchie Arithmétique]

[3] selon ma définition personnelle de [facile]

mercredi 7 juillet 2010

Travail

Pour vous donner une idée: je lis un théorème T et j'ai un problème pour comprendre la démonstration... (L'horreur des passages: "il est clair que P", où je me sens idiot car pour moi P n'est pas évident du tout). Je laisse tomber. Quelques temps plus tard je tombe sur un article A indiquant que le théorème T est faux et donnant une preuve par l'absurde, montrant que si T était vrai alors on aboutissait à une contradiction. Je lis A et suis surpris; malheureusement je n'ai pas les notions pour comprendre la démonstration de cet article, et surtout il n'indique pas quel est la partie de la preuve de T qui est fausse (Bravo, il a démontré que les mathématique sont inconsistante !)

Après renseignement cet article A est connu par les gens du milieu comme étant faux, et ne devrait plus être en ligne, curieux je retente de comprendre la preuve de T, et je bloque sur P, que je ne comprend toujours pas, et finalement je prouve que P est faux en donnant un contre exemple.

Donc on a un ex-théorème T qu'on pensait vrai, mais dont la démonstration est fausse, comme ça avait été indiqué par l'article A, dont la démonstration était fausse (aussi) mais le résultat potentiellement juste.

Sans aucun rapport, je ne sais pas comment elle survit, ça fait une semaine que j'ai une coccinelle qui vole autour de la lampe de ma chambre. (L'autre question étant: comment tout ces insectes rentrent t-il malgré la moustiquaire !)

samedi 5 juin 2010

Comment j'occupes mon temps de libre

Je savais pas trop quoi faire là, alors j'ai rédigé ça, un draft pour peut-être un futur article wikipédia (anglais) sur les [graphes de configuration].

Bon, faut vraiment que j'arrête de procrastiner moi.

jeudi 3 juin 2010

De l'utilité des mathématiques pour les mathématique

On dit souvent que la recherche ne doit pas avoir un but, car on ne trouve jamais ce qu'on cherche explicitement, et que les plus grandes découvertes ont été faites par hasard.

J'aimerai rajouter une contraposée à cette affirmation, l'avantage des maths, c'est que ça permet d'être sur que ce qu'on fait sert à rien alors que dans les autres matières on ne fait que le supposer. Attention, même les maths qu'on pense inutiles peuvent un jour servir, l'exemple canonique étant la théorie des nombres, qui n'était qu'un jeu pour mathématicien et qui a commencé à vraiment servir qu'avec l'informatique. Moi je parle d'une vrai preuve mathématique d'inutilité.

Eh bien, grâce à ça, je sais désormais que mon travail de ces trois dernière semaine ne servira à rien ! MAIS JE LE SAIS MATHÉMATIQUEMENT ! :D


Pour ceux qui veulent plus de détail, je dirai juste que, si en première approximation on dit que la complexité est une droite où on peut classer les langages, avec le plus simple tout à gauche de la droite sur le 0, puis de plus en plus complexe quand on va vers la droite, la question qui se pose est de positionner différent langage.

A partir de deux langages, FO et MALL déjà bien étudié, j'ai créé une extension FO-MALL, et je savais que FO-MALL était à gauche de MALL, puis j'ai montré qu'il était à droite de FO (donc qu'il était plus complexe que FO mais pas plus complexe que MALL)... Et aujourd'hui j'ai montré que FO-MALL était exactement à la même place que MALL... donc que l'extension ne sert à rien car la complexité est exactement la même...

Je sais pas si je dois rire ou pleure, ni ce que je fais de mon pdf de trente pages, mais bon... au moins c'était marrant.

Arthur qui aime bien faire de la "recherche" mais pas tout le temps.

dimanche 30 mai 2010

Automates à compteurs fuyant

Un "automate" en théorie, c'est une machine avec des compteurs/variable(au moins 2) qui contiennent un nombre quelconque, disons les compteurs A et B. On a le droit de faire des truc comme "copier A dans B", "augmenter A", "diminuer A" et "Si A=0 faire ceci sinon cela". Des truc très bien défini qui permettent de simuler tout ce qu'un ordinateur peut faire comme calcul. (En plus on a une instruction "accepter" et une "refuser" mais c'est pour la fin du programme)

Et bien pour mon travail, je défini un autre type d'automate qui ressemble, avec des instructions comme "copier A dans B, mais pas totalement et on peut avoir B plus petit que A après, voir même B=0 si ça nous amuse" et "Si A=0 alors fait ceci, sinon fais 'cela' sauf si tu préfères faire 'ceci' ce que tu peux faire si tu veux"... Et ça m'énerve, je ne trouve aucune information sur ce genre de machine dans les articles que je lis ! Non mais c'est vrai, pourquoi personne il a fait des machines aussi bien définie et naturelle que mes nouveaux automates ?


Edit: il semble qu'il était connue que les automates non-déterministes que j'ai trouvée sont équivalents aux réseaux de pétri.

vendredi 28 mai 2010

Beaucoup de variable

Pour mon travail de recherche je devais faire un preuve, au début j'ai tenté une induction sur le produit cartésien de 10 variables entières, toutes utiles, et j'ai galéré pour trouver l'ordre exacte de la récursion.

Je suis content d'en être venu à bout et finalement ça ne prend que 8 variable et une aspirine.

Sinon, je peux aussi vous dire que en logique linéaire descriptive[1] on additionne grâce au connecteurs multiplicatif, et on monte au carré grâce aux connecteurs additifs, alors que les connecteurs exponentiels semblent ne servir à rien. Je pense donc de plus en plus que les logiciens sont cinglés. [2].

J'en profite pour vous proposez une blague, il est bien connu qu'en logique classique il est impossible de compter, ce qui explique qu'on ne puisse exprimer la parité et la majorité en logique classique. Or il semble que l'administration ne sache faire que ça, compter; ça prouve bien que les gens de l'administration n'ont pas une logique classique !

Notes

[1] googlez pas, c'est moi qui ait inventé le terme à défaut de mieux

[2] J'en veux pour preuve un texte écrit par l'inventeur de la logique linéaire, les montre à moutarde, et que Lewis Caroll, l'auteur d'Alice au pays des merveilles était logicien.

mardi 18 mai 2010

Comment gagner un tournoi

J'avais envie de vous soumettre une idée géniale, sous entendu dans un article de l'excellent blog computational complexity qui permet de facilement gagner les tournois quand vous recevez chez vous.

Si vous recevez dans votre pays et avez peur de perdre, contester aux joueur le fait qu'ils ont régulièrement le droit d'être présent dans votre état, gagner sur un terrain un peu vide, c'est quand même bien plus simple !




Parlant de complexité, j'ai enfin un nouveau résultat (je ne garanti pas qu'il soit intéressant, même pour un informaticien, ni même pour un théoriste), mais chut, c'est secret, je vous donne pas le résultat, vous pourriez peut-être me le piquer et en faire... Bon, je sais pas ce qu'on peut en faire, mais c'est une autre question.

La question subsidiaire sera, ai-je le droit de dire ma preuve "après y avoir bien réfléchi je suis sur qu'il est évident que c'est trivial que c'est vrai, mais ça demande peut-être un peu de réflexion" ?"

mercredi 5 mai 2010

Complexité descriptive dans le zoo

Dans mon domaine, si on a pas une super mémoire il existe un Zoo, où l'on peut aller admirer tout un tas de classes de complexité et où des zoologiste ont bien expliqué comment tout ce petit monde se comporte dans la nature.

Cependant, pour des raisons obscures, toute une famille était oublié, et c'est celle sur laquelle je travaille actuellement ! Je viens donc d'offrir au zoo une description de chacune de ses classes, tout du moins de celles que je connais moi même.

Si des gens sont curieux de savoir ce que je fais actuellement, cela concerne beaucoup les classes logiques (si vous savez ce que signifient (et, ou, non, implique, pour tout et il existe, vous êtes bien parti) et les rapport avec la complexité (si vous savez ce qu'est la mesure du temps/de l'espace d'un algorithme c'est mieux), il y a donc à la base le premier ordre FO (suivie de toutes les classes du nom FO(...), ensuite il y a le second ordre SO (avec encore une fois ces variantes et restrictions).

Sans aucun rapport avec la logique, il y a aussi une rapide description du langage de programmation WHILE qui avec certaines restriction décrit tout langages en temps polynomiale/espace logarithmique (avec le petit coté marrant que un programme WHILE ne prendra jamais un temps polynomiale mais peut TOUJOURS se transformer en un tel programme dans un autre langage)

samedi 1 mai 2010

Théorie Milchior

Après plus de 2 mois de recherche, je peux vous livrer mes premières conclusions expérimentales, composé d'une théorie simple, d'une exception à la règle et d'un corollaire:

Théorie 1: Quand on prouve un théorème, il y a forcément une faute dans la preuve.

Exception 1: Quand le théorème est juste il était déjà connu depuis plus de 10 ans.

Corollaire 1: Il est passionnant de travailler dans un domaine où personne n'a jamais travaillé, c'est moins bien de découvrir pourquoi personne n'a jamais publié sur ce domaine.

mercredi 9 septembre 2009

Rapport de stage

Comme je suis de nature généreuse, et que je pense que mon rapport de stage pourrait intéresser d'autre personnes ayant besoin de faire du matching modulo égalité incrémentale, typé[1] purement fonctionnels, je vous indique que ce rapport est librement accessible ici.

Sur ce, je vous souhaite une bonne nuit.

Notes

[1] avec des types polymorphes

vendredi 21 août 2009

Petite question intéressé

Je vous explique le problème.

J'ai mis le réveil à 8 heures, je prévois de partir de la maison pour aller au boulot stage.

A une heure du mat, j'ai tenté de me coucher, mais ne trouvant pas le sommeil, à 4 heure je me suis relevé.

Là il est 7h30, mon réveil sonne dans une demi heure, je commence à avoir envie de dormir, et je vais être incapable de travailler de la journée(alors que j'ai bien avancé durant la nuit[1]).

Je suis sensé faire quoi? SVP, réponse rapide nécessaire. Parce qu

Notes

[1] J'ai enfin eu un teste important, notre programme passe de 35 minutes à 21 minutes grâce à l'amélioration que j'améliore, yeah!

mercredi 19 août 2009

Programmation tolkienesque.

Dans le code que j'écris actuellement, j'utilise un arbre paresseux[1], vous pensez que si je l'appelle sylverbarbe ça fera rire quelqu'un?

N'empêche, ça fait parti de ces structures de donnée qui me font comprendre pourquoi les geeks aiment la fantasy!

Notes

[1] Si, si, c'est une structure de donnée qui existe vraiment, c'est simplement un arbre, dont les branches sont créé de manière paresseuse.

dimanche 26 juillet 2009

Abscence

Je voulais juste vous prévenir que je serai absent quelque temps.

En effet, mon programme bug parfois, de manière aléatoire, sur de gros exemple. J'ai actuellement un fichier de log de 36031 linges à parcourir.

Je devrai avoir fini d'ici 2011, 2050 au plus tard.

A la prochaine

jeudi 16 juillet 2009

Essaye cette méthode

Maitre de stage: Pour le moment, pour résoudre le problème P, on utilise la méthode A qui est simple. On sait que la méthode B est meilleure, alors écris nous le code de B et on l'utilisera.

Un mois et demi plus tard, moi: voilà B.
Maitre de stage:Ok, sinon on se disait, peut-être qu'on pourrait utiliser la méthode C. La méthode C sert à résoudre le problème Q, mais c'est globalement pareil, sauf ces trois points. En fait, les utilisateurs des méthodes B et C sont dans des laboratoires qui font des choses assez différente, donc je pense que personne n'a essayé la méthode C pour résoudre le problème A.

Une semaine plus tard, moi: Après avoir bien étudié la méthode C, j'ai envie de dire qu'on ne l'utilise pas, car le problème Q n'a rien à voir avec le problème P. Ca se ressemble sauf que c'est exactement le contraire.
Maitre de stage: Ce n'est pas assez précis, si on essayait de le faire quand même, qu'est-ce qu'on obtiendrait.
Moi: Si on a de la chance, la réponse au problème Q, sinon rien. Peut-être que dans certains cas, par chance, ce sera une réponse au problème P.
Maitre de stage: mais encore?
Moi: euh...
Maitre de stage:Etudie ça et dis moi quand tu sauras exactement.


Souhaitez moi bonne chance, je crains d'avoir du mal à faire mon nouveau boulot.

dimanche 3 mai 2009

Les vacances d'été

C'est sur, pour les vacances d'été, je quitte Paris.

Je vais les passer à l'INRIA de Saclay, et comme je suis gentil, je vous donne même l'image sur google map.

Et dire qu'il y en a qui doivent rester chez eux tout l'été. Je suis vraiment chanceux.