Réflexions Sur La Complexité Algorithmique, Chapitre 2

Je prends enfin le temps de te repondre. A ma decharge, la somme des remarques et des corrections est impressionnante et pour ca je ne peux que te remercier une nouvelle fois.

Pour alleger un peu, je ne reponds pas aux remarques orthographiques, typographiques, et autres, qui sont acceptees et deseormais corriges, pas plus que certaines petites remarques que je n'ai pas juges pertinentes (elles sont peu nombreuses et concernent juste le style parfois). Tes remarques ont aussi parfois amener a modifier une phrase ou deux au dela de celles-ci.

Remarque generale sur les locutions latines: a contrario, a fortiori, a posteriori, a priori ont une forme francisee correcte depuis la reforme orthographique de 1990. C'est celle-ci que j'utilise et je pense etre coherent dessus. Du coup, pas d'italique et des accents, sauf pour de facto dont je n'ai pas trouve dans le dictionnaire qu'elle a ete francise.

∀1≤i≤m

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

C'est une forme contractee, pas forcement des plus jolies pour "quelque soit i entre 1 et m". Je n'ai pas corrige mais il faudrait que je le fasse.

Avec A∈M^m×n

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

En general on le sait. Si c'est autre chose, on le precise et par ailleurs, le probleme porte souvent un nom different. Par exemple, sur $\mathbb{Z}$ on parle d'optimisation lineaire en nom entier et le probleme n'est plus aussi simple, c'est meme tout le contraire ! J'ai tout de meme modifie pour eviter d'avoir a revenir dessus.

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}$ ?

Bien vu. Des fois avec la tete dans le guidon on fait des petites choses pas coherentes ou disons pas les plus simples.

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

Plus haut, tu parlais de minimisation.

Minimisation ou maximisation, c'est la meme chose. maximiser $f$ c'est minimiser $-f$. J'ai tout de meme rajoute entre parentheses plus haut "ou maximisation". En fait dans les cours on etudie toujours ou presque, dans la theorie, la minimisation (sauf a passer dans le dual ou la maximisation peut apparaitre) et c'est seulement en pratique qu'on a l'un ou l'autre.

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$.

On peut toujours. En fait, dans le cas general, tu as des contraintes superieur ou egal, superieur strict, inferieur ou egal, inferieur strict, et egal. Mais on peut montrer que l'on peut toujours se ramener a la forme que je donne qu'on appelle generalement la forme canonique ou la forme standard (je ne sais jamais laquelle est laquelle et il me semble que cela varie d'un pays a l'autre en plus…). Voir ici.
Je n'ai pas voulu en parler car cela ne presente qu'un interet limite dans le cadre de l'article.

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

C'est un oubli corrige.

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 ?

J'ai remonte la figure d'un paragraphe. Du coup on voit la figure sous le paragraphe sans scroller et on n'a pas d'image juste sous un titre, ce qui me parait une bonne pratique de mise en page.

une complexité dans le pire des cas qui est exponentielle

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

Oui et non. Dans l'absolu tu as raison et cela serait comprehensible, mais ici comme le sujet c'est vraiment de parler des differentes notions de complexites, je considere l'expression 'complexite dans le pire des cas' comme insecable.

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" ?

J'ai reformule mais l'idee c'est bien de retablir. En effet, la complexite dans le pire des cas est normalement utilise pour mesure la scalabilite d'un algorithme, notamment vis a vis d'un autre algorithme. Le fait qu'on l'utilise pour essayer de comparer des temps de calculs reels ou qu'on considere qu'il s'agit d'une bonne indication du temps de calcul est une erreur et il faut pour la corriger retablir le vrai sens de 'comportement aymptotique'.

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.

C'est vraiment tres tres standard et la je renvoie a la premiere partie (qui finiront un jour par fusionner).

"en théorie de la complexité, une instance d'un problème est obtenue en spécifiant des valeurs précises pour tous les paramètres du problème." Par exemple, l'exemple de plan de guerre est une instance du probleme d'optimisation lineaire.

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

Tant qu'a faire, autant corriger le correcteur. En typographie espace est un mot feminin, donc une espace. Je te dois bien ca.

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".

Effectivement. Dans ma tete c'est l'ordre qui est total, on peut ordonner totalement les objets selon la relation mais ce n'est vraisembablement pas la regle grammaticale a adopter et donc je me suis aligne sur le reste du monde. :')

É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.

J'ai modifie le titre pour montrer que c'est un exemple pour etudier l'encadrement du nombre d'operation que l'on vient d'etablir. Pour le coup, avec ce titre plus explicite, j'ai pu passer le paragraphe au niveau 3. Je pense que c'est plus clair ainsi.

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.

J'ai peur que cela ne rentre pas. Et cela fera reflechir le lecteur, aka, comment reporter sa flemme sur le lectorat.

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).

Comme il y a plusieures defauts sur les images, je vais devoir effectivement les refaire. Ce n'est pas un soucis vu qu'il d'agit de scripts GnuPlot et donc elles peuvent etre regenerees en une seconde, mais comme l'import, la mise a jour et l'insertion des images dans les tutoriels sur ZdS est affreuse, ce sera vraiment la derniere chose que je ferais.

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" ?

J'ai mis le different au niveau de plages. Ce sont bien les plages des tailles qui sont differentes. D'un cote tu as des instances de tailles inclues dans un intervale et de l'autre des tailles incluses dans un autre intervale.

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$.

Rejete mon capitaine. Le but de ce petit paragraphe est de presenter les graphes dont on dispose et que l'on va decrire. Cela perd tout son sens de le mettre ensuite.

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.

Je vais refaire les images en utilisant $T_A$ par exemple. Comme cela ce sera plus consistant avec la notation et plus facile a suivre.

C'est qui $S$ ? Le sous-ensemble des instances pratiques ?

C'est $\Pi$.

Par exemple si l'on génère de manière aléatoire des tableaux à trier

Tu donnes un exemple artificiel, c'est ça ?

Oui. Et un exemple tout court par ailleurs.

Comme le calcul exact est rendu impossible mais aussi inutile

Pourquoi inutile ?

J'ai retire le inutile, mais en general avoir un calcul exact sur le nombre d'operations pour ensuite devoir faire des hypotheses incertaines sur la distribution de probabilite des instances, cela me pousse a dire qu'on s'est embete pour rien.

on préférera une approche empirique

Je donnerais un exemple. Notamment, je ne comprends pas trop ce que signifie "en phase d'exploitation".

Je donne des exemples de phase d'exploitation: par exemple au niveau d'Amazon ou de notre petit libraire. C'est a dire que tu ne connais pas theoriquement la distribution de probabilite des instances par rapport a une situation reelle (une entreprise utilisant l'algorithme pour ses besoins = phase d'exploitation). Par contre, tu peux l'estimer au fur et a mesure que tu as des instances qui se crees (chaque jour tu observes le nombre de commandes, la localisation des gens, etc), ce qui te permet empiriquement de connaitre cette distribution.

Je chipote, mais le nombre d'éléments n'est pas vraiment comparable à la mémoire: élément $\neq$ case mémoire.

Il en découle qu'on peut très bien avoir $t < c$ mais ne pas pouvoir ajouter d'élément dans le tableau. C'est le cas si $c - t < M$, où $M$ désigne la mémoire nécessaire pour stocker un élément.

Mais c'est vraiment pour chercher la petite bête.

Je ne suis pas d'accord. Quand on parle de capacite dans le cas d'un tableau dynamique, on parle de la taille memoire qui a ete allouee en fonction de la taille des elements du tableau et on se moque en realite de la taille de chaque element. C'est ainsi que en C++ ont fait la difference entre '''capacity''' et '''size''' pour un '''vector'''. La taille etant le nombre d'elements effectivement stockes dans le tableau alors que la capacite etant le nombre d'element qui peuvent tenir dans le tableau car la memoire est deja allouee pour cela. Par ailleurs, on utilise '''reserve''' en C++ pour justement dire de reserver autant de memoire que necessaire pour $n$ objets. Jamais on ne parle de la taille de l'objet, tout est calcule derriere, en coulisse.

La première politique consiste à simplement ajouter 1 à la capacité

Ou : incrémenter la capacité

En typographie francaise les nombres qui ne comportent qu'un chiffre doivent s'ecrire en toutes lettres. Mais au final j'ai utilise incrementer, c'est plus hype.

Il est évident que la première politique est optimale en terme de capacité: aucun espace mémoire n'est jamais inutilisé.

J'ai eu du mal à comprendre cette phrase avant de me rendre compte que les abscisses représentaient le nombre d'éléments dans le tableau. Tu devrais le préciser, même si ça parait évident.

Cela fait partie des choses que je dois refaire sur les illustrations.

le nombre moyen d'opération à 2,5 tout en augmenter légèrement la capacité moyenne

augmentant

Le tout en a un sens de en meme temps ici.

les politiques additives sont peu scalables

J'expliquerais un peu ce terme. En note par exemple.

Quel terme ? Scalable ou additive ?

maintenir une partition d'un ensemble en classes qui sont disjointes

Je ne comprends pas. C'est quoi une classe ? Que signifie "maintenir une partition" ?

Une classe est un objet mathematique, proche de l'ensemble. En general, j'aurais pu dire un ensemble mais cela aurait ete assez imprecis car pour le coup, c'est vraiment une classe. Il faut lire la phrase jusqu'au bout : maintenir une partition en classes disjointes.

l'implémentation est libre

Cela signifie qu'il en existe plusieurs ?

Oui et j'en donne plusieurs exemples : liste chainees, arbres avec plusieures heuristiques differentes.

Sans plus d'information, l'implémentation est libre mais va entrainer des complexités différentes. C'est ainsi qu'une implémentation triviale utilisant des listes chaînées pour la représentation des classes aura une complexité amortie en O(m+nlog n) lorsque l'on effectue m appels successifs à Union puis Find sur n éléments.

Complexités différentes -> C'est ainsi -> un seul exemple de complexité.

Voir ma remarque plus haut. Je donne 3 complexites differentes sur 3 exemples differents d'implementation.

La fonction d'Ackermann est une fonction qui croit tellement vite que l'on peut considérer que son inverse vaut quatre quelle que soit la valeur de n.

C'est pas plutôt "inférieure à 4" ?

Ou egal. Mais oui.

En effet, la fonction d'Ackermann au point (4,4)

Au point ? On ne lui donne pas des réels ?

La 'vraie' fonction d'Ackerman a deux parametres (n,m). Maintenant, sur union-find on a la transformation N -> NxN avec n -> (n,n). Mais c'est du detail qui est peu interessant.

Et si l'on renvoie le lecteur à la littérature pour plus de renseignement sur Union-Find et la démonstration de la complexité amortie associée, l'exemple est donné pour prendre conscience de l'écart entre ce que prédit la complexité dans le pire des cas et le comportement en pratique, représenté par la complexité amortie.

Je ne comprends pas la logique de la phrase.

D'un cote on renvoit le lecteur a la litterature, et de l'autre on justifie cette si breve introduction par l'interet d'observer l'écart entre ce que prédit la complexité dans le pire des cas et le comportement en pratique, représenté par la complexité amortie.

Supposons que l'on puisse métriser l'espace

Le verbe "métriser" existe-t-il vraiment ?

Si non, il vient d'etre invente. Il y a metrisable qui existe deja, peut etre pas dans les dictionnaires, mais comme terme technique, donc bon, je me permets cette petite liberte.

De plus, juste après, il ne me semble pas que tu aies défini $\delta$.

C'est fait, mais on comprend avec Markov normalement. Ca mange pas de pain.

Notons par ailleurs que l'algorithme du Simplexe

J'indiquerais entre parenthèses que tu fais référence au problème d'optimisation linéaire. D'ailleurs, tu n'as pas mis de majuscule à "simplexe" la première fois.

Si le lecteur a tout lu je pense qu'il n'y a pas de soucis a ne pas le preciser (vu que le Simplexe ne resout que le probleme d'optimisation lineaire par ailleurs). Par contre, j'ai mis une majuscule partout.

De plus, ce n'est pas vraiment la complexité, mais plutôt le nombre d'opérations, non ?

Synonyme. La complexite represente un nombre d'operations.

Si l'OGA indique que B est meilleur que B, la réalité n'est pas tout à fait aussi clair

Ca doit être cool d'être meilleur que soi-même.

C'est un style de vie. Deal with it. 8-)

Soit f:Ω→Y, alors

La virgule fait bizarre. Je ferais : "Soit Ω, un espace dit des variables de décisions, X⊂Ω une partie de l'espace de décision souvent appelé espace admissible, Y un espace totalement ordonné appelé espace objectif, souvent R, et f:Ω→Y. Alors".

J'ai pas encore corrige mais tu as raison. Je laisse ca ici pour ne pas oublier.

le problème de minimisation consiste à minimiser f sur X

Et si le minimum n'existe pas ?

Le probleme consiste a minimiser ; l'existence sur une instance particuliere, c'est une autre histoire. Plus particulierement, c'est une etape.

Un exemple de chose qu'on voudrait optimiser ici (i.e. un exemple de fonction $f$) ?

Disance du chien au pilier. Du coup c'est le cercle limite qui est solutio. Toute la frontiere du domaine est solution.

La question peut faire sourire, mais il existe bien des problèmes où l'existence même d'une solution n'est pas facilement démontrable !

Tu pourrais au moins nous fournir une petite note là-dessus !

En l'absence d'hypothese sur l'ensemble admissible ou sur la fonciton objective le probleme d'optimisation n'admet pas de solution. Des contre exemples generaux ont ete batis par Murat. Ensuite, les resultats d'existences se font au cas par cas, et en parler plus reviendrait a donner un cours d'analyse fonctionnel et un cours d'optimisation complet malheureusement.

plusieurs éléments de X donnent la valeur optimale pour f

minimale, non ? Ou alors il faut généraliser plus haut.

Optimale dans un contexte general d'optimisation. C'est compatibible avec le terme minimale puisque comme le probleme est un probleme de minimisation, alors la valeur optimale est une valeur minimale.

l'existence de plusieurs modes est caractéristique de problèmes plus difficiles que les problèmes n'ayant qu'un mode

Mode = solution ? Ce qui est plus difficile, c'est de les trouver toutes, pas le simple fait qu'elles existent, si ?

Cela depend de ce que tu consideres comme une solution. Certains s'interessent a la valeur optimale de la fonction, et d'autres a l'ensemble des elements qui realisent cette valeur. C'est meme plus complique car il est possible dans certains cas d'obtenir les valeurs optimales sans les elements qui realisent cette valeur. Le graal serait de trouver tous les elements qui realise la valeur optimale mais c'est le cas le plus complique et justement souvent inextricable.

problèmes multi-objectifs qui sont de facto multi-modaux

Pourquoi ? Je peux avoir plusieurs objectif et une unique solution les satisfaisant tous, non ? D'ailleurs, tu dis juste après : "il n'existe pas en général une solution".

Dans des cas particuliers tu peux n'avoir qu'une solution (les objectifs ne sont pas antinomiques), mais en general non, tu auras un ensemble de solutions qui sont des compromis. D'ailleurs en optimisation multi-objectif tu n'as pas de valeur optimale mais des valeurs optimales. En effet, le concept de solution lui meme est modifie et on utilise le concept d'optimalite de Pareto. Voici un petit exemple sur deux objectifs: quelle est la meilleure solution entre $(3,5)$ et $(4,2)$ ? Impossible a dire en l'etat. On dit qu'aucune de ces solutions ne domine l'autre car pour passer de l'une a l'autre tu dois necessairement degrader un objectif.

En général les méthodes adoptées pour résoudre ces problèmes sont des suites itératives xn dont on espère beaucoup de propriétés

Exemple ? Tu parles plus bas de la méthode de Newton, tu pourrais développer un peu. Notamment faire le lien avec le fait de vouloir minimiser une fonction. Concrètement, je ne vois pas ce qu'une suite vient faire là. J'ai ma petite idée, vu que je connais un peu la méthode de Newton, mais sans ça on ne voit pas le rapport avec $f$.

Cela m'amenerait a faire un court d'optimisation, mais typiquement on dit qu'une suite $(x_n)$ est une suite minimisante de f sur X si la limite de f(x_n) lorsque n temps vers l'infini est egale a la valeur optimale de f sur X. On montre ensuite que cette suite existe, on essaye de la construire, etc.
La encore, on montre qu'en dimension finie sur les convexes tout va bien, une telle suite existe toujours (en dimension infinie il y a des hypotheses de compacites meme sur les convexes fermes), etc. Bref c'est vraiment une etude de topologie sur le domaine de definition et sur les proprietes de f.

https://w3-connections.ibm.com/wikis/home?lang=en-us#!/wiki/Wa21e1750cc61_4ffa_83aa_7216382fb550/page/Platform%20Management%20High%20Level%20Architecture

Avec un beau contre-exemple en dimension infini meme sur un ferme borne.

Une fiche rappel: https://www.ljll.math.upmc.fr/~charles/pperso/docs_enseignement/optimisation1.pdf

Je reformulerais, parce que tu ne dis pas assez clairement que linéarité = simplicité. Plutôt : "La linéarité influe sur la difficulté intrinsèque d'un problème, les problèmes linéaires étant les problèmes faciles à résoudre, et durant des années on a pensé qu'elle constituait le facteur majoritaire. Cependant,".

C'est surtout que ce n'est pas la linearite en tant que telle qui donne la facilite. C'est le fait que l'intersection d'hyperplan est un convexe ferme. C'est vraiment parce que les problemes lineaires sont des problemes convexes qu'ils sont faciles.

Je ne comprends pas le "dont il résulte". Tu parles de $X$ ? Je dirais plutôt "dont il est une partie".

C'est une partie certes, mais je voulais exprimer le fait que X est le resultat de Omega sur lequel on applique des contraintes. C'est un peu un travail d'usinage: en partant d'un gros bloc brut de materiau, tu extrudes, retires de la matiere, pour obtenir un sous ensemble.

L'exemple de programme d'optimisation linéaire permet d'obtenir un domaine X sous la forme d'un polytope, donc convexe par définition.

Pourquoi parler de convexité tout à coup ?

Pour pouvoir aborder la convexite vu que c'est ce qui rend le probleme d'OL facile.

Ainsi, en étudiant la topologie du domaine X

Le "ainsi" ne se tient pas. Tu n'as fait que dire que les domaines pour la guerre et le chien étaient convexes, pas que cela rendait le problème plus simple.

J'ai reformule.

On parle bien de la convexité de $X$, l'espace admissible ?

Toujours oui.

http://zestedesavoir.com/media/galleries/1822/ab4b7132-3148-427b-96cf-83dd9aeb6a6d.png.960x960_q85.png

Une petite légende pour dire qu'à gauche c'est convexe, mais pas à droite.

TODO.

Pourquoi a-t-on l'existence et l'unicité ? Un disque ouvert (convexe) dans $\mathbf C$ n'a pas de maximum (en module), si ? Et un disque fermé en a plusieurs.

Il y a forcement unicite de la valeur optimale. Il peut y avoir plusieurs valeures qui realisent ce minimum. Une hypothese implicite de l'article est qu'on travaille en dimension finie et avec des fermes.

les problèmes non convexes sont fondamentalement difficiles

J'imagine que c'est pas évident d'expliquer pourquoi ?

Je pense que j'ai donne des elements de reponses ici.

En particulier, il est possible de séparer un singleton de la frontière d'un convexe avec le reste du convexe.

Je ne comprends pas trop le schéma là. Celui de droite est un contre-exemple ?

Oui, contre exemple sur un ensemble non convexe.

En somme, on aurait plutôt :

Une version plus faible, ne supposant pas l'ouverture de A, permet d'obtenir le même résultat de séparation, mais par un hyperplan qui n'est pas nécessairement fermé. En particulier, il est possible de séparer un singleton de la frontière d'un convexe avec le reste du convexe.

Dès lors, on peut définir la notion d'hyperplan d'appui, et de fil en aiguille, définir le sous-différentiel en un point de la frontière du convexe comme l'ensemble des coefficients des pentes des hyperplans d'appui en ce point. Il ne s'agit pas d'entrer plus dans les détails, cet article concernant avant tout la complexité algorithmique, mais plutôt de donner quelques pistes de recherches pour le lecteur désireux d'en savoir plus.

Au contraire, sur des espaces non-convexes, on peut trouver des points de la frontière pour lesquels le sous-différentiel n'existe pas, tout simplement car il n'existe pas d'hyperplan d'appui, comme illustré sur la figure suivante.

TODO

multi-objectifs

Non, optimisation multiobjectif (ou avec le tiret).

Dans un tel cas, la particularité est que l'on cherche l'ensemble des points de la frontière

Pourquoi juste sur la frontière ?

Frontiere de Pareto, ce sont les points non domines, donc qui realisent un equilibre de Pareto. En fait, projete X dans l'espace objectif, et tu obtiendras un ensemble, convexe ou non. Les points non domines au sein de cet ensemble sont necessairement sur la frontiere. L'exemple montre la difficulte a atteindre les zones concaves via une fonction d'agregation.

D'ailleurs, j'ignore ce qu'est un équilibre de Pareto.

J'ai mis un lien dans l'article, rien de bien complique a comprendre.

Il est écrit $F$ alors que tu as mis $f$ dans le texte.

Parce que je n'ai pas fait l'image et que je voulais rester coherent avec mes notations.

Pourquoi $\omega_{1}$ ne va pas jusqu'à $1$ ?

Par choix de l'auteur, surement pour des questions de visibilite.

Je ne comprends pas ce que sont les droites qui bougent.

La droite passant par l'origine n'est la que pour reperer la seconde comme combinaison convexe des objectifs. La seconde montre l'evolution de la fonction objective en fonction des valeurs de omega. Le cercle est le point de contact que l'on obtient en rapprochant autant que possible la droite de l'ensemble. On voit bien qu'en faisant cela on ne pourra jamais toucher les parties concaves.

Pourquoi $f_{1}$ et $f_{2}$ sont comprises entre $0$ et $1$ ?

Par choix de l'auteur. Arbitraire. Enfin pas tout a fait, il y a des raisons techniques a la normalisation des objectifs dans bien des cas, mais ce n'est pas le propos.

dans lesquels les algorithmes habituels vont être piégés, comme c'est le cas de l'algorithme de Newton

Il faudrait vraiment que tu développes cet exemple (cf plus haut).

Je ne sais pas trop, ca me parait le truc classique que l'on voit avec Newton. Si on n'a pas vu comment Newton echoue, on a pas vu Newton (8-)). Newton est une methode locale, elle utilise de l'information locale. La suite de la methode n'utilise que le gradient au point ou elle se trouve a un instant donne. De fait, imagine un plan avec a divers endroits des creux, plus ou moins profonds. Si tu demarres la methode proche d'un des creux les moins profonds, la suite va converger tout au fond de ce creux puisque c'est ce qu'indique la direction du gradient. Au fond du trou (pauvre suite), le gradient est nulle, la suite ne bouge plus. Pourtant elle n'est pas dans le bon creux. D'ailleurs les methodes a base de voisinage explore l'environnement directement autour d'eux, avec divers strategemes pour dejouer ce genre de choses, mais on comprendra qu'il faut regler ces parametres.

Comme nous l'avons vu, la notion pertinente pour caractériser la difficulté d'un problème est la notion de convexité

"une notion pertinente" plutôt, non ? Après, il ne me semble pas qu'on ait vu que la convexité impliquait la simplicité. Tu as donné un exemple illustrant le fait que la non-convexité impliquait la difficulté, mais tu n'as pas dit grand chose sur la convexité, c'est qui est normal, vu que tu as écrit : "Il ne s'agit pas d'entrer plus dans les détails, cet article concernant avant tout la complexité algorithmique, mais plutôt de donner quelques pistes de recherches pour le lecteur désireux d'en savoir plus.". Du coup, aurais-tu une source précise concernant le lien entre simplicité intrinsèque et convexité (une source sur les hyperplans d'appui j'imagine) ?

Il faut que je reflechisse plus a cela.

et non non pas celle de complexité des algorithmes pour le résoudre

Non, non, non, non, je ne veux pas t'oublier !

Comme le pourrais-tu ? 8-)

si l'optimisation continue est en générale plus facile que l'optimisation combinatoire

Je ne connais personnellement pas ces termes.

Si les variables a optimiser sont continue ou discrete (on parle de combinatoire dans le dernier cas).

autrement dit, une variance faible.

La phrase ne se tient pas. Il manque un "avec", non ?

C'est bien le fait que cela varie peu qui indique une variance faible.

fonction objectif

Je ne crois pas que tu aies employé ce terme précédemment. J'imagine que c'est la fonction à minimiser ?

C'est effectivement la fonction a optimiser.

"fonction-objectif" ?

Oula malheureux ! Il y a des bornes a ne pas franchir. 8-)

pour la transformation de la fonction objectif par une fonction strictement monotone

C'est un peu lourd, non ? Plutôt "pour la transformation par une fonction strictement monotone".

C'est lourd mais c'est minimal. C'est bien une transformationb de la fonction objectif. Il faut vraiment separer les deux types de transformation.

espace de recherche

Il s'agit bien de $X$ ici ?

Oui. En fait en optimisation, selon la branche ou le point de vue il y a plusieurs termes pour un meme concept. espace de recherche car on recherche la solution dedans ou espace admissible car les solutions dedans respectent les contraintes du probleme. On a de plus en plus tendance a privilegier espace de recherche lorsque l'on n'etudie pas les proprietes des contriantes et donc que l'on essaye de faire des methode generales ou selon la topologie de l'espace X.

Il faudrait des exemples concrets (genre avec une guerre ou un chien) de transformation de la fonction objectif et de l'espace de recherche. Là, je ne vois pas du tout comment ça marche en pratique.

Pour un exemple ca ne peut pas se faire pour une instance particuliere mais pour un probleme. Dans le cas d'un probleme d'optimisation quelconque, il se peut que ton algorithme soit performant sur une fonction a optmiser $f$ mais mauvais sur $g$, qui representent chacune une instance differente du probleme, toute chose egale par ailleurs. Imagine qu'il existe une transformatoin (par exemple tout betement une translation) T pour passer de f a g c'est a dire que g = Tf. Si tu as montre que ton algorithme est invariant par ce type de transformation ou celle-ci en particulier, alors tu peux affirmer sans meme tester que ton algorithme sera aussi performant sur f que sur g. En general il sera aussi performant sur f que sur T^{n f et si on parle pour une classe de transformation (toute les translations par exemple et pas juste celle ci), alors ca sera encore plus large: ton algorithme sera aussi performant sur f que sur T}n f pour tout T qui soit une transformation de type translation.

C'est aussi important pour montrer qu'un algorithme est performant meme sur des cas pathologiques. Le top c'est vraiment l'invariance par fonction monotone: optimiser x^{2 ou 3x}0.2-100 est exactement la meme chose pour l'algorithme.

l'opérateur de perturbation est une transformation particulière, aléatoire notamment

Pourquoi "notamment" ?

Parce que ce n'est pas sa seule propriete.

à moins d'exploiter l'information disponible au niveau d'un problème particulier, il n'existe pas de métaheuristique qui soit intrinsèquement meilleure qu'une autre

Mais du coup, une telle métaheuristique sera moins efficace sur les autres problèmes et s'éloignera un peu de son caractère de métaheuristique, non ?

Non puisqu'une metaheuristique est une methode qui peut resoudre un vaste panel de problemes. La question de la performance est subsidiaire. Pour tirer le meilleur d'une meta sur un probleme donne voire une instance, il faut regler ses parametres effectivement. Et la encore, on a pas forcement la garantie qu'elle sera meilleure qu'une autre.

http://zestedesavoir.com/media/galleries/1822/5d0b4109-e8b4-41a5-b9e2-9d4209696557.png.960x960_q85.png

Une légende me semble nécessaire. On comprend, mais quand même.

TODO

on obtient déjà un espace de configuration de taille

J'ai pas compris comment tu obtenais ce calcul.

J'ai 90 valeurs pour le premier parametre, 11 pour les deux derniers. L'ensemble des reglages possibles c'est 90 x 11 x 11. Une configuration serait par exemple $(50, 0.1, 0.5)$.

On ne peut pas en tirer beaucoup d'information que la classe de complexité d'un algorithme, et ainsi les conséquences sur la dynamique des performances en fonction de la taille du problème.

Le "ainsi" me paraît bizarre. Ca se comprend mais je ferais plutôt comme ça : "On ne peut pas en tirer beaucoup plus d'informations que la classe de complexité d'un algorithme et que les conséquences sur la dynamique des performances en fonction de la taille du problème.".

Non car la classe de complexite d'un algorithme indique la dynamique des performances en fonction de la taille. C'est un "donc".

et les algorithmes non efficaces, voire dans le pire des cas, aucun algorithme efficace ne peut exister

Qu'entends-tu par "efficace" ?

Plein de choses, c'est pour ca qu'il est en italique. Normalement le lecteur a pu s'appercevoir en conclusion que la notion d'efficacite renforme beaucoup de criteres.

Enfin, avec la multiplication des problèmes non-convexes, des techniques satisfaisantes en pratique ont vu le jour

J'imagine que tu parles des métaheuristiques ?

Pas uniquement. Gradient stochastique et autres techniques qui restent efficaces sur des problemes difficiles.

Tout d'abord, fais attention à tes notes : elles n'apparaissent pas dans le bon ordre. Cela est dû à ça.

TODO

De plus, il me semble important d'ajouter des légendes aux images. Tout le monde n'a pas l'habitude de lire des graphes (dont moi, et celui sur l'ajout d'un élément dans un tableau dynamique m'a au début perturbé).

TODO

D'autre part, comme je n'ai pas de recul sur la question, j'ai du mal à comprendre les notions de linéarité et convexité. Pas la définition, mais comment ça se passe en pratique. Par exemple, peut-on parler de linéarité ou convexité dans le cas du problème sur l'ajout d'un élément tableau (cf : analyse amortie) ? Ou encore quand il s'agit de trier un tableau d'entiers ?

En fait, oui on peut… si l'on modelise le probleme sous forme d'optimisation. Par exemple "minimiser le nombre de reallocations" + hypotheses sur le domaine ou contraintes. Pour trier 'minimiser le nombre d'elements qui ne sont pas a la bonne place'. Il y a plein de formulation pour un meme probleme de ce type et c'est justement le boulot du mathematicien ou de l'ingenieur en mathematiques que de faire ce travail de modelisation vers une formulation qui soit agreable et facile a utiliser ou se ramene a des problemes deja connus et etudies.

Un petit theoreme / resultat: tout probleme de decision peut se mettre sous la forme d'un probleme d'optimisation. Cela fait deja un paquet de choses.

De même, la notion d'invariance apparaît un très vague. Disons qu'on a (du moins, j'ai) du mal à rattacher ça à des exemples concrets. Il faudrait donc que tu en donnes.

Parce que ce sont des resultats plus abstraits. En gros c'est : est-ce que si je deforme les instances de mon probleme mon algorithmes va rester performant par rapport a ces deformations. On travaille vraiment sur la formulation mathematique pour le coup car les transformations sont evidemment mathematiques et pour prouver l'invarience on a aussi besoin de faire des maths pures et dures (si j'ose dire), et pas de l'algorithmique.

De manière générale, je pense qu'on (là encore : je) n'a pas assez de recul sur ce qu'est un problème, et plus précisément sur la modélisation mathématique d'un problème. Et comme on ne parvient pas à le modéliser, on peine à comprendre les caractéristiques que tu énonces (linéarité, convexité, invariance…).

Effectivement, mais cela vient par l'experience, la connaissance aussi des problemes de references, mais cela serait des cours entiers pour cela. J'ai conscience que l'article s'adresse peut etre a des gens avec deja un petit parcours dans le domaine, mais je t'assure que la realite est infiniment plus complique que ce que je decris la.

Par exemple, suite à la lecture de l'article, je ne saurais dire si trier un tableau d'entiers est un problème intrinsèquement simple ou non. Autrement dit, de "Vers des critères de difficulté en amont" à la fin, tu restes un peu trop en surface à mon goût. Inutile de fournir les détails mathématiques, des références suffisent, mais des exemples seraient extrêmement bienvenus.

Parce qu'on sait algorithmiquement que oui. C'est a dire qu'on a des algorithmes tres performants pour cela. On a des preuves meme qu'il faut, pour les tris a comparaisons, au moins une complexite en n log n. Personne ne s'interesse donc a modeliser le probleme mathematiquement et l'etudier. On prefere des problemes plus generaux par ailleurs, et qu'ensuite on ramene une situation concrete a un probleme general pour utiliser les outils generaux de resolution. Ca pourrait etre un prochain article.

Après, cela est-il dû à mon faible niveau en mathématiques et au fait qu'il s'agisse d'un article. Mais en ajoutant des exemples, tu clarifierais grandement tout ça et permettrais probablement au contenu d'être un tutoriel.

Je ne dis pas non a etoffer un peu la fin en exemples mais clairement, l'article n'a pas vocation a etre un tutoriel.

Dans la conclusion, il me semble que tu ne parles pas du passage sur les invariances, c'est-à-dire du passage mentionnant les qualités d'un algorithme. Ca me semble important parce que tu changes un peu de direction à ce moment-là (tu passes du problème à l'algorithme).

J'en parle implicitement: nouveaux criteres de qualite, progrès en mathématiques. Pour moi il est important de ne pas perdre le fait que le sujet c'etait montrer que la complexite algorithmique dans le pire des cas et meme generalement, n'est plus le seul critere important aujourd'hui.

Bonjour à tous !

La beta du tutoriel a été mise à jour.

Merci pour vos relectures

Bonjour à tous !

La beta du tutoriel a été mise à jour.

Merci pour vos relectures

Bonjour à tous !

La beta du tutoriel a été mise à jour.

Merci pour vos relectures

Pour information, j'ai mis le tutoriel en validation. Petit soucis, la version en demande validation a ete modifiee puisque j'avais inverse deux images lorsque j'ai peniblement mis a jour celles-ci.

J'ai pris compte des remarques de Vayel, que je remercie encore une fois.

J'ai aussi fais un travail sur le typographie: espaces fines insecables la ou il faut, guillement et apostrophe francaise notamment.

Enfin, j'ai rajoute un petit paragraphe sur la transition entre des problemes tres generaux et l'optimisation mathematique pour faire comprendre que tout et n'importe quoi peut se formuler comme de l'optimisation.

Par ailleurs, si cela est interessant, je peux donner plus de liens bibliographiques, de references et eventuellement des liens dans le texte pour les concepts sur lesquels je passe rapidemment.

Pour information, j'ai mis le tutoriel en validation. Petit soucis, la version en demande validation a ete modifiee puisque j'avais inverse deux images lorsque j'ai peniblement mis a jour celles-ci.

Pas un souci, il suffit de mettre à jour la version en validation par la plus récente.

Remarques en vrac :

• Tu n'as pas utilisé les extraits (en gros : un extrait pour le problème d’optimisation linéaire, et ainsi de suite) et tu fais encore référence dans le texte à un article (or, que c'est un tuto)
• Manque le premier chapitre (ou un lien vers celle-ci dans l'intro, à la limite). Ce serait bien que les deux soient publiés ici/donner un lien pour le lecteur.
• Plus de liens bibliographiques + ref + liens (surtout pour les concepts et certaines notions) serait effectivement très appréciés

Le probleme c'est que pour moi ce n'est pas un tutorial, mais bien un article. Il est long, techniques et dense mais on est loin d'un tutoriel pedagogique. Le soucis c'est que ce genre de format ne correspond pas aux articles sur ZdS..

C'est pas faux. Ou alors, faut scinder l'article (et publié chaque partie séparément) mais ça ne me parait pas faisable ici.

De toute manière, tu as bien dit que tu comptais écrire un troisième chapitre et en profiter pour rapatrier le premier, non ? Ce sera probablement l'occasion d'avoir un "vrai" tutoriel intitulé "Réflexions Sur La Complexité Algorithmique", avec trois chapitres ou, si tu le préfères, trois extraits.

Oui, mais il s'est passe deux ans entre le premier et second chapitre. Donc si on doit attendre deux ans pour voir la troisieme partie, je ne sais pas quelle solution adopter.

Couper l'article me semble impossible. Il n'y a pas vraiment de partie independante.

Ceci dit, il est possible eventuellement de faire un mini-tuto, en separant, tout en precisant dans l'introduction qu'il s'agit en realite d'un format un peu batard, dont la finalite est de s'apparenter a une sorte de 'dossier', en trois volumes.

Pour l'instant, il faut se poser la question du découpage du chapitre 2. Avec la ZEP-12, changer la structure du tutoriel pour intégrer le premier chapitre et le futur troisième sera un jeu d'enfant.

Le découpage suivant me semble un peu correct :

• Introduction : "Avant-propos"
• Position du problème : "Le problème d’optimisation linéaire", "Quelques notations et remarques de vocabulaire", "Problème d’ordre total pour la comparaison d’algorithmes"
• Mesures de complexité d’un algorithme : "Mesures de complexité d’un algorithme", "Les défauts de la complexité pour la comparaison d’algorithmes"
• Vers des critères de difficulté en amont : "Vers des critères de difficulté en amont"
• Robustesse théorique et empirique d’un algorithme : "Robustesse théorique et empirique d’un algorithme"
• Conclusion : "Conclusion", "Références", "Crédits des illustrations"

Les noms des extraits sont à titre indicatif seulement (comme le reste :P).

D'ailleurs, un découpage en extraits aidera à suivre ton raisonnement, ce que j'avais eu du mal à faire dans la première version du contenu (pas eu l'occasion de lire les suivantes).

Bonjour à tous !

La beta du tutoriel a été mise à jour.

Merci pour vos relectures

Bonjour à tous !

La beta du tutoriel a été mise à jour.

Merci pour vos relectures

• Séparation en extraits.
• Ajout de liens Wikipédia pour l'ensemble des concepts qui peuvent mériter une définition pour le lecteur lorsque je n'en donne pas. Lorsque le lien est en anglais cela est précisé entre parenthèses, et ce n'est que sous la contrainte de l'inexistance d'une page équivalente en français que ces liens sont présents.
• Ajouts de quelques exemples de fonctions multi-modales qu'on utilisent souvent pour les tests d'algorithmes d'optimisation, ainsi qu'une mention à un logiciel de méta-optimisation qui fait référence aujourd'hui, et qui est le fruit de plusieurs articles de recherches.
• Ajout d'un lien d'un de ces articles sur la méta-optimisation.

TODO: - Expliquer en introduction en quoi l'écrit se lit comme un article et non pas comme un tutorial.

To wszystko będzie.

Là, c'est mieux.

Bonjour à tous !

La beta du tutoriel a été mise à jour.

Merci pour vos relectures

• Explication article / tutoriel.

Je rechigne un peu à mettre plus de références car les références sont les textes dont je me suis servis pour écrire cet article et que je pourrais citer dedans. Ce n'est pas beaucoup dans le cas présent, mais il serait plus utile éventuellement de donner des cours directement. Cependant je ne suis pas fan du concept pour un article qui n'est pas un tutoriel.

Quand tu n'auras plus de TODO, fais-moi signe, j'essayerai de relire le tout.