Éléments de complexité

Bonjour tout le monde,

J’ai écrit une petite introduction à la complexité et à son analyse. J’ai eu du mal à me positionner sur le niveau auquel je m’attendais et des connaissances préalables. J’espère être resté suffisamment accessible. C’est difficile d’abord un sujet si vaste dans un texte si court. Je suis ouvert à n’importe quelle remarque ;-) À présent, c’est à vous !

Merci d’avance

Qui est le public cible pour cet article ? J’ai l’impression qu’il vise les personnes ayant déjà un bon bagage scientifique. Je pense qu’il serait utile de le préciser dans l’introduction.

Quelques remarques:

• Je pense qu’il faut être réaliste sur le fait que l’article sera indigeste pour les gens n’ayant pas ce bagage; les paragraphes qui contiennent des rappels de notion (par exemple la notion de "comportement asymptotique") doivent être compris comme des rappels de choses que les lecteurs ont probablement déjà vues mais un peu oubliées. En effet, leur traitement ne permet pas à une personne qui découvre complètement le domaine de les comprendre (et il y a trop de notions nouvelles pour qu’une personne débutante puisse suivre).

• Je ne suis qu’à demi convaincu par la partie "histoire des idées" du document. Je ne suis pas sûr de ce que tu veux dire au sujet de la thèse de Church-Turing, mais je ne comprends pas le sens que tu donnes à la phrase que tu cites, "Il est possible d’exprimer, par un ensemble de règles de calcul, tout ce qui est calculable en suivant un traitement systématique, un algorithme." J’ai l’impression que c’est soit tautologique (on peut calculer ce qui est calculable), soit difficilement compréhensible puisque les notions mentionnées ne sont pas définies. Pour moi le résultat central autour de Church-Turing est l’équivalence en terme de calculabilité entres machines de Turing, lambda-calculs et fonctions récursives, qui n’a pas la portée que tu présentes.

• Le document est concentré sur la calculabilité et la complexité comme sciences, et en particulier leur théorie et les problématiques de recherche qui en découle. C’est dit relativement clairement dans l’introduction, et c’est un choix intéressant. Mais il est peut-être un peu dommage d’occulter complètement le fait que la complexité est un outil utile, au jour le jour, pour les programmeurs qui réfléchissent à l’efficacité de leur code. Ce n’est clairement pas le point de vue central dans le document, donc je ne dis pas qu’il faudrait faire des tartines à ce sujet, mais je trouve un peu curieux de faire comme si ça n’existait pas du tout, un peu comme si on lisait un document introductif à la chimie ou à la physique qui occulte complètement le travail des gens qui appliquent ces sciences à l’industrie.

P.S.: J’ai co-rédigé un document sur la complexité avec un point de vue très très différent, Algorithmique pour l’apprenti programmeur. Notre but était d’être accessible au plus grand nombre (on ne suppose rien de plus que les maths niveau collège), et de se concentrer sur l’usage concret en programmation. Je trouve ça très bien que les contenus ZdS s’élargissent avec des présentations complémentaires, qui couvrent d’autres aspects de la discipline. Merci pour ton travail !

Je trouve que c’est une super initiative. Le problème essentiel, je pense, c’est qu’il y a un décalage entre ce que tu annonces au départ et les thèmes que tu traites. Le passage subtil sur les modèles de calcul est assez expéditif (ça commence par "les fameuses machines de Turing" et ça continue directement avec un enchaînement de remarques beaucoup trop abstraites pour que ce soit compréhensible, à mon avis), alors que la partie "algorithmique pour l’industrie" est beaucoup plus détaillée.

Par exemple, les notations asymptotiques pourraient être remplacées par des $\lesssim$ et $\gtrsim$ intuitifs sans que ça ne dérange personne. Et au risque de choquer les fans du CLRS, je trouve aussi que le théorème maître n’a pas d’intérêt scientifique — il ne comporte pas vraiment d’idée fondamentale sous-jacente et c’est un calcul technique qu’on imagine faisable a priori. Au passage, j’ai l’impression que tu mélanges un peu bornes inférieures et supérieures dans ton passage sur $\log(n!)$.

En bref, je pense que tu gagnerais à sélectionner quelques points que tu mentionnes dans ton "pour aller plus loin" (ils sont très intéressants mais ils ne peuvent pas être expliqués en 2 lignes) et à taper dans le champ des idées plutôt que dans les aspects techniques — ou alors à annoncer clairement ce que tu vas présenter au départ.

(C’est un petit détail mais j’ai un peu tiqué sur l’abus de notation $O(f(n)) = \{ g(n) \mid \dots \}$, où on écrit $f(n)$ pour dire $f$. Je préférerais faire sans, que ce soit pour les gens qui connaissent le sujet et vont préférer la définition rigoureuse, ou les gens qui ne connaissent pas peuvent se perdre avec des variables $n$ quantifiées ou définies nulles part, au milieu d’une définition un peu subtile.)

Tu écris $O({\rm id})$ pour $O(n)$ ? Et $O(n\mapsto n^2)$ pour $O(n^2)$ ?

D’ailleurs, c’est quantifié puisque techniquement (même si on ne le marque pas), on a $n\to \infty$.

Il y a une différence pour moi entre écrire $O(n^2)$ quand on utilise la notation (dans le contexte il est assez clair que l’on veut dire $n \mapsto n^2$) et écrire $O(f(n))$ quand on définit la notation, et qu’on a plein de quantificateurs dans les parages. La définition donnée dans l’article pour l’instant est

là où j’aimerais mieux lire

Je comprends ce que tu veux dire, mais il ne faut pas que le formalisme soit un frein inutile. On devrait définir et utiliser les objets de la même façon.

Sinon on introduit une difficulté en changeant de notation

Merci à tous pour vos retours ! Je m’attendais quelque peu à ce genre de retours et je les comprends et reçoit parfaitement. En tout cas, c’est extrêmement constructif et j’espère arriver à une situation qui vous (et à moi) conviendra davantage au final, je perçois mieux les problèmes intrinsèques. Je vais laisser reposer ma tête pour revenir avec une vision plus fraîche sur le sujet et étoffer les parties qui font défaut en essayant d’aller moins vite sur certains points et tentant de mieux expliquer. Le problème c’est que c’est un sujet qui me passionne et que j’ai trop de choses à exprimer sur ce sujet :/

Gasche:

Qui est le public cible pour cet article ? J’ai l’impression qu’il vise les personnes ayant déjà un bon bagage scientifique. Je pense qu’il serait utile de le préciser dans l’introduction.

J’avais aussi l’impression que cela s’adressait davantage à des bacheliers plutôt qu’à des enthousiastes à la fin des secondaires. Je souhaitais quand même toucher un public plus large en les invitant à réfléchir sur la nature des choses, quel problème on essaye de définir, comment on le définit et comment on construit à partir de lui-même. Il est vrai qu’il faut un bagage scientifique un peu plus conséquent pour ce genre de démarches.

Je pense qu’il faut être réaliste sur le fait que l’article sera indigeste pour les gens n’ayant pas ce bagage; les paragraphes qui contiennent des rappels de notion (par exemple la notion de "comportement asymptotique") doivent être compris comme des rappels de choses que les lecteurs ont probablement déjà vues mais un peu oubliées. En effet, leur traitement ne permet pas à une personne qui découvre complètement le domaine de les comprendre (et il y a trop de notions nouvelles pour qu’une personne débutante puisse suivre).

Cela me gêne que vous ayez eu cette impression parce que c’est une notion assez centrale dans ce domaine et j’ai un sentiment d’échec à cet égard. Je vais chercher à étoffer cette partie en vue de palier aux défauts soulevés. De mon point de vue personnel, j’ai observé que les étudiants avaient tendance à oublier extrêmement vite ce genre de notions parce que: 1) Ils comprennent bien que ce sont des complexités théoriques et qu’il faudra toujours mesurer en réalité. 2) On a des ordinateurs suffisamment puissants que pour ne pas s’en soucier, et on ne revient à ces notions que si l’on a un souci. 3) L’algorithmique n’est pas très populaire par rapport à d’autres branches de l’informatique, rares sont ceux qui vont voir plus loin que leur cours à son sujet.

Je ne suis qu’à demi convaincu par la partie "histoire des idées" du document. Je ne suis pas sûr de ce que tu veux dire au sujet de la thèse de Church-Turing, mais je ne comprends pas le sens que tu donnes à la phrase que tu cites, "Il est possible d’exprimer, par un ensemble de règles de calcul, tout ce qui est calculable en suivant un traitement systématique, un algorithme." J’ai l’impression que c’est soit tautologique (on peut calculer ce qui est calculable), soit difficilement compréhensible puisque les notions mentionnées ne sont pas définies. Pour moi le résultat central autour de Church-Turing est l’équivalence en terme de calculabilité entres machines de Turing, lambda-calculs et fonctions récursives, qui n’a pas la portée que tu présentes.

C’était justement le sens de ma phrase, l’équivalence de la calculabilité est définie par la construction d’un modèle (machines de Turing, …) qui obéit à un traitement systématique => on est capable de définir ce qui est calculable en employant un système simple. Je vais rajouter cela dans la partie à clarifier/étoffer.

Le document est concentré sur la calculabilité et la complexité comme sciences, et en particulier leur théorie et les problématiques de recherche qui en découle. C’est dit relativement clairement dans l’introduction, et c’est un choix intéressant. Mais il est peut-être un peu dommage d’occulter complètement le fait que la complexité est un outil utile, au jour le jour, pour les programmeurs qui réfléchissent à l’efficacité de leur code. Ce n’est clairement pas le point de vue central dans le document, donc je ne dis pas qu’il faudrait faire des tartines à ce sujet, mais je trouve un peu curieux de faire comme si ça n’existait pas du tout, un peu comme si on lisait un document introductif à la chimie ou à la physique qui occulte complètement le travail des gens qui appliquent ces sciences à l’industrie.

Si j’étais méchant, je dirais que le monde de l’industrie ne va jamais demander d’aller plus loin qu’une boucle for =) Parce qu’il faut, et des problèmes compliqués, et des gens qui veulent se renseigner pour savoir comment on peut résoudre le problème; sachant que son ego personnel est évidemment bien plus intelligent que tous les scientifiques. Fondamentalement, je veux bien rajouter une partie concernant les enjeux plus globaux de ce domaine. Ce n’est pas par pure volonté que je n’aborde pas ces points-là, c’est plus que ça ne m’était pas venu à l’esprit car hors propos par rapport à ce que je voulais mettre en avant.

P.S.: J’ai co-rédigé un document sur la complexité avec un point de vue très très différent, Algorithmique pour l’apprenti programmeur. Notre but était d’être accessible au plus grand nombre (on ne suppose rien de plus que les maths niveau collège), et de se concentrer sur l’usage concret en programmation. Je trouve ça très bien que les contenus ZdS s’élargissent avec des présentations complémentaires, qui couvrent d’autres aspects de la discipline. Merci pour ton travail !

J’avais suivi l’écriture de ce tutoriel à l’époque d’un certain site dont il ne faut plus prononcer le nom (sdz) =). J’avais trouvé dommage qu’ils s’arrêtaient si tôt.

(C’est un petit détail mais j’ai un peu tiqué sur l’abus de notation O(f(n)) = { g(n) \mid \dots }O(f(n))={g(n)∣…}, où on écrit f(n) pour dire f. Je préférerais faire sans, que ce soit pour les gens qui connaissent le sujet et vont préférer la définition rigoureuse, ou les gens qui ne connaissent pas peuvent se perdre avec des variables n quantifiées ou définies nulles part, au milieu d’une définition un peu subtile.)

Je reçois l’argument, mais il est très rare de présenter ces définitions sans l’apparition explicite d’une variable pour insister qu’on étudie la manière dont évolue cette complexité en fonction de la taille du problème. Mais oui, n n’est défini nulle part chez moi =)

Lucas-84:

Je trouve que c’est une super initiative. Le problème essentiel, je pense, c’est qu’il y a un décalage entre ce que tu annonces au départ et les thèmes que tu traites. Le passage subtil sur les modèles de calcul est assez expéditif (ça commence par "les fameuses machines de Turing" et ça continue directement avec un enchaînement de remarques beaucoup trop abstraites pour que ce soit compréhensible, à mon avis), alors que la partie "algorithmique pour l’industrie" est beaucoup plus détaillée.

Je comptais agrandir la partie concernant les modèles de calcul. Mais j’étais bloqué dans ma tête par l’envie de ne pas présenter un modèle en particulier mais d’avoir quand même un élément sur lequel se baser. Et personnellement, je pense que la machine de Turing a fait son temps … Mais oui, je comptais certainement revoir cette partie-là en particulier.

Par exemple, les notations asymptotiques pourraient être remplacées par des \lesssim≲ et \gtrsim≳ intuitifs sans que ça ne dérange personne. Et au risque de choquer les fans du CLRS, je trouve aussi que le théorème maître n’a pas d’intérêt scientifique — il ne comporte pas vraiment d’idée fondamentale sous-jacente et c’est un calcul technique qu’on imagine faisable a priori. Au passage, j’ai l’impression que tu mélanges un peu bornes inférieures et supérieures dans ton passage sur \log(n!).

≲ et ≳ pour moi c’est un non catégorique. Je n’ai vu que dans de très rares occasions ce genre de notations. Je ne trouve pas non plus le Master Theorem intéressant, mais c’est une clef de voûte beaucoup trop importante pour ne pas le mentionner, les seuls intérêts que j’y vois est la démonstration relativement simple (si on secoue les mains suffisamment forts, combien d’articles ont été écrits sur son manque de rigueur ?) et que cela met en évidence une manière de concevoir la complexité d’un problème de manière plus concrète avec cet arbre de complexité.

En bref, je pense que tu gagnerais à sélectionner quelques points que tu mentionnes dans ton "pour aller plus loin" (ils sont très intéressants mais ils ne peuvent pas être expliqués en 2 lignes) et à taper dans le champ des idées plutôt que dans les aspects techniques — ou alors à annoncer clairement ce que tu vas présenter au départ.

Personnellement, j’ai envie d’écrire des articles sur ces notions plus avancées. Mais oui, il y a un rush beaucoup trop important qui est lié au fait que je ne souhaitais faire qu’un survol pour susciter l’émergence de questions chez le lecteur et qu’il ait également de pistes pour voir ce qui a déjà été étudié.

Merci à vous deux !

Je reviens vers vous parce que j’ai mis à jour l’article, en essayant de prendre en compte vos remarques. J’espère que les aspects un peu nébuleux se sont suffisamment améliorés. Je reste convaincu que des points abordés nécessiteront des articles connexes futurs pour aller plus en profondeur sur certains points.

En attente de vos remarques éventuelles.

Merci pour les changements ! Je n’ai pas encore tout regardé, mais un retour rapide:

Cet article nécessite quand même un certain bagage scientifique, il est préférable d’avoir des connaissances de bases en informatique et cela s’adresserait donc à des étudiants étant au moins au milieu d’un bachelier.

C’est un détail mais pour moi un bachelier est une personne qui a obtenue son baccalauréat, donc être "au milieu d’un bachelier" est un concept étrange. Tu pourrais peut-être ajouter une formulation qui donne une équivalence dans le système LMD (Licence Master Doctorat), si c’est bien des études supérieures qu’il s’agit, puisque le système LMD est assez répandu en Europe et à l’international.

(Tu parles de connaissances "en informatique", mais je pense qu’il vaudrait mieux dire "en mathématiques et informatique" ou "en informatique théorique", car quelqu’un qui a suivi surtout une formation appliquée aurait du mal à suivre, alors qu’un mathématicien avec juste une très vague connaissance de Python pourrait sans doute suivre.)

Salut,

Je suis un peu mal à l’aise avec ta partie "Définitions".

Déjà elle ne donne pas clairement de définitions, ce qui est un peu déroutant.

Ensuite, la progression n’est pas super claire :

• tu ne donnes pas de définition du dictionnaire (tu pourrais presque enlever le paragraphe en fait 😁) ;
• tu dis en gros que la définition intuitive n’est pas suffisante (soit) ;
• ensuite tu montres (un peu rapidement) sur l’exemple du jeu de carte qu’on peut mesurer la complexité en termes d’opérations élémentaires ;
• ce qui pose la problème lors de la comparaison de problèmes très différents les uns avec les autres ;
• tu parles de la solution à ça (mais c’est pas explicite) que sont les règles de calculabilité.

La transition entre ces idées n’est pas assez explicite et je pense que tu gagnerais en clarté en la renforçant de manière importante. Un lecteur peu familier avec tout ça aura du mal à voir où tu veux en venir et sera potentiellement perdu.

Dans la suite, tu parles de l’universalité des règles de calcul et d’une méthode, mais je ne suis pas sûr d’avoir saisi la nuance. Puis tu ne parles pas de l’universalité avant, c’est un peu bizarre car la formulation de la première phrase laisse penser que oui.

La suite est étrange. Tu as ta liste de remarques qui tombe comme un cheveux sur la soupe, avec plein d’idées sans liant ou progression.

Puis tu parles de RAM (ce qui semble peu important pour la suite) et on saute à la partie d’après brutalement.

Et c’est tout pour le moment.

Bonjour,

Gasche:

C’est un détail mais pour moi un bachelier est une personne qui a obtenue son baccalauréat, donc être "au milieu d’un bachelier" est un concept étrange. Tu pourrais peut-être ajouter une formulation qui donne une équivalence dans le système LMD (Licence Master Doctorat), si c’est bien des études supérieures qu’il s’agit, puisque le système LMD est assez répandu en Europe et à l’international.

Justement, on parle de "Bachelor, Master and Doctoral Degree" au niveau européen. Et pour l’anecdote, la Belgique a remplacé les mots License par Master et, l’équivalent de votre licence, Candide par Bachelier.

Aabu:

Merci énormément pour ta réponse Aabu !

Déjà elle ne donne pas clairement de définitions, ce qui est un peu déroutant.

Ce point est parfaitement valide, je vais rajouter une mini-conclusion à cette partie pour mettre les choses au clair. Malgré que, d’un point de vue purement personnel, je pense que la recherche d’une définition est davantage d’une démarche personnelle, afin de trouver ses propres contre-exemples, et qu’il est préférable de présenter les thématiques connexes pour atteindre ce but.

La transition entre ces idées n’est pas assez explicite et je pense que tu gagnerais en clarté en la renforçant de manière importante. Un lecteur peu familier avec tout ça aura du mal à voir où tu veux en venir et sera potentiellement perdu.

Merci de cibler le point qui me posait problème. J’ai essayé de bouger des phrases pour que ce soit un peu plus cohérent. Il est vrai que ça manquait de logique et des choses sortaient de nulle part.

Ajouter "Licence" et/ou "Bachelor" pourrait clarifier dans tous les cas.

Ce point est parfaitement valide, je vais rajouter une mini-conclusion à cette partie pour mettre les choses au clair. Malgré que, d’un point de vue purement personnel, je pense que la recherche d’une définition est davantage d’une démarche personnelle, afin de trouver ses propres contre-exemples, et qu’il est préférable de présenter les thématiques connexes pour atteindre ce but.

Je comprends un peu l’idée, mais je trouve que pédagogiquement, ça reste plus facile de fournir une définition même imparfaite et d’expliquer d’où elle vient et ses éventuelles limites, que de donner les problématiques qui y conduisent et laisser le lecteur se débrouiller avec. L’intérêt d’un cours est justement de formaliser les connaissances pour faciliter leur assimilation, s’il faut faire la synthèse soi-même, autant donner une bibliographie exhaustive des articles sur le sujet et la lire dans l’ordre chronologique.

En tout cas, je trouve que c’est mieux. En particulier, le dernier paragraphe de "Définitions" ressemble à une définition ; il synthétise les idées essentielles pour la suite.

Merci énormément pour ta réponse Lucas-84 !

(Même remarque pour le paragraphe à ce propos dans ta conclusion.) Les classes de complexité conventionnelles sont au contraire définies comme des bornes supérieures (tel problème est dans telle classe s’il existe un algorithme pour ce problème de complexité inférieure à tel seuil). Les classes dérivées *-difficile sont, il est vrai, définies "inférieurement", mais par des réductions à d’autres problèmes. En pratique, ces questions de complexité minimale relèvent plutôt de la complexité "fine-grained" — comme dans ton exemple du tri.

Ce qui tu dis est tout à fait correct. Et ce point est d’ailleurs abordé dans l’article wikipédia associé. Mais je ne sais pas trop quel message passer, quelle position adopter. J’ai essayé de faire Salomon et j’ai transformé en ceci:

"""Il existe également une question opposée, quels sont tous les algorithmes qui ont pour complexité $\Omega(N \log N)$ ? Quid des autres, pourquoi ces différences ? Des tentatives de réponses sont données par la définition de classes de complexité, ensemble de problèmes dont la complexité est "équivalente". Ce sont des questions particulièrement ardues, qui nécessitent une grande rigueur dans leur définition; les classes sont toutefois définies en termes de $O(.)$, même si l’on cherche la plus petite classe englobante d’un problème. […]"""

Je pense qu’il y a trop d’abus de notations dans cette partie, surtout pour un article qui est censé introduire les notations asymptotiques. Pour rappel, l’argument logique est le suivant : pour que 2^k\ge N!2 k ≥N!, il faut que k\ge \log(N!)k≥log(N!) et donc il faut que k=\Omega(N\log N)k=Ω(NlogN). Une manière de passer de l’avant-dernière inégalité à la dernière est de dire \log(N!)=\sum_{i\le N}\log i\ge (N/2)\log(N/2)log(N!)=∑ i≤N logi≥(N/2)log(N/2) (pas besoin de Stirling ou autre). L’inégalité que tu donnes dans l’article est une borne supérieure !

C’est ce que j’avais écrit initialement mais en réécrivant j’ai du faire la boulette de ne pas relire 🤐. Je voulais mentionner Stirling parce que cela avait été le sujet de remarques de Floyd sur ce sujet spécifiquement.

Je n’ai pas compris cette remarque. Que sont les "cas" dont tu parles ?

J’ai corrigé et précisé qu’il s’agit des instances du problème, des configurations initiales possibles. Bien vu.

Je n’ai jamais entendu cette terminologie et je n’ai pas vraiment compris ta définition d’algorithme "aléatoire". Est-ce que tu parles de Las Vegas/Monte Carlo ?

Je voulais insister sur cette différence-là justement. Que "Las Vegas" donne toujours la bonne réponse mais au bout d’un nombre indéterminé d’étapes (randomized) alors que "Monte Carlo" donne quelque chose de correct à x% (probabilistic). Mais je sais qu’il y a beaucoup de confusions sur les termes (auquel peut s’adjoindre stochastic, approximate ou heuristic). Mais je n’avais pas ces algorithmes-là en tête, je pensais à ceux associés au streaming, au secretary problem, à Kirkpatrick–Seidel ou aux bloom filters. C’est davantage tout ce qui n’est pas probabilistic qu’on appelle randomized, c’est un mot plus général.

Pareil, je pense pas que ce paragraphe soit compréhensible. Il faut préciser quelque part qu’on compare le coût online/offline, non ?

J’ai essayé de clarifier le paragraphe, je suis pas encore convaincu, je verrai si j’ai plus d’inspiration dans la semaine :/ Est-ce qu’il faut préciser qu’on compare le coût online/offline ? Éventuellement, je ne sais pas, on peut faire les deux. Généralement, on compare le online par rapport au offline, parce que "c’est plus simple", cela a beaucoup de sens et que le coût entre le offline et le online est intéressant. Mais au niveau du online, on peut comparer le meilleur et le pire cas, voir l’évolution de ces variations, mais cela sert davantage de preuve de non-compétitivité. D’autre part, la complexité offline peut également fortement variée en fonction de la séquence d’actions choisies.

Oui, j’imagine que c’est peu utilisé… dans les domaines où on a pas besoin d’en écrire beaucoup ! Quand tu dois écrire des successions d’égalité "à constante universelle près", tu as vite envie de te débarrasser des notations de Landau. J’ose même pas imaginer ce que donneraient certains articles de probas avec des O partout.

Cela m’intéresserait de savoir de quels domaines vous parlez lorsque vous évoquez ces notations. Théorie des nombres ? Statistiques ? Optimisation ? Je vous crois à 100% sur le fait qu’on emploie ces symboles dans d’autres domaines. Parce que je suis relativement bien, sur arxiv, les catégories: Computational Complexity, Computational Geometry ou Data Structures and Algorithms. Et la seule référence (dans la première page par date) qui emploie cette notation: Algorithms and Hardness for Linear Algebra on Geometric Graphs et qui manifestement a besoin de définir ces symboles.

Ce qui tu dis est tout à fait correct. Et ce point est d’ailleurs abordé dans l’article wikipédia associé. Mais je ne sais pas trop quel message passer, quelle position adopter. J’ai essayé de faire Salomon et j’ai transformé en ceci:

"""Il existe également une question opposée, quels sont tous les algorithmes qui ont pour complexité $\Omega(N \log N)$ ? Quid des autres, pourquoi ces différences ? Des tentatives de réponses sont données par la définition de classes de complexité, ensemble de problèmes dont la complexité est "équivalente". Ce sont des questions particulièrement ardues, qui nécessitent une grande rigueur dans leur définition; les classes sont toutefois définies en termes de $O(.)$, même si l’on cherche la plus petite classe englobante d’un problème. […]"""

C’est pas faux mais peut-être que c’est juste pas le moment de parler des classes de complexité, non ? De manière générale cette partie "Analyse de complexité" part un peu dans tous les sens (typiquement, l’écart sur la conjecture de Collatz ?!). Je résume :

• Qu’est-ce qu’un "problème intéressant" ? (Ok, même si honnêtement je vois pas trop quelles informations je suis censé retenir de ce paragraphe)

• Ici il faudrait rajouter quelque chose comme : "La complexité d’un problème = la meilleure complexité d’un algorithme qui le résout."

• Les différentes notions de complexité (Tu en as pas déjà parlé dans un paragraphe au-dessus ?)

• Bornes supérieures sur la complexité d’un problème = la question associée au $O$

• Bornes inférieures sur la complexité d’un problème = la question associée au $\Omega$

Side note en dehors du tuto : si on ne définit pas les classes de complexité comme des gros $\Omega$, c’est probablement parce qu’on est très loin d’avoir les bons outils pour générer des bornes inférieures. Paradoxalement, dans le cas moyen, qui paraissait historiquement plus difficile parce qu’on ne disposait pas d’une théorie puissante de réductions entre problèmes, finalement on en arrive à faire de la complexité "avec $\Omega$ et $O$"  — mais dans un modèle de calcul plus faible, où on s’autorise juste à résoudre des SDPs.

C’est ce que j’avais écrit initialement mais en réécrivant j’ai du faire la boulette de ne pas relire 🤐. Je voulais mentionner Stirling parce que cela avait été le sujet de remarques de Floyd sur ce sujet spécifiquement.

D’accord, mais du coup il faut préciser c’est pour avoir quelque chose de plus précis qu’un $O$. D’ailleurs petite question : quels sont les travaux de Landau dont tu parles ?

J’ai corrigé et précisé qu’il s’agit des instances du problème, des configurations initiales possibles. Bien vu.

C’est toujours pas très clair dans ma tête. Qu’est-ce que veut dire "toutes les instances du problème peuvent s’exprimer au travers de cet argument" ? T’as un exemple de démonstration universelle vs existentielle pour un même problème ?

Je voulais insister sur cette différence-là justement. Que "Las Vegas" donne toujours la bonne réponse mais au bout d’un nombre indéterminé d’étapes (randomized) alors que "Monte Carlo" donne quelque chose de correct à x% (probabilistic). Mais je sais qu’il y a beaucoup de confusions sur les termes (auquel peut s’adjoindre stochastic, approximate ou heuristic). Mais je n’avais pas ces algorithmes-là en tête, je pensais à ceux associés au streaming, au secretary problem, à Kirkpatrick–Seidel ou aux bloom filters. C’est davantage tout ce qui n’est pas probabilistic qu’on appelle randomized, c’est un mot plus général.

D’accord, ça a l’air assez vague comme terminologie, du coup. Tu pourrais juste dire qu’il existe des algorithmes qui font des choix aléatoires, que souvent on les autorise à se tromper avec une faible probabilité et que parfois leur complexité dépend des résultats de ces choix aléatoires.

J’ai essayé de clarifier le paragraphe, je suis pas encore convaincu, je verrai si j’ai plus d’inspiration dans la semaine :/ Est-ce qu’il faut préciser qu’on compare le coût online/offline ? Éventuellement, je ne sais pas, on peut faire les deux. Généralement, on compare le online par rapport au offline, parce que "c’est plus simple", cela a beaucoup de sens et que le coût entre le offline et le online est intéressant. Mais au niveau du online, on peut comparer le meilleur et le pire cas, voir l’évolution de ces variations, mais cela sert davantage de preuve de non-compétitivité. D’autre part, la complexité offline peut également fortement variée en fonction de la séquence d’actions choisies.

Non mais ce dont tu parles, de toute manière ça ne s’applique qu’à des algorithmes online. Il faudrait simplement expliquer ce que veut dire online, et ensuite dire qu’une manière d’analyser de type d’algorithme/modèle (la fameuse "analyse compétitive"), c’est de comparer son coût au coût du meilleur algorithme offline. Après évidemment la notion de "coût" est très abstraite.

Haha si j’en crois arxiv, mes centres d’intérêt sont cs.ST, cs.CC, math.PR, math.ST et math.FA, quoi que ça veuille dire !

Après je suis pas un militant des notations, je pense de manière générale que ça n’est pas très important, et qu’on pourrait apprendre les concepts sans trop se prendre la tête. A cet égard, $\lesssim$ est plus proche de ce que tu écrirais sur un brouillon ou sur un tableau. Mais j’utilise aussi $O$ et $\Omega$ dans le sens "fonction anonyme" en dehors d’un calcul.

Pour répondre à ta question, je dirais que la notation est assez largement utilisée en probas. Ceci dit, si tu es déjà dérangé par un petit $\lesssim$, je pense que tu serais outré par les notations de Talagrand, qui utilise $L$ comme une constante universelle, qui, même utilisée plusieurs fois au sein de la même équation, peut prendre une valeur différente — mais pour être honnête, ça allège beaucoup ses expressions !

Merci pour la réponse.

C’est pas faux mais peut-être que c’est juste pas le moment de parler des classes de complexité, non ? De manière générale cette partie "Analyse de complexité" part un peu dans tous les sens (typiquement, l’écart sur la conjecture de Collatz ?!). Je résume :

• Qu’est-ce qu’un "problème intéressant" ? (Ok, même si honnêtement je vois pas trop quelles informations je suis censé retenir de ce paragraphe)

• Ici il faudrait rajouter quelque chose comme : "La complexité d’un problème = la meilleure complexité d’un algorithme qui le résout."

• Les différentes notions de complexité (Tu en as pas déjà parlé dans un paragraphe au-dessus ?)

• Bornes supérieures sur la complexité d’un problème = la question associée au $O$

• Bornes inférieures sur la complexité d’un problème = la question associée au $\Omega$

---

Side note en dehors du tuto : si on ne définit pas les classes de complexité comme des gros $\Omega$, c’est probablement parce qu’on est très loin d’avoir les bons outils pour générer des bornes inférieures. Paradoxalement, dans le cas moyen, qui paraissait historiquement plus difficile parce qu’on ne disposait pas d’une théorie puissante de réductions entre problèmes, finalement on en arrive à faire de la complexité "avec $\Omega$ et $O$"  — mais dans un modèle de calcul plus faible, où on s’autorise juste à résoudre des SDPs.

J’ai rajouté la phrase que tu proposais sur le fait qu’on définisse la complexité d’un problème que celui du meilleur algorithme qui le résout.

D’accord, mais du coup il faut préciser c’est pour avoir quelque chose de plus précis qu’un $O$. D’ailleurs petite question : quels sont les travaux de Landau dont tu parles ?

Je parlais des travaux liés aux questions soulevées par l’école de pensée de "de La Vallée-Poussin", notamment liées à l’expansion en power series des fonctions analytiques, est-ce que cela est possible, est-ce que Fourier approxime mieux que Taylor ? Ce qui a conduit, d’une part, à Chebyshev, Bernstein ou Jackson, et d’autre part, à la notion de tauberian et schlicht functions. Landau n’était peut-être pas le plus célèbre de cette période mais je trouve que ces travaux synthétisent l’état d’esprit de l’époque.

C’est toujours pas très clair dans ma tête. Qu’est-ce que veut dire "toutes les instances du problème peuvent s’exprimer au travers de cet argument" ? T’as un exemple de démonstration universelle vs existentielle pour un même problème ?

Prenons le problème suivant: "Quel est le maximum dans une liste ?". Une démonstration universelle serait de calculer l’espérance de la position du maximum, et donc du nombre d’éléments à lire, soit N/2. Alors qu’une démonstration existentielle serait de jouer face à un adversaire qui peut changer la position du maximum après chaque coup du joueur, on est alors obligé de consulter dans le pire cas tous les éléments; il existe au moins un cas qui nécessite cette complexité.

D’accord, ça a l’air assez vague comme terminologie, du coup. Tu pourrais juste dire qu’il existe des algorithmes qui font des choix aléatoires, que souvent on les autorise à se tromper avec une faible probabilité et que parfois leur complexité dépend des résultats de ces choix aléatoires.

Les algorithmes probabilistic ne font pas forcément de choix aléatoires. L’aspect aléatoire vient du fait qu’il y a un pigeonhole principle et qu’on ne sait pas prédire quels éléments vont rentrer en collision. Mais ils ne se basent pas forcément sur un processus stochastique de type RNG.

Non mais ce dont tu parles, de toute manière ça ne s’applique qu’à des algorithmes online. Il faudrait simplement expliquer ce que veut dire online, et ensuite dire qu’une manière d’analyser de type d’algorithme/modèle (la fameuse "analyse compétitive"), c’est de comparer son coût au coût du meilleur algorithme offline. Après évidemment la notion de "coût" est très abstraite.

J’ai essayé d’éclaircir ce passage.

Je parlais des travaux liés aux questions soulevées par l’école de pensée de "de La Vallée-Poussin", notamment liées à l’expansion en power series des fonctions analytiques, est-ce que cela est possible, est-ce que Fourier approxime mieux que Taylor ? Ce qui a conduit, d’une part, à Chebyshev, Bernstein ou Jackson, et d’autre part, à la notion de tauberian et schlicht functions. Landau n’était peut-être pas le plus célèbre de cette période mais je trouve que ces travaux synthétisent l’état d’esprit de l’époque.

C’est intéressant, mais quel est le rapport avec la minoration de $\log(n!)$ ? Landau a donné un développement asymptotique plus précis ?

Prenons le problème suivant: "Quel est le maximum dans une liste ?". Une démonstration universelle serait de calculer l’espérance de la position du maximum, et donc du nombre d’éléments à lire, soit N/2. Alors qu’une démonstration existentielle serait de jouer face à un adversaire qui peut changer la position du maximum après chaque coup du joueur, on est alors obligé de consulter dans le pire cas tous les éléments; il existe au moins un cas qui nécessite cette complexité.

Mais dans les deux cas tu ne parles pas de la même complexité : dans la première tu supposes que tes instances sont aléatoires, alors que la deuxième est dans un modèle de calcul étrange (pas très bien défini). J’ai l’impression que cette propriété d’être "existentielle" ou "universelle" est une propriété d’un problème (d’un théorème, si tu veux), pas d’une démonstration. Par ailleurs, si par "cas" tu entends encore une fois "instance", je ne vois pas en quoi la démonstration que tu donnes dans ton article est "universelle" : un algorithme de tri par comparaison peut très bien avoir une complexité temporelle en $O(n)$ sur certaines classes d’instances.

Les algorithmes probabilistic ne font pas forcément de choix aléatoires. L’aspect aléatoire vient du fait qu’il y a un pigeonhole principle et qu’on ne sait pas prédire quels éléments vont rentrer en collision. Mais ils ne se basent pas forcément sur un processus stochastique de type RNG.

Tu veux dire que tu appelles "probabilistic" un algorithme déterministe à qui tu donnes des instances aléatoires ? Je n’ai jamais vu cette terminologie…

C’est intéressant, mais quel est le rapport avec la minoration de $\log(n!)$ ? Landau a donné un développement asymptotique plus précis ?

Si c’est par pure curiosité, à l’époque, on retrouvait les idées suivantes : les séries formelles peuvent avoir un rayon de convergence, quel est le comportement hors de ces limites ? Est-ce que Taylor est "mieux" que Fourier ? Est-ce qu’on peut définir une meilleure approximation à l’infini ou dans un intervalle donné ? Comment peut-on dire que l’approximation de Ramanujan est meilleure que celle de Stirling ? Sujets qui seront étudiés plus tardivement par Cheney ou Jackson. Je ne peux que conseiller le livre : "An Introduction to the Approximation of Functions" de Rivlin. Si la question est en rapport avec la contribution de Landau à ce sujet, cela me paraît un peu hors sujet, l’un de ses livres "Handbuch der Lehre von der Verteilung der Primzahlen" donne des outils de démonstrations par rapport à ce type de question.

Mais dans les deux cas tu ne parles pas de la même complexité : dans la première tu supposes que tes instances sont aléatoires, alors que la deuxième est dans un modèle de calcul étrange (pas très bien défini). J’ai l’impression que cette propriété d’être "existentielle" ou "universelle" est une propriété d’un problème (d’un théorème, si tu veux), pas d’une démonstration. Par ailleurs, si par "cas" tu entends encore une fois "instance", je ne vois pas en quoi la démonstration que tu donnes dans ton article est "universelle" : un algorithme de tri par comparaison peut très bien avoir une complexité temporelle en O(n) sur certaines classes d’instances.

Je ne comprends pas la différence que tu fais entre un théorème et une démonstration, pour moi un théorème est le résultat d’une démonstration, cela me paraîtrait étonnant si la démonstration n’employait pas une hypothèse du théorème. Ici, c’est la différence entre montrer que tous les cas peuvent s’exprimer au travers d’un même algorithme et que il existe un cas qui nécessite au moins un algorithme ayant cette complexité, si il existe des instances du problème ayant une meilleure complexité, cela n’intervient pas dans l’argumentation. Le "meilleur" cas ayant évidemment une complexité différente par rapport au "pire" et donc ça n’aurait aucun sens de parler d’universalité.

Tu veux dire que tu appelles "probabilistic" un algorithme déterministe à qui tu donnes des instances aléatoires ? Je n’ai jamais vu cette terminologie…

Non, absolument pas, un algorithme est censé décider une instances d’un problème, si on lui donne une instance aléatoire comment peut-il répondre à la question, cela n’aurait strictement aucun sens. Mais rien n’empêche d’employer des instances "aléatoires" en vue de résoudre le problème, comme pour un algorithme du "Convex hull". J’emploie le terme "probabilistic" dans un sens qui me paraît "standard" en complexité : probabilistic data structures, le fameux test de primalité de Rabin, sans doute le "premier", l’algorithme de Morris pour estimer la cardinalité, ou encore l'hyperloglog qui avait été remis au goût du jour avec le big data et les streaming algorithms.

Bon, je crois que la communication entre nous est impossible. Je pense que je ne comprendrai pas ta "définition" d’universalité/existentialité tant que je n’aurai pas vu une définition formelle. Et quand je lis

Non, absolument pas, un algorithme est censé décider une instances d’un problème, si on lui donne une instance aléatoire comment peut-il répondre à la question, cela n’aurait strictement aucun sens.

je me dis qu’effectivement, on doit pas vivre sur la même planète. BTW, tous les algos que tu me cites font des choix aléatoires.