Pytania otagowane jako machine-models

7
Możliwość zastosowania tezy Church-Turinga do interaktywnych modeli obliczeniowych
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 rzeczywistości dotyczy on tylko obliczeń funkcji, które …
3
Jaki jest właściwy model teoretyczny do projektowania algorytmów dla obecnych i przyszłych komputerów o wysokiej wydajności
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 nadchodzące superkomputery. Biorąc pod uwagę, że komputery …
1
Wykonalność maszyn Gödel
Ostatnio natknąłem się na dość interesującą konstrukcję teoretyczną. Tak zwana maszyna Gödela To ogólne narzędzie do rozwiązywania problemów, które jest zdolne do samooptymalizacji. Nadaje się do środowisk reaktywnych. Jak rozumiem, można go zaimplementować jako program do uniwersalnej maszyny Turinga, choć jego wymagania wykraczają daleko poza obecnie dostępny sprzęt. Nie mogłem …
2
Złożoność czasowa algorytmu Bellmana-Helda-Karpa dla TSP, weź 2
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 modelu obliczeń.O(2nn2)O(2nn2)O(2^n n^2) Oto krótki opis algorytmu. Dane wejściowe składają …
6
Co wiadomo na temat skuteczności niezawodnego przetwarzania?
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 po błędach spowodowanych przez ten hałas w skuteczny sposób? Na …
2
Możliwe do przewidzenia luki między złożonością drzewa decyzyjnego a „prawdziwą” złożonością
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 dopuszcza dolną granicę (w bardziej szczegółowym modelu) …
3
Czy każdy program można wdrożyć mechanicznie?
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 programu? Czy w pewnym momencie wymaga to zbudowania maszyny …
3
Czy środowisko MapReduce jest rodzajem BSP?
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ę mapReduce?
1
Czy ludzie patrzą na zagęszczenie pętli w obwodach boolowskich?
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, modulo kilka szczegółów technicznych dotyczących tego, czym jest pętla i co stanowi zagnieżdżoną pętlę, …
1
Odwracalne plandeki Turinga?
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 „tarpit” Niektóre modele obliczeń …
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.