questions générales sur la sélection d'un meilleur élément parmi un ensemble d'alternatives disponibles.
Je suis plutôt confus par la littérature sur l'optimisation continue et la littérature TCS sur les types de programmes mathématiques (MP) (continus) qui peuvent être résolus efficacement et ceux qui ne le peuvent pas. La communauté de l'optimisation continue semble affirmer que tous les programmes...
Dans ma formation en informatique, je remarque de plus en plus que la plupart des problèmes discrets sont NP-complets (au moins), alors que l'optimisation de problèmes continus est presque toujours facilement réalisable, généralement grâce à des techniques de gradient. Y a-t-il des exceptions à...
Que sait-on de la complexité du problème suivant: Étant donné: nombres rationnels .x1<x2<…<xnx1<x2<…<xnx_1 < x_2 < \dotso < x_n Sortie: entiers .y1≤y2≤…≤yny1≤y2≤…≤yny_1 \le y_2 \le \dotso \le y_n Objectif: minimiser où∑1≤i<j≤ne(i,j),∑1≤i<j≤ne(i,j),\sum_{1 \le i < j \le n}...
Les ordinateurs quantiques sont très bons pour échantillonner des distributions que nous ne savons pas échantillonner en utilisant des ordinateurs classiques. Par exemple, si f est une fonction booléenne (de à - 1 , 1 ) qui peut être calculée en temps polynomial, alors avec des ordinateurs...
Je m'intéresse au problème d'emballer des copies identiques de rectangles (2 dimensions) dans un polygone convexe (2 dimensions) sans chevauchements. Dans mon problème, vous n'êtes pas autorisé à faire pivoter les rectangles et pouvez supposer qu'ils sont orientés parallèlement aux axes. On vous...
Considérez les problèmes d'optimisation de la forme suivante. Soit une fonction calculable en temps polynomial qui mappe une chaîne en un nombre rationnel. Le problème d'optimisation est le suivant: quelle est la valeur maximale de sur les chaînes à bits ?x f ( x ) n xf(x)f(x)f(x)xxxF( x...
Comme nous le savons, la fonction kkk -clique CLIQUE(n,k)CLIQUE(n,k)CLIQUE(n,k) prend un sous-graphe ( couvrant ) d'un graphe sommet complet , et les sorties si contient une -clique . Les variables dans ce cas correspondent aux arêtes de K n . On sait (Razborov, Alon-Boppana) que, pour 3 ≤ k ≤ n /...
Le code de Huffman pour une distribution de probabilité est le code de préfixe avec la longueur moyenne pondérée minimale du mot de code , où est la longueur du ème mot de code. C'est un théorème bien connu que la longueur moyenne par symbole du code Huffman est comprise entre et , où est...
On vous donne un graphe avec n sommets. Il peut être bipartite si vous le souhaitez. Il existe m ensembles d'arêtes E 1 , … , E m ⊆ E (disons disjoints). Je m'intéresse au problème de trouver un sous-ensemble S ⊆ V , aussi petit que possible (ou même plus petit), tel que le graphe induit G S ait au...
Est-il possible de tester algorithmiquement si un nombre calculable est rationnel ou entier? En d'autres termes, serait-il possible pour une bibliothèque qui implémente des nombres calculables de fournir les fonctions isIntegerou isRational? Je suppose que ce n'est pas possible, et que cela est en...
Mon fils de 8 ans s'est ennuyé à créer des labyrinthes conventionnels et a commencé à créer des variantes qui ressemblent à ceci: L'idée est de partir de x et d'atteindre o via les règles normales. De plus, vous pouvez "sauter" de tout entier à tout autre entier , mais vous devez payerdollars pour...
Considérez ce problème: étant donné une liste d'ensembles finis, recherchez un ordre qui minimise .s1,s2,s3,…s1,s2,s3,…s_1, s_2, s_3, \ldots|s1|+|s1∪s2|+|s1∪s2∪s3|+…|s1|+|s1∪s2|+|s1∪s2∪s3|+…|s_1| + |s_1 \cup s_2| + |s_1 \cup s_2 \cup s_3| + \ldots Existe-t-il des algorithmes connus pour cela?...
Nous savons que les programmes linéaires (LP) peuvent être résolus exactement en temps polynomial en utilisant la méthode ellipsoïde ou une méthode de point intérieur comme l'algorithme de Karmarkar. Certains LP avec un nombre super-polynomial (exponentiel) de variables / contraintes peuvent...
Il y a de nombreuses années, j'ai entendu dire que le calcul du NFA minimal (automate fini non déterministe) à partir d'un DFA (déterministe) était une question ouverte, par opposition à la direction inverse qui est connue depuis des décennies et est bien étudiée avec un efficace algorithme....
Considérez le problème suivant: Entrée : un hyperplan , donné par un vecteur et en représentation binaire standard.H= { y ∈ Rn: unTy = b }H={y∈Rn:uneTy=b}H = \{ \mathbf{y} \in \mathbb{R}^n: \mathbf{a}^T\mathbf{y} = {b}\}a ∈ Znune∈Zn\mathbf{a} \in \mathbb{Z}^nb ∈ Zb∈Zb \in \mathbb{Z} Sortie :x ∈ Zn=...
J'ai posé cette question sur Stack Overflow il y a un moment: Problème: la vente de Bob . Quelqu'un a également suggéré de poser la question ici. Quelqu'un a déjà posé une question liée à ce problème ici - sous- forêt de poids minimum de cardinalité donnée - mais pour autant que je comprends cela...
Considérons l' espace à nnn dimensions {0,1}n{0,1}n\{0,1\}^n , et soit ccc une contrainte linéaire de la forme a1x1+a2x2+a3x3+ ... +an−1xn−1+anxn≥ka1x1+a2x2+a3x3+ ... +an−1xn−1+anxn≥ka_1x_1 + a_2x_2 + a_3x_3 +\ ...\ + a_{n-1}x_{n-1} + a_nx_n \geq k , où ai∈Rai∈Ra_i \in \mathbb{R} , et k ∈ R...
Je prépare du matériel de cours sur l'heuristique pour l'optimisation et j'ai étudié les méthodes de descente de coordonnées. Le réglage est ici une fonction multivariée que vous souhaitez optimiser. f a la propriété qui se limite à une seule variable, il est facile à optimiser. Ainsi, la descente...
Je me suis récemment intéressé au problème général de l'optimisation de l'utilisation de la mémoire dans une situation où il y a plus d'un type de mémoire disponible, et il y a un compromis entre la capacité d'un segment de mémoire donné et la vitesse d'accès. L'exemple familier est un programme...
Quelle est la complexité de calcul de l'optimisation de diverses fonctions sur le groupe unitaire ?U(n)U(n)\mathcal{U}(n) Une tâche typique, résultant souvent en théorie quantique de l' information, on maximiser le nombre de types (ou des polynômes d'ordre supérieur en U ) sur l' ensemble des...