Random Thoughts

Après une explication rapide sur les enjeux de la décidabilité, j'ai jugé intéressant de parler de quelques classes de complexité. La plupart d'entre vous a sûrement déjà entendu parler de "NP-complet", mais tout le monde ne sait pas forcément ce que c'est. Ce qu'il faut savoir :

Classes de complexité

• Les problèmes dits simples ont des solutions qui s'éxécutent en temps polynomial : ils appartiennent à la classe P. Cette classe regroupe la plus grande partie des problèmes traités aujourd'hui par l'informatique. Exemples :
  • Un produit de matrice se fait en O(n^x), x compris entre 2 et 3.
  • Un tri rapide s'exécute en O(n log(n)).
  • Les algorithmes les plus efficaces en terme de traduction se font en O(n^5) (à base de Tree-adjoining grammar).
• Il existe des problèmes dit "exponentiels" : le meilleur algorithme existant possible est exponentiel. Rien à faire, dès que l'entrée dépasse une taille de 10, il n'est pas possible d'avoir un algorithme praticable en raison de l'explosion combinatoire. Exemple : IA d'un jeu d'échec, Go, etc.

Une classe particulière : la classe NP

C'est entre ces deux classes de problèmes que se situe la classe NP. Les problèmes de cette classe ont tous la même caractéristique : il est possible de vérifier une solution donnée à un problème de la classe NP en temps polynomial. Par exemple, on peut vérifier facilement que le résultat d'un tri est correct : on regarde si notre tableau est trié (O(n)), donc P est inclus dans NP. Il existe cependant des problèmes qui sont dans NP mais dont on n'a pas prouvé l'appartenance à P. Ces problèmes sont les problèmes NP-complets.

Problèmes NP-complets

Les problèmes NP-complets sont concrètement les problèmes les plus durs de la classe NP, et sont tous équivalents. Il est possible de démontrer que le problème SAT est NP-complet (je sais pas faire), et de montrer son équivalence à d'autres problèmes (plus facile). Par exemple, 3-SAT est équivalent. On peut de la même manière réduire le problème 3-SAT à un problème de coloration de graphe, etc.

Une rapide liste de problèmes équivalents :

• génération d'emploi du temps ;
• problème du voyageur de commerce ;
• problème du sac à dos ;
• problème de la clique (applicable aux réseaux sociaux)...

L'astuce pour savoir si un problème donné est NP-complet est assez simple : si la seule possibilité c'est de tester toutes les possibilités, et de recenser les possibilités correctes, le problème est certainement NP-complet. (Il est assez facile de savoir si une possibilité est valide grâce à la propriété principale de la classe NP : elle se fait en temps polynomial.) On peut ensuite chercher une complexité plus précise, par exemple, générer un emploi du temps consiste à placer k cours dans n créneaux. La solution connue la plus efficace est exponentielle, mais on peut vérifier une solution en temps exponentiel : c'est ce qui fait du problème un problème NP-complet.

P = NP ?

Le problème « P = NP » peut être considéré comme le problème le plus important qui reste non résolu en informatique. On sait que P est inclus dans NP, mais on ne sait pas si NP est inclus dans la classe des problèmes exponentiels ou dans la classe des problèmes polynomiaux. Millenium propose un million de dollars à la personne qui saura résoudre ce problème. :)

Pour montrer P = NP, il suffit de montrer que les problèmes NP-complets sont polynomiaux : ce sont les plus durs de NP, donc si ils sont P, NP = P. Pour montrer que les problèmes NP-complets sont dans P, il suffit de montrer qu'un seul de ces problèmes a une solution polynomiale, étant donné qu'ils sont tous équivalents. Personne n'a réussi jusque là. :)

Complexité en temps, en espace ?

Le dernier point que vous pouvez vouloir retenir est que la complexité peut s'exprimer de deux manières : en temps, et en espace. Je n'ai parlé ici que de la complexité en temps, pour une raison simple : un problème qui a une complexité donnée en temps ne pourra pas avoir une complexité pire en espace. Intuitivement, dans un temps donné, on ne peut pas toucher à une infinité de cases mémoires.

Comme d'habitude, n'hésitez pas à réagir sur Buzzerl. :) J'envisage de proposer à bluestorm d'ajouter au tutoriel d'algo sur le sdz une adapation de ce sujet, dans mon souvenir ce n'est pas dans le plan.

Le problème de l'arrêt est un problème classique en décidabilité. Il fait partie des problèmes qui n'ont pas de solution : il est impossible d'écrire un algorithme qui résoud ce problème. La plupart des autres problèmes indécidables reviennent à ce problème. On les montres d'ailleurs par diagonalisation : on montre qu'ils reviennent à résoudre le problème de l'arrêt, et donc qu'ils sont indécidables.

Qu'est-ce qu'un problème décidable ? C'est un problème pour lequel, pour toute entrée, on peut répondre en temps fini au problème par oui ou par non : décider si l'entrée correspond.

Le problème de l'arrêt consiste à prendre en entrée un algorithme, et déterminer si cet algorithme s'arrête ou non (pas de boucle infinie). Sa formalisation se fait dans les machines de Turing, mais le résultat vaut aussi dans un langage qui ne comporterait que des conditions, des boucles, et des affectations, et c'est équivalent à tous les langages que vous utilisez actuellement, nos machines n'étant pas grand chose de plus que de machines de Turing à n bandes.

Démonstration

Je vais donc programmer en C pour montrer que ce n'est pas possible d'écrire un programme qui résoud le problème de l'arrêt. On suppose que le problème est décidable. Il est donc possible d'écrire une fonction halt(), sans perte de généralité.

int zero()            int loop()
{                     {
  return 0;               while (true);
}                         return 0;
                      }
int weird()
{
  if (halt(weird)
    return loop();
  else
    return zero();
}

• Si halt(weird) retourne vrai alors weird() retourne loop() (contradiction)
• Si halt(weird) retourne faux alors weird() retourne zero() (contradiction)

Donc on ne peut pas écrire une fonction halt(), donc le problème de l'arrêt est bien indécidable.

Théorème de Rice

On peut généraliser ce problème au théorème de Rice qui dit qu'il n'est pas possible de déterminer une propriété non triviale d'un algorithme. Une propriété est une caractéristique d'un algorithme. Exemples : "Il calcule la racine carrée de son entrée", "Il ne s'arrête pas". Elle doit être non triviale : ne pas être vraie pour tous les algorithmes, ou fausse pour tous les algorithmes.

Je reprendrai ici la preuve (la non formelle) présente sur wikipedia. On suppose qu'on a un algorithme qui examine un programme quelconque, et qui sait dire si ce problème calcule bien le carré de son entrée. Voici un exemple de programme de calcul de carré :

int carre(n) { a(i); return n*n; }

a et i sont une fonction et une entrée quelconque. a peut s'arrêter sur i, ou pas. carre est donc seulement une fonction qui calcule le carré d'une fonction si a ne s'arrête pas. Si on pouvait savoir ça, on saurait résoudre le problème de l'arrêt.

Donc, il est impossible d'obtenir une propriété sur un algorithme. En particulier, on ne peut pas :

• Savoir si ce programme s'arrête
• Savoir si c'est un virus (il est donc impossible d'écrire un antivirus infaillible)

Un peu plus de formalisation ?

Ces résultats peuvent être démontrés formellement en utilisant les machines de Turing universelles. Le principe est d'utiliser un codage sous forme de 0 et de 1 pour coder un algorithme et son entrée. On écrit ensuite une machine de Turing qui sait lire ce codage, et on peut raisonner dessus.

Wikipedia (plutôt la version anglaise) dispose d'articles qui montrent ça bien. Je peux vous passer les slides que j'ai eu en cours si vous voulez, aussi.

Ce billet est là pour raconter rapidement comment on peut faire du web en Java. Je ne recommande ça à personne, c'est simplement que j'aurais été curieux de savoir comment ça marchait avant. C'est quelque chose qui est apparement pas mal utilisé en entreprise tout ça.

L'avantage principal que ces entreprises doivent justement y voir, c'est le fait qu'à chaque livrable, il suffit de donner au client un simple fichier (un .war) qui contient tout le code du site, les librairies utiles, etc. Le client n'a plus qu'à déployer le fichier .war chez lui, et paf, tout marche comme par magie, donc il est content. Le fournisseur n'a pas besoin de montrer les sources ni de s'occuper de l'installation, donc il est content. Et voilà, tout le monde est content, et on obtient un truc qui est pas mal utilisé.

Le client et le développeur n'ont qu'à avoir un conteneur Java EE, "Tomcat" par exemple, qui s'occupe des détails. Dans la pratique, un .war c'est simplement des dossiers agencés selon une organisation particulière, et le tout zippé.

Au niveau de code, de base quand une requête est envoyée, le conteneur la redirige vers le bon projet puis vers la bonne "servlet". Concrètement une servlet c'est un controlleur : c'est là que sont envoyées les requêtes, il faut implémenter doGet(request, response) et doPost(request, response) pour jouer avec. On peut ensuite coder en Java pur, en écrivant la réponse directement depuis le Java, ou alors en passant par une vue.

Au fur et à mesure des versions (comme d'habitude en Java) ont été greffés par dessus le tout des nouveaux trucs pour que des non codeurs puissent mettre des boucles dans les vues (un langage de template particulièrement verbeux en XML), puis des nouveaux frameworks sont nés, Spring, Roo, tous plus géniaux les uns que les autres.

Aucun intérêt à en faire tout seul ceci dit.

Désolé pour le ton un peu con, ceci est un recyclage d'un mail auquel on ne m'a jamais répondu. :)

Imaginez deux programmeurs affamés, assoifés, luisant de sueur, ayant fini leur dernier paquet de Duo Keks. Il est 2h30 du matin, ils viennent de se réveiller, la nuit va être longue. Pour survivre à cette épreuve, ils décident de lever une assemblée générale !

Ils ont un problème à résoudre, et ne peuvent le résoudre qu'ensemble. L'un est expert en droites, l'autre en assemblage de traits. Ils se retrouvent donc devant un frigo, armés de l'instrument le plus adéquat qui soit : un marqueur, et ont besoin de dessiner un carré. Ils se retrouvent obligés de collaborer pour réussir, tout ça.

Ils viennent d'inventer le pattern frigo ! Dans la littérature ça s'appelle une "blackboard architecture". Le principe est d'avoir un certain nombre d'entités travailler sur un même espace de travaille. La plupart des entités voient des demandes, regardent comment elles peuvent découper le travail, puis écrivent d'autres demandes sur l'espace de travail.

Par exemple, vous pouvez avoir dix soldats, deux chefs d'équipes, un colonel. Chacune de ces entités est experte dans son domaine, et résoud les problèmes qu'on lui donne efficacement (tuer, communiquer, trouver une stratégie). Les chefs d'équipes vont suivre la stratégie du colonel, et les soldats vont écouter leur chef d'équipe. Dans un jeu vidéo, on a différents sous-systèmes, l'intelligence artificielle, le système de navigation, le moteur physique, etc. Chaque système va demander des choses sous formes d'assertions, et les autres vont remplacer par d'autres assertions jusqu'à répondre.

Attention, ce n'est pas de la logique des prédicats avec résolution SLD (enfin du prolog quoi) ! C'est beaucoup plus extensible et permissif (et moins formel aussi). Les experts peuvent être des threads indépendants qui vivent leur vie avant d'aller voir l'espace de travail, on peut aller en avant, en arrière, et on peut avoir plusieurs stratégies possibles en même temps. C'est suffisament intéressant et extensible pour jouer avec dans un certain nombre de situations.

Cette réaction ne traite qu'une petite partie d'une thèse qui concerne la définition de l'intelligence. L'intelligence est historiquement divisée en un certain nombre d'aspects. Ça peut être la compréhension du langage naturelle, l'aisance avec une langue, la mémoire associative, le raisonnement abstrait, etc. Il existe même un modèle qui sépare l'intelligence en 120 parties différentes. Il parait cependant difficile d'évaluer chacune de ces parties.

L'auteur continue ensuite en traitant spécifiquement l'intelligence humaine en citant un certain nombre de définitions et aboutit à une définition que je vais essayer de traduire : « L'intelligence mesure la capacité qu'a un agent de réaliser ses objectifs dans un grand nombre d'environnements ». En continuant plus loin, j'ai eu l'impression de retrouver deux grandes définitions (un peu plus satisfaisantes) de l'intelligence :

1. La capacité à résoudre des problèmes.
2. La capacité à apprendre.

Ces mots sont les miens et ne recouvrent pas toutes les nuances apportées par le papier. Cependant, ça permet d'avoir une idée, et de savoir si vous avez envie de lire ce papier.

L'avantage de la première définition, c'est qu'elle est mesurable facilement, et c'est d'ailleurs ce qui est fait dans tous les tests de QI existants : on donne beaucoup de problèmes à quelqu'un, et on regarde le nombre de problèmes qu'il est capable de résoudre. Le plus gros problème de cette définition est que quelqu'un qui a déjà vu le test, ou à qui on a appris des méthodes pour résoudre les problèmes donnés sera plus intelligent. Est-ce que les notes données à l'école permettent de montrer une certaine intelligence ? Certainement pas, et pourtant c'est le raisonnement implicite qui est fait.

La seconde définition est là pour pallier à ce problème. Elle considère que quelqu'un qui peut apprendre à apprendre, qui est capable d'être capable est intelligent. C'est beaucoup plus satisfaisant. L'intelligence n'est plus une fonction du travail, mais est aussi quelque chose que l'on ne peut pas finalement palper, visualiser. C'est aussi très rassurant, et c'est un discours que j'ai beaucoup entendu : c'est pas parce que d'autres ont des meilleurs notes que toi ou réussisent mieux que toi qu'ils sont plus intelligents. Peut-on pour autant considérer un enfant très prometteur comme plus intelligent qu'un adulte qui a développé un certain nombre de compétences au fil des années ? Ne doit-on pas aussi attacher de l'importance à la capacité à résoudre des problèmes tout de suite ? La première définition a alors du sens.

"Intelligence is what is measured by intelligence tests." Boring (1923)

Cette définition facétieuse en apparence exprime le fait que l'intelligence, ce n'est rien de particulier, mais une capacité abstraite qui affecte les performances d'un grand nombre de tâches, ce qui est là où les tests d'intelligences prennent du sens lorsqu'ils sont bien conçus. Cette définition met aussi en évidence que l'intelligence et la mesure de l'intelligence sont liées.

En ce qui concerne les machines, on considère ici les machines de Turing simplement. Il faut greffer aux problèmes vu au-dessus la question de la performance. Il est inutile d'avoir une machine qui a besoin d'une mémoire infinie et d'un temps infini. L'auteur, en tant que bon chercheur, précise cependant qu'il ne faut pas trop se focaliser sur les performances, des fois qu'on changerait de modèle de machine (pour passer de Turing à l'ordinateur quantique par exemple).

N'hésitez pas à aller voir la thèse en question pour plus d'approfondissement, c'est assez facile à lire, au moins au début. :)

Si vous avez déjà utilisé un "Vanilla" Gnome, vous aviez peut-être remarqué que Nautilus ouvre une nouvelle fenêtre à chaque fois que vous voulez ouvrir un nouveau dossier. C'est quelque chose de complètement horrible à utiliser mais cependant justifié d'un point de vue ergonomique.

C'est en fait la bataille entre deux "métaphores" utilisés pour de telles GUIs. La première, la métaphore orienté objet, consiste à considérer chaque fichier, chaque dossier, chaque élément comme un objet au sens de la POO, avec ses caractéristiques et des informations telles que sa position sur l'écran, sa taille, etc. stoqués entre les différents affichages de cet élément. Si vous ouvrez un paper que vous aviez fermé il y a deux semaines, il se retrouvera au même endroit, avec la même taille, à la même page, etc.

L'inconvénient de cette méthode exercée à l'abus c'est que vous vous retrouverez avec un nombre incalculable de fenêtres dès que vous voulez fouiller un peu dans vos dossiers.

Récemment, nautilus a renoncé à activer cette fonctionnalité par défaut. La raison principale, c'est le Gnome Shell. C'est la nouvelle façon de penser le bureau pour Gnome 3.0. C'est d'ailleurs assez intéressant, je vous invite à lire la page dédíée au Gnome Shell, et plus particulièrement le design document si ça vous intéresse. Ça propose un moyen plus simple d'accéder à ses fenêtres qui sont regroupées par activité, ça centralise les événements (réception d'un nouveau message, demande d'une application) pour les gérer au niveau du bureau. Si vous êtes occupés, vous pouvez filtrer une partie des messages, et les applications pourront limiter le nombre de popups qu'elles vous jettent à la figure. Le tout saupoudré de pas mal de recherche sur l'ergonomie, ça donne plutôt envie d'essayer.

Du coup donc, la principale manière d'accéder à ses fichiers ne sera plus Nautilus mais un autre machin, ce qui a permi à Nautilus de revenir à la métaphore de navigation, où on ne crée notamment pas de nouvelle fenêtre. L'autre raison, c'est que personne n'utilisait ça de toute façon. :)

Plus d'infos sur http://www.bytebot.net/geekdocs/spatial-nautilus.html qui lie vers tous les liens qui vont bien. Have fun.

J'ai ouvert un blog il y a quelques jours, et je n'y ai toujours rien écrit. Je me demande donc pourquoi je l'ai fait, quel genre de choses je veux y placer, et quel genre de lectorat je vais avoir (si j'en ai).

Déjà, clairement je ne veux pas parler de ma vie, seulement de sujets plus ou moins techniques et plus ou moins liés à l'actualité et en rapport avec l'informatique en général, suivant les sujets du moment.

Pourquoi pas le site du zéro, le bhm, le blog de rz0 ? Le niveau demandé de présentation demandé est trop élevé pour la plupart des trucs que je voudrais dire. Des fois j'ai juste besoin de partager une découverte, un sentiment, et voudrait un petit peu plus de feedback qu'IRC peut apporter, sans trop m'investir non plus.

Ce blog sera donc plutôt destiné à toutes les petites choses que j'aurai envie de partager avec vous, ci-possibles avec un aspect technique, et dans le but de vous faire découvrir quelque chose.

Si vous voulez discuter un des articles (j'en serais ravi), lancez la discussion sur Buzzerl !

Bonne lecture.