Pytania otagowane jako reference-request

Prośba o referencję jest wykorzystywana, gdy autor musi wiedzieć o pracy związanej z pytaniem.

7
Soczewka algorytmiczna w naukach społecznych
Patrzenie na pytania przez obiektyw algorytmiczny (tj. Z punktu widzenia algorytmu lub złożoności) stało się przydatne w dyscyplinach poza „standardową dziedziną” informatyki. W szczególności CS wywarł wpływ na biologię poprzez biologię obliczeniową, na fizykę poprzez kwantowe przetwarzanie informacji, a AI i teoria złożoności wydają się regularnie oddziaływać z neuronauką. Nauki …
1
Czy LOGLOG = NLOGLOG?
Zdefiniuj LOGLOG jako klasę języków, które mogą być obliczane w przestrzeni O (loglog n) przez deterministyczną maszynę Turinga (z dwukierunkowym dostępem do danych wejściowych). Podobnie zdefiniuj NLOGLOG jako klasę języków, które mogą być obliczane w przestrzeni O (log log n) przez niedeterministyczną maszynę Turinga (z dwukierunkowym dostępem do danych wejściowych). …
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ć …
2
Metoda wielomianowa dla wyników złożoności
Metody wielomianowe , powiedzmy twierdzenie kombinatoryczne Nullstellensatz i twierdzenie Chevalleya-Ostrzegania, są potężnymi narzędziami w kombinatywnej addytywności. Reprezentując problem z właściwymi wielomianami, mogą zagwarantować istnienie rozwiązania lub liczbę rozwiązań wielomianów. Zostały one wykorzystane do rozwiązania problemów, takich jak ograniczone zestawy sum lub problemy o sumie zerowej , a niektóre twierdzenia w …
5
Ekologia i ewolucja poprzez soczewkę algorytmiczną
Badanie ekologii i ewolucji staje się coraz bardziej matematyczne, ale wydaje się, że większość narzędzi teoretycznych pochodzi z fizyki. Jednak w wielu przypadkach problemy mają bardzo dyskretny charakter (patrz na przykład SLBS00 ) i mogą skorzystać z perspektywy informatyki . Jednak wiem tylko o kilku poważnych wynikach TCS, które próbują …
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 …
1
Inne zastosowania wzmocnienia rozgałęzień Karger-Stein?
Właśnie nauczyłem losowego algorytmu skrótu Karger-Stein w mojej klasie algorytmów dla absolwentów. To prawdziwy klejnot algorytmiczny , więc nie mogę tego nie uczyć, ale zawsze denerwuje mnie, ponieważ nie znam innych zastosowań głównej techniki. (Trudno więc przypisać pracę domową, która doprowadzi ten punkt do domu.) Algorytm Kargera i Steina jest …
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 …
1
Kto pierwszy zaproponował użycie
Jestem pewien, że wszyscy wiedzą o eksperymencie igły Buffona w XVIII wieku, który jest jednym z pierwszych algorytmów probabilistycznych do obliczeniaππ\pi. Implementacja algorytmu w komputerach zwykle wymaga użycia ππ\pilub funkcja trygonometryczna, która nawet jeśli są zaimplementowane jako skrócone serie, to w pewnym sensie nie udaje się to osiągnąć. Aby obejść …
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.