Pytania otagowane jako ds.algorithms

Pytania dotyczące dobrze zdefiniowanych instrukcji wykonania zadania oraz odpowiedniej analizy pod względem czasu / pamięci / itp.

1
Algorytm optymalnego sortowania w liczbie zamian
Biorąc pod uwagę ciąg liczb, czy można go sortować za pomocą porównań O ( n ln n ) i O ( n ) zamian / ruchów? Każdy wskaźnik do publikacji na ten temat lub kontrargumentów pokazujących dolną granicę Ω ( n ln n ) byłby pomocny.nnnO(nlnn)O(nln⁡n)O(n \ln n)O(n)O(n)O(n)Ω(nlnn)Ω(nln⁡n)\Omega(n \ln n)
2
Maksymalne cięcie w kształcie euklidesa w małych wymiarach
x1,…,xnx1,…,xnx_1, \ldots, x_nR2R2\mathbb{R}^2∥xi−xj∥2‖xi−xj‖2\|x_i - x_j\|^22323\frac 2 32323\frac 2 3 Najgorszy przykład, jaki mogę znaleźć, to 3 punkty na równobocznym trójkącie, który osiąga . Zauważ, że losowy podział dałby , ale intuicyjnie wydaje się intuicyjnie, że w niskich wymiarach można skupić się lepiej niż losowo.2323\frac 2 31212\frac 1 2 Co się …
2
Odwołanie do szybkiego algorytmu dla najkrótszych ścieżek wąskich gardeł
Szukam dobrego odniesienia do najkrótszych ścieżek wąskich gardeł. W szczególności, biorąc pod uwagę wierzchołki si na grafie bezkierunkowym z wagami krawędzi, potrzebujesz najkrótszej ścieżki od s do t, gdzie długość ścieżki jest maksymalną krawędzią na tej ścieżce. Można to rozwiązać w czasie O (n + m), znajdując środkową masę krawędzi …
4
Jakie jest najważniejsze pojęcie rzadkości w projektowaniu wydajnych algorytmów graficznych?
Istnieje kilka konkurencyjnych pojęć „rzadkiego wykresu”. Na przykład wykres, który można osadzić na powierzchni, można uznać za rzadki. Lub wykres z ograniczoną gęstością krawędzi. Lub wykres z wysokim obwodem. Wykres z dużym rozszerzeniem. Wykres z ograniczoną szerokością. (Nawet w obrębie podpól losowych wykresów jest nieco niejednoznaczne co do tego, co …
1
Jaki algorytm kryje się za akinatorem lub 20q?
Tytuł mówi sam za siebie. Oto Akinator i 20Q . Zasadą tych gier jest zadawanie użytkownikowi szeregu pytań związanych z wybraną przez niego jednostką. A następnie dowiedz się, co to za istota. Istotą algorytmu jest znalezienie „najbardziej użytecznego pytania” w każdej rundzie, przy jednoczesnym postępowaniu z użytkownikiem, który może nie …
2
Odwracanie listy przy użyciu dwóch kolejek
To pytanie jest inspirowane istniejącym pytaniem, czy stos można symulować przy użyciu dwóch kolejek w zamortyzowanym czasie na operację stosu. Odpowiedź wydaje się nieznana. Oto bardziej szczegółowe pytanie, odpowiadające specjalnemu przypadkowi, w którym najpierw wykonywane są wszystkie operacje PUSH, a następnie wszystkie operacje POP. Jak skutecznie można odwrócić listę N …
2
Problemy z optymalizacją MSOL na wykresach ograniczonej płynności z predykatami liczności
CMSOL to zliczanie logiki monadycznej drugiego rzędu, tj. Logiki grafów, w których domeną jest zestaw wierzchołków i krawędzi, istnieją predykaty dla przylegania wierzchołków i wierzchołków oraz występowania krawędzi i wierzchołków, istnieje kwantyfikacja na krawędziach, wierzchołkach, zestawach krawędzi i wierzchołkach ustawia, a istnieje predykat która wyraża, czy rozmiar S jest n …
2
Minimalne maksymalne rozwiązania LP
Programowanie liniowe jest oczywiście obecnie bardzo dobrze rozumiane. Mamy dużo pracy, która charakteryzuje strukturę wykonalnych rozwiązań i strukturę rozwiązań optymalnych. Mamy silną dualność, algorytmy wielogodzinne itp. Ale co wiadomo na temat minimalnych maksymalnych rozwiązań LP? Lub równoważnie maksymalne minimalne rozwiązania? (To nie jest tak naprawdę pytanie badawcze, ale może możemy …
1
Typowa twardość rozkładu drzew?
Rozkład drzew jest trudny w najgorszym przypadku, ale chciwa metoda wydaje się być prawie optymalna w małych rzeczywistych sieciach. Czy coś wiadomo o twardości rozkładu drzewa „typowego” wystąpienia jakiejś klasy grafów? Czy istnieje przykład rodziny grafów, w której chciwe metody rozkładu drzew źle się sprawdzają?
3
Problem wielokrotnego cięcia
Szukam nazwy lub jakichkolwiek odniesień do tego problemu. Biorąc pod uwagę wykres ważony G=(V,E,w)G=(V,E,w)G = (V, E, w) znajdź podział wierzchołków na n=|V|n=|V|n = |V|ustawia S1,…,SnS1,…,SnS_1,\ldots,S_n tak, aby zmaksymalizować wartość przyciętych krawędzi: c(S1,…,Sn)=∑i≠j⎛⎝∑(u,v)∈E:u∈Si,v∈Sjw(u,v)⎞⎠c(S1,…,Sn)=∑i≠j(∑(u,v)∈E:u∈Si,v∈Sjw(u,v))c(S_1,\ldots,S_n) = \sum_{i \ne j}\left(\sum_{(u,v)\in E : u \in S_i, v \in S_j}w(u,v)\right) Zauważ, że niektóre zestawySiSiS_imogą być …
3
Jakie są problemy z najlepszym współczynnikiem aproksymacji uzyskanym przez algorytm zwracający jednolicie losowe rozwiązanie?
Jakie są problemy z najlepiej znanym współczynnikiem aproksymacji osiągniętym przez algorytm zwracający jednolicie losowe rozwiązanie? Znam jeden taki przykład problemu : w artykule „ Tight Bounds for Permutation Flow Shop Scheduling ” Viswanath Nagarajan i Maxim Sviridenko udowodnili, że losowa sekwencja zadań ma gwarancję 2 √fa| perm | dom a …
1
Warunki podatności na zadowalanie 3SAT-Satisfiable
Zastanawiam się konkretnie, czy istnieje interesujący warunek dotyczący odsetka zadań spełniających formułę 3SAT, aby zagwarantować, że takie problemy są możliwe do rozwiązania. Załóżmy na przykład, że klasa problemów 3SAT z 2 n możliwych przypisań spełnia wzór logiczny; czy możemy skutecznie znaleźć satysfakcjonujące zadanie? Po co ϵ wynika problem w P?ϵ …
3
Czy istnieje algorytm online do śledzenia komponentów na zmieniającym się niekierowanym wykresie?
Problem Mam nieukierunkowany wykres (z wieloma krawędziami), który z czasem się zmieni, węzły i krawędzie można wstawiać i usuwać. Przy każdej modyfikacji wykresu muszę aktualizować połączone elementy tego wykresu. Nieruchomości Dodatkowe właściwości polegają na tym, że żadne dwa składniki nigdy nie zostaną ponownie połączone. Oczywiście wykres może mieć dowolne cykle …
2
Szybki rzadki produkt typu boolean z możliwym przetwarzaniem wstępnym
Jakie są najbardziej efektywne algorytmy mnożenia dwóch bardzo rzadkich macierzy boolowskich (powiedzmy, N = 200, a jest tylko około 100-200 niezerowych elementów)? W rzeczywistości mam tę zaletę, że kiedy mnożę A przez B, B są predefiniowane i mogę na nich dowolnie skomplikowane przetwarzanie wstępne. Wiem też, że wyniki produktów są …
1
Pozytywne uporządkowanie topologiczne, weź 2
Jest to kontynuacja ostatniego pytania Davida Eppsteina i jest motywowana tymi samymi problemami. Załóżmy, że mam wierzchołek z ciężarami na liczbach rzeczywistych na jego wierzchołkach. Początkowo wszystkie wierzchołki są nieoznaczone. Mogę zmienić zestaw zaznaczonych wierzchołków, albo (1) zaznaczając wierzchołek bez nieoznaczonych poprzedników, albo (2) odznaczając wierzchołek bez zaznaczonych następców. (Zatem …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.