Dans le cas général, on ne peut pas faire mieux que n log n
Heu, on se préoccupe peu du cas général. En informatique il n'y a que des applications spécifiques à un domaine donné. Le rendu 3D "cheap", les calculs de routage ont longtemps utilisé des tris en O(n) en limitant la dynamique des valeurs considérées (radix sort).
ce qui donne bien un temps minimal, il suffit de traduire ça en terme de cycle d'horloge.
Et la constante multiplicative, et le caractère asymptotique du O(n log n), ils sont partis où ? Ton estimation de cycles d'horloge, elle ne veut rien dire si elle se base sur la complexité théorique du problème et non sur la complexité pratique d'un algorithme...
Ouarf ! Je ne comprends pas ce que tu veux dire par technique.
Disons : procédés appliqués à un domaine précis pour obtenir des résultats précis, et mis au point par la maturation progressive d'un savoir-faire. Contrairement à la recherche scientifique où l'objectif est l'élargissement de l'horizon intellectuel et théorique, non la résolution de problèmes concrets et immédiats. Note que certaines disciplines peuvent se situer à la frontière entre les deux (exemple : des résultats mathématiques sont mis à profit pour s'assurer de certaines caractéristiques des réseaux de neurones).
Ca ne depend pas, il est prouve (mathematiquement) que si un probleme NP complet a une solution polynomiale, alors tous les problemes NP complet ont une solution polynomiale
Tu n'as pas compris ce que je voulais dire. Ce n'est pas parce qu'on a prouvé que P=NP qu'on a trouvé une solution polynomiale à un problème NP-complet. On a simplement pu démontrer son existence par des moyens détournés, sans exhiber une solution précise au problème.
De plus, le débat P=NP n'est pas très intéressant en pratique. Ce n'est pas parce qu'un problème est connu comme acceptant une résolution en temps polynomial, que l'algorithme trouvé par les moyens de réduction est acceptable (s'il est en O(n^8) avec une énorme constante multiplicative, tu conviendras que c'est pas génial). Comme Boubou, tu confonds la prouvabilité d'une propriété (il existe une méthode en temps polynomial) avec l'exhibition d'une solution intéressante en pratique (je sais décrire une méthode qui convient dans les cas considérés). Cette divergence des objectifs prouve bien, à mon sens, que les mathématiques appliquées et l'informatique sont deux disciplines séparées. C'est un peu comme la différence entre physique des matériaux et architecture.
Du reste, intuitivement, P=NP est une utopie. C'est comme l'existence de Dieu : même si on n'a aucune preuve la niant, il est raisonnable de ne pas y croire...
Notons que QTParted se base certainement sur GNU Parted, un petit outil en ligne de commande méconnu mais très utile quand on a perdu sa table des partitions (il y a une fonction pour "retrouver" les partitions effacées, et ça marche - j'ai eu l'occasion d'essayer ;-)).
Si quelqu'un prouve que P=NP, tout le travail de réduction qui a été fait (rapporter un problème NP à un autre)
Ca dépend. Pour moi, si quelqu'un prouve que P=NP, il y a de fortes chances que la démonstration se fasse autrement qu'en trouvant un moyen "magique" de réduire tous les problèmes... ;)
le fait de savoir qu'on ne peut pas faire un tri en mieux que n log n permet de donner des temps minimaux d'exécution
??? Non, pas du tout. D'ailleurs, on peut faire un tri en mieux que n log n, sous certaines contraintes.
de se diriger vers un algo ou un autre
Je ne vois pas en quoi la complexité théorique d'un problème change le choix que tu feras entre des algorithmes de complexités pratiques connues.
Il ne faut pas non plus négliger l'effet "j'évite de perdre mon temps". Par exemple, il est salutaire qu'on sache qu'on ne peut pas faire de mouvement perpétuel !
Certes. Mais les gens qui travaillent sur toute une partie de l'algorithmique n'ont pas comme objectif la résolution de problèmes informatiques précis, je pense. Je suis bien d'accord qu'il y a toujours des retombées potentielles (comme avec n'importe quelle branche des maths).
Quand on fait du data mining, on fait de l'informatique, de même que pour l'IA
Ce sont des (ensembles de) techniques informatiques. L'algorithmique n'est à mon avis pas une technique, plutôt une science qui étudie des techniques.
Elles ont d'ailleurs conduit à des questions qu'on peut qualifier de purement probabiliste, sans autre intérêt que l'avancement de la théorie des probabilités.
C'est pareil pour l'algorithmique / maths appliquées. En pratique quand on écrit un soft on se fiche de savoir si un problème est NP-complet ou pas, si P!=NP, etc. On veut juste concevoir un algorithme permettant de le résoudre en un temps raisonnable dans le domaine prévu. L'étude théorique des classes de problèmes n'apporte rien dans cette optique, elle ne permet pas de trouver un algo efficace pour un problème donné (et encore moins d'écrire l'implémentation). Il s'agit bien d'une science extra-informatique.
Philippe Lheureux, troll bien connu sur les newsgroups français, spécialiste de la mauvaise foi et de l'entêtement jusqu'au-boutiste... Mouais ;) On doit faire plus crédible comme exemple.
C'est une branche de l'informatique car ce sont des motivations informatiques (analyse a priori d'un programme quelles que soient ses conditions matérielles de mise en oeuvre) qui ont conduit à sa création. Le problème P!=NP (ou P=NP, d'ailleurs, pourquoi pas) est un problème d'informatique.
Dans ce cas, l'arithmétique ayant été créée pour satisfaire aux besoins des marchands de l'Antiquité, on peut dire que l'arithmétique est une branche du commerce.
Il y a des procès qui ignorent les preuves existantes, mais peu inventent des preuves imaginaires (quand un noir est accusé du meurtre d'un redneck au fin fond du Texas...).
ZDNet dit : "According to a statement from Microsoft, the company will license SCO's Unix patents and the source code". Ce qui signifie bien qu'ils ont acheté une licence d'utilisation, pas racheté la propriété intellectuelle.
C'est mal modifié. Il faut changer le titre et remplacer "les droits d'utilisation" par "une licence d'utilisation". Evidemment, après, il n'y a plus qu'à supprimer la dépêche car elle n'a aucun intérêt.
Je ne comprends pas pourquoi les gens se passionnent pour cette affaire. On voit à trois kilomètres que c'est un ridicule pétard mouillé de la part d'une entreprise qui ne sait plus quoi faire pour récupérer un vieux reste de notoriété...
Ce texte nous apprend qu'au moment de la révolution espagnole, « la C.N.T. [espagnole] groupait alors 1 200 000 adhérents, dont 200 000 en Catalogne ». Ce qui donne une idée de l'importance du mouvement anarchiste en Espagne à cette époque.
(note : la CNT est le syndicat anarcho-syndicaliste)
PHP-GTK est un concept très intéressant, par contre j'ai un léger doute sur la fraîcheur du soft... Voir la mention suivante à la page http://gtk.php.net/download.php(...) :
Note: PHP-GTK requires PHP 4.0.5 or greater (latest CVS version will work too). Versions 0.1.x currently require PHP 4.1.0 or CVS version to compile.
PHP-GTK currently supports GTK+ v1.2.6 or greater, but not GTK+ v2.0 (which is still under development and won't be widely used for a while).
PHP 4.1.0 CVS, GTK+ 2 "still under development"... PHP-GTK est-il activement maintenu ? Ce serait dommage de s'enfermer avec une combinaison qui ne bouge plus.
D'autre part est-ce que quelqu'un a fait la comparaison avec Mono (GTK# ou Windows) pour la réalisation de petites applis graphiques portables ?
Le problème : PLEASE NOTE: You should create a new profile for Mozilla Firebird 0.6. To create a new profile, start Mozilla Firebird by running MozillaFirebird.exe -p and click on the "Create Profile" button. If you don't want to delete your old profile and are willing to incur the risk of new bugs, you should at least delete your profile's downloads.rdf file.
A chaque nouvelle version de Phoenix/Firebird c'est la même recommandation (je passe sur le MozillaFirebird.exe assez comique pour un linuxien ;-))... Est-ce quelqu'un a réussi à installer cette dernière version en conservant l'ancien profil ?
# Re: Toujours trop de tavail
Posté par Moby-Dik . En réponse au journal Toujours trop de tavail. Évalué à 1.
[^] # Re: Droit d'auteur et travailleurs
Posté par Moby-Dik . En réponse à la dépêche Droit d'auteur et travailleurs. Évalué à 1.
Heu, on se préoccupe peu du cas général. En informatique il n'y a que des applications spécifiques à un domaine donné. Le rendu 3D "cheap", les calculs de routage ont longtemps utilisé des tris en O(n) en limitant la dynamique des valeurs considérées (radix sort).
ce qui donne bien un temps minimal, il suffit de traduire ça en terme de cycle d'horloge.
Et la constante multiplicative, et le caractère asymptotique du O(n log n), ils sont partis où ? Ton estimation de cycles d'horloge, elle ne veut rien dire si elle se base sur la complexité théorique du problème et non sur la complexité pratique d'un algorithme...
Ouarf ! Je ne comprends pas ce que tu veux dire par technique.
Disons : procédés appliqués à un domaine précis pour obtenir des résultats précis, et mis au point par la maturation progressive d'un savoir-faire. Contrairement à la recherche scientifique où l'objectif est l'élargissement de l'horizon intellectuel et théorique, non la résolution de problèmes concrets et immédiats. Note que certaines disciplines peuvent se situer à la frontière entre les deux (exemple : des résultats mathématiques sont mis à profit pour s'assurer de certaines caractéristiques des réseaux de neurones).
[^] # Re: Droit d'auteur et travailleurs
Posté par Moby-Dik . En réponse à la dépêche Droit d'auteur et travailleurs. Évalué à 1.
Tu n'as pas compris ce que je voulais dire. Ce n'est pas parce qu'on a prouvé que P=NP qu'on a trouvé une solution polynomiale à un problème NP-complet. On a simplement pu démontrer son existence par des moyens détournés, sans exhiber une solution précise au problème.
De plus, le débat P=NP n'est pas très intéressant en pratique. Ce n'est pas parce qu'un problème est connu comme acceptant une résolution en temps polynomial, que l'algorithme trouvé par les moyens de réduction est acceptable (s'il est en O(n^8) avec une énorme constante multiplicative, tu conviendras que c'est pas génial). Comme Boubou, tu confonds la prouvabilité d'une propriété (il existe une méthode en temps polynomial) avec l'exhibition d'une solution intéressante en pratique (je sais décrire une méthode qui convient dans les cas considérés). Cette divergence des objectifs prouve bien, à mon sens, que les mathématiques appliquées et l'informatique sont deux disciplines séparées. C'est un peu comme la différence entre physique des matériaux et architecture.
Du reste, intuitivement, P=NP est une utopie. C'est comme l'existence de Dieu : même si on n'a aucune preuve la niant, il est raisonnable de ne pas y croire...
# Re: Knoppix 3.2 du 16 mai
Posté par Moby-Dik . En réponse à la dépêche Knoppix 3.2 du 16 mai. Évalué à 3.
[^] # Re: Brevetabilité : Brevets logiciels et menaces sur l'économie
Posté par Moby-Dik . En réponse à la dépêche Brevetabilité : Brevets logiciels et menaces sur l'économie. Évalué à 2.
Certes.
[^] # Re: Droit d'auteur et travailleurs
Posté par Moby-Dik . En réponse à la dépêche Droit d'auteur et travailleurs. Évalué à 1.
Ca dépend. Pour moi, si quelqu'un prouve que P=NP, il y a de fortes chances que la démonstration se fasse autrement qu'en trouvant un moyen "magique" de réduire tous les problèmes... ;)
le fait de savoir qu'on ne peut pas faire un tri en mieux que n log n permet de donner des temps minimaux d'exécution
??? Non, pas du tout. D'ailleurs, on peut faire un tri en mieux que n log n, sous certaines contraintes.
de se diriger vers un algo ou un autre
Je ne vois pas en quoi la complexité théorique d'un problème change le choix que tu feras entre des algorithmes de complexités pratiques connues.
Il ne faut pas non plus négliger l'effet "j'évite de perdre mon temps". Par exemple, il est salutaire qu'on sache qu'on ne peut pas faire de mouvement perpétuel !
Certes. Mais les gens qui travaillent sur toute une partie de l'algorithmique n'ont pas comme objectif la résolution de problèmes informatiques précis, je pense. Je suis bien d'accord qu'il y a toujours des retombées potentielles (comme avec n'importe quelle branche des maths).
Quand on fait du data mining, on fait de l'informatique, de même que pour l'IA
Ce sont des (ensembles de) techniques informatiques. L'algorithmique n'est à mon avis pas une technique, plutôt une science qui étudie des techniques.
[^] # Re: Droit d'auteur et travailleurs
Posté par Moby-Dik . En réponse à la dépêche Droit d'auteur et travailleurs. Évalué à 1.
C'est pareil pour l'algorithmique / maths appliquées. En pratique quand on écrit un soft on se fiche de savoir si un problème est NP-complet ou pas, si P!=NP, etc. On veut juste concevoir un algorithme permettant de le résoudre en un temps raisonnable dans le domaine prévu. L'étude théorique des classes de problèmes n'apporte rien dans cette optique, elle ne permet pas de trouver un algo efficace pour un problème donné (et encore moins d'écrire l'implémentation). Il s'agit bien d'une science extra-informatique.
[^] # Re: Droit d'auteur et travailleurs
Posté par Moby-Dik . En réponse à la dépêche Droit d'auteur et travailleurs. Évalué à 1.
[^] # Re: Droit d'auteur et travailleurs
Posté par Moby-Dik . En réponse à la dépêche Droit d'auteur et travailleurs. Évalué à 1.
[^] # Re: Droit d'auteur et travailleurs
Posté par Moby-Dik . En réponse à la dépêche Droit d'auteur et travailleurs. Évalué à 1.
Dans ce cas, l'arithmétique ayant été créée pour satisfaire aux besoins des marchands de l'Antiquité, on peut dire que l'arithmétique est une branche du commerce.
[^] # Re: La rébellion s'organise au Royaume d'Espagne
Posté par Moby-Dik . En réponse à la dépêche La rébellion s'organise au Royaume d'Espagne. Évalué à -1.
[^] # Re: Microsoft rachète les droits sur Unix (SCO)
Posté par Moby-Dik . En réponse à la dépêche Microsoft achète une licence sur Unix (SCO). Évalué à 1.
# Re: Grosse connerie ou scoop
Posté par Moby-Dik . En réponse au journal Grosse connerie ou scoop. Évalué à 3.
[^] # Re: Microsoft rachète les droits sur Unix (SCO)
Posté par Moby-Dik . En réponse à la dépêche Microsoft achète une licence sur Unix (SCO). Évalué à 1.
# Re: Les pseudonymes bientôt interdits sur les forum koréens
Posté par Moby-Dik . En réponse à la dépêche Les pseudonymes bientôt interdits sur les forums sud-coréens. Évalué à 2.
[^] # Re: Questions
Posté par Moby-Dik . En réponse à la dépêche Microsoft achète une licence sur Unix (SCO). Évalué à 1.
Non, ça c'est juste ce que prétend SCO, et ils ne sont pas très crédibles (voir papier d'ESR linké plus haut)...
[^] # Re: Microsoft rachète les droits sur Unix (SCO)
Posté par Moby-Dik . En réponse à la dépêche Microsoft achète une licence sur Unix (SCO). Évalué à 6.
Je ne comprends pas pourquoi les gens se passionnent pour cette affaire. On voit à trois kilomètres que c'est un ridicule pétard mouillé de la part d'une entreprise qui ne sait plus quoi faire pour récupérer un vieux reste de notoriété...
Les prétentions de SCO massacrées par une analyse d'Eric Raymond : http://www.opensource.org/sco-vs-ibm.html(...)
# Re: Half life 2
Posté par Moby-Dik . En réponse au journal Half life 2. Évalué à 2.
http://gamefiles.blueyonder.co.uk/blueyondergames/trailers/halflife(...)
[^] # Re: Un peut de poésie
Posté par Moby-Dik . En réponse à la dépêche La rébellion s'organise au Royaume d'Espagne. Évalué à -3.
[^] # Re: Un peut de poésie
Posté par Moby-Dik . En réponse à la dépêche La rébellion s'organise au Royaume d'Espagne. Évalué à -3.
[^] # Re: Un peut de poésie
Posté par Moby-Dik . En réponse à la dépêche La rébellion s'organise au Royaume d'Espagne. Évalué à -3.
http://www.republique.ch/culture/anarchisme/mouvements-anarchistes.(...)
Ce texte nous apprend qu'au moment de la révolution espagnole, « la C.N.T. [espagnole] groupait alors 1 200 000 adhérents, dont 200 000 en Catalogne ». Ce qui donne une idée de l'importance du mouvement anarchiste en Espagne à cette époque.
(note : la CNT est le syndicat anarcho-syndicaliste)
[^] # Re: Mes questions à la noix
Posté par Moby-Dik . En réponse à la dépêche Introduction à PHP-GTK. Évalué à 1.
http://cvs.php.net/cvs.php/php-gtk?login=2(...)
# Mes questions à la noix
Posté par Moby-Dik . En réponse à la dépêche Introduction à PHP-GTK. Évalué à 3.
Note: PHP-GTK requires PHP 4.0.5 or greater (latest CVS version will work too). Versions 0.1.x currently require PHP 4.1.0 or CVS version to compile.
PHP-GTK currently supports GTK+ v1.2.6 or greater, but not GTK+ v2.0 (which is still under development and won't be widely used for a while).
PHP 4.1.0 CVS, GTK+ 2 "still under development"... PHP-GTK est-il activement maintenu ? Ce serait dommage de s'enfermer avec une combinaison qui ne bouge plus.
D'autre part est-ce que quelqu'un a fait la comparaison avec Mono (GTK# ou Windows) pour la réalisation de petites applis graphiques portables ?
# Profils
Posté par Moby-Dik . En réponse à la dépêche Sortie de Mozilla Firebird 0.6. Évalué à 5.
A chaque nouvelle version de Phoenix/Firebird c'est la même recommandation (je passe sur le MozillaFirebird.exe assez comique pour un linuxien ;-))... Est-ce quelqu'un a réussi à installer cette dernière version en conservant l'ancien profil ?
[^] # Re: Lettre aux 1500 plus grosses boites
Posté par Moby-Dik . En réponse à la dépêche Caldera c'est vraiment fini. Évalué à 1.