ogólne pytania dotyczące wyboru najlepszego elementu z zestawu dostępnych alternatyw.
Jestem raczej zdezorientowany literaturą o ciągłej optymalizacji i literaturą TCS o tym, które rodzaje (ciągłych) programów matematycznych (MP) można skutecznie rozwiązać, a które nie. Wydaje się, że społeczność ciągłej optymalizacji twierdzi, że wszystkie programy wypukłe można skutecznie...
W mojej edukacji informatycznej coraz częściej zauważam, że większość dyskretnych problemów jest NP-kompletna (przynajmniej), podczas gdy optymalizacja ciągłych problemów jest prawie zawsze łatwo osiągalna, zwykle za pomocą technik gradientowych. Czy są od tego
Co wiadomo na temat złożoności następującego problemu: Biorąc pod uwagę: liczby wymierne x1<x2<…<xnx1<x2<…<xnx_1 < x_2 < \dotso < x_n . Wyjście: liczby całkowite y1≤y2≤…≤yny1≤y2≤…≤yny_1 \le y_2 \le \dotso \le y_n . Cel: zminimalizować ∑1≤i<j≤ne(i,j),∑1≤i<j≤ne(i,j),\sum_{1...
Komputery kwantowe są bardzo dobre do dystrybucji próbkowania, których nie wiemy jak próbkować przy użyciu klasycznych komputerów. Na przykład, jeśli f jest funkcją logiczną (od do ), którą można obliczyć w czasie wielomianowym, to za pomocą komputerów kwantowych możemy skutecznie próbkować zgodnie...
Interesuje mnie problem pakowania identycznych kopii (2-wymiarowych) prostokątów w wypukły (2-wymiarowy) wielokąt bez nakładania się. W moim problemie nie wolno obracać prostokątów i można założyć, że są one ustawione równolegle do osi. Właśnie podano wymiary prostokąta i wierzchołki wielokąta i...
Rozważ problemy z optymalizacją w poniższym formularzu. Niech f(x)f(x)f(x) będzie funkcją obliczalną w czasie wielomianowym, która odwzorowuje ciąg xxx na liczbę wymierną. Problem optymalizacji jest następujący: jaka jest maksymalna wartość f(x)f(x)f(x) ponad nnn bitowych ciągów xxx...
Jak wiemy, funkcja - pobiera ( obejmujący ) z pełnego wykresu -vertex , i wyprowadza iff zawiera klik . Zmienne w tym przypadku odpowiadają krawędzi z . Wiadomo (Razborov, Alon-Boppana), że dla funkcja ta wymaga obwodów monotonicznych o wielkości około . C L I Q U E ( n , k )kkkdoL IQ Umi( n , k...
Kod Huffmana dla rozkładu prawdopodobieństwa jest kodem prefiksu o minimalnej średniej ważonej długości słowa kodowego , gdzie jest długością tego słowa kluczowego. Jest dobrze znanym twierdzeniem, że średnia długość na symbol kodu Huffmana zawiera się między a , gdzie jest entropią Shannona...
Otrzymujesz wykres z n wierzchołkami. Jeśli chcesz, może być dwustronny. Istnieje m zestawów krawędzi E 1 , … , E m ⊆ E (powiedz rozłączny). Interesuje mnie problem znalezienia podzbioru S ⊆ V , tak małego, jak to możliwe (lub nawet mniejszego), takiego, że indukowany wykres G S ma co najmniej...
Czy możliwe jest algorytmiczne testowanie, czy liczba obliczalna jest liczbą wymierną czy całkowitą? Innymi słowy, możliwe byłoby dla biblioteki, który implementuje numery obliczalne, aby zapewnić funkcje isIntegerlub isRational? Zgaduję, że nie jest to możliwe i że jest to w jakiś sposób związane...
Mój 8-latek znudził się tworzeniem konwencjonalnych labiryntów i zaczął tworzyć warianty, które wyglądają tak: Chodzi o to, aby zacząć od x i osiągnąć normalne zasady. Dodatkowo możesz „przeskoczyć” z dowolnej liczby całkowitej aaa na inną liczbę całkowitą bbb , ale musisz zapłacić...
Rozważ ten problem: biorąc pod uwagę listę zbiorów skończonych, znajdź porządek który minimalizuje .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 Czy istnieją na to znane algorytmy? Jaka jest...
Wiemy, że programy liniowe (LP) można rozwiązać dokładnie w czasie wielomianowym za pomocą metody elipsoidy lub metody punktu wewnętrznego, takiej jak algorytm Karmarkara. Niektóre LP z super-wielomianową (wykładniczą) liczbą zmiennych / ograniczeń można również rozwiązać w czasie wielomianowym,...
Wiele lat temu słyszałem, że obliczenie minimalnego NFA (niedeterministycznego automatu skończonego) z DFA (deterministycznego) było otwartym pytaniem, w przeciwieństwie do odwrotnego kierunku, który jest znany od dziesięcioleci i jest dobrze zbadany z wydajnym algorytm. Czy ktoś wymyślił...
Rozważ następujący problem: Dane wejściowe : hiperpłaszczyzna H = { y ∈ R n : a T y = b }H={y∈Rn:aTy=b}H = \{ \mathbf{y} \in \mathbb{R}^n: \mathbf{a}^T\mathbf{y} = {b}\} , podana przez wektor a ∈ Z na∈Zn\mathbf{a} \in \mathbb{Z}^n i b ∈ Zb∈Zb \in \mathbb{Z} w standardowej reprezentacji...
Jakiś czas temu zadałem to pytanie na temat Przepełnienia stosu: Problem: sprzedaż Boba . Ktoś zasugerował także opublikowanie pytania tutaj. Ktoś już zadał tutaj pytanie związane z tym problemem - minimalna waga lasów danej liczności - ale o ile rozumiem, nie pomaga mi to z moim problemem. Warto...
Rozważmy nnn -wymiarowej przestrzeni {0,1}n{0,1}n\{0,1\}^n , niech ccc być liniowy ograniczenie formy 1 x 1 + 2 x 2 + 3 x 3 + . . . + a n - 1 x n - 1 + a n x n ≥ k , gdzie a i ∈ R , x i ∈a1x1+a2x2+a3x3+ ... +an−1xn−1+anxn≥ka1x1+a2x2+a3x3+ ... +an−1xn−1+anxn≥ka_1x_1 + a_2x_2 + a_3x_3 +\ ...\ +...
Przygotowuję materiały szkoleniowe na temat heurystyki do optymalizacji i szukam metod zejścia ze współrzędnymi. Ustawienie jest tu wielowymiarowa funkcja , które chcesz zoptymalizować. f ma właściwość ograniczoną do dowolnej pojedynczej zmiennej, którą łatwo zoptymalizować. Tak więc zejście...
Niedawno zainteresowałem się ogólnym problemem optymalizacji wykorzystania pamięci w sytuacji, gdy dostępny jest więcej niż jeden rodzaj pamięci, i istnieje kompromis między pojemnością danego segmentu pamięci a szybkością dostępu do niego. Znanym przykładem jest program decydujący, kiedy...
Jaka jest złożoność obliczeniowa optymalizacji różnych funkcji w grupie jednolitej ?U(n)U(n)\mathcal{U}(n) Typowe zadanie, często wynikające z teorii informacji kwantowej byłoby maksymalizując ilość typu (lub wyższych wielomiany rzędu w U ) w stosunku do wszystkich macierze jednostkowe U . Czy...