Pytania otagowane jako big-list

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

2
Jakie są przypuszczenia TCS, które zostały udowodnione dla liczb pierwszych i małych wartości, ale okazały się fałszywe?
Czy są jakieś przypuszczenia w informatyce teoretycznej, które dotyczą jakiegoś parametru n i zostały udowodnione dla małych wartości n AND dla liczb pierwszych, ale później okazały się fałszywe? W teorii liczb takie problemy istnieją, np. jak wskazuje Aaron Meyerowitz na temat współczynników wielomianów cyklotomicznych. Z TCS znam tylko takie przykłady, …
17 big-list  primes 
7
Wskaźniki dla logicznych aplikacji CS
Jestem studentem matematyki z solidnym doświadczeniem w logice. Wziąłem roczny kurs magisterski z logiki wraz z kursami absolwentów teorii modeli skończonych, a także teorii wymuszania i teorii mnożenia. Większość tekstów CS wydaje się przyjmować jedynie bardzo skromne tło logiki, które w większości obejmuje podstawy logiki zdań i logiki pierwszego rzędu. …
3
Przykłady udanej derandomizacji z BPP na P.
Jakie są główne przykłady udanej derandomizacji lub przynajmniej postępów w wykazywaniu konkretnych dowodów w kierunku celu (a nie związku losowości z twardością)?P=BPPP=BPPP=BPP Jedyny przykład, jaki przychodzi mi na myśl, to deterministyczne badanie pierwotności wielomianów czasowych AKS (nawet w tym przypadku istniała metodologia zakładająca GRH). Więc jakie konkretne dowody na przykładzie …
5
Przykłady pedanterii w TCS
Larry Wasserman ma niedawny post, w którym mówi o „policji p-value”. Robi interesujący punkt (wszystkie moje podkreślenia) (przesłankę kursywą, którą dodałem, a jego odpowiedź poniżej): Najczęstszą skargą jest to, że fizycy i dziennikarze nieprawidłowo wyjaśniają znaczenie wartości p. Na przykład, jeśli wartość p wynosi 0,000001, zobaczymy takie stwierdzenia, jak: „istnieje …
2
Godne uwagi przykłady idei pierwiastka kwadratowego w analizie złożoności
Istnieje wiele algorytmów i struktur danych, które wykorzystują ideę, że otrzymuje minimalną wartość przy k = \ sqrt n . Typowe przykłady to k = √max{k,n/k}max{k,n/k}\max \left\{k, n/k\right\}k=n−−√k=nk=\sqrt n algorytm gigantycznego kroku dziecka do obliczania logarytmu dyskretnego w O(n−−√)O(n)O(\sqrt n) , statyczne zliczanie zakresu ortogonalnego 2D w czasie O(n−−√)O(n)O(\sqrt n) …
6
odmiany SAT
Spojrzałem w Internecie, ale nie mogłem znaleźć żadnej „dużej listy” wariantów problemu SAT. Oprócz (wspólnego) SAT, k-SAT, MAX-kSAT, Half-SAT, XOR-SAT, NAE-SAT jakie jeszcze są warianty? (również będzie to bardzo przydatne, jeśli podano klasy złożoności (tam, gdzie to możliwe))
3
Dolne granice dla struktur danych
Czy znane są wyniki, które wykluczają istnienie struktur danych „zbyt dobrych, by były prawdziwe”? Na przykład: czy można dodać funkcjonalność SplitSplitSplit i do struktury danych obsługi zamówień (patrz Dietz i Sleator STOC '87 ) i nadal uzyskiwać operacje czasowe ?JoinJoinJoinO(1)O(1)\mathcal{O}(1) Lub: czy można zaimplementować uporządkowany zestaw z kluczami całkowitymi i …
9
Wyniki sprzeczne z intuicją dla studentów
Szukam przykładów wyników, które są sprzeczne z intuicją ludzi podczas ogólnej dyskusji publiczności. Wyniki, które na pytanie ekspertów niebędących ekspertami „co podpowiada ci intuicja?”, Prawie wszystko byłoby błędne. Oświadczenie o wynikach powinno być łatwe do wyjaśnienia studentom w cs / matematyce. Głównie szukam wyników w informatyce. Jakie są najbardziej sprzeczne …
4
Interesujące wyniki w TCS, które można łatwo wytłumaczyć programistom bez wiedzy technicznej
Załóżmy, że spotykasz się z programistami, którzy odbyli profesjonalne kursy programowania (/ self-think), ale nie studiowali matematyki na poziomie uniwersyteckim. Aby pokazać im piękno TCS, chciałbym zebrać kilka fajnych wyników / otwartych pytań pochodzących z TCS, które można łatwo wyjaśnić. Dobry kandydat do tego celu (IMHO) pokaże, że problem zatrzymania …
2
Książki z algorytmami online
Czy są jakieś najnowsze książki na temat algorytmów online? Znam tylko dwie książki na ten temat. Obliczenia online i analiza konkurencji Allana Borodina i Ran El-Yaniv: Jest to klasyczna, ale stara książka i nie zawiera wielu najnowszych osiągnięć w tej dziedzinie. Projektowanie konkurencyjnych algorytmów online za pomocą podejścia pierwotnego podwójnego …
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.