informatique/autodidacte-apprendre la manipulation de bits

Le 17-06-2010, Antoine Leca <root@localhost.invalid> a écrit :

Marc Boyer écrivit :

Le 16-06-2010, Antoine Leca <root@localhost.invalid> a écrit :

Marc Boyer écrivit :

Je ne nie pas ce que tu dis, mais à mon sens, la difficulité du
code actuel n'est pas l'algorithmique (a part certains domaines métiers),
et les grands plantages informatiques ne sont pas liés à des
pb d'algorithmes.

À mon avis, ce n'est pas propre au génie logiciel, cela s'étend à
l'ensemble des « sciences de l'ingénieur » (génie sans qualificatif a un
autre sens !) : savoir, la plus grand part des problèmes ne sont pas
techniquement difficiles, unitairement ; par contre ils sont complexes.

Je ne suis pas sûr. L'écoulement des gaz dans un réacteurs, c'est
compliqué.

Pas d'accord. Cela s'appelle équation de Navier-Stokes, et ce n'est pas
sorcier à comprendre (mais ne me demande pas de te l'expliquer, cela
fait trop longtemps que j'ai séché le TD correspondant :^)).
Le seul souci en l'occurrence, c'est que l'on ne connait pas de manière
de résoudre directement le problème, donc on fait le tour. Et c'est là
que cela devient complexe, le « comment faire le tour ».
On a la même chose avec le problème des n corps, ou avec Schröedinger.

C'est pas parce que l'énoncé est court que le problème est simple.
C'est justement une des grandes différences, à mon sens, entre les
math classiques et l'informatique. L'informatique manipule des
notions très simples (un processeur, c'est 4 opérations arithmétique, le
branchement conditionnel et lire/ecrire). Mais quand on s'intéresse
au comportement d'un processeur qui effectue 10^9 opérations par
seconde dans un code de 10^7 intructions, ca devient compliqué.
En math, l'objet lui même est complexe (même si on a des notations
simples pour le représenter).

Et le logiciel a cela de particulier qu'il a tendance a être
très sensible aux petites erreurs.

Moi j'appelle cela être fragile, et c'est exactement la même chose avec
p.ex. les pièces en titane au milieu de ton réacteur : pour obtenir les
performances voulues, surtout sur les avions de compétition^W militaires
on utilise les limites des matériaux mis en œuvre, mais on est alors à
la merci du moindre problème, par exemple des oiseaux qui visitent.

Sauf que le logiciel est discret.
On peut faire une pièce 20% plus épaisse, elle sera 20% plus lourde
et n% plus robuste. C'est continu.

Gérard Berry dit que l'ordinateur est un amplificateur à connerie.
La moindre bétise activée se démultiplie partout.

Le logiciel, on ne sait que faire de la redondance: on code deux fois
la même chose, et si l'un est en panne, on regarde l'autre. Et si on
ne sait pas distinguer une erreur d'une panne, on doit en mettre au
moins 3 et faire un vote...
Donc, multiplication par 3 des coûts, ad-minima...

L'autre facteur, c'est la sauvegarde. Quelle autre domaine
sait rétablir un système dans l'état dans lequel il était la veille ?
Lorsque l'erreur n'a pas d'impact sur le monde physique,
il suffit de revenir à la dernière sauvegarde... On a juste perdu
24h de travail.

Je pense que cette conjonction: robustesse discrette et
sauvegarde quasi gratuite expliquent une partie du fait qu'on
reste dans le fragile.

Avec les programmes c'est pareil, *sauf* que apparemment on ne sait
faire *que* fragile, on ne sait pas construire solide.
ÀMHA cela viendra.

Je ne sais pas. Dans un monde continu, on met 20% de marge
et ça passe. Dans un monde discret, c'est soit juste, soit faux,
et pour corriger l'erreur, il faut multiplier par un facteur entier.

Je ne suis pas capable d'imaginer un système informatique qui
ait une resistance aux agressions continues.
On peut dire qu'on fait 20% de plus de tests, qu'on passe 30% de plus
sur la spec, le produit final reste discret.

Mais il est vrai que pour le moment, il semble préférable de produire du
logiciel fragile, plutôt que du solide. Est-ce parce que c'est
économiquement rentable? ou parce que les programmeurs préfèrent cela
(syndrome NIH)? ou parce que le logiciel n'est pas financé correctement
du fait de la différence entre le modèle économique (réitératif) et le
modèle productif (par clonage à coût quasiment nul) ?

Pour résumer mon avis.
Je pense que le logiciel est intrinsequement discret, et que sa
fiabilisation implique un surcout en facteur entier.
De plus, on sait sauvegarder un état à coût quasi nul.

Donc, on fait du fragile, sauf quand il y a un impact sur
le monde physique et qu'on ne peut pas juste sauvegarder.
Et là, soit on sait arrêter la machine, soit il faut fiabiliser
et multiplier les coûts pour 2, 3 ou 4...
Ou on fait des autos, et on prie, on paye des avocats, et
parfois il faut indemniser.

Marc Boyer
--
En prenant aux 10% des francais les plus riches 12% de leurs revenus,
on pourrait doubler les revenus des 10% les plus pauvres.
http://www.inegalites.fr/spip.php?article1&id_mot0

In article <hvfonv$odv$1@news.cict.fr>,
Marc Boyer <Marc.Boyer@cert.onera.fr.invalid> wrote:

C'est justement une des grandes différences, à mon sens, entre les
math classiques et l'informatique. L'informatique manipule des
notions très simples (un processeur, c'est 4 opérations arithmétique, le
branchement conditionnel et lire/ecrire). Mais quand on s'intéresse
au comportement d'un processeur qui effectue 10^9 opérations par
seconde dans un code de 10^7 intructions, ca devient compliqué.
En math, l'objet lui même est complexe (même si on a des notations
simples pour le représenter).

je ne suis pas du tout d'accord avec ton point de vue.

L'arithmetique informatique n'a rien d'evident, entre les problemes de
debordement de capacite, l'utilisation de l'arithmetique modulaire pour
les valeurs non signees, ou les problemes tres epineux de precision en
mode flottant.

Il y a plein de choses en maths qui s'expriment tres simplement, mais qui
conduisent a des choses effroyablement compliquees. La notion de nombre
entier, par exemple.

Sans parler du probleme de l'arret, des problemes NP-complets, et de toutes
ses petites choses plus ou moins decidables qui rendent les choses
"interessantes".

Pour ma pomme, je ne fais pas de reelle distinction entre "mathematiques" et
"informatique": memes concepts, memes problemes, meme combat.

Apres, qu'un grand nombre d'informaticiens pratiquants (voire professionnels!)
n'aient que de tres vagues notions concernant l'objet de leur pratique,
c'est une evidence (regrettable...). Apres tout, tu n'attend pas forcement
d'un comptable qu'il connaisse toutes les nuances de l'arithmetique, ou
d'un physicien qu'il ait compris la notion de fonction derivable (paf,
un trollometre tout neuf)...

Le 18-06-2010, Marc Espie <espie@lain.home> a écrit :

In article <hvfonv$odv$1@news.cict.fr>,
Marc Boyer <Marc.Boyer@cert.onera.fr.invalid> wrote:

C'est justement une des grandes différences, à mon sens, entre les
math classiques et l'informatique. L'informatique manipule des
notions très simples (un processeur, c'est 4 opérations arithmétique, le
branchement conditionnel et lire/ecrire). Mais quand on s'intéresse
au comportement d'un processeur qui effectue 10^9 opérations par
seconde dans un code de 10^7 intructions, ca devient compliqué.
En math, l'objet lui même est complexe (même si on a des notations
simples pour le représenter).

je ne suis pas du tout d'accord avec ton point de vue.

L'arithmetique informatique n'a rien d'evident, entre les problemes de
debordement de capacite, l'utilisation de l'arithmetique modulaire pour
les valeurs non signees, ou les problemes tres epineux de precision en
mode flottant.

J'aurais pu exclure l'arithmérique flottante en effet, toute la partie
calcul numérique.
Mais je ne connais pas de problème industriel grave qui soit lié à
un problème de virgule flottante.

Sans parler du probleme de l'arret, des problemes NP-complets, et de toutes
ses petites choses plus ou moins decidables qui rendent les choses
"interessantes".

Sauf qu'en pratique, ce n'est pas un problème.
C'est un problème dans le sens où cela exclue toute vérification
automatique générale.
Mais cela n'est pas la cause des "bugs" (hormis la question de la
vérif). Les codes ne plantent pas parce qu'un programmeur a mal
évalué la classe de complexité de son problème. Les codes plantent
parce qu'on a oublié de vérifier qu'il y avait de la place dans
les buffers (http://www.sans.org/top25-programming-errors/).

Pour ma pomme, je ne fais pas de reelle distinction entre "mathematiques" et
"informatique": memes concepts, memes problemes, meme combat.

Sections 25-26 contre 27 au ministères.
Section 1 contre 7 au CNRS.

Il y a un continuum, des parties communes non nulles (et pas inintéressantes)
et énormément de points communs méthodologiques. Mais pourtant, il me semble
que cela reste des objets distincts.

Mais pour en revenir au sujet, qui est de se demander si la fragilité
des codes vient de la nature de l'informatique où juste des méthodes
industrielles, c'est plus à la physique qu'aux maths qu'il faut opposer
l'informatique.
Et la physique est continue à son échelle humaine industrielle. Elle
permet donc des approximations, des marges de tolérance. Pas l'informatique.

Marc Boyer
PS: J'aurais bien fait fu2 fr.comp.divers, mais au milieu des
points d'exclamation jaune et des croix rouges, ça va faire tâche.
--
En prenant aux 10% des francais les plus riches 12% de leurs revenus,
on pourrait doubler les revenus des 10% les plus pauvres.
http://www.inegalites.fr/spip.php?article1&id_mot0

In article <hvfr6l$pda$1@news.cict.fr>,
Marc Boyer <Marc.Boyer@cert.onera.fr.invalid> wrote:

Le 18-06-2010, Marc Espie <espie@lain.home> a écrit :

Sans parler du probleme de l'arret, des problemes NP-complets, et de toutes
ses petites choses plus ou moins decidables qui rendent les choses
"interessantes".

Sauf qu'en pratique, ce n'est pas un problème.
C'est un problème dans le sens où cela exclue toute vérification
automatique générale.
Mais cela n'est pas la cause des "bugs" (hormis la question de la
vérif). Les codes ne plantent pas parce qu'un programmeur a mal
évalué la classe de complexité de son problème. Les codes plantent
parce qu'on a oublié de vérifier qu'il y avait de la place dans
les buffers (http://www.sans.org/top25-programming-errors/).

Ahaha! doit-on en rire ou en pleurer.

Effectivement, l'informatique n'est pas un probleme. C'est plutot LE
probleme, en fait...

ce que nous montrent les "bugs", c'est qu'un programmeur humain ne fait que
tres rarement un boulot correct. Mais comme la plupart des programmeurs
humains n'entravent rien aux maths, ni aux techniques de verification
formelles, rien que le design d'un langage qui s'y preterait mieux leur
est totalement alien. Du coup, on se retrouve coince avec du C/Java/C#
et autres machins avec lesquels on peut bien s'amuser, mais qui n'ont aucune
qualite de rigueur cote industriel (remarque: ca fait mon beurre. Tant que
la programmation a la mano reclamera une telle attention aux details, je ne
m'inquiete pas trop pour mon employabilite...)

Marc Boyer écrivit :

Mais je ne connais pas de problème industriel grave qui soit lié à
un problème de virgule flottante.

Trop gros, ou pas assez grave, le vol L501 ?

Mais pour en revenir au sujet, qui est de se demander si la fragilité
des codes vient de la nature de l'informatique où juste des méthodes
industrielles, c'est plus à la physique qu'aux maths qu'il faut opposer
l'informatique.

Fragile est le contraire de robuste. Et robuste est un qualificatif que
tu peux appliquer à des démonstrations, à des conjectures...

Après, évidemment l'analogie a des limites : je n'ai par exemple pas
d'idée de ce que pourrait signifier l'élasticité d'un logiciel...

Et la physique est continue à son échelle humaine industrielle.

Mais pas à l'échelle atomique, ni même microscopique pour certains
phénomènes comme les frottements ; donc ce n'est pas continu au sens
mathématique du terme.

De la même manière, si l'informatique des programmes est effectivement
discrète, lorsque tu t'intéresses à un système informatique dans son
ensemble, tu peux considérer certaines propriétés comme
pseudo-continues: c'est ainsi que la notion de « fragile » se comprend
assez bien comme étant celle d'un logiciel (ou un aspirateur, une télé,
ou une voiture) qui fonctionne uniquement lorsque les données sont
fournies par le démonstrateur dans un salon... et se casse lorsque c'est
toi qui l'utilises !

Elle permet donc des approximations, des marges de tolérance.

Bah ? Si tu permets à un sous-système de diverger jusqu'à un certain
point, et qu'à ce moment-là tu tues le processus et le relances
(technique classique, utilisée par exemple dans le noyau Windows), c'est
exactement la même chose qu'établir des marges de tolérance, non ?
Idem pour les algorithmes réseau : on utilise un modèle de faillites
possibles, qui définit des tolérances, et quand on sort on décide qu'il
s'agit d'une vraie défaillance.


Antoine

Marc Boyer a écrit :

Mais je ne connais pas de problème industriel grave qui soit lié à
un problème de virgule flottante.

Oui ou des problèmes d'arrêts de machine de Turing. Les trucs
industriels sont bien plus bateaux et moins théoriques que cela dans
leur immense majorité.

Sans parler du probleme de l'arret, des problemes NP-complets, et de toutes
ses petites choses plus ou moins decidables qui rendent les choses
"interessantes".

Sauf qu'en pratique, ce n'est pas un problème.

Tout a fait car contrairement à l'algorithmique théorique qui traite de
tout ce qui est exécutable par tel ou tel modèle de calcul, en pratique
on utilise qu'une sous partie de cet ensemble. Les problèmes pratique
viennent plus souvent de specs imprécises que de problèmes de fonds
algorithmique. On oublie assez vite la combinatoire énorme que fait

C'est un problème dans le sens où cela exclue toute vérification
automatique générale.

Oui et sans pour autant exclure une vérification automatique d'un sous
ensemble "utilisée" des modèles de calcul.

C'est assez rigolo. Il y a un domaine que je connais bien où la théorie
(mathématique) et la pratique (industrielle) ne sont pas non plus en
accord. C'est la programmation linéaire (résoudre un système linéaire
sous contrainte: maximiser c.x sachant que Ax = B; x>=0;).

En gros il y a 2 classes d'algos. Ceux à base de points intérieurs et
les algos de type simplexe où l'on se ballade sur la surface du
polytope. En théorie, les algos à base de points intérieurs sont
polynomiaux et les algos de type simplexe sont exponentiels. Le soucis
c'est que les algos polynomiaux ont de très gros coefs et exposants
alors que les algos exponentiels ont des tout petits coefs. Du coup en
pratique avec les problèmes actuels, l'algo exponentiel est souvent plus
rapide que l'algo polynomial.

Je me dis que qu'une différence entre la théorie et la pratique c'est
qu'en théorie on travaille sur toutes les matrices "A" dans Ax=B en
supposant telle ou telle répartition des coefficients, des valeurs
propres, que sais-je, mais qu'en pratique, les matrices "A" ne sont pas
des nombres aléatoires, mais des nombres codant des trucs
"faisant/codant quelque chose". Les deux ensembles de problèmes (nombre
aléatoires / nombres ayant du "sens") ne se recouvrent pas, loin de là.
Les propriétés algorithmiques d'un même algo peuvent être assez
différente entre les deux ensembles.

Mais pour en revenir au sujet, qui est de se demander si la fragilité
des codes vient de la nature de l'informatique où juste des méthodes
industrielles, c'est plus à la physique qu'aux maths qu'il faut opposer
l'informatique.

Je le pense aussi.

Et la physique est continue à son échelle humaine industrielle. Elle
permet donc des approximations, des marges de tolérance. Pas l'informatique.

C'est d'ailleurs assez paradoxal. Les choses physiques sont quelques
part plus faciles à décrire que les choses informatiques. Et pourtant il
y a beaucoup d'interactions entre les éléments physiques qu'entre les
éléments informatiques. Néanmoins on arrive à décrire précisément les
premiers avec peu de termes là ou il faut des pages et des pages de
description, précisions, pour le moindre programme.

Il faut dire que la physique dispose des outils pour "abstraire" et
raisonner simplement, mais elle hérite de plusieurs siècles de pratique.
Au regard de cela l'informatique est toute jeune, et les outils
commencent à peine à arriver (description "objet" --tiens tiens-- etc).
Voyons ce que donnera l'informatique dans 200 ou 300 ans quand les
programmes ne seront plus les monolythes actuels rigide et ne supportant
pas les erreurs mais des tas de petits trucs simples, redondants, qui
s'assemblent librement pour exhiber un comportement collectif interressant.

sam.

Samuel DEVULDER écrivit :

C'est assez rigolo. Il y a un domaine que je connais bien où la théorie
(mathématique) et la pratique (industrielle) ne sont pas non plus en
accord.

Pourquoi dis-tu « pas en accord » ?
À te lire, on a l'impression que tu dérives du résultat mathématique (A
est polynomial et B est exponentiel) un autre résultat (A est meilleur
que B), qui correspond peut-être à la situation à l'infini mais qui,
comme tu l'expliques par ailleurs, n'est pas forcément valable en tous
points.

Je me dis que qu'une différence entre la théorie et la pratique c'est
qu'en théorie on travaille sur toutes les matrices "A" dans Ax=B en
supposant telle ou telle répartition des coefficients, des valeurs
propres, que sais-je, mais qu'en pratique, les matrices "A" ne sont pas
des nombres aléatoires, mais des nombres codant des trucs
"faisant/codant quelque chose".

Ce n'est pas une différence entre théorie et pratique, c'est une
différence entre « théorie sans contrainte » et « théorie avec
/contrainte/ complémentaire ».
De la seconde, tu déduis comme résultat les valeurs des coefficients
avec les deux algorithmes, ce qui explique les données expérimentales
issues de la pratique (à savoir, le simplexe c'est mieux).

Par ailleurs, le problème « avec des nombres aléatoires » est un autre
problème, avec une autre réponse théorique et d'autres applications
pratiques. Par exemple, un des inconvénients du tri quick-sort, c'est
qu'il y a « un très mauvais cas ». Dans la pratique on néglige, mais en
programmation très défensive, tu peux avoir du code spécialement dédié à
repérer ce très mauvais cas, pour éviter une attaque de type DdS.

Les propriétés algorithmiques d'un même algo peuvent être assez
différente entre les deux ensembles.

Oui, c'est exactement cela. Et si tu peux caractériser chacun des deux
ensembles, tu peux mieux appliquer la théorie, dans chaque cas.
Meilleure connaissance des données (de l'environnement) => meilleur
produit, une règle de base des sciences de l'ingénieur.


Antoine

In article <4c1b98d8$0$8105$426a74cc@news.free.fr>,
Samuel DEVULDER <samuel-dot-devulder@laposte-dot-com> wrote:

Marc Boyer a écrit :

Mais je ne connais pas de problème industriel grave qui soit lié à
un problème de virgule flottante.

Oui ou des problèmes d'arrêts de machine de Turing. Les trucs
industriels sont bien plus bateaux et moins théoriques que cela dans
leur immense majorité.

Mais c'est du grand n'importe quoi, ce que tu affirmes !

Sans parler du probleme de l'arret, des problemes NP-complets, et de toutes
ses petites choses plus ou moins decidables qui rendent les choses
"interessantes".

Sauf qu'en pratique, ce n'est pas un problème.

Tout a fait car contrairement à l'algorithmique théorique qui traite de
tout ce qui est exécutable par tel ou tel modèle de calcul, en pratique
on utilise qu'une sous partie de cet ensemble. Les problèmes pratique
viennent plus souvent de specs imprécises que de problèmes de fonds
algorithmique. On oublie assez vite la combinatoire énorme que fait

Pareil, la-aussi.

Le probleme de l'arret, c'est l'exemple simple qu'on donne aux gens.
Le theoreme suivant dit en gros que les problemes informatiques se separent
en deux categories, les problemes triviaux, et les problemes indecidables
(en nuancant un peu, tu as les problemes triviaux, les NP-complets, et
les indecidables). Une des particularites, c'est que quasiment tout ce qui
est "meta" est indecidable. Dire si un programme s'arrete -> indecidable,
*DIRE SI UN PROGRAMME EST SANS BUG* -> indecidable. Dire si un programme ne
va pas planter pour cause de division par zero -> indecidable.

Le rapport avec la programmation reelle ? Il n'y a pratiquement *aucun*
langage industriel qui se preoccupe de ses meta-considerations. Typiquement,
ils sont tous Turing-complets, tout le temps, que tu sois en train de
resoudre des problemes triviaux, ou des problemes impossibles.

En particulier, tu n'as pas de facon de dire *OKAY, LA J'AI UN ALGO ELEMENTAIRE,
J'AIMERAIS BIEN RESTER DE FACON CERTAINE DANS LA PARTIE DE L'INFORMATIQUE
SUR LAQUELLE ON SAIT RAISONNER*.

Nan, tu as toujours tout, tout le temps. Du coup, on ne peut pas prouver que
les choses marchent, et du coup, on a des bugs.

Dans les experiences rigolotes, je ne sais pas si tu as deja passe du temps
avec des outils de verification de code ? Ca peut meme etre *aussi con*
qu'une nouvelle version de gcc, avec "un peu plus" d'analyse de code, et un
peu plus de warnings pour variables potentiellement initialisees.

Dans mon experience, meme sur du code *a priori* completement debile, on y
voit des choses interessantes:
- soit le compilo qui d'un coup voit des variables *reelleement* non
initialisees dans certaines branches, alors qu'on a relu le code 25 fois
et qu'on s'en sert depuis dix ans (ben oui, si c'est une branche de gestion
d'erreur, peut-etre qu'on ne l'a jamais vraiment testee).
- soit le compilo qui n'arrive pas a conclure, tout betement parce que
l'explosion combinatoire necessaire pour l'analyse du code est trop
importante (voire impossible).

Et partant de la, on modifie, et on simplifie, pour que des choses *triviales*
soient effectivement triviales et que le compilateur y retrouve ses petits.

Tout ca, c'est des choses que je vois tous les jours, sur du code ecrit
par des informaticiens pas trop mauvais, mais qui arrivent, de temps en
temps, sur des centaines de ligne de code, a se planter/mettre en echec
les systemes de verification...

Toujours dans mon experience, si on passe du C a un autre langage, tout
ce qu'on fait c'est changer le domaine ou les problemes vont apparaitre.
Aucun langage "industriel" n'est reellement meilleur de ce point de vue.

Evidemment, je suis biaise: je passe beaucoup plus de temps a lire,
a auditer et a corriger du code qu'a en ecrire. Mais pour moi, l'idee
de pouvoir raisonner sur un programme, voire de pouvoir PROUVER des choses
sur celui-ci, c'est quelque chose qui a des TONNES d'applications tres
pratiques et immediates.

Antoine Leca a écrit :

Samuel DEVULDER écrivit :

C'est assez rigolo. Il y a un domaine que je connais bien où la théorie
(mathématique) et la pratique (industrielle) ne sont pas non plus en
accord.

Pourquoi dis-tu « pas en accord » ?

En théorie un algo exponentiel n'est pas, par principe, un bon algo
alors qu'un algo polynomial est souvent considéré comme meilleur. On
peut dire sans trop exagérer que l'exponentiel traduit le fait qu'on ne
sait pas intelligemment exploiter les structures régulières présentes
dans les données à traiter et qu'on ne fait pas tellement mieux que
l'approche naive à force brute.

En première approximation c'est pas complètement faux, mais en pratique
il arrive qu'un bon exponentiel marche mieux qu'un mauvais polynomial.
C'est ce que j'entends par "la théorie" n'est pas en accord avec la
"pratique".

À te lire, on a l'impression que tu dérives du résultat mathématique (A
est polynomial et B est exponentiel) un autre résultat (A est meilleur
que B), qui correspond peut-être à la situation à l'infini mais qui,
comme tu l'expliques par ailleurs, n'est pas forcément valable en tous
points.

Absolument. Tout dépend à quelle valeur de /n/ la différence entre la
version polynomiale ou exponentielle se fait sentir. Bref à partir de
quelle valeur de taille d'entrée on considère qu'on est en mode
asymptotique, voisin de l'infini.

Je me dis que qu'une différence entre la théorie et la pratique c'est
qu'en théorie on travaille sur toutes les matrices "A" dans Ax=B en
supposant telle ou telle répartition des coefficients, des valeurs
propres, que sais-je, mais qu'en pratique, les matrices "A" ne sont pas
des nombres aléatoires, mais des nombres codant des trucs
"faisant/codant quelque chose".

Ce n'est pas une différence entre théorie et pratique, c'est une
différence entre « théorie sans contrainte » et « théorie avec
/contrainte/ complémentaire ».
De la seconde, tu déduis comme résultat les valeurs des coefficients
avec les deux algorithmes, ce qui explique les données expérimentales
issues de la pratique (à savoir, le simplexe c'est mieux).

On raisonne souvent en supposant les entrées "uniformes" parce qu'on ne
sait pas modéliser plus précisément les choses, alors qu'en pratique
dans beaucoup d'algos, les entrées ne sont pas des bits aléatoires
équiprobables, mais des choses qui ont plus de sens. La répartition
uniforme a de bonnes propriétés simplificatrices, mais elle a ses
limites. Parfois il ne faut pas considérer que le cas uniforme
s'applique identiquement aux cas rééls.

Par ailleurs, le problème « avec des nombres aléatoires » est un autre
problème, avec une autre réponse théorique et d'autres applications
pratiques. Par exemple, un des inconvénients du tri quick-sort, c'est
qu'il y a « un très mauvais cas ». Dans la pratique on néglige,

On peut effectivement le négliger si la probabilité de tomber dessus est
faible, mais on peut aussi faire en sorte d'éviter ce cas là en
commençant par mélanger *volontairement* les données à trier. Certains
algos marchent mieux sur des données bruitées que sur des données bien
propres.

Les propriétés algorithmiques d'un même algo peuvent être assez
différente entre les deux ensembles.

Oui, c'est exactement cela. Et si tu peux caractériser chacun des deux
ensembles, tu peux mieux appliquer la théorie, dans chaque cas.
Meilleure connaissance des données (de l'environnement) => meilleur
produit, une règle de base des sciences de l'ingénieur.

Tout à fait. Mais force est de constater que souvent la distribution
aléatoire uniforme n'est finalement que le reflet de notre mauvaise
maitrise des entrées du problème.

sam.

Marc Espie a écrit :

In article <4c1b98d8$0$8105$426a74cc@news.free.fr>,
Samuel DEVULDER <samuel-dot-devulder@laposte-dot-com> wrote:

Marc Boyer a écrit :

Mais je ne connais pas de problème industriel grave qui soit lié Ã
un problème de virgule flottante.

Oui ou des problèmes d'arrêts de machine de Turing. Les trucs
industriels sont bien plus bateaux et moins théoriques que cela dans
leur immense majorité

Problèmes d'encoding?

Mais c'est du grand n'importe quoi, ce que tu affirmes !

Si c'est toi qui le dis.

Sans parler du probleme de l'arret, des problemes NP-complets, et de toutes
ses petites choses plus ou moins decidables qui rendent les choses
"interessantes".

Sauf qu'en pratique, ce n'est pas un problème.

Tout a fait car contrairement à l'algorithmique théorique qui traite de
tout ce qui est exécutable par tel ou tel modèle de calcul, en pratique
on utilise qu'une sous partie de cet ensemble. Les problèmes pratique
viennent plus souvent de specs imprécises que de problèmes de fonds
algorithmique. On oublie assez vite la combinatoire énorme que fait

Pareil, la-aussi.

Quoi? Que le problème de l'arrêt n'est pas un problème pratique. Oui
parfaitement. Je rejoins Marc là dessus: Les problèmes non décidables ne
sont pas des problèmes pratiques dans la vie industrielle où les choses
sont finalement bien plus simples que ca.

Le probleme de l'arret, c'est l'exemple simple qu'on donne aux gens.
Le theoreme suivant dit en gros que les problemes informatiques se separent
en deux categories, les problemes triviaux, et les problemes indecidables
(en nuancant un peu, tu as les problemes triviaux, les NP-complets, et
les indecidables). Une des particularites, c'est que quasiment tout ce qui
est "meta" est indecidable. Dire si un programme s'arrete -> indecidable,
*DIRE SI UN PROGRAMME EST SANS BUG* -> indecidable. Dire si un programme ne

Juste une question bête: c'est quoi ta définition d'un prog sans bug? La
mienne est celle d'un prog fidèle aux specs. Le soucis c'est que les
specs c'est du langage +/- naturel bourré d'implicite, de non-dits, et
de choses ambigües. On attends toujours et encore une façon d'écrire
des specs qui tiennent la route par rapport à cela.

Parler d'absence de bug en général sans savoir par rapport à quoi est
trompeur. Est ce qu'on peut dire qu'un prog à qui on envoi "2+2" et qui
réponds "2" est buggé? Ben ca dépend si l'opération demandée, le "+",
est un "ou" bit a bit ou une addition artihmétique. Savoir si un prog
est buggé ou pas dépend de ses specs. Souvent quand tu as un prog réputé
non buggé et que tu lui change ses specs.. hop tu s'aperçoit qu'il bug.

De mon experience, une bonne partie des bugs viennent justement de cela:
on change les specs du prog en cours de route sans être capable de voir
où il faut changer l'implémentation, et après ca beug. Pour éviter cela
l'industrie du logicielle utilise des notions spécifiques (tracabilité,
requirements, mesure d'impacts) ainsi que des outils dédiés.

va pas planter pour cause de division par zero -> indecidable.

Indécidable dans le cas *général*, mais en pratique on ne travaille que
sur des cas particuliers. La théorie de l'indécidabilité dit qu'on ne
peut pas dire si un prog quelconque parmi tous les programmes de taille
arbitraires, bref un prog tiré au hasard ne va, par exemple, boucler.

Très bien.. mais en pratique les progs ne sont pas écrit au hasard. Ils
répondent à un cahier des charges, font des choses, et même que parfois
on impose des règles d'écriture. Par exemple interdiction d'utiliser des
while, des goto, de la récursivité, des allocations dynamiques. Seules
les boucles for() bornées en nombre de tour (les boucles "for" du
langage pascal typiquement) ne sont utilisables. Ces règles pratiques
font que dans les domaines où elles sont appliquées le pb de l'arrêt est
un truc de théoricien et pas de praticien.

Le rapport avec la programmation reelle ? Il n'y a pratiquement *aucun*
langage industriel qui se preoccupe de ses meta-considerations. Typiquement,

Bien entendu, ca n'est pas leur boulot. Ils ne sont pas là pour cela.
Ils sont là pour traiter des problèmes concrets, pas des trucs méta.

ils sont tous Turing-complets, tout le temps, que tu sois en train de
resoudre des problemes triviaux, ou des problemes impossibles.

Mais on dit la même chose alors? Du coup je ne comprends pas ton "C'est
du grand n'importe quoi" initial ? Une (mauvaise) habitude de langage?

En particulier, tu n'as pas de facon de dire *OKAY, LA J'AI UN ALGO ELEMENTAIRE,
J'AIMERAIS BIEN RESTER DE FACON CERTAINE DANS LA PARTIE DE L'INFORMATIQUE
SUR LAQUELLE ON SAIT RAISONNER*.

Bien sur que si. Les standards de codage existent et servent en partie à
cela. L'informatique industrielle ne traite pas de l'informatique *en
général* mais de trucs plus simples et maitrisés. Tu ne vas pas mettre
dans un ECU de portière de voiture du code qui va chercher à résoudre
une conjecture mathématique dont on ne sait pas dire si elle est
décidable ou pas.

Peut être que tu penses que l'informatique et les mathématiques sont une
seule et même chose parce que tu es trop général. Si tu regardes le
concret des programmeurs de ce bas monde, ils sont loin, oui bien loin
des abstractions mathématiques et ont plutôt à se battre à faire rentrer
leur code dans les contraintes techniques de leur OS, de leur ROM, ou de
leur horloge (WCET correspondant à ce qui est autorisé par les specs)
qu'à savoir si leur code ne va pas partir en boucle infinie (il aurait
du mal d'ailleurs vu qu'on leur a interdit les boucles non finies).

Nan, tu as toujours tout, tout le temps. Du coup, on ne peut pas prouver que
les choses marchent, et du coup, on a des bugs.

Ben là ca dépend vraiment du domaine et de ses contraintes.

Dans les experiences rigolotes, je ne sais pas si tu as deja passe du temps
avec des outils de verification de code ? Ca peut meme etre *aussi con*
qu'une nouvelle version de gcc, avec "un peu plus" d'analyse de code, et un
peu plus de warnings pour variables potentiellement initialisees.

Dans mon experience, meme sur du code *a priori* completement debile, on y
voit des choses interessantes:
- soit le compilo qui d'un coup voit des variables *reelleement* non
initialisees dans certaines branches, alors qu'on a relu le code 25 fois
et qu'on s'en sert depuis dix ans (ben oui, si c'est une branche de gestion
d'erreur, peut-etre qu'on ne l'a jamais vraiment testee).

Dans mon expérience, quand on lance des tests de couverture, on
s'appercoit qu'il y a toujours 1 ou 2 bugs (== problèmes par rapport à
la spec) dans les branches non précédemment couvertes par les jeux de
tests. Ca n'est pas pour rien que certaines certifications demandent
d'avoir une couverture de 100% du code avec des jeux de tests (ou si on
a pas 100% il faut le justifier et c'est pas évident).

- soit le compilo qui n'arrive pas a conclure, tout betement parce que
l'explosion combinatoire necessaire pour l'analyse du code est trop
importante (voire impossible).

Certaines normes de codage imposent des complexité de code maximales:
Pas trop de boucles for imbriquées, pas trop de if imbriqués non plus, etc.

Et partant de la, on modifie, et on simplifie, pour que des choses *triviales*
soient effectivement triviales et que le compilateur y retrouve ses petits.

Des codes simples, tout con, sont souvent une bonne chose en pratique.

Ils peuvent être facilement repris par un tiers et sont de relecture et
croisement facile par rapport à la spec. Les codes "usine à gaz", lourds
avec des effets de bords de partout qui traitent 36 pbs à la fois sont
une gène à terme pour tout le monde.

Tout ca, c'est des choses que je vois tous les jours, sur du code ecrit
par des informaticiens pas trop mauvais, mais qui arrivent, de temps en
temps, sur des centaines de ligne de code, a se planter/mettre en echec
les systemes de verification...

BTW en parlant de système de vérif, tu connais cbmc?
(http://www.cprover.org/cbmc/).

Toujours dans mon experience, si on passe du C a un autre langage, tout
ce qu'on fait c'est changer le domaine ou les problemes vont apparaitre.
Aucun langage "industriel" n'est reellement meilleur de ce point de vue.

A mon sens c'est pas un problème de langage industriel, mais un problème
de métier. Si le métier est bien cerné et bien maitrisé, les problèmes
sont réduits. Tu as raison, aucun langage industriel n'est mieux que
l'autre du point de vue des bugs. Reste que le choix du langage a
souvent plus avoir à faire à des raisons historiques ou économiques
internes à la boite que des raisons intrinsèque au langage lui même. Par
contre même avec un langage aussi dangereux que le C, dans certains
domaine on impose des règles de codage strictes, qui certes brident le
fun du programmeur, mais qui évitent surtout de faire (trop de)
n'importe quoi.

Evidemment, je suis biaise: je passe beaucoup plus de temps a lire,
a auditer et a corriger du code qu'a en ecrire. Mais pour moi, l'idee
de pouvoir raisonner sur un programme, voire de pouvoir PROUVER des choses
sur celui-ci, c'est quelque chose qui a des TONNES d'applications tres
pratiques et immediates.

Oui effectivement c'est un biais. En plus je pense que tu dois être
multi-domaine. En pratique, dans un métier la variabilité du code est
plus réduite que ce que tu vois je pense.

sam.