Pytania otagowane jako ho.history-overview

Historia stojąca za tematami: skąd wzięła się ich nazwa, kto je odkrył, kiedy po raz pierwszy udowodniono, jak ewoluowali przez lata.

1
Jakie są historyczne korzenie bigraphów Milnera?
Robin Milner zdefiniował bigraphy jako rodzaj struktury graficznej o strukturze podobnej do wykresu, ale w której węzły można zagnieżdżać. Uogólniają kalkulatory procesowe, takie jak CCS i calculus, ale wydaje się, że Milner zamierzał je stosować znacznie bardziej ogólnie: notatki z seminarium na krótko przed jego śmiercią opisują ostatnie wydarzenia.ππ\pi Patrząc …
1
„Stopień trudności Rabina w obliczeniu funkcji i częściowe uporządkowanie zbiorów rekurencyjnych”
Szukam: Michael O. Rabin, „Stopień trudności obliczenia funkcji i częściowe uporządkowanie zbiorów rekurencyjnych”, Uniwersytet Hebrajski, Jerozolima, 1960 Streszczenie: „Próbujemy zmierzyć ilość pracy związanej z obliczeniem danej funkcji obliczeniowej (rekurencyjnej). Wprowadzono i zbadano pojęcie stopnia trudności obliczeń. Pojęcie to jest niezmienne w tym sensie, że jest niezależne od wyidealizowanych komputerów (maszyn …
1
Dlaczego Martin-Löf potrzebował stworzyć intuicyjną teorię typów?
Czytałem o Intuitionistic Type Theory (ITT) i to ma sens. Ale staram się zrozumieć, dlaczego „dlaczego” zostało stworzone? Intuicyjna logika (IL) i prosty typ rachunek (STLC) i teoria typów ogólnie poprzedzają samo istnienie samego Martina-Löfa! Wydaje się, że w STLC można zrobić wszystko, co jest możliwe w ITT (mogę się …
2
Dlaczego stan FSM tradycyjnie oznacza
Ucząc, jak implementować FSM przy użyciu synchronicznych obwodów logicznych, zauważyłem intrygujący zbieg okoliczności: zarówno w teoretycznym świecie CS, jak iw świecie elektrotechniki „stan” jest zwykle oznaczany jako (i przestrzeń stanu Q ). Najpierw zapytałem na EE.sx , ale potem, badając nieco ten temat, odkryłem, że nawet oryginalny papier Turinga z …
2
Jak dokładnie rachunek lambda uwzględnia intuicyjne pojęcie obliczalności?
Próbowałem owinąć głowę wokół tego, co, dlaczego i jak rachunek, ale nie jestem w stanie poradzić sobie z „dlaczego to działa”?λλ\lambda „Intuicyjnie” dostaję model obliczeniowy Turing Machines (TM). Ale ta abstrakcja wprawia mnie w zakłopotanie.λλ\lambda Załóżmy, że bazy danych nie istnieją - jak więc można „intuicyjnie” przekonać się o zdolności …
1
Entscheidungsproblem vs. Unvollständigkeitssatz (miękkie pytanie)
Pierwszy termin jest używany przez Hilberta w swojej pracy z 1928 roku, ale w późniejszej pracy Gödela to samo nazywa się Unvollständigkeitssatz („twierdzenie o niekompletności”). Dla dzisiejszych niemieckich badaczy CS wydaje się, że częściej stosuje się Unvollständigkeitssatz , a Entscheidungsproblem („problem decyzyjny”) jest nadal rozumiany, ale niekoniecznie związany z das …
2
Eksponaty dla muzeum komputerów
Wydaje mi się, że wszystkie muzea i wystawy związane z komputerami obejmują jedynie historię maszyn komputerowych, ale nic na temat informatyki. Uczestniczysz w tworzeniu nowego Muzeum Informatyki, którego zadaniem jest edukacja, rozrywka i inspirowanie ogółu społeczeństwa w szerokim zakresie tematów związanych z informatyką / informatyką / komunikacją / matematyką. Choć …
2
Relacja między Babbage a von Neumann
Powszechnie wiadomo, że maszyna analityczna Charlesa Babbage'a miała architekturę silnie przypominającą nowoczesną architekturę von Neumanna. Warto również zauważyć, że tabele reprezentujące program maszyny analitycznej Babbage'a ( http://www.fourmilab.ch/babbage/figures/menat3.png ) oraz prace von Neumanna (takie jak http://library.ias.edu /files/pdfs/ecp/planningcodingof0103inst.pdf ) są dość analogiczne. Teraz zastanawiam się, czy są jakieś wskazówki, w jakim stopniu …
1
Czy Stephen Cook dostrzegł znaczenie wykazania, że ​​SAT jest NP-twardy przed faktycznym udowodnieniem?
Jeśli dobrze rozumiem, aby udowodnić, że problem jest trudny NP, musisz wybrać wszystkie możliwe problemy które są w NP, a następnie udowodnić, że redukują się do za pomocą funkcji obliczania czasu wielomianowego, która odwzorowuje wystąpienia każdego z nich do przypadków .ZAAAbjaBiB_{i}ZAAAbjaBiB_{i}ZAAA Po znalezieniu pierwszego trudnego problemu NP, stosując redukcje, możesz …
2
Wczesne referencje do dyskretnej optymalizacji
(Przepraszamy, jeśli jest to źle umieszczone lub zbyt szerokie. Jestem otwarty na sugestie, jak to przeformułować). Interesuje mnie prześledzenie „starożytnej” historii algorytmów maksymalnego przepływu i ogólnie dyskretnych algorytmów optymalizacji. Ford-Fulkerson jest moim słomkowym punktem wyjścia. Jakie były wcześniej znaczące postępy? Jak daleko możemy się cofnąć, wciąż będąc w stanie uzasadnić, …
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.