Prośba o referencję jest wykorzystywana, gdy autor musi wiedzieć o pracy związanej z pytaniem.
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...
[ 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....
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...
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]....
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...
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ż...
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,...
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...
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...
Znam wiele wyników wykorzystujących twierdzenie PCP (głównie w algorytmach aproksymacyjnych), ale nigdy nie spotkałem się z jasnym wyjaśnieniem twierdzenia PCP (tj. Że ).N P = P C P (O(log( n ) ) , O ( 1 ) )NP=PCP(O(log(n)),O(1))\mathsf{NP} = \mathsf{PCP}(O(\log(n)),O(1)) Jakie są dobre artykuły...
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...
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...
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...
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...
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...
Rozumiem, że model Turinga stał się „standardem” przy opisywaniu obliczeń. Interesuje mnie, dlaczego tak jest - to znaczy, dlaczego model TM stał się szerzej stosowany niż inne teoretycznie równoważne (o ile mi wiadomo) modele, na przykład μ-Recursion Kleene'a lub rachunek lambda (rozumiem to...
Obecnie piszę ankietę na temat twierdzeń hierarchicznych dotyczących TCS. Szukając powiązanych artykułów zauważyłem, że hierarchia jest fundamentalną koncepcją nie tylko w TCS i matematyce, ale w wielu naukach, od teologii i socjologii po biologię i chemię. Widząc, że ilość informacji jest ogromna,...
W 1937 r. Turing opisał maszynę Turinga. Od tego czasu opisano wiele modeli obliczeń, próbując znaleźć model, który jest jak prawdziwy komputer, ale wciąż wystarczająco prosty do projektowania i analizy algorytmów. W rezultacie mamy kilkanaście algorytmów dla np. Problemu SORT dla różnych modeli...
To jest cross-post z math.stackexchange. Niech FACT oznaczają problemu faktoringowej całkowitą: podany znaleźć liczb pierwszych p i ∈ N , a całkowite e I ∈ N , tak, że N = Π k i = 0 p e ı ı .n∈N,n∈N,n \in \mathbb{N},pi∈N,pi∈N,p_i \in \mathbb{N},ei∈N,ei∈N,e_i \in...
Szukam ostatecznej odpowiedzi na pytanie, czy generowanie „prawdziwie losowych” liczb jest obliczalne przez Turinga. Nie wiem, jak to dokładnie sformułować. Pytanie StackExchange dotyczące „wydajnych algorytmów do generowania liczb losowych” jest bliskie odpowiedzi na moje pytanie. Charles Stewart...