Quand tu n'auras plus de TODO, fais-moi signe, j'essayerai de relire le tout. 
Y a plus de TODO.
Dans cet article on tâchera
Par la suite on expliquera
Fort de ce constat, on explicitera
Enfin, on donnera
"Nous" ?
Fort de ce constat, on explicitera quelques propriétés en amont, c’est-à-dire du point de vue du problème, et donc sans disposer explicitement de méthode de résolution, qui caractérisent un problème difficile.
Le "qui caractérisent un problème difficile" est un peu loin "quelques propriétés en amont".
l’enjeu ici est de montrer les difficultés de caractériser
à caractériser
beaucoup de termes ou concepts ne soit pas familier
soient
familiers
J'enlèverais "ou concepts", puisque tu dis juste après : "se renseigner sur les différents concepts".
minimiser (ou maximiser) une fonction linéaire f
Je préciserais qu'elle est à valeurs réelles, même si c'est évident en lisant la suite. D'ailleurs, le lecteur se demandera si on peut travailler ailleurs que sur $\mathcal R$.
Avec A∈Mm×n(R et b∈Rm.
Problème de parenthèses.
dégats
"dégâts" (dans le tableau).
Le titre ne serait-il pas d'un niveau de trop ?
Et voici la modélisation mathématique pour se ramener au problème d’optimisation linéaire.
Ca répète un peu beaucoup le titre.
20 avions que l’on peut produire. Ainsi xA+xV
$x_B$
ce qui conduit à deux contraintes supplémentaires:
Une (:P) espace.
Par rapport à la forme matricielle, nous aurions
Le "Par rapport" me semble bizarre.
Même remarque sur le niveau du titre.
Comme nous n’avons que deux variables de décisions, il est possible de visualiser les contraintes comme montré sur la figure suivante.
Je préciserais : "il est possible de visualiser les contraintes dans un plan".
Chaque contrainte est représentée par une droite qui limite
Je préfère "limitant".
Par exemple, si l’on prend la première contrainte, en vert sur la figure
Je suis daltonien et je ne saurais dire, sans la légende, quelle zone tu désignes. Je vois la différence, mais je ne saurais donner la couleur de chacune.
Chaque point à l’intérieur de ce domaine satisfait toutes les contraintes et l’objectif du problème est donc de trouver le point qui maximise notre fonction de départ.
"trouver le point de ce polyèdre", sinon le "donc" ne se tient pas.
Sans plus d’explication
explications ?
(notons au passage que pour faire un maximum de dégâts, il ne nous faut pas construire 20 avions mais seulement 18)
Je pense que tu peux enlever les parenthèses, en créant une phrase.
et si nous renvoyons le lecteur à la littérature sur le sujet pour de plus amples détails, nous nous contentons de les citer
Ca fait bizarre. Soit "et comme nous renvoyons le lecteur à la littérature sur le sujet pour de plus amples détails, nous nous contentons de les citer", soit "et si nous renvoyons le lecteur à la littérature sur le sujet pour de plus amples détails, nous les citons tout de même pour", non ?
Proposée par Dantzig en 1947
Nouveau paragraphe ?
Enfin, Karmarkar propose en 1984
Le "enfin" me semble de trop. Je me suis demandé pourquoi tu n'avais pas ouvert de paragraphe.
pour résoudre un problème P dont l’ensemble des instances est Π
Tu introduis déjà cette notation au-dessus. Ce n'est pas gênant, mais on se demande pourquoi tu as défini des notations si tu les rappelles. Je sais pas trop à quel niveau agir, ni même s'il faut changer quelque chose.
Dès lors il est impossible a priori
Tu utilises déjà "Dès lors" en début de paragraphe.
à priori
mesure d’efficacité pour les algorithmes pour pouvoir
"afin de pouvoir" ?
Une mesure qui s’est imposée est la mesure asymptotique en fonction de la taille du problème.
La phrase est un peu lourde. Plutôt un truc du genre "La mesure asymptotique en fonction de la taille du problème de ce côté-là" ? Sinon, "Une qui s’est imposée est la mesure asymptotique en fonction de la taille du problème.".
To be continued.
Pardon :
Pour répondre à ces question
questions
Il s’agit de donner une borne supérieure du nombre d’étapes nécessaires à la terminaison de l’algorithme sur l’ensemble des instances du problème qu’il résout.
"sur l’ensemble des instances" me semble incorrect. Il faut fixer leur taille, comme tu le fais dans la formule qui suit, sinon on risque de ne pas avoir de borne supérieure dans $\mathbf N$.
De manière formelle, la complexité d’un algorithme dans le pire des cas est défini par :
Centrer la formule ?
Dire que l’algorithme A a une complexité dans le pire des cas de O(n2) veut dire
Ne devrais-tu pas préciser que c'est asymptotique, i.e. quand $n$ tend vers l'infini ?
De plus, ne centrerais-tu pas la formule ?
Il faut comprendre que si Tmax est un nombre exact du nombre d’opérations
"le nombre exact"
Tu n'as pas défini Tmax, seulement Tmax(n).
grandit avec la taille du problème: on parle
Espace
par rapport à la notion dans le pire des cas :
Centrer la formule ?
c’est-à-dire comme le minimum du nombre d’étapes pour résoudre une instance parmi toutes les instances
Là encore, tu parles de "toutes les instances" mais tu précises leur taille dans la formule.
Remarquons par exemple que l’algorithme A possède un nombre minimal d’opérations qui dépend de la taille de l’instance
On ne voit pas trop où est fmin.
Enfin, l’algorithme B possède un comportement oscillant pour sa borne supérieure
Are you sure?
et ce, quel que soit la plage de valeurs
quelle que soit
Dans le cas de l’algorithme A, l’estimation asymptotique est une borne supérieure au nombre d’opérations, et ce, quel que soit la plage de valeurs de la taille des instances considérées. Dans le cas de l’algorithme C, on dispose également de deux plages différentes de taille d’instances, ce qui nous permettra de visualiser certains défauts de la complexité asymptotique pour l’évaluation pratique de la performance des algorithmes.
Les deux phrases n'ont pas le même rôle : la première analyse le graphe de $A$ tandis que la seconde est une simple indication. Je ferais comme ça :
Voyons maintenant les différences qu’il peut exister entre la complexité exacte et la complexité asymptotique. Les cinq images suivantes montrent le tracé de la complexité exacte et asymptotique en fonction de la taille des instances. Dans le cas de l’algorithme C, on dispose également de deux plages différentes de taille d’instances, ce qui nous permettra de visualiser certains défauts de la complexité asymptotique pour l’évaluation pratique de la performance des algorithmes.
Pour l’algorithme A, on constate sur la figure suivante que l’estimation asymptotique est une borne supérieure au nombre d’opérations, et ce, quel que soit la plage de valeurs de la taille des instances considérées.
C’est ce que l’on peut observer sur les deux figurent
figures
et qui représente l’écart relatif entre le nombre d’opérations
représentent
si l’on considère que l’utilisateur de l’algorithme B ou C ne va avoir à traiter en pratique que des instances de taille comprise entre 0 et 100, alors on peut voir que l’algorithme est très loin de se comporter comme le prédit la complexité asymptotique.
La phrase est lourde. Plutôt :
en supposant que l’utilisateur de l’algorithme B ou C ne va avoir à traiter en pratique que des instances de taille comprise entre 0 et 100, on peut voir que l’algorithme ne se comportera pas du tout comme le prédit la complexité asymptotique.
peut être largement faussée, tout comme la comparaison entre deux algorithmes a priori
à priori
L’importance de la constante multitplicative
multiplicative
avec pour effet de rendre la comparaison d’algorithmes impossible à priori comme nous le verrons par la suite
à priori (pas d'italique)
Cependant, cet encadrement atteint ses limites assez rapidement.
Le "cependant" ne va pas avec les critiques que tu fais juste au-dessus.
Malgré tout, on remarque très souvent qu’en pratique ces cas pathologiques n’arrivent que rarement si ce n’est jamais, et l’on peut munir l’espace
Ca va un peu vite. Je ferais plutôt un truc du genre :
Malgré tout, on remarque très souvent qu’en pratique ces cas pathologiques n’arrivent que rarement si ce n’est jamais. Pour prendre en compte cela, on peut munir l’espace
Le sous-ensemble des instances pratiques dépend de la configuration de l’exploitation de l’algorithme.
Plutôt :
Pour un même algorithme, le sous-ensemble des instances pratiques dépend de la configuration de l’exploitation qu'on en fait.
elles peuvent ne pas avoir les mêmes cas à traiter en règle générale
Plutôt que "cas", je mettrais "types d'instances".
pour déterminer le plan pour les livraisons de leurs livres
afin de déterminer
et [b1,b2]⊂N avec a priori
pour le libraire
à priori
b2<a2 qui traduit
b2<a2, pour traduire
Dans le cas du nombre de clients, il est probable que le nombre de commandes du libraire soit bien plus variable au sein de sa plage que celui d’Amazon
Je ne comprends pas le "Dans le cas du nombre de clients". Il manque un "même", non ? Le cas échéant, je préciserais : "même nombre de clients à livrer". Sinon, s'il y a le même nombre de clients en tout, la suite ne va pas.
Ainsi la distribution du nombre de clients par jour suivra peut-être quelque chose qui ressemble à une loi normale
Pour Amazon
Partant du principe que les instances pathologiques sont souvent exclues du sous-ensemble des instances pratiques ou suffisamment rares en son sein pour ne pas être considérées comme significatives, on s’intéresse à la complexité en moyenne d’un algorithme.
J'insisterais en disant, en évitant les répétitions de termes, que la complexité en moyenne est relativement fiable du fait de l'absence des cas pathologiques, la moyenne étant sensible aux valeurs extrêmes. C'est en gros ce que tu dis, mais je pense que ce n'est pas assez clair.
mais d’émettre une hypothèse sur la distribution de probabilité d’apparition des instances possibles
Ca fait bizarre de lire ça, parce que tu as déjà parler d'une mesure de probabilité quelques paragraphes auparavant. Du coup, on a un peu du mal à suivre le raisonnement. On a l'impression que tu introduis la complexité en moyenne dans ce paragraphe alors que tu le fais depuis le début, avec Amazon et compagnie. Je dirais donc un truc du genre :
Cela s'appelle la complexité en moyenne. Elle est relativement fiable parce que les cas pathologiques ont été dégagés par la mesure de probabilité. La complexité en moyenne n'est pas, comme on pourrait le penser, une moyenne du nombre d'opérations blablabla.
Supposons une mesure de probabilité μ
Plutôt "Définissons", non ?
Alors la complexité moyenne est definie par :
Je centrerais bien la formule.
Sinon, cette espérance ne m'est pas très naturelle, ayant l'habitude de ne travailler qu'avec des variables alétoires. C'est quoi $T(\Pi)$ ?
Dans le cas où Π est un ensemble discret
Je centrerais les formules qui suivent et mettrais l'indice de la somme sous la somme.
Par exemple si l’on génère de manière aléatoire des tableaux à trier, où chaque case sera remplie selon une même loi uniforme, alors toutes les instances auront même probabilité
Euh… toutes les instances de même taille, non ?
Les résultats en moyenne seront bien différents
Le "en moyenne" fait bizarre. De plus, "bien différents" de quoi ? De la complexité en moyenne ? Mais pour quelle mesure de probabilité ?
ou bien sûr les capacités globales
"sur" ?
Cela rajoute un élément à l’objet dont on cherche à caracteriser
caractériser
Mais d’une part, on peut retarder le besoin d’une nouvelle allocation en initialisant notre tableau avec une capacité qui est la taille estimée nécessaire pour notre application. Et d’autre part
Faire deux phrases ne va pas très bien parce que le "d’autre part" est également rattaché au "mais".
Pour définir la complexité amortie, il faut définir le coût amorti de chaque opération :
C'est quoi $n$ ?
Le paragraphe suivant n'est pas très clair non plus. Tu devrais préciser cela : "allouer n cases contiguës en mémoire est un O(n) mais permet d'effectuer par la suite n opérations en O(1). On définit alors le coût amorti…".
Les trois figures suivantes illustrent le nombre nécessaire d’opérations à 10 insertions en partant d’un tableau vide
Pas seulement. On a aussi le nombre d'opérations nécessaires pour 1, 2, 3… insertions.
J'ai toujours du mal avec ces graphes. Déjà, on distingue très mal les légendes. Et je ne comprends pas le second graphe. En fait, l'expression "nombre d'opérations" n'est pas très claire. Est-ce le nombre total d'opérations ou est-ce le nombre d'opérations pour insérer un nème élément ?
Je penses que tu devrais essayer de représenter ça sous forme d'un tableau.
Ajout de 1 :
| Elements dans le tableau | Nombre d'opérations pour insérer l'élément | Capacité totale |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 2 | 2 |
| 3 | 3 | 3 |
Ajout de 3 :
| Elements dans le tableau | Nombre d'opérations pour insérer l'élément | Capacité totale |
|---|---|---|
| 1 | 1 | 3 |
| 2 | 1 | 3 |
| 3 | 1 | 3 |
| 4 | 4 | 6 |
Multiplication par 2 :
| Elements dans le tableau | Nombre d'opérations pour insérer l'élément | Capacité totale |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 2 | 2 |
| 3 | 3 | 4 |
| 4 | 1 | 4 |
exponentielles, c’est à dire qu’elles sont mal adaptées
c'est-à-dire
Bien souvent, l’amélioration de l’analyse amortie se fait par des heuristiques
Le lien merde, mais je crois que c'est un bug du Markdown. Ce n'est pas le seul lien qui pose problème.
par exemple dans le cas du tableau dynamique, on a en pratique en permanence une occupation mémoire qui n’est pas nécessaire
par exemple, dans le cas du tableau dynamique, on a en pratique en permanence une occupation mémoire qui n’est pas nécessaire
disjointes. Elle possède deux opérations:
Espace
Union-Find est une structure de données utile pour maintenir une partition d’un ensemble en classes disjointes.
L'article de Wikipédia n'est pas très explicite, ainsi je donnerais des détails là-dessus. Il est dit qu'on a un ensemble d'éléments et qu'on veut le partitionner. Dans le cas où cet ensemble est représenté par un liste, ça me semble trivial, non ? Je ne vois pas comment on se sert d'Union-Find en pratique. Un exemple simple serait le bienvenu.
tandis que la complexité dans le pire des cas reste la même ou augmente même.
reste la même voire augmente.
De prime abord, la différence entre l’analyse amortie et l’analyse en moyenne peut ne pas sembler flagrante. Je me permets donc d’insister sur ce qui fait la différence
Petite répétition.
Si la complexité en moyenne a été introduite pour pallier certaines
pallier à
Dans le cas ou σ tend vers l’infini
où
la complexité lisse a pour but d’être une synthèse permettant d’outrepasser les limitations des mesures de complexité précédentes et notamment en expliquant pourquoi certains algorithmes restent efficaces en pratique contrairement aux études théoriques effectuées jusque-là.
Je ne comprends pas en quoi l'analyse lisse permet de faire ça. Plus généralement, la partie sur l'analyse lisse n'est pas simple à assimiler.
qui est un domaine très courant dans le domaine de la simulation numérique
Répétition
de faire ressortir une distance entre deux instances et de fait
et, de fait
il devient alors impossible d’utiliser l’analyse lisse
Le "alors" ne répéterait-il pas le "de fait" ?
La complexité algorithmique asymptotique possède un certain nombre de defauts
défauts
(et même en dehors cela peut être vrai)
(et parfois même en dehors)
Si dans la partie précédente nous avons mis en avant qu’il existe
"le fait qu'il existe" ?
ici on met en avant le fait qu’un algorithme
"met en avant" fait répétition.
et que si je sais a priori que la majorité des instances
donc si
à priori
Pire, même une étude précise pourra être mise en défaut et ce d’autant plus facilement que les deux algorithmes comparés offrent une complexité proche, par l’évaluation empirique.
Pire, même une étude précise pourra être mise en défaut par l’évaluation empirique, et ce d’autant plus facilement que les deux algorithmes comparés offrent une complexité proche.
Plus les systèmes deviennent complexes, de même que les algorithmes ou les problèmes qu’ils résolvent et
Plus les systèmes deviennent complexes, de même que les algorithmes ou les problèmes qu’ils résolvent, et
Il y a beaucoup de notions donc je pense que c'est normal, mais on peine à prendre du recul par rapport à tout ça. Autant je comprends comment est construite chacune des complexités, autant je ne parviens pas à les comparer et à voir à quoi elles servent. Ce qui n'est pas simple, c'est qu'un coup on travaille sur les instances, un coup de manière asymptotique, un coup…
Est-il normal que tu ne parles que d'OGA dans la section "Les défauts de la complexité pour la comparaison d’algorithmes" ? Vu que tu introduis le reste du tutoriel en disant que les mesures de complexité ne sont pas satisfaisantes, ce serait bien d'expliquer pourquoi chacune ne l'est pas.
Je ne comprends pas le rapport avec les complexités. Enfin un peu quand même, mais tu devrais l'expliciter dans l'introduction. D'ailleurs, on comprend d'autant moins que tu n'as pas trop parlé des limitations dans complexités autres que OGA.
Est-il possible de caractériser la difficulté d’un problème sans avoir d’algorithme pour le résoudre ? Peut-on prédire le comportement d’algorithmes types sur un problème donné en amont ? Je propose ici quelques concepts et idées qui permettent de répondre par l’affirmative à ces questions sur des types de problèmes particuliers. La démarche est donc en général de transformer l’énoncé d’un problème en formulation mathématique, puis de se ramener à un autre problème type dont a déjà étudié les caractéristiques ou donné des preuves sur le comportement attendu d’un certain type de méthodes de résolution.
Il y a pas mal de "types".
Présentons une version plus générale plus problème d’optimisation
du
d’optimisation dont nous avons abordé le cas particulier
d’optimisation, dont
Soit f:Ω→Y, alors le problème de minimisation
. Alors
Tu passes d'optimisation à minimisation. C'est pareil, mais je l'indiquerais.
le problème de minimisation consiste à minimiser f sur X
Et si $f = Id$ et $X = \ ]0, 1]$ ?
L’intérêt de ce problème est qu’il est toujours possible en pratique de ce ramener à cette formulation, même de manière artificielle. S’il est évident que pour des problèmes classiques du type trier un tableau, le problème a été étudié spécifiquement et des algorithmes très spécifiques ont vu le jour
"problèmes" et "spécifiques" engendrent des répétitions.
Pour cette catégorie, on peut montrer qu’il existe un problème d’optimisation associé à chaque problème de décision.
"à chaque problème de décision" répète "Pour cette catégorie".
Dès lors, lorsque l’on atteint le minimum de (PO)
maximum
alors la répondre à (PD) est « non »
réponse
Autrement dit, on résolvant (PO) on résout exactement (PD).
en
J'ai plutôt l'impression qu'on répond à la question "est-il possible de le trier ?" et non à "est-il trié ?".
qui vient par habitude et avec la connaissance des problèmes récurrents
C'est quoi qui vient ?
L’important est plutôt de saisir l’infinité des problèmes qui peuvent se formuler in fine comme un problème d’optimisation et donc l’importance que revêt cette branche des mathématiques pour les applications aussi bien en informatique qu’en physique ou en science sociale.
Aurais-tu une source prouvant que tout PD est équivalent à un PO ?
versus
Une fonction f est linéaire si elle satisfait le principe de superposition, c’est-à-dire si
Centrer la formule ?
(qui sont des droites en dimension 2)
(qui, en dimension 2, sont des droites)
c’est l’intersection d’hyperplans (qui sont des droites en dimension 2) qui caractérise X au sein de l’ensemble Ω.
Mouais. On pourrait déduire de cette phrase que $X$ est l'intersection des hyperplans. "Délimite" ?
L’ensemble des positions que le chien peut adopter, c’est-à-dire l’ensemble X est
L’ensemble des positions que le chien peut adopter, c’est-à-dire l’ensemble X, est
autrement dit le disque de rayon l
et de centre le pilier.
Un exemple de la fonction que l’on voudrait maximiser
de fonction
serait la fonction f(x,y)
serait f(x,y)
définit comme la distance
définie
Ca ne te coûte pas grand chose d'expliciter la fonction.
Ainsi, l’existence de plusieurs modes
mode = solution ?
(on parle de suite minimisante)
Ou maximisante ?
et dont on espère beaucoup de propriétés pour arriver à cette fin :
On a l'impression que tu parles des suites minimisantes. Le cas échéant, le premier point de la liste fait étrange, puisque tu dis : "parmi les propriétés qu'on espère d'une suite minimisante, il y a son existence". C'est plutôt du problème qu'on espère une telle propriété.
était liée majoritairement à la caractéristique de linéarité ou non
"caractéristique de linéarité" fait bizarre. Plutôt : "Durant des années on a pensé que la difficulté intrinsèque d’un problème était liée majoritairement à la propriété de linéarité, les problèmes linéaires…".
en particulier voir Analyse fonctionnelle
en particulier, voir Analyse fonctionnelle
c’est-à-dire les contraintes s’appliquant à Ω dont il résulte
On ne sait pas trop si le "c’est-à-dire" fait référence à "la nature de X" ou "le procédé pour l’obtenir". C'est le deuxième bien sûr, mais ça gagnerait à être clarifié. Par exemple : "c’est-à-dire plus que les contraintes s’appliquant".
tandis que le second uniquement à partir de contraintes quadratiques et pourtant ces deux problèmes sont simples
tandis que le second uniquement à partir de contraintes quadratiques ; et pourtant ces deux problèmes sont simples
ce n’est donc pas la propriété de linéarité qui implique la simplicité mais la convexité
C'est audacieux. Ca pourrait être une autre propriété commune, voire le hasard.
Il ne faut cependant pas trop prêter attention à ces séparations. Les seules séparations valables sont celles qui séparent deux catégories de problèmes par rapport aux outils disponibles pour les résoudre et ainsi, en fonction du temps ces frontières changent, ou plus précisemment reculent. Le travail de la recherche étant d’étendre les outils déjà existants à des problèmes plus difficiles, d’en proposer de nouveaux, ce qui permet d’unifier des domaines.
C'est une note.
Il ne faut cependant pas trop prêter attention à ces séparations. Les seules valables sont celles qui partagent deux catégories de problèmes par rapport aux outils disponibles pour les résoudre ; ces frontières changent donc en fonction du temps, ou plus précisemment reculent.
Le participe présent de la dernière phrase fait bizarre.
A gauche c'est convexe, à droite non-convexe.
Je viens de me demander : comment on dessine un concave ?
dont certaines citées plus haut telle
telles
qui est dans ce cas un polytope
qui est également dans ce cas un polytope
Le problème de la tour de Hanoï a été prouvé comme étant inextricable3, tandis que l’on suppose que le problème du voyageur de commerce est inextricable, mais l’on ne dispose pas de preuve pour cela.
Le rythme de la phrase n'est pas excellent.
Pas besoin de dire que la plupart
Inutile de dire
Petite légende ? 
Tu peux faire la correspondance en légende entre les deux images. Que représentent le bleu et le rouge à droite ?
Inexistence d’hyperplan d’appui en tout point pour un ensemble non-convexe.
On pourrait lire "Il n'y a d'hyperplan d'appui en aucun point". Plutôt un truc du genre : "Il existe des points n'admettant pas d'hyperplan d'appui.".
Or, l’illustration suivante montre qu’en utilisant une fonction d’agrégation qui est une combinaison linéaire des objectifs, il est impossible d’atteindre la partie concave du front4.
J'expliquerais pourquoi c'est pas bien de ne pas pouvoir atteindre cette partie concave. Autrement dit, cela nous fait-il risquer de manquer des solutions ou cela nous fait-il nécessairement manquer des solutions ?
Fonction de Hölder Table aux multiples optimums locaux.
Je ne comprends pas ce qu'est l'espèce de plafond.
celle-ci va converger vers un des quatre optimums possible
possibles
Il existe une zone autour de chacun de ces points que l'on nomme bassin d'attraction (lien anglais) et qui « capture » la suite qui s’aventure en son sein.
C'est beau.
Je rappellerais que tout problème se ramène à un PO, c'est-à-dire que pour tout problème on peut parler de fonction objectif et compagnie, comme tu le fais dans la suite.
Cependant, comme suggéré, on peut tout de même raffiner en étudiant en étudiant
Etudier une fois me suffira. 
(nécessite l’existence d’une dérivée d’ordre supérieur par exemple)
C'est quoi qui nécessite ?
une variance faible sur le temps de résolution
Il me semble que ça ne s'inscrit pas dans la continuité de la phrase. "ayant une variance faible" ?
Invariance par une transformation de la fonction objectif. Plus
Invariance par transformation de l’espace de recherche. Il
Double-point ?
La différence est que dans l’analyse lisse on s’intéresse au pire des cas obtenu par perturbation tandis que dans l’étude d’invariance on étudie des classes d’équivalence pour la transformation considérée, non aléatoire, sans tenir compte de la complexité.
Je viens de remarquer "pire des cas obtenu". Je ne sais pas trop s'il faut mettre "obtenus" ou pas.
Ce passage n'est pas très clair.
Illustration du théorème No Free Lunch avec 3 métaheuristiques appliquées à 6 problèmes.
"trois" et "six" ?
Dès lors, ce sont de bon candidats
bons
un nombre très important de paramètres, parmi les plus généraux
Je mettrais un point ou un point-virgule.
Si l’on reprend l’exemple des paramètres de taille de population et les deux probabilités
du paramètre de taille
et des deux probabilités
On parle également, plus généralement de parameter tuning en anglais.
La virgule me semble de trop.
d’une part rapide à optimiser, et d’autre part, que
d’une part rapide à optimiser et, d’autre part, que
on parle de méthode en ligne
Ressource ?
Très bien résumé. Idéalement, il faudrait grosso modo copier-coller chaque paragraphe à la fin de l'extrait le concernant, histoire qu'il soit plus simple de suivre le fil du tutoriel.
L’ensemble des images jusqu’à « Une question de domaine » et l'illustration de la fonction de Hölder ont été créées pour les besoins de cet article et placé dans le domaine public.
créés
placés
Je ne suis pas certain que les "(lien anglais)" soient nécessaires. Ils ne sont pas gênants mais gagneraient, je pense, à être enlevés.
Merci pour ce superbe article et pour l'attention que tu portes à mes remarques. C'est bien plus dur de les prendre en compte que de les faire.
Je ne réponds pas à tout, il y a trop de choses et il faut que ça avance un peu.
Sinon, cette espérance ne m'est pas très naturelle, ayant l'habitude de ne travailler qu'avec des variables alétoires. C'est quoi T(Π) ?
Tu as une variable aléatoire sous-jacente si tu veux. Tu es d'accord qu'une espérance n'est rien d'autre qu'une moyenne sur des espaces continues ? Et donc une moyenne est défini comme la somme des points (les instances) multiplié par leur poids (la mesure de probabilité sur l'espace des instances).
Tu peux intérpréter la formule comme le nombre moyen d'opérations sur $\Pi$ sachant que la probabilité associé à chaque point de $\Pi$ est donné par $\mu$. On pourrait définir l'espace probabilisé, dire que $\mu$ est la loi d'une certaine variable aléatoire qui à un $\omega$ de la $\sigma$-algèbre de l'espace probabilisé associe une instance, mais ça serait inutilement abstrait. Dans la formulation présente c'est à la fois très précis et tout à fait valable et cela évite la complexité des détails techniques.
Le paragraphe suivant n'est pas très clair non plus. Tu devrais préciser cela : "allouer n cases contiguës en mémoire est un O(n) mais permet d'effectuer par la suite n opérations en O(1). On définit alors le coût amorti…".
Je le trouve très clair pourtant. Il faut déterminer le coût de chaque opération de la série, de manière individuelle pour obtenir l'OGA individuel et le moyenner par le nombre d'opérations. Quand tu fais n insertions, les n-1 premières ne te coûte rien. Seule la dernière déclenche une réallocation qui coûte O(n). Le max est donc O(n). Ce que tu proposes me semble trop rapide.
Si tu as réussi à lire les graphiques c'est qu'ils sont lisibles non ?
Si l’on « remédie à quelque chose », en revanche on « pallie quelque chose ». Ce dernier verbe est transitif direct, ce qui signifie qu’il est inutile de le faire suivre de la préposition « à ».
Alors est compatible avec de fait.
Je ne comprends pas le rapport avec les complexités. Enfin un peu quand même, mais tu devrais l'expliciter dans l'introduction. D'ailleurs, on comprend d'autant moins que tu n'as pas trop parlé des limitations dans complexités autres que OGA.
Calculs très techniques et difficiles pour l'analyse lisse. Obligation d'utiliser une approche empirique pour la complexité en moyenne.
Et si f=Id et X= ]0,1] ?
Je ne vois pas le problème. Le minimum existe de manière triviale.
J'ai plutôt l'impression qu'on répond à la question "est-il possible de le trier ?" et non à "est-il trié ?".
Il est toujours possible de trier un tableau d'entier à priori ?
Aurais-tu une source prouvant que tout PD est équivalent à un PO ?
Ce n'est pas une équivalent, c'est qu'il existe au moins (et c'est une précision qui manque et que j'ai rajouté).
Un exemple trivial partant de PO: Il suffit de se demander si un élément est optimal. Tu as un PD associé.
Pour PD vers PO, c'est plus complexe et faut faire pas mal de formalisme. Voici une début de réponse : http://cs.stackexchange.com/a/943
Je suis pas fan de centrer les formules lorsque ce n'est pas nécessaire dans ce genre d'exercice puisqu'il ne s'agit pas de donner un cours formel et de dégager des définitions ou des formules super importantes à placer bien en avant. Typiquement, l'encadrement du début me semblait important mais pas le rappelle sur la définition de la linéarité d'une fonction.
On a l'impression que tu parles des suites minimisantes. Le cas échéant, le premier point de la liste fait étrange, puisque tu dis : "parmi les propriétés qu'on espère d'une suite minimisante, il y a son existence". C'est plutôt du problème qu'on espère une telle propriété.
Effectivement, je parle des suites minimisantes, dont l'existence n'est pas garantie selon le problème. En réalité c'est même plutôt une propriété de $X$.
Je viens de me demander : comment on dessine un concave ?
https://fr.wikipedia.org/wiki/Fonction_concave
La notion est plus difficile à appréhender. Je me refuse généralement à dire que une fonction non-convexe est concave. Certains le font mais cela me fait me poser beaucoup de questions en général, surtout lorsque je travaille ne optimisation multi-objectifs où la concavité est plus une propriété locale, c'est à dire que les zones difficiles d'accès de $X$ sont celles qui sont localement concaves alors que d'autres zones peuvent êtra facilement accessible. Du coup, dire qu'un ensemble non convexe est concave c'est très binaire et réducteur.
D'un autre côté, et ça mériterait que j'y réfléchisse plus, mais je dirais que le seul moyen d'avoir un ensemble presque uniquement que concave serait un ensemble fractal dérivable en aucun point. C'est marrant comme remarque.
Le rythme de la phrase n'est pas excellent.
J'essayerais une marche harmonique modulante la prochaine fois, ou un cycle de quarte pour maintenir l'attention du lecteur. J'avais juste peur qu'avec les mesures composées de cette phrase cela ne rende pas bien. :')
Tu peux faire la correspondance en légende entre les deux images. Que représentent le bleu et le rouge à droite ?
Il n'y a pas de correspondance. Ce sont juste des convexes quelconque. Eventuellement le seul truc que l'on pourrait dire est que ceux en roses (oui, ils sont plutôt roses que rouges) sont des polyèdres et pas des convexes quelconques, mais ça n'a aucun intérêt par rapport au texte ou aux illustrations.
On pourrait lire "Il n'y a d'hyperplan d'appui en aucun point".
Je pars du principe que le lecteur sait lire.
De toute manière, les gens qui font des doubles négations devraient être brûlés vifs.
J'ai quand même fait la modification vu le public pas forcément formé en logique ou maths.
J'expliquerais pourquoi c'est pas bien de ne pas pouvoir atteindre cette partie concave. Autrement dit, cela nous fait-il risquer de manquer des solutions ou cela nous fait-il nécessairement manquer des solutions ?
J'ai modifié la phrase plus haut: « Dans un tel cas, la particularité est que l’on cherche l’ensemble des points de la frontière du domaine, qui tous, réalisent un équilibre de Pareto. »
Autrement dit, TOUS les points de la frontière sont des points que l'on veut trouver. Et donc, à partir du moment où l'on ne trouve pas les points des zones concaves (en gris sur la frontière), on manque nécessairement des solutions. On ne trouve que les points en noirs.
La question ne se pose même pas parce pour savoir si ces points sont des solutions au problème, il faudrait déjà pouvoir les atteindre.
Je ne comprends pas ce qu'est l'espèce de plafond.
C'est la projection de la fonction de Hölder sur un plan avec le gradient de valeurs. C'est souvent plus facile de visualiser la « topographie », on parle de « landscape », qu'une vue 3D qui nécessiterait de pouvoir bouger la figure pour se rendre compte de tous les détails.
C'est quoi qui nécessite ?
L'application d'une méthode. Certaines méthodes nécessite l'existence d'une dérivée à l'ordre 2 par exemple, ce qui n'est pas nécessairement le cas.
Je viens de remarquer "pire des cas obtenu". Je ne sais pas trop s'il faut mettre "obtenus" ou pas.
Non, c'est LE pire parmi les cas possibles.
d’une part rapide à optimiser et, d’autre part, que
J'ai vraiment envie de mettre l'incise comme elle est actuellement.
Ressource ?
Parameter Control in Evolutionary Algorithms dans les références
Automatic Algorithm Configuration based on Local Search dans les références.
Sinon, je suppose que tu trouveras ton bonheur http://www.princeton.edu/~sbubeck/BubeckLectureNotes.pdf
Merci une nouvelle fois de tes remarques qui m'aident vraiment.
EDIT: Et on dit « pallier » quelque chose et non pas « pallier à » quelque chose.
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
L’intérêt de ce problème est qu’il est toujours possible en pratique de ce ramener
se ramener (c'est dans le tuto)
Je ne vois pas le problème. Le minimum existe de manière triviale.
Peut-être n'a-t-on pas la même définition de minimum : pour moi, il y a une borne inférieure ($0$) qui n'est pas atteinte.
Il est toujours possible de trier un tableau d'entier à priori ?
Ouep. 
Du coup, je ne me souviens plus pourquoi j'avais fait la remarque.
EDIT: Et on dit « pallier » quelque chose et non pas « pallier à » quelque chose.
Décidément, je vais de surprise orthographique en surprise orthographique avec toi.
Merci pour tes retours.
Peut-être n'a-t-on pas la même définition de minimum : pour moi, il y a une borne inférieure ($0$) qui n'est pas atteinte.
J'avais pas vu que ton intervalle était ouvert. Effectivement, je devrais utiliser plus largement la notation $inf$ pour montrer que l'on ne sait pas si la borne est atteinte.
La suite minimisante existe toujours car sa définition formelle c'est une suite qui converge vers l'infimum qui existe toujours. Ce qui n'existe pas toujours c'est le minimum.
Je ne veux pas rentrer dans les détails parce qu'il faudrait dire des choses techniques du style des considération sur la compacité, etc. J'ai cependant modifié quelque peut ce passage pour renforcer un peu l'intérêt de la convexité : c'est cette propriété qui garantie l'existence d'un minimum en dimension infinie.
Bonjour à tous !
La beta du tutoriel a été mise à jour.
Merci pour vos relectures
Maintenant que le texte est découpé, pourquoi ne pas le publier sous forme d'une série d'articles ?
J'ignore où en est la validation, mais vu que la ZEP-12 est pour bientôt, il serait peut-être intéressant de publier ce contenu sous forme d'article (avec plusieurs extraits).
Désactivation de la beta du tutoriel Nos algorithmes sont-ils vraiment comparables ?
Pour plus d'informations envoyez-moi un message privé.
