Réflexions Sur La Complexité Algorithmique, Chapitre 2

Je ne l'ai pas lu mais il est effectivement long. Et il ne semble pas candidat à la scission. Si tu importes le premier chapitre de PDP, la question du type de contenu ne se pose AMHA plus.

Coucou Höd

J'ai lu jusqu'à la partie sur les Benchmark (c'est encore en rédaction, non?).

Tout d'abord j'ai trouvé ça très intéressant. Tu donnes des exemples pertinents et tu mènes une bonne critique du sujet. Le plan me paraît bon.

En soi, je ne considère pas ça comme du contenu donnant lieu à un tutoriel. On apprend pas vraiment à faire quelque chose, par contre on a appris à mieux réfléchir sur ce qu'on fait. Je suis donc assez partagé.

Sur ZdS je pense que ça aurait ça place en tant qu'article mais ça mérite quelque chose de plus intemporel à mon avis. Je trouverai ça dommage que ton article soit oublié en un mois, alors que tout est encore valable et mérite largement de l'attention.

Je pencherai donc pour un tutoriel.

Après j'ai peur que tu aies un problème à la validation. Déjà que mon petit tuto de DL semblait trop théorique, autant là on est largués si on s'accroche pas et si on s'y connaît pas du tout. Ta réaction de vouloir mettre des références pour le lecteur (est une excellente idée) me semble trop académique pour le public de ZdS.

En gros ça t'aide pas. Peut-être que ZdS n'est pas prêt à recevoir ce genre de textes ?

Après j'ai peur que tu aies un problème à la validation. Déjà que mon petit tuto de DL semblait trop théorique

Trop théorique pour qui ?

autant là on est largués si on s'accroche pas et si on s'y connaît pas du tout. Ta réaction de vouloir mettre des références pour le lecteur (est une excellente idée) me semble trop académique pour le public de ZdS.

Je ne pense pas qu'il soit nécessaire de s'auto-censurer ainsi sur ZdS. Les tutoriels n'ont pas vocation à être lus par tout le monde, juste par les gens que ça intéresse. Avec les moyens techniques appropriés, on pourra même expliciter des pré-requis pour les cours avancés. Pourquoi se priver ?

Lors de la première beta, (quasiment ?) tous les avis allaient dans ce sens.

Après si ça se trouve, plein de gens ont trouvé ça parfaitement adapté mais n'ont rien dit. Auxquels cas c'est pas malin parce que ça m'aurait aidé.

Après il ne s'agit pas de mon tuto ici.

Je ne dis pas qu'il faut se priver. Si Höd considère que ZdS est un bon endroit, libre à lui. Je partage juste mes doutes sur le niveau des lecteurs du site. Parce que « les gens que ça intéresse » seront peut-être pas assez nombreux. Et peut-être même pas présent dans l'équipe de validation (même si j'imagine qu'@dri1 doit pouvoir relire ça).

J'ai d'ailleurs fait un long topic (auquel Höd a participé de mémoire) sur la rédaction scientifique sur ZdS. Il manque énormément d'outils (faire des bibliographies et des tableaux de notations en font partie), c'est pour ce genre de raison que je crains qu'un tel contenu ne soit pas suffisamment bien mis en valeur.

D'ailleurs Höd a du se rendre compte pendant l'écriture qu'il est difficile d'énoncer une définition proprement dans le texte. Il ne s'en sort pas trop mal, mais on a toujours du mal à bien voir rapidement où ça commence et où ça se finit.

Bonjour à tous,

J'ai commencé (il y a 8 minutes) la rédaction d'un tutoriel dont l'intitulé est Réflexions Sur La Complexité Algorithmique, Chapitre 2 .

Je crois que tu m'impressionnes énormément là !

Blague à part, j'ai a peine eu le temps de survoler entièrement le tutoriel, mais c'est très intéressant, tout comme le chapitre précédent !

_{Et je ne vois personnellement toujours pas de soucis à un tutoriel plus théorique, que ce soit pour les développements limités ou la complexité algorithmique.}

Hello, très bonne initiative, un sujet pas facile à aborder tant il est vaste et théorique, mais très intéressant.

Une première remarque, sur le ton général de ton écrit : tu n'y vas pas de main morte. C'est une excellente chose d'expliquer qu'un algo polynomial peut être inefficace, et qu'un algo exponentiel peut être efficace, et l'exemple du Simplexe est parfait pour l'illustrer, mais certaines phrases sont énoncées de manière particulièrement audacieuses, comme celle-ci :

Par la suite on expliquera en quoi les etudes de complexites n'arrivent pas ou plus a caracteriser la difficulte d'un probleme ni a exprimer la qualite empirique des algorithmes.

En finissant la lecture, on en est quasiment à - bon, $P = NP$, finalement, on s'en fout - je caricature. C'est tout à fait possible que ce soit juste ta façon d'écrire le premier jet, mais je pense qu'un peu plus de nuance serait bienvenue. Il est bon de garder en tête comme règle générale qu'un algo polynomial vaut mieux qu'un algo exponentiel, même s'il faut faire attention en pratique et que ça n'est pas toujours le cas. En plus des intérêts académiques de la découverte d'un algo polynomial pour un problème - même s'il est inefficace -, un intérêt pratique de disposer d'algos polynomiaux est qu'ils passent mieux à l'échelle lorsqu'on augmente les performances des ordinateurs. Non seulement la taille des problèmes industriels augmente - ce qui pénalise plus les algos exponentiels, y compris le simplexe -, mais les performances des ordinateurs ne cessent de s'améliorer, rendant peut-être raisonnables dans quelques dizaines d'années des algos polynomiaux qui sont impraticables aujourd'hui.

Seconde remarque, sur le début du plan : j'ai l'impression que tu passes du coq à l'âne en présentant l'optimisation linéaire, puis en présentant les comparaisons d'algos et les différentes complexités, pour revenir à l'exemple du simplexe à la fin de Analyse lisse. Je ne suis pas encore certain de comprendre le rôle que tu veux faire jouer à l'optimisation dans ton texte, mais peut-être serait-il plus judicieux d'en discuter après l'introduction des différentes complexités afin d'utiliser alors le simplexe comme illustration ? Il serait alors plus facile de rebondir sur la programmation mathématique comme traduction des problèmes en langage mathématique qui permette d'étudier les caractéristiques intrinsèques du problème.

Enfin, quelques remarques plus techniques :

Remarquons par exemple que l'algorithme $A$ possède un nombre minimal d'opérations qui dépend de la taille de l'instance tandis que l'algorithme $C$ possède un coût minimal fixe de $5000$, qui correspond certainement à un pré-traitement indépendant de l'instance.

Sans doute une simple faute de frappe, mais qui a son importance : si le pré-traitement est indépendant de l'instance, pas de raison de l'inclure dans la complexité de l'algorithme, on le fait une fois quand on a le temps, on stocke le résultat et on en parle plus. Par contre si c'est un traitement qui est seulement indépendant de la taille de l'instance, et qu'il faut le refaire à chaque fois, c'est tout à fait justifié de l'inclure dans la complexité.

Ma dernière remarque est liée : c'est à propos de l'utilisation que tu fais régulièrement du terme "équivalent asymptotique", que je trouve impropre dans le sens où la complexité asymptotique que l'on exprime généralement avec un $O$ n'est pas un équivalent de la complexité au sens mathématique du terme. Et précisément, si on exprimait la complexité asymptotique sous forme d'équivalent et non de $O$ - c'est plus ou moins ce qui est proposé dans cet article pour des raisons qui incluent celle dont on parle - le piège serait, en partie, déjoué et on pourrait démasquer les algorithmes polynomiaux inefficaces et les algorithmes exponentiels efficaces - modulo les algos où des instances dégénérées rendent la complexité dans le pire des cas non représentative. De tout ce qui est masqué par l'utilisation du $O$, ce n'est pas la constante additive qui fait l'(in)efficacité de l'algorithme - elle devrait atteindre des niveaux galactiques pour poser problèmes aux ordinateurs actuels, mais bien plus la constante multiplicative.

Voilà, je ne me prononce pas sur la classification article/tuto, bon courage pour la suite de ta rédaction.

Pourquoi ne pas fusionner ce que tu as écrit avec ton premier article de réflexion sur la complexité, et transformer le tout en un big/moyen-tutoriel ?

Si je te fais cette suggestion, c'est simplement que ce que tu as écris est très dense : personnellement, j'ai saturé et abandonné la lecture au milieu du cours. Et ce n'est pas le contenu (qui ne parait très bon), ni la longueur du cours qui pose problème, mais vraiment le fait que le contenu est très serré, compacté. Aussi, pour améliorer la situation, je te conseillerais de :

• faire des paragraphes moins longs (4/8 lignes maximum) ;
• utiliser des titres 2 ou extraits avec des titres bien choisis ;
• éventuellement modifier le plan pour réorganiser tes idées (d'où ma suggestion).

Après, je ne dis pas que ton cours n'est pas adapté à ZdS, juste que sa forme et son organisation pourrait être rendue plus claire et plus lisible, indépendamment du contenu.

Je suis aussi d'avis que déplacer la partie sur l'optimisation linéaire juste après la description des problèmes des complexités, en seconde partie, pourrait être une bonne idée.

Voilà quelques remarques :

• Tu appelles $P$ un opérateur de perturbation aléatoire alors que c'est déjà la notation pour le problème posé ;
• pour le calcul quand $\sigma\to 0$, ce serait mieux de le mettre en centré ;
• il manque la note de bas de page un petit peu avant la partie sur la multiplication matricielle ;
• dans linéarité vs non-linéarité tu as mis $f: \Omega\mapsto Y$ au lieu de $f:\Omega\to Y$ !

Sinon c'était sympa

Quelques fautes de frappes et de français (mais de l'étourderie). J'ai pas pu relever mais ça se concentre sur la deuxième partie.

Juste une question : la ligne bizarre en tête de l'article, c'est un bogue ou pas ?

l'étude d'un problème par rapport à l'ensemble des algorithmes connus qui le résolve

résolvent

Il s'agit donc de caractériser la difficulté d'un problème au travers des méthodes de résolutions

résolution

consiste à essayer de caractériser la difficulté du problème par rapport à ses caractéristiques intrinsèques

"caractériser" et "caractéristiques", ça fait un peu répétition.

qu'il faut pouvoir trouver un langage commun d'expression des problèmes et ce langage est la mathématique et plus précisément

J'ajouterais une virgule : "ce langage est la mathématique, et"

Le terme programmation n'a ici rien à voir avec l'informatique

Peut-être faudrait-il mettre des guillemets (français quitte à faire) autour de "programmation".

tout comme le terme recherche opérationnelle

Idem.

notamment pour l'élaboration du plan optimal de gestion de certaines ressources, c'est-à-dire rechercher la meilleure façon d'opérer

"rechercher", en tant que verbe, ne convient pas. Ou bien "élaborer", ou bien "la recherche".

Dans cet article on tâchera de montrer qu'une très vaste partie des problèmes qui peuvent se poser sous la forme d'un problème d'optimisation

Il y a un "qui" en trop et "peuvent" devrait être au singulier.

Par la suite on expliquera en quoi les études de complexités

Je ne suis pas certain, mais peut-être y a-t-il un "s" en trop à "complexités".

difficulté d'un problème notamment au travers de l'évolution des attentes

"difficulté d'un problème, notamment" plutôt ?

la difficulté d'un problème notamment au travers de l'évolution des attentes des performances des algorithmes, ainsi que les facteurs influençant sur la qualité empirique des algorithmes

La phrase ne se tient pas. Je pense que c'est plutôt "ainsi que des facteurs".

on donnera quelques pistes supplémentaires pour faire lien

"le lien" ?

Si la première partie de mes réflexions

Le "je" contraste un peu avec le "on" employé au-dessus.

caractériser les performances d'un algorithme et donc à fortiori

"a fortiori".

Les n variables dites de décisions

"décision" ?

∀1≤i≤m

Le ∀ fait bizarre, mais je ne suis pas un expert.

b∈R

C'est $b_{i}$.

Avec A∈M^m×n

Tu ne précises pas que la matrice est réelle ?

On résume tout cela dans le tableau suivant

Il n'y aurait pas une colonne (la seconde) en trop ?

combien de chaque modèle d'avion doit on

"doit-on"

On appelle x1 et x2 les quantités d'avions à produire, respectivement du modèle A et du modèle B

Du coup, $x_{A}$ et $x_{B}$ ?

et l'on cherche donc à maximiser f(x1,x2)=5x1+11x2

Plus haut, tu parlais de minimisation.

Par rapport à la forme matricielle, nous aurions

Du coup, on ne peut pas représenter les contraintes de positivité sous forme matricielle ? On pourrait dans la définition du problème ajouter un truc du genre : $d \leq Bx$.

De plus, pourquoi n'inclus-tu pas la contrainte $x1+x2 \leq 20$ dans $A$ ?

Comme nous n'avons que deux variables de décisions

Je me mets à douter là : "décision" ?

il est possible de visualiser les contraintes comme montré sur la figure suivante. Chaque contrainte

Ne serait-il pas judicieux de mettre la figure après la fin de la phrase, i.e. avant les explications ?

dans le cas où les contraintes sont antinomiques

J'ai appris un mot.

ou réduit à un point, voire infini

J'imagine que le "voire infini" se rapporte au domaine ? Je le mettrais avant le "soit vide", parce que l'apparté "dans le cas où les contraintes sont antinomiques ou réduit à un point" le coupe du sujet.

il ne nous faut pas construire 20 mais seulement 18 avions

Je dirais plutôt : "il ne nous faut pas construire 20 avions mais seulement 18".

Il existe plusieurs méthodes pour la résolution de problème d'optimisation linéaire

Plutôt : "Il existe plusieurs méthodes pour la résolution d'un problème d'optimisation linéaire"

et si nous renvoyons

Dans l'avant-propos, tu as employé le "on" : "Dans cet article on tâchera".

Proposé par Dantzig en 1947, la méthode du simplexe

"Proposée"

une complexité dans le pire des cas qui est exponentielle

"une complexité qui est exponentielle dans le pire des cas"

les performances empiriques sont excellentes au point qu'il s'agit encore aujourd'hui d'une méthode très utilisée

"les performances empiriques sont excellentes, au point qu'il s'agit encore aujourd'hui d'une méthode très utilisée"

À contrario

A contrario

mais pourtant elle est inefficace

"mais s'avère inefficace"

Karmarkar propose en 1984 une variante de la méthode des points interieurs

"intérieurs"

qui soit à la fois efficace théoriquement et en pratique

Je crois que le subjonctif ne va pas.

Il s'agit notamment de rétablir ce qu'est exactement un comportement asymptotique

"rétablir" fait un peu bizarre. C'est la première fois que je le rencontre en tout cas. Plutôt "rappeler" ?

Pour un problème P, on note Π l'ensemble des instances possibles.

C'est quoi une instance ?

En lisant la suite on devine, mais une définition ne mangerait pas trop de pain.

Nous nous donnons deux algorithmes, A et B

La virgule fait bizarre. Ou alors il en faudrait une derrière "B".

Dans le cas où Π ne contient qu'une instance π, alors on peut comparer

Le "alors" me semble de trop.

en observant le comportant sur π:

comportement

Il manque un espace derrière le $\pi$.

Dès lors il est impossible a priori

"a priori"

d'obtenir une relation d'ordre total

"totale". Quoique, on pourrait parler de l'ordre. La définition 3.0.19 de ce cours attache l'adjectif à "relation".

nous manquons de précision en omettant que nous prenons pour référence la complexité dans le pire des cas, mais en plus, on fait naître

nous/on

La mesure de la complexité dans le meilleur des cas se définit symétriquement par rapport à la notion dans le pire des cas:

Il manque un espace entre "cas" et ":".

Étude d'un exemple

Le titre devrait être de taille 3 (comme "Pire des cas" et "Meilleur des cas"), non ? En effet, l'exemple ne concerne pas uniquement le meilleur des cas.

que l'on peut résumer par le tableau suivant:

Idem.

Quel que soit l'instance considérée

Quelle que soit

à un pré-traitement indépendant de la taille l'instance

"de l'instance"

elle peut cependant être importante pour des instances de petites tailles

Je ne suis pas certain qu'il faille mettre "petites tailles" au pluriel.

Voyons maintenant les différences qu'il peut exister entre la complexité exacte et la complexité asymptotique.

Peut-être devrais-tu ajouter la seconde dans le tableau.

De plus, il pourrait être intéressant d'ajouter des légendes à tes images pour indiquer de quel algorithme il s'agit. Tu pourrais aussi légender tes axes (taille de l'instance, nombre d'opérations).

Dans le cas de l'algorithme C, on dispose également de deux plages de taille d'instances différentes

J'avoue que je suis perdu au niveau du pluriel ici. Plutôt "de deux instances de tailles différentes" ?

Dans le cas de l'algorithme C, on dispose également de deux plages de taille d'instances différentes, ce qui nous permettra de visualiser certains défauts de la complexité asymptotique pour l'évaluation pratique de la performance des algorithmes.

Je placerais cette partie juste au-dessus des graphes associés à $C$.

quel que soit la plage de valeur de la taille des instances considérées

"valeurs"

À contrario, dans le cas de l'algorithme B

A contrario

est toujours majorée par la valeur exacte

"majoré"

cela est moins problématique comme on le vérifiera par la suite.

"cela est moins problématique, comme on le vérifiera par la suite."

C'est ce que l'on peut observer sur les deux figurent qui suivent

Là encore, je les mettrais avant les remarques. De plus, tu étiquettes tes courbes avec $f$, $g$ et $h$, mais parles des algorithme $A$, $B$ et $C$. Il n'est pas difficile de faire la correspondance (cf : le tableau), mais c'est pas très pratique pour le lecteur.

Il y a plusieurs remarques à faire:

Espace.

Ceci permet de mettre en évidence la définition même de la complexité asymptotique:

Idem.

tandis que l'algorithme C, il faut attendre plus longtemps

"tandis que pour"

Et voici où la complexité asymptotique échoue:

Espace.

peut être largement faussée tout comme la comparaison

"peut être largement faussée, tout comme la comparaison"

c'est-à-dire de l'OGA est totalement passé sous silence

"passée"

avec pour effet de rendre la comparaison d'algorithmes impossibles

"impossible"

d'algorithmes impossibles à priori comme

a priori

J'ai relu jusqu'à la fin de "Mesures de complexité d'un algorithme/Étude d'un exemple". La suite un de ces quatre.

Certaines remarques sont des broutilles et je te laisse juger de leur pertinence.