Historia stojąca za tematami: skąd wzięła się ich nazwa, kto je odkrył, kiedy po raz pierwszy udowodniono, jak ewoluowali przez lata.
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...
Jest to „pytanie historyczne” bardziej niż pytanie badawcze, ale czy klasyczne sprowadzenie do ustalania porządku w algorytmie Shora dla faktoryzacji zostało początkowo odkryte przez Petera Shora, czy też było wcześniej znane? Czy istnieje artykuł opisujący redukcję, która poprzedza Shora, czy jest...
Chciałbym napisać ankietę na temat zastosowań topologii w informatyce. Planuję opisać historię pomysłów topologicznych w dziedzinie informatyki, a także zwrócić uwagę na kilka aktualnych osiągnięć. Byłoby niezwykle pomocne, gdyby ktokolwiek mógł udzielić informacji na temat któregokolwiek z...
Moje dzisiejsze pytanie jest (jak zwykle) trochę głupie; ale prosiłbym cię o pomyślne rozważenie. Chciałem wiedzieć o genezie i / lub motywacji leżącej u podstaw koncepcji treewidth. Z pewnością rozumiem, że jest on stosowany w algorytmach FPT, ale nie sądzę, że to był powód, dla którego...
Rozumiem, że model Turinga stał się „standardem” przy opisywaniu obliczeń. Interesuje mnie, dlaczego tak jest - to znaczy, dlaczego model TM stał się szerzej stosowany niż inne teoretycznie równoważne (o ile mi wiadomo) modele, na przykład μ-Recursion Kleene'a lub rachunek lambda (rozumiem to...
Gdybyś mógł zmienić nazwę programowania dynamicznego, jak byś to
W klasycznym artykule Andrew Chi-Chiha Yao z 1979 r. Nawiązuje do „MO Rabin i AC Yao w przygotowaniu”. Wynika to z tego, że złożoność komunikacji z błędem ograniczonym funkcji równości EQ (czy dwie liczby całkowite z zakresu od do są równe) wynosi .NN_N000N−1N−1N-1O(loglogN)O(loglogN)O(\log\log...
Ten problem jest inspirowany pytaniem MO , które moim zdaniem było bardzo interesujące. Jaki jest najstarszy otwarty problem w TCS? To pytanie wymaga wyjaśnienia. Po pierwsze, czym jest TCS? Myślę, że istnienie liczb nieparzystych idealnych nie jest TCS. Powiedziałbym, że dziesiątym...
Alan Turing , jeden z pionierów (teoretycznej) informatyki, wniósł znaczący wkład naukowy w naszą dziedzinę, w tym definiując maszyny Turinga, tezę Kościoła-Turinga, nierozstrzygalność i test Turinga. Jednak jego ważne odkrycia nie ograniczają się do tych, które wymieniłem. Na cześć jego 100....
Mam pytanie historyczne. Próbuję ustalić odniesienie dla faktu, że 3-kolorowalność grafów (alternatywnie, kolorowalność dla danego k ≥ 3 ) jest NP-trudna.kkkk ≥ 3k≥3k\geq 3 Kuszącą odpowiedzią jest „oryginał Karpa”, ale to nieprawda. Oto skan: Reducibility Among Combinatorial Problems, Karp...
„Wiemy”, że nazwano na cześć Steve'a Cooka, a nazywa się Nick Pippenger. Jeśli się nie mylę, Steve Cook nazwał NC na cześć Nicka Pippengera i powiedziano mi, że jest też odwrotnie. Nie znalazłem jednak żadnego dowodu na ten ostatni fakt ani w pracy Steve'a Cooka na temat DCFL, ani w dowodzie...
W kilku ostatnich pytaniach ( q1 q2 ) omawiano „Teorię A” vs. „Teorię B”, najwyraźniej w celu uchwycenia podziału między nauką logiki i języków programowania a badaniem algorytmów i złożoności. Ta terminologia była dla mnie nowa, a szybkie wyszukiwanie w Internecie nie przyniosło żadnych...
W swojej książce Boolean Function Complexity Stasys Jukna wspomina (strona 564), że Kołmogorow wierzył, że każdy język w P ma obwody o wielkości liniowej. Nie ma wzmianki o referencjach i nie mogłem znaleźć niczego online. Czy ktoś wie o tym
Dlaczego języki regularne (i te wyrażenia regularne) nazywane są „regularnymi”? Dużo prawidłowości występuje również w językach bezkontekstowych i innych rodzajach języków. Przypuszczam, że na początku zastosowano przymiotnik „zwykły” w celu odróżnienia tego rodzaju języków od innych...
Grothendieck zmarł . Miał ogromny wpływ na matematykę XX wieku trwającą aż do XXI wieku. To pytanie jest zadawane nieco w stylu / duchu, na przykład w sprawie wkładu Alana Turinga w informatykę . Jakie główne wpływy Grothendiecka na informatykę
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...
Jeśli jest nieukierunkowane -regular wykres i jest podzbiorem wierzchołków liczności , wywołać ekspansję krawędzi o o ilościd S ≤ | V | / 2G=(V,E)G=(V,E)G=(V,E)dddSSS≤|V|/2≤|V|/2\leq |V|/2SSS ϕ(S):=Edge s ( S, V- S)re⋅ | S.| ⋅ | V.- S|ϕ(S):=Edges(S,V−S)d⋅|S|⋅|V−S|\phi(S) := \frac...
Mądrzy inni redaktorzy Wikipedii odrzucili moją prośbę o przeniesienie artykułu z Wikipedii na temat algorytmu Rabin – Karp do tego, co moim zdaniem powinno się nazywać, algorytm Karp – Rabin, ponieważ częściej używa się nazwy Rabin – Karp ( fałsz, jeśli ktoś idzie według liczb uczonego Google) lub...
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...
Ostatnio uczyłem ekspanderów i wprowadziłem pojęcie grafów ramanujańskich. Michael Forbes zapytał, dlaczego tak się nazywają, i musiałem przyznać, że nie wiem.