Teoretyczne informatyka ds.algorithms

1

Jaki jest kompromis między wielkością populacji a liczbą pokoleń w algorytmach genetycznych

Algorytmy genetyczne ewoluują w mniejszej liczbie pokoleń z większą populacją, ale także obliczanie pokolenia trwa dłużej. Czy istnieją jakieś wytyczne dotyczące równoważenia tych dwóch czynników, aby jak najszybciej znaleźć realne rozwiązanie? Czy to najlepsze miejsce na pytanie?

13 ds.algorithms machine-learning genetic-algorithms

1

Mnożenie macierzy w

Szukałem mnożenia macierzy, więc najpierw odwiedziłem algorytmy mnożenia macierzy wiki. W referencjach znalazłem artykuł, który twierdzi, że używa algorytmu O ( n2)l o g( n ) )O(n2)losol(n))O(n^2 log(n)) , chciałbym przeczytać artykuł, ale jest skomplikowany i zajmie zbyt wiele czasu, aby go przeczytać, ale jeśli jest ktoś, kto czyta ten …

13 ds.algorithms linear-algebra matrix-product

2

Zliczanie roztworów wzorów Monotone-2CNF

Formuła Monotone-2CNF to formuła CNF, w której każda klauzula składa się z dokładnie 2 literałów dodatnich. Teraz mam wzór Monotone-2CNF . Niech S będzie zbiorem satysfakcjonujących zadań F. Mam również wyrocznię O, która może podać następujące informacje:FFFSSSFFFOOO Kardynalność zbioru (tj. Liczba rozwiązań F ).SSSFFF Biorąc pod uwagę zmienną : xxx …

13 cc.complexity-theory ds.algorithms sat counting-complexity

1

Szybki rzadki łańcuch boolowski z matrycą

Mam więc około 100-200 bardzo rzadkich kwadratowych macierzy boolowskich o długości boku ~ kilkudziesięciu i muszę obliczyć ich iloczyn. Wiem, że jeśli pomnożę je szeregowo, produkt zwykle pozostanie tak rzadki na każdym kroku. Czy w tym przypadku są jakieś algorytmy łańcucha macierzy, które działają szczególnie szybko? Na wyższym poziomie problemem …

13 ds.algorithms automata-theory matrix-product sparse-matrix

1

Kompromis czasoprzestrzenny w dolnych granicach

Po dyskusji na temat dolnych granic dla 3SAT [ 1 ] zastanawiam się, jakie są główne wyniki dolnej granicy sformułowane jako kompromisy czasoprzestrzenne. Wykluczam wyniki takie jak, powiedzmy, twierdzenie Savitcha; dobry wpis koncentrowałby się na jednym problemie i jego granicach. Przykładem może być: „Niech T i S będą czasem działania …

13 cc.complexity-theory ds.algorithms big-list space-time-tradeoff

12

Jakie są rzeczywiste zastosowania algorytmów genetycznych?

Jakie są niektóre rzeczywiste problemy rozwiązane za pomocą algorytmu genetycznego? Jaki jest problem? Jakiego testu sprawności używa się do rozwiązania tego problemu?

13 ds.algorithms machine-learning ai.artificial-intel application-of-theory ne.neural-evol

1

Znajdowanie nieparzystych dziur w krążących grafach Paleya

Paley wykresy P P są takie, których wierzchołek osadzone jest przez skończonego GF (q) dla pierwszego mocarstw q≡1 mod (4), w których dwa wierzchołki przylega wtedy i tylko wtedy, gdy różnią się o 2 do niektórych a ∈ GF (q). W przypadku, gdy q jest liczbą pierwszą, skończone pole GF …

13 ds.algorithms graph-theory

2

Co to jest dobry algorytm sortowania specjalnych przypadków?

Mam zestaw danych, który jest liczbą obiektów ułożonych w siatkę 2D. Wiem, że mam ścisłą kolejność, rosnącą wraz z ruchem od lewej do prawej w każdym rzędzie i rosnącą od góry do dołu w każdej kolumnie. Na przykład, 1 2 3 4 6 7 5 8 9 Czy mogę ulepszyć …

13 ds.algorithms total-ordering sorting

3

Czy każdy zachłanny algorytm ma strukturę matroidu?

Jest dobrze znane, że dla każdego matroid M.MM żadna funkcja ciężaru www , nie wychodzi algorytm GreedyBasis (M, w )GreedyBasis(M,w)\mbox{GreedyBasis}(M,w) , która zwraca na podstawę maksymalny ciężar MMM . Czy zatem odwrotny kierunek jest również prawdą? Oznacza to, że jeśli istnieje jakiś chciwy algorytm, musi również istnieć pewna struktura matroidu.

13 ds.algorithms greedy-algorithms

1

Znalezienie najkrótszej ścieżki w obecności cykli ujemnych

Biorąc pod uwagę ukierunkowany wykres cykliczny, na którym ciężar każdej krawędzi może być ujemny, koncepcja „najkrótszej ścieżki” ma sens tylko wtedy, gdy nie ma żadnych cykli ujemnych, iw takim przypadku można zastosować algorytm Bellmana-Forda. Jestem jednak zainteresowany znalezieniem najkrótszej ścieżki między dwoma wierzchołkami, która nie wymaga cyklizacji (tj. Pod warunkiem, …

13 ds.algorithms graph-algorithms shortest-path

1

Sortuje

W ostatnim przedruku https://arxiv.org/abs/1801.00776 twierdzi się, że liczb rzeczywistych można posortować w czasie O ( n √nnn i przestrzeń liniowa. Artykuł wydaje się rozsądny, chociaż nie jestem ekspertem w dziedzinie algorytmów sortowania.O(nlogn−−−−√),O(nlog⁡n),O(n \sqrt{\log n}), Jeśli jest poprawny, byłoby to, moim zdaniem, znaczące, przynajmniej teoretycznie. Przedstawienie głównego argumentu jest jednak nieco …

12 cc.complexity-theory ds.algorithms sorting

2

Wymagana pamięć do szybkiego mnożenia macierzy

Załóżmy, że chcemy pomnożyć macierzy. Algorytm powolnego mnożenia macierzy działa w czasie O ( n 3 ) i wykorzystuje pamięć O ( n 2 ) . Najszybsze mnożenie macierzy przebiega w czasie n ω + o ( 1 ) , gdzie ω jest stałą algebry liniowej, ale co wiadomo o …

12 ds.algorithms linear-algebra

1

Zakrywający sznur palindromami

Biorąc pod uwagę ciąg , okładka palindromu jest sekwencją słów tak że i takie, że każdy jest palindromem.w=σ1σ2…σnw=σ1σ2…σnw=\sigma_1\sigma_2\ldots\sigma_np1p2⋯pmp1p2⋯pmp_1p_2\cdots p_mpipip_ip1p2⋯pm=wp1p2⋯pm=wp_1p_2\cdots p_m = wpipip_i Jak trudno jest znaleźć minimalną wielkość palindromu? (wydaje się to wykonalne przez programowanie dynamiczne, ale nie jestem pewien, czy to działa). Czy problem staje się trudniejszy, jeśli podany …

12 ds.algorithms dynamic-programming string-matching covering-problems

6

Książka do samodzielnego studiowania algorytmów w teorii grup

Jestem głównym matematykiem zainteresowanym TCS. Chcę samemu przestudiować algorytmy i ich złożoność w celu rozwiązania grupowych problemów teoretycznych, takich jak znajdowanie porządku elementów, wyliczanie zbioru, wyszukiwanie generatora, testowanie, czy dany podzbiór generuje grupę. Jaką książkę powinienem przeczytać?

12 ds.algorithms reference-request gr.group-theory books

1

Do jakiej klasy złożoności należy ten problem teorii liczb?

'Biorąc pod uwagę , czy jest , ' jest -kompletny. x , y ∈ N a x 2 + b y = c N Pa,b,c∈Na,b,c∈Na,b,c\in\Bbb Nx,y∈Nx,y∈Nx,y\in\Bbb Nax2+by=cax2+by=cax^2+by=cNPNP\mathsf{NP} Do której klasy złożoności należy „Biorąc pod uwagę , czy istnieje , '? x , y ∈ N a x 2 + b …

12 ds.algorithms complexity-classes reductions nt.number-theory np-complete

Pytania otagowane jako ds.algorithms