Jednym ze świętych graali projektowania algorytmów jest znalezienie silnie wielomianowego algorytmu programowania liniowego, tj. Algorytmu, którego czas działania jest ograniczony wielomianem w liczbie zmiennych i ograniczeń i jest niezależny od wielkości reprezentacji parametrów (przy założeniu...
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...
Przybliżenie liczby kolorów wydaje się łatwe na niewielkich wykluczonych wykresach przy użyciu algorytmu Jung / Shah. Jakie są inne przykłady problemów, które są trudne na ogólnych wykresach, ale łatwe na niewielkich wykluczonych wykresach? Aktualizacja 10/24 Wydaje się, że podąża za wynikami...
Lata osiemdziesiąte dały początek modelom obliczeń równoległych PRAM i BSP . Wygląda na to, że okres świetności obu modeli przypadał na przełom lat 80. i 90. Czy obszary te są nadal aktywne w zakresie badań algorytmów równoległych? Czy istnieją nowsze, bardziej wyrafinowane modele do obliczeń...
W przypadku problemu maksymalnego przepływu wydaje się, że istnieje wiele bardzo wyrafinowanych algorytmów, przy czym co najmniej jeden opracowano dopiero w zeszłym roku. Max przepływy Orlina w czasie O (mn) lub lepiej daje algorytm działający w O (VE). Z drugiej strony algorytmy, które...
Prowadzę kurs zaawansowanych algorytmów i chciałbym uwzględnić niektóre tematy związane z uczeniem maszynowym, które zainteresują moich studentów. W związku z tym chciałbym usłyszeć opinie ludzi na temat najbardziej interesujących / największych wyników algorytmicznych w uczeniu maszynowym....
Podczas badań pojawił się następujący problem, który jest zaskakująco czysty: Masz źródło monet. Każda moneta ma stronniczość, a mianowicie prawdopodobieństwo upadku na „głowę”. Dla każdej monety niezależnie istnieje prawdopodobieństwo 2/3, że ma ona stronniczość co najmniej 0,9, a przy pozostałym...
Łańcuch ma podsekwencje, ale zwykle nie wszystkie są odrębne. Jaka jest złożoność znalezienia maksymalnej częstotliwości dowolnego podsekwencji?2n2n2^n Na przykład ciąg „podsekwencja” zawiera 7 kopii podsekwencji „sue” i jest to maksimum. Przykładowy kod brute-force na stronie...
Były dwa pytania zadawane niedawno na cs.se które były albo spokrewnione lub miał szczególny przypadek równoznaczne z następującym pytaniem: Załóżmy, że masz ciąg a1,a2,…ana1,a2,…ana_1, a_2, \ldots a_n z nnn liczb takich, że Rozłóż go na sumę dwóch permutacji, i , z , tak...
Szukam ładnych przykładów, w których występuje następujące zjawisko: (1) Problem algorytmiczny wygląda na trudny, jeśli chcesz go rozwiązać, korzystając z definicji i używając tylko standardowych wyników. (2) Z drugiej strony staje się łatwe, jeśli znasz jakieś (nie tak standardowe)...
Prezentowałem wykład na temat sortowania naleśników i wspomniałem, że: Sortowanie według zamian jest trudne „podpisany” sortując odwrócenia jest w P . Co skłoniło mnie do myślenia. W pewnym sensie sortowanie „sygnowane” jest „ukierunkowane” - możesz postrzegać znak jako kierunek (i rzeczywiście...
Niech klasa A oznacza wszystkie wykresy wielkości które mają cykl hamiltonowski. Z tej klasy łatwo jest utworzyć losowy wykres - weź n izolowanych węzłów, dodaj losowy cykl hamiltonowski, a następnie losowo dodaj krawędzie.nnnnnn Niech klasa B oznacza wszystkie wykresy wielkości które nie mają...
W ISGCI listy ponad 1100 klas grafów. W przypadku wielu z nich wiemy, czy można ustalić niezależny zestaw w czasie wielomianowym; nazywane są czasem klasami IS-easy . Chciałbym skompilować listę maksymalnych klas IS-easy. Klasy te razem tworzą granicę (znanej) podatności na rozwiązywanie tego...
Załóżmy, że mam poset „S” i monotoniczny predykat „P” na S. Chcę znaleźć jeden lub wszystkie maksymalne elementy S spełniające P. EDIT : Jestem zainteresowany minimalizując liczbę ocen P . Jakie algorytmy istnieją dla tego problemu i jakich właściwości i dodatkowych operacji wymagają na S? Co z...
Jeśli jest nieukierunkowane -regular wykres i jest podzbiorem wierzchołków liczności , wywołać ekspansję krawędzi o o ilościd S ≤ | V | / 2G=(V,E)G=(V,E)G=(V,E)dddSSS≤|V|/2≤|V|/2\leq |V|/2SSS ϕ(S):=Edge s ( S, V- S)re⋅ | S.| ⋅ | V.- S|ϕ(S):=Edges(S,V−S)d⋅|S|⋅|V−S|\phi(S) := \frac...
Edycja: wybieram odpowiedź z najwyższym wynikiem do 6 grudnia 2012 r. To delikatne pytanie. Pojęcie (deterministycznych) algorytmów sięga BC. Co z algorytmami probabilistycznymi? W tym wpisie wiki algorytm Rabina dla problemu najbliższej pary w geometrii obliczeniowej podano jako pierwszy...
Właśnie nauczyłem losowego algorytmu skrótu Karger-Stein w mojej klasie algorytmów dla absolwentów. To prawdziwy klejnot algorytmiczny , więc nie mogę tego nie uczyć, ale zawsze denerwuje mnie, ponieważ nie znam innych zastosowań głównej techniki. (Trudno więc przypisać pracę domową, która...
Przez jakiś czas myślałem o następującym problemie i nie znalazłem rozwiązania wielomianowego. Tylko brutalne źródło. Próbowałem też zredukować problem NP-Complete bez powodzenia. Oto problem : Masz posortowany zestaw {(A1,B1),(A2,B2),…,(An,Bn)}{(A1,B1),(A2,B2),…,(An,Bn)}\{(A_1, B_1), (A_2,...
Ku mojemu zaskoczeniu nie udało mi się znaleźć artykułów na ten temat - prawdopodobnie przeszukałem niewłaściwe słowa kluczowe. Mamy więc tablicę czegokolwiek i funkcję na jej indeksach; jest permutacją.ffffff Jak zmienić kolejność tablic zgodnie z pamięcią i czasem działania tak blisko i jak to...
W przypadku zwykłego języka (NFA, DFA, gramatyki lub wyrażenia regularnego), jak można policzyć liczbę słów akceptowanych w danym języku? Interesujące są zarówno „z dokładnie n literami”, jak i „z najwyżej n literami”. Margareta Ackerman ma dwa artykuły na powiązany temat wyliczania słów...