W 1937 r. Turing opisał maszynę Turinga. Od tego czasu opisano wiele modeli obliczeń, próbując znaleźć model, który jest jak prawdziwy komputer, ale wciąż wystarczająco prosty do projektowania i analizy algorytmów. W rezultacie mamy kilkanaście algorytmów dla np. Problemu SORT dla różnych modeli...
Paul Wegner i Dina Goldin od ponad dekady publikują artykuły i książki, argumentując przede wszystkim, że teza o Kościele Turinga jest często fałszywie przedstawiana w społeczności CS Teorii i gdzie indziej. Oznacza to, że jest prezentowany jako obejmujący wszystkie obliczenia, podczas gdy w...
To pytanie jest podobne do bardziej ogólnego pytania dotyczącego tego, jaki jest właściwy model teoretyczny komputera do projektowania algorytmów i struktur danych. Tutaj pytam konkretnie o obecne komputery o wysokiej wydajności (takie jak te wymienione na liście 500 najlepszych ), a nawet o...
Ostatnie pytanie dotyczyło teraz klasycznego algorytmu programowania dynamicznego dla TSP, niezależnie od Bellmana i Held-Karpa . Algorytm jest powszechnie zgłaszany do działania w czasie . Jednak, jak niedawno zauważył jeden z moich studentów, ten czas działania może wymagać nieracjonalnie silnego...
Jak dobrze zbadano następujący problem w TCS? (Przepraszam, jeśli opis problemu brzmi niejasno!) Biorąc pod uwagę model obliczeń MC (maszyna Turinga, automaty komórkowe, maszynę Kolmogorov-Uspenskii ... itd.) Oraz model hałasu, który mógłby wpływać na obliczenia MC, istnieje sposób na odzyskanie...
Jaka klasa złożoności jest powiązana z wyczerpującymi algorytmami wyszukiwania? (jeśli jest) Czy to jest NP czy PSPACE? Czy istnieją ograniczone modele obliczeń przechwytujące klasę wyczerpujących algorytmów wyszukiwania podobnych do modeli dla chciwego i dynamicznego...
Czy można zbudować mechaniczną implementację powiedzmy Microsoft Word w jednym celu (bez Turinga)? Czy można wdrożyć takie rzeczy jak iteratory, funkcje pierwszego rzędu, całą gamę technik programowania? Czy koła zębate i inne części mechaniczne mogą reprezentować struktury danych, a nawet obiekty...
Tytuł jest trochę mylący: ale mam nadzieję, że pytanie nie brzmi: Grønlund and Pettie Nowa wynik pokazujący, że 3SUM ma tylko drzewo decyzyjne złożoność got me zastanawiasz się:O ( n3 / 2)O(n3/2)O(n^{3/2}) Czy istnieje prosty przykład problemu ze złożonością drzewa decyzyjnego ale który...
Podczas studiów licencjackich EE uczestniczyłem w kilku wykładach, które przedstawiały ładną charakterystykę obwodów boolowskich pod względem liczby zagnieżdżonych pętli. Ze złożonością obwody boolowskie są często uważane za sztylety, ale w rzeczywistości cykle sprzętowe są powszechne. Teraz,...
Czy nazywanie frameworku mapReduce jest rodzajem masowego synchronicznego frameworku programowania równoległego bez przechowywania pamięci lokalnej w procesorach między synchronizacjami? Jeśli nie, to jaki model programowania równoległego najdokładniej ujmuje strukturę
To pytanie o to, czy istnieją jakieś znane tarpits odwracalny Turinga, gdzie „odwracalne” oznacza w sensie Axelsen i Glück , a „Tarpit” jest znacznie bardziej nieformalny pojęcie (i może nie być bardzo dobrym wyborem słowa), ale postaram się wyjaśnić, co mam na myśli. Co rozumiem przez...
Dobrze znanymi przykładami obliczeń inspirowanymi zjawiskiem naturalnym są komputery kwantowe i komputery DNA. Co wiadomo o potencjale i / lub ograniczeniach obliczeń z prawami lub grawitacją Maxwella? Czyli poprzez włączenie „szybkich” rozwiązań natury do równań Maxwella lub problemu n-ciała...
Czy istnieje ramy / formalizm, który definiuje modele obliczeniowe oparte na białkach innych niż model DNA Adlemana lub ta praca Cherry i Qian