Teoretyczne informatyka

Pytania i odpowiedzi dotyczące teoretycznych informatyków i badaczy w pokrewnych dziedzinach

7
Solidne zastosowania teorii kategorii w TCS?
Nauczyłem się kilku fragmentów teorii kategorii. Z pewnością jest to inny sposób patrzenia na rzeczy. (Bardzo ogólne podsumowanie dla tych, którzy go nie widzieli: teoria kategorii daje sposoby wyrażania wszelkiego rodzaju zachowań matematycznych wyłącznie w kategoriach funkcjonalnych związków między obiektami. Na przykład rzeczy takie jak iloczyn kartezjański dwóch zbiorów są …
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, …
15
Prosty problem, którego rozstrzygalność nie jest znana
Przygotowuję się do wykładu skierowanego do studentów kierunków matematycznych, w ramach których rozważam omówienie koncepcji rozstrzygalności. Chcę podać przykład problemu, o którym obecnie nie wiemy, że jest rozstrzygalny lub nierozstrzygalny. Istnieje wiele takich problemów, ale jak dotąd żaden z nich nie wyróżnia się na tle innych. Co to jest prosty …
5
Lista konferencji i warsztatów TCS
Chciałbym prosić o pomoc w opracowaniu listy jak największej liczby konferencji i warsztatów związanych z TCS. Moją główną motywacją do tego jest zaplanowanie potencjalnego zasięgu blogów na temat większej liczby miejsc teoretycznych - znalezienie korespondentów biorących udział w tych wydarzeniach, którzy byliby gotowi napisać krótkie lub szczegółowe wpisy na blogu …
7
Jaki jest wkład rachunku lambda w dziedzinę teorii obliczeń?
Właśnie czytam rachunek lambda, żeby go „poznać”. Widzę to jako alternatywną formę obliczeń w przeciwieństwie do maszyny Turinga. Jest to interesujący sposób robienia rzeczy z funkcjami / redukcjami (z grubsza mówiąc). Niektóre pytania wciąż mnie dręczą: Jaki jest sens rachunku lambda? Po co przechodzić przez te wszystkie funkcje / ograniczenia? …
10
Co to znaczy obalić tezę Turinga?
Przepraszam za chwytliwy tytuł. Chcę zrozumieć, co należy zrobić, aby obalić tezę Turinga? Gdzieś czytam, że jest to matematycznie niemożliwe! Dlaczego? Turing, Rosser itp. Użyli różnych terminów, aby rozróżnić: „co można obliczyć” i „co można obliczyć za pomocą maszyny Turinga”. Definicja Turinga z 1939 r. Jest następująca: „Użyjemy wyrażenia„ funkcja …
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ą …
14
Jakie podstawy matematyczne są potrzebne do teorii złożoności?
Obecnie jestem studentem, który w tym roku musi ukończyć studia. Po ukończeniu studiów rozważam pracę w kierunku magistra / doktora TCS. Zacząłem się zastanawiać, jakie dziedziny matematyki są uważane za pomocne w TCS, zwłaszcza (klasyczna) teoria złożoności. Jakie dziedziny uważasz za niezbędne dla kogoś, kto chce studiować teorię złożoności? Czy …
7
Jak wyglądałby bardzo prosty program kwantowy?
W świetle ogłoszenia pierwszego na świecie programowalnego układu kwantowego , zastanawiałem się, jakie byłoby oprogramowanie dla komputera wykorzystującego splątanie kwantowe. Jeden z pierwszych programów, które napisałem, był podobny for i = 1 to 10 print i next i Czy ktoś może podać przykład kodu o porównywalnej prostocie, który wykorzystywałby kwantowe …
8
Czy prace badawcze są trudne do odczytania?
To pytanie może nie pasować tutaj, ale nie mogłem znaleźć lepszego miejsca do zadawania pytań (zostało zamknięte w SO). Trudno mi zrozumieć prace badawcze z zakresu informatyki. Oczywiście tematy są skomplikowane. Ale po tym, jak rozumiem artykuł, zwykle mogę komuś to powiedzieć w prostszy sposób i sprawić, by zrozumiał. Jeśli …
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 …
5
Techniki odwracania porządku kwantyfikatorów
Dobrze wiadomo, że ogólnie nie można odwrócić kolejności uniwersalnych i egzystencjalnych kwantyfikatorów. Innymi słowy, dla logicznego ogólnym wzorze ,ϕ(⋅,⋅)ϕ(⋅,⋅)\phi(\cdot,\cdot) (∀x)(∃y)ϕ(x,y)⇎(∃y)(∀x)ϕ(x,y)(∀x)(∃y)ϕ(x,y)⇎(∃y)(∀x)ϕ(x,y)(\forall x)(\exists y) \phi(x,y) \quad \not\Leftrightarrow \quad (\exists y)(\forall x) \phi(x,y) Z drugiej strony wiemy, że prawa strona jest bardziej restrykcyjna niż lewa; czyli (∃y)(∀x)ϕ(x,y)⇒(∀x)(∃y)ϕ(x,y)(∃y)(∀x)ϕ(x,y)⇒(∀x)(∃y)ϕ(x,y)(\exists y)(\forall x) \phi(x,y) \Rightarrow (\forall x)(\exists …
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 & …
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.