Teoretyczne informatyka

1

Problem polega na obliczeniu wielomianu . Załóżmy, że wszystkie współczynniki mieszczą się w słowie maszynowym, tzn. Można nimi manipulować w czasie jednostkowym.(a1x+b1)×⋯×(anx+bn)(a1x+b1)×⋯×(anx+bn)(a_1 x + b_1) \times \cdots \times (a_n x + b_n) Możesz zrobić czas , stosując FFT w sposób drzewny. Czy możesz zrobić O ( n log n ) …

35 ds.algorithms reference-request open-problem polynomials

8

Jakiej definicji asymptotycznej stopy wzrostu powinniśmy uczyć?

Kiedy postępujemy zgodnie ze standardowymi podręcznikami lub tradycją, większość z nas uczy następującej definicji notacji Big-Oh w pierwszych kilku wykładach klasy algorytmów: Być może podajemy nawet całą listę ze wszystkimi jej kwantyfikatorami:f=O(g) iff (∃c>0)(∃n0≥0)(∀n≥n0)(f(n)≤c⋅g(n)).f=O(g) iff (∃c>0)(∃n0≥0)(∀n≥n0)(f(n)≤c⋅g(n)). f = O(g) \mbox{ iff } (\exists c > 0)(\exists n_0 \geq 0)(\forall n …

35 ds.algorithms soft-question teaching

3

Konsekwencje NC = P?

Zoo złożoności wskazuje we wpisie na EXP, że jeśli L = P, to PSPACE = EXP. Ponieważ NPSPACE = PSPACE autorstwa Savitcha, o ile mogę powiedzieć, podstawowy argument dopełniania rozszerza się, aby pokazać, że Wiemy również, że L NL NC \ subseteq P poprzez zmienną hierarchię ograniczoną zasobami Ruzzo.(NL=P)⇒(PSPACE=EXP).(NL=P)⇒(PSPACE=EXP).(\text{NL} = …

35 cc.complexity-theory conditional-results

8

Algorytmy wyższego rzędu

Większość dobrze znanych algorytmów jest pierwszego rzędu, w tym sensie, że ich dane wejściowe i wyjściowe są danymi „prostymi”. Niektóre są drugiego rzędu w trywialny sposób, na przykład sortowanie, tablice skrótów lub funkcje mapowania i składania: są one parametryzowane przez funkcję, ale tak naprawdę nie robią z nią nic ciekawego …

35 ds.algorithms functional-programming ds.data-structures pl.programming-languages

9

Zaskakujące wyniki w złożoności (nie na liście blogów złożoności)

Jakie były najbardziej zaskakujące wyniki w złożoności? Myślę, że przydałaby się lista niespodziewanych / zaskakujących wyników. Obejmuje to zarówno zaskakujące wyniki, które pojawiły się znikąd, jak i wyniki, które okazały się inne niż oczekiwano. Edycja : biorąc pod uwagę listę Gasarcha, Lewisa i Ladnera na blogu złożoności (wskazanym przez @Zeyu), …

35 cc.complexity-theory big-list

3

Rozszerzona teza kościelna

Jednym z najczęściej dyskutowanych pytań na stronie było to, co oznaczałoby obalenie tezy Kościoła . Wynika to częściowo z faktu, że Dershowitz i Gurevich opublikowali w 2008 r. Dowód, że teza Kościoła to Biuletyn Symboliki Logicznej. - bezwstydna autopromocja - napisałem wpis na blogu ). To pytanie dotyczy rozszerzonej tezy …

35 soft-question lo.logic church-turing-thesis

1

Konsekwencje

Wielu wierzy, że . Jednak wiemy tylko, że B P P znajduje się na drugim poziomie hierarchii wielomianowej, tj. B P P ⊆ Σ P 2 ∩ Π P 2 . Etap kierunku pokazano B P P = P jest najpierw doprowadzić go do pierwszego poziomu hierarchii, to znaczy wielomian …

34 cc.complexity-theory randomness randomized-algorithms nondeterminism barriers

8

Wkład Alana Turinga w informatykę

Alan Turing , jeden z pionierów (teoretycznej) informatyki, wniósł znaczący wkład naukowy w naszą dziedzinę, w tym definiując maszyny Turinga, tezę Kościoła-Turinga, nierozstrzygalność i test Turinga. Jednak jego ważne odkrycia nie ograniczają się do tych, które wymieniłem. Na cześć jego 100. urodzin pomyślałem, że byłoby miło poprosić o bardziej kompletną …

34 soft-question ho.history-overview

11

Algorytmy aproksymacyjne dla problemów w P.

Zwykle myśli się o zbliżeniu rozwiązań (z gwarancjami) do problemów trudnych dla NP. Czy trwają badania nad zbliżeniem problemów, o których wiadomo, że są w P? To może być dobry pomysł z kilku powodów. Z góry mojej głowy algorytm aproksymacyjny może działać ze znacznie mniejszą złożonością (lub nawet znacznie mniejszą …

34 ds.algorithms approximation-algorithms

3

Struktura danych oparta na porównaniu do znajdowania pozycji

Czy istnieje struktura danych, która pobiera nieuporządkowaną tablicę elementów, wykonuje wstępne przetwarzanie w i odpowiada na zapytania: czy na liście jest jakiś element , każde zapytanie w najgorszym czasie ?nnnO(n)O(n)O(n)xxxO(logn)O(log⁡n)O(\log n) Naprawdę uważam, że nie ma, dlatego mile widziany jest również dowód, że nie ma.

34 ds.data-structures sorting

11

Pojęcia w teoretycznej CS, które byłyby dostępne dla osób w wieku 8-14 lat

Zgadywanie nie jest częstym pytaniem, ale zastanawianie się, czy ktokolwiek widział materiał, który został wyraźnie stworzony, aby przemówić do odbiorców w znaczący sposób.

34 soft-question teaching

3

Konsekwencje faktoringu w P?

Faktoring nie jest znany jako NP-zupełny. To pytanie dotyczyło konsekwencji faktoringu jako NP-zupełnego. Co ciekawe, nikt nie pytał o konsekwencje faktoringu w P (być może dlatego, że takie pytanie jest banalne). Więc moje pytania to: Jakie byłyby teoretyczne konsekwencje faktoringu w P? Jak taki fakt wpłynie na ogólny obraz klas …

34 cc.complexity-theory cr.crypto-security conditional-results factoring

6

Kod w dokumentach naukowych

W mojej karierze akademickiej przeczytałem sporo artykułów naukowych na różne tematy informatyczne. Wiele z nich obejmuje implementację i pewną ocenę tej implementacji, ale odkryłem, że bardzo niewielu z nich faktycznie publikuje używany kod. Dla mnie korzyści płynące z włączenia faktycznego wdrożenia byłyby znaczące, a mianowicie: Rozszerzenie zaufania lub odtwarzalności (po …

34 soft-question research-practice paper-review

3

Biorąc pod uwagę ważony Dag, czy istnieje algorytm O (V + E), który zastępuje każdą wagę sumą wag przodka?

Problemem jest oczywiście podwójne liczenie. Jest to dość łatwe dla niektórych klas DAG = drzewo, a nawet drzewo szeregowo-równoległe. Jedynym algorytmem, który znalazłem, który działa na ogólnych DAG w rozsądnym czasie, jest przybliżony (dyfuzja streszczenia), ale zwiększenie jego precyzji jest wykładnicze pod względem liczby bitów (i potrzebuję dużo bitów). Tło: …

34 ds.algorithms graph-theory directed-acyclic-graph

14

Codzienne problemy z NP-zupełnymi problemami

Mark Dominus zebrał kilka przykładów redukcji czasu wielomianowego od różnych trudnych problemów NP do dopasowania „wyrażenia regularnego” . Wyobrażanie sobie weryfikacji w czasie wielomianowym nie jest ogromnym skokiem. Jak zilustrujesz klasę NP-zupełną studentom lub przyjaciołom z innych dziedzin, którzy chcieli zrozumieć niedawne zamieszanie związane z pracą Deolalikara?

34 np-hardness big-list