Pytania otagowane jako big-list

Pytania, których odpowiedzi to duża lista pozycji (książki, twierdzenia, oprogramowanie, ...)

14
Książka o prawdopodobieństwie
Chociaż zdałem kilka kursów z teorii prawdopodobieństwa, zarówno w szkole średniej, jak i na uniwersytecie, trudno mi czytać artykuły TCS, jeśli chodzi o prawdopodobieństwo. Wydaje się, że autorzy artykułów TCS są bardzo dobrze zaznajomieni z prawdopodobieństwem. Magicznie działają ze wzorami prawdopodobieństwa i bardzo łatwo dowodzą twierdzeń; podczas gdy muszę spędzić …
5
Problemy z NEXP-complete
Wokół jest mnóstwo problemów z kompletnym NP i źródła je zbierające, np. Patrz książka Garey i Johnsona. Byłbym również zainteresowany, aby zobaczyć listę problemów uzupełniających NEXP. Czy jest dostępny? Ponieważ zakładam, że nie ma, otwieram to pytanie (czy to ma być wiki społeczności? Nie wiem o tych rzeczach). W idealnym …
7
Najbardziej wpływowe wyniki Liptona
Richard J. Lipton został wybrany zwycięzcą nagrody Knuth Prize 2014 „za wprowadzenie nowych pomysłów i technik”. Jakie są według Ciebie główne nowe pomysły i techniki opracowane przez Lipton? Uwaga. To pytanie stanie się wiki społeczności, proszę podać jeden taki pomysł, technikę lub wynik na odpowiedź.
30 big-list 
19
Piękne wyniki w TCS
Niedawno mój przyjaciel (pracujący w TCS) wspomniał w rozmowie, że „chciał zobaczyć / poznać wszystkie (lub jak najwięcej) pięknych wyników w TCS w swoim życiu”. Ten rodzaj sprawił, że zastanawiałem się nad pięknymi wynikami w tej dziedzinie, a tym samym motywacją do następującego pytania: Które wyniki (lub pomysły) są Twoim …
17
Przykłady, w których wgląd w geometrię był przydatny do rozwiązania czegoś całkowicie niegeometrycznego
Jedną z miłych rzeczy w ewolucji we wszechświecie o trzech wymiarach przestrzennych jest to, że rozwinęliśmy umiejętności rozwiązywania problemów dotyczące obiektów w przestrzeni. Tak więc na przykład możemy myśleć o tryplecie liczb jako o punkcie 3-d, a zatem obliczenia o tripletach liczb jako o obliczeniach o punktach w 3-d, które …
10
Algorytmy probabilistyczne (randomizowane) przed pojawieniem się „nowoczesnej” informatyki
Edycja: wybieram odpowiedź z najwyższym wynikiem do 6 grudnia 2012 r. To delikatne pytanie. Pojęcie (deterministycznych) algorytmów sięga BC. Co z algorytmami probabilistycznymi? W tym wpisie wiki algorytm Rabina dla problemu najbliższej pary w geometrii obliczeniowej podano jako pierwszy algorytm losowy (rok ???). Lipton wprowadził algorytm Rabina jako początek ery …
5
Dowody kwantowe klasycznych twierdzeń
Interesują mnie przykłady problemów, w których twierdzenie, które pozornie nie ma nic wspólnego z mechaniką / informacją kwantową (np. Mówi coś o obiektach czysto klasycznych), może jednak zostać udowodnione za pomocą narzędzi kwantowych. Badanie Kwantowe dowody dla klasycznych twierdzeń (A. Drucker, R. Wolf) podaje ładną listę takich problemów, ale na …
2
Złożoność właściwości topologicznych.
Jestem informatykiem biorącym udział w kursie na temat topologii (posypka topologii punktowej mocno przyprawionej teorią kontinuum). Zainteresowały mnie problemy decyzyjne testujące opis przestrzeni (uproszczeniem) dla właściwości topologicznych; zachowane do homeomorfizmu. Wiadomo na przykład, że określenie rodzaju węzła znajduje się w PSPACE i jest NP-twarde. (Agol 2006; Hass, Lagarias, Pippenger 1999) …
6
Dobrze znane klasy wzorów boolowskich, które wymagają wykładniczo długich prób rozdzielczości
W solverach SAT często można znaleźć metody płaszczyzny cięcia, zmienną propagację, odgałęzienie i wiązanie, uczenie się klauzul, inteligentne cofanie, a nawet ręcznie tkaną ludzką heurystykę. Jednak przez dziesięciolecia najlepsze solwery SAT polegały w dużej mierze na technikach sprawdzania rozdzielczości i używają kombinacji innych rzeczy po prostu do pomocy i do …
4
Brakuje artykułów z Wikipedii
O których brakujących tematach TCS na Wikipedii najbardziej chciałbyś znaleźć artykuł? Mogą to być rażące pominięcia lub po prostu tematy, które Twoim zdaniem powinny zawierać artykuł. Poproszę jeden temat na odpowiedź, aby głosować na najbardziej poszukiwanych. Aktualizacja 5/2/2017 : Shuchi Chawla stara się poprawić zasięg TCS na Wikipedii . Dodam …
5
Długotrwałe błędy w informatyce
To jest moje pierwsze pytanie na stosie cstheory, więc nie bądź zbyt niegrzeczny, jeśli w jakiś sposób naruszam etykietę) Jak wiemy, w matematyce nawet znani matematycy, supergwiazdy i geniusze od czasu do czasu popełniają poważne błędy. Na przykład, zarówno twierdzenie 4-kolorowe, jak i twierdzenie Fermata dostarczają nam dramatycznych przypadków, w …
11
Jakie książki popularnonaukowe inspirują TCS?
Istnieje reputacja, że ​​w informatyce nie mamy książek popularnonaukowych. Oczywiście to nie do końca prawda! (W tym samym duchu listy Co Książki każdy powinien przeczytać? , Jakie dokumenty powinien każdy przeczytać? , Co każdy powinien oglądać filmy? A zainspirowana Ulubiony popularnej książce matematyka ) Jakie książki popularnonaukowe lub zasoby inspirują …
24 big-list  books 
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.