Pytania otagowane jako reference-request

Prośba o referencję jest wykorzystywana, gdy autor musi wiedzieć o pracy związanej z pytaniem.

6
Co nowego w czysto funkcjonalnych strukturach danych od czasu Okasaki?
Od czasu książki Chrisa Okasakiego z 1998 r. „Czysto funkcjonalne struktury danych”, nie widziałem zbyt wielu nowych ekscytujących czysto funkcjonalnych struktur danych; Mogę wymienić tylko kilka: IntMap (również wynaleziony przez Okasaki w 1998 r., Ale nieobecny w tej książce) Drzewa palcowe (i ich uogólnienie na monoidy) Istnieje również kilka interesujących …
30
Jakie książki każdy powinien przeczytać?
[ Oś czasu ] To pytanie ma ten sam duch, co artykuły powinny przeczytać wszyscy i jakie filmy wszyscy powinni oglądać . Prosi o niezwykłe książki z różnych dziedzin informatyki teoretycznej. Książki mogą być zorientowane na matematykę, ale mogą się okazać przydatne dla informatyków. Przykłady: Prawdopodobieństwo Nierówności Logika Teoria grafów …
15
Jakie notatki z wykładu powinien przeczytać każdy?
Było kilka pytań o tym samym schemacie jak ten: Jakie gazety każdy powinien przeczytać Jakie książki każdy powinien przeczytać Jakie są najnowsze książki TCS, których wersje robocze są dostępne online jakie filmy wszyscy powinni oglądać Nie chciałem publikować jeszcze jednego, ale notatki z wykładów na temat algorytmów Jeffa Ericksona zmieniły …
17
Przykłady ceny abstrakcji?
Informatyka teoretyczna dostarczyła kilka przykładów „ceny abstrakcji”. Dwa najbardziej znaczące dotyczą eliminacji i sortowania Gaussa. Mianowicie: Wiadomo, że eliminacja Gaussa jest optymalna do, powiedzmy, obliczenia wyznacznika, jeśli ograniczysz operacje do wierszy i kolumn jako całości [1]. Oczywiście algorytm Strassena nie przestrzega tego ograniczenia i jest asymptotycznie lepszy niż eliminacja Gaussa. …
30
Jakie są najnowsze książki TCS, których wersje robocze są dostępne online?
Idąc za postem Co książki powinny przeczytać wszystkie , zauważyłem, że są ostatnie książki, których wersje robocze są dostępne online. Na przykład pozycja Algorytmy aproksymacji powyższego wpisu cytuje książkę z 2011 r. (Jeszcze do opublikowania) zatytułowaną Projektowanie algorytmów aproksymacyjnych . Myślę, że znajomość najnowszych prac jest naprawdę przydatna dla każdego, …
30
Śmieszne dokumenty związane z TCS itp.?
Jaka jest najśmieszniejsza opublikowana praca związana z TCS? Podaj tylko te, które mają być śmieszne. Preferowane są prace, które zostały stworzone z myślą o inteligentnym humorze (zamiast, powiedzmy, opublikowanym zbiorem krótkich dowcipów dotyczących teorii złożoności). Akceptowane są również prace z humorystycznymi (właściwie humorystycznymi, nie tylko uroczymi) tytułami. Zadaj tylko jedną …
20
Przykłady „niepowiązanej” matematyki grającej podstawową rolę w TCS?
Proszę wymienić przykłady, w których twierdzenie matematyki, które normalnie nie było uważane za stosowane w informatyce, zostało po raz pierwszy wykorzystane do udowodnienia wyniku w informatyce. Najlepszymi przykładami są te, w których połączenie nie było oczywiste, ale kiedy zostało odkryte, jest to wyraźnie „właściwy sposób”, aby to zrobić. To jest …
2
Jaka jest faktyczna złożoność czasowa eliminacji Gaussa?
W odpowiedzi na wcześniejsze pytanie wspomniałem o powszechnym, ale fałszywym przekonaniu, że eliminacja „gaussowska” przebiega w czasie . Chociaż oczywiste jest, że algorytm wykorzystuje operacje arytmetyczne , nieostrożna implementacja może tworzyć liczby z wykładniczo wieloma bitami. Jako prosty przykład, załóżmy, że chcemy diagonalizować następującą macierz:O(n3)O(n3)O(n^3)O(n3)O(n3)O(n^3) ⎡⎣⎢⎢⎢⎢⎢⎢⎢211⋮1021⋮1002⋮1⋯⋯⋯⋱⋯000⋮2⎤⎦⎥⎥⎥⎥⎥⎥⎥[200⋯0120⋯0112⋯0⋮⋮⋮⋱⋮111⋯2]\begin{bmatrix} 2 & 0 & …
13
Zastosowania struktur algebraicznych w informatyce teoretycznej
Jestem praktykiem oprogramowania i piszę ankietę na temat struktur algebraicznych do badań osobistych i staram się przedstawić przykłady wykorzystania tych struktur w informatyce teoretycznej (oraz, w mniejszym stopniu, w innych dziedzinach informatyki) . W ramach teorii grup natknąłem się na monoidy syntaktyczne dla języków formalnych oraz monoidy śledzenia i historii …
14
Zastosowania topologii w informatyce
Chciałbym napisać ankietę na temat zastosowań topologii w informatyce. Planuję opisać historię pomysłów topologicznych w dziedzinie informatyki, a także zwrócić uwagę na kilka aktualnych osiągnięć. Byłoby niezwykle pomocne, gdyby ktokolwiek mógł udzielić informacji na temat któregokolwiek z poniższych pytań. Czy są jakieś prace lub notatki opisujące chronologię wykorzystania topologii w …
17
Zastosowania TCS w matematyce klasycznej?
W TCS często używamy potężnych wyników i pomysłów z matematyki klasycznej (algebry, topologii, analizy, geometrii itp.). Jakie są przykłady sytuacji, w której sytuacja się odwróciła? Oto niektóre, o których wiem (a także, aby dać smak wyników, o które pytam): Sześcienne pianki (Guy Kindler, Ryan O'Donnell, Anup Rao i Avi Wigderson: …
2
Czy można wzmocnić P = NP poza P = PH?
W złożoności opisowej Immerman ma Wniosek 7.23. Następujące warunki są równoważne: 1. P = NP. 2. Przekroczone, uporządkowane struktury, FO (LFP) = SO. Można to uznać za „wzmocnienie” P = NP do równoważnego wyrażenia w (przypuszczalnie) większych klasach złożoności. Zauważ, że SO przechwytuje wielomianową hierarchię czasu PH, a FO (LFP) …
7
Dla jakich problemów w P łatwiej jest zweryfikować wynik niż go znaleźć?
W przypadku (wyszukiwania wersji) problemów z NP zakończonych weryfikacja rozwiązania jest wyraźnie łatwiejsza niż znalezienie, ponieważ weryfikacja może być przeprowadzona w czasie wielomianowym, podczas gdy znalezienie świadka zajmuje (prawdopodobnie) wykładniczy czas. Jednak w P rozwiązanie można znaleźć również w czasie wielomianowym, więc nie wydaje się oczywiste, kiedy weryfikacja jest szybsza …
4
Uogólnione twierdzenie Ladnera
Twierdzenie Ladnera stwierdza, że ​​jeśli P ≠ NP, to istnieje nieskończona hierarchia klas złożoności ściśle zawierających P i ściśle zawartych w NP. Dowód wykorzystuje kompletność SAT przy wielu redukcjach NP. Hierarchia zawiera klasy złożoności skonstruowane przez rodzaj diagonalizacji, z których każda zawiera pewien język, do którego języków w niższych klasach …
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.