Teoretyczne informatyka

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

16
Jakich narzędzi używasz do pisania prac?
Jakich narzędzi używasz do pisania prac? Z mojego małego doświadczenia teoretycy spędzają dużo czasu na pisaniu i doskonaleniu artykułów, poza tym, że są kreatywni. Oznacza to, że przekazują swoją pracę innym ludziom. Być może artykuły nie są odpowiednim sposobem, ale należy to pozostawić do kolejnej dyskusji. W każdym razie wydaje …
3
Zaskakujące algorytmy liczenia problemów
Istnieją pewne problemy z liczeniem, które polegają na zliczaniu wykładniczo wielu rzeczy (w stosunku do wielkości danych wejściowych), a jednak mają zaskakujące algorytmy deterministyczne o czasie wielomianowym. Przykłady obejmują: Zliczanie idealnych dopasowań na wykresie planarnym ( algorytm FKT ), który jest podstawą działania algorytmów holograficznych . Zliczanie drzew rozciągających się …
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) …
13
Teoria informacji użyta do udowodnienia trafnych twierdzeń kombinatorycznych?
Jakie są twoje ulubione przykłady, w których teoria informacji jest wykorzystywana do udowodnienia zgrabnego kombinatorycznego stwierdzenia w prosty sposób? Niektóre przykłady, które mogę wymyślić, są związane z dolnymi granicami dla dekodowanych lokalnie kodów, np. W tym artykule: załóżmy, że dla wiązki ciągów binarnych długości ma to, że dla każdego , …
5
Jakie blogi CS powinni wszyscy przeczytać?
Wielu wybitnych informatyków i grup badawczych prowadzi aktywne blogi, które informują nas o najnowszych badaniach w zakresie zainteresowań autorów. W większości przypadków posty na blogu są łatwiejsze do zrozumienia niż oficjalne dokumenty, ponieważ pomijają większość krwawych szczegółów technicznych i podkreślają intuicję (które zwykle pomijają). Przydałoby się zatem mieć listę polecanych …
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 …
13
Dla jakich algorytmów istnieje duża luka między analizą teoretyczną a rzeczywistością?
Istnieją dwa sposoby analizy wydajności algorytmu nałożyć asymptotyczną górną granicę czasu działania, oraz aby go uruchomić i zebrać dane eksperymentalne. Zastanawiam się, czy są znane przypadki, w których istnieje znaczna różnica między (1) a (2). Rozumiem przez to, że albo (a) dane eksperymentalne sugerują silniejszą asymptozę, albo (b) istnieją algorytmy …
21
Opis teoretycznego informatyki na stole?
Często jestem pytany, co robi teoretyczny informatyk. Byłoby wspaniale mieć kilka miłych odpowiedzi na to pytanie. Zwykle wracam do technicznego żargonu, a oczy ludzi zwykle w tym momencie się błyszczą. Co robi teoretyczny informatyk w kategoriach zrozumiałych dla osób niebędących informatykami? Dobra odpowiedź powinna być zgryźliwa, dokładna w duchu, bez …
3
Rygorystyczny dowód bezpieczeństwa dla kwantowych pieniędzy Wiesnera?
W swoim słynnym artykule „Conjugate Coding” (napisanym około 1970 r.) Stephen Wiesner zaproponował schemat pieniądza kwantowego, który jest bezwarunkowo niemożliwy do sfałszowania, zakładając, że bank emitujący ma dostęp do ogromnej tabeli liczb losowych i że banknoty można przynieść z powrotem do banku w celu weryfikacji. W schemacie Wiesner, każdy banknot …
18
Najbardziej pamiętne tytuły papierowe CS
Po owocnym pytaniu w MO pomyślałem, że warto przedyskutować kilka znaczących nazw artykułów w CS. Oczywiste jest, że większość z nas może być zainteresowana przeczytaniem (lub przynajmniej spojrzeniem) artykułu o interesującym tytule (przynajmniej robię to za każdym razem, gdy przeglądam listę artykułów na konferencji) lub unikam słabego czytania nazwane artykuły. …
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.