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
Dlaczego zwykłe języki nazywane są „zwykłymi”?
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 „nieregularnych” lub w jakiś sposób nienormalnych języków. Jeśli tak, to gdzie te inne typy …
2
Dokumenty do uznania za spektralny podział grafów
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 {Edges(S,V-S)}{d\cdot |S|\cdot |V-S|} Gdzie jest liczbą krawędzi z jednego punktu końcowego …
1
Rabin – Karp vs Karp – Rabin
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 że brzmi …
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ść …
2
Jaki był pierwotny zamiar stworzenia rachunku Lambda?
Czytałem, że początkowo Kościół zaproponował -calculus jako część swoich postulatów z logiki (co jest gęstym odczytem). Ale Kleene udowodnił, że jego „system” jest niespójny, po czym Church wyodrębnił odpowiednie rzeczy do swojej pracy nad „skutecznym obliczeniem” i porzucił wcześniejsze prace nad logiką.λλ\lambda Tak jak ja rozumiem, -system i jego oznaczenia …
2
Dlaczego Kołmogorow opublikował algorytm Karatsuby?
Algorytm Karatsuba do szybkiego namnażania został po raz pierwszy opublikowany w A. Karatsuba i Yu. Ofman (1962), „Mnożenie liczb wielu cyfrowych przez komputery automatyczne”, Proceedings of ZSRR Academy of Sciences 145: 293–294. Według Karatsuby (1995, „Złożoność obliczeń”, Proc. Steklov Institute of Mathematics 211: 169–183) , artykuł ten został napisany przez …
3
Kto wprowadził niedeterministyczne obliczenia?
Mam dwa historyczne pytania: Kto pierwszy opisał obliczenia niedeterministyczne? Wiem, że Cook opisał problemy z NP-zupełnością i że Edmonds zaproponował, że algorytmy P są algorytmami „wydajnymi” lub „dobrymi”. Przeszukałem ten artykuł w Wikipedii i odszukałem „O złożoności obliczeniowej algorytmów”, ale nie mogłem znaleźć żadnego odniesienia do pierwszego omówienia obliczeń niedeterministycznych. …
2
Argumenty za / przeciw hipotezie Kołmogorowa o złożoności obwodu P.
Według (niezweryfikowanego) rachunku historycznego Kołmogorow uważał, że każdy język w ma złożoność obwodów liniowych. (Zobacz wcześniejsze pytanie Hipoteza Kołmogorowa, że ma obwody o rozmiarach liniowych .) Zauważ, że implikuje .PP\mathsf{P}PPPP≠NPP≠NP\mathsf{P}\neq \mathsf{NP} Jednak przypuszczenie Kołmogorowa może się nie powieść. Na przykład Ryan Williams pisze w niedawnym artykule: „Przypuszczenie byłoby zaskakujące, jeśli …
3
Czy koncepcja maszyny Turinga pochodzi od automatów?
Niedawno miałem dyskusję na temat maszyn Turinga, kiedy zapytano mnie: „Czy maszyna Turinga pochodzi od automatów, czy jest na odwrót”? Oczywiście nie znałem odpowiedzi, ale jestem ciekawy, aby się dowiedzieć. Maszyna Turinga jest w zasadzie nieco bardziej wyrafinowaną wersją automatów Push-Down. Zakładam, że Maszyna Turinga pochodzi od automatów, jednak nie …
5
Dlaczego ekonomiści powinni dbać o złożoność obliczeniową
Czy próbując przekonać ekonomistów o znaczeniu teorii złożoności w druku, istnieje standardowe odniesienie do cytowania? Znam post na blogu Noama Nisana , ankietę Tima Roughgarden i rozdział 11 eseju Scotta Aaronsona . Te posty są dostępne dla informatyków, ale nie używają języka ekonomistów i nie są publikowane w miejscach zwykle …
6
Kiedy znaleźliśmy lepsze granice dla znanych algorytmów?
Czy istnieją interesujące przypadki algorytmów, które zostały opublikowane ze sprawdzonymi granicami i gdzie opublikowano później ściśle lepsze ograniczenia? Nie lepsze algorytmy z lepszymi granicami - oczywiście tak się stało! Ale lepsza analiza prowadząca do lepszego powiązania z istniejącym algorytmem Myślałem, że mnożenie macierzy jest tego przykładem, ale sam sobie z …
1
Dlaczego praca Schönfinkela nad wyeliminowaniem „zmiennych powiązanych” w logice była tak istotna?
AFAIK, Pierwsze dowody używania funkcji wyższego rzędu sięgają artykułu Schönfinkela z 1924 r .: „O elementach logiki matematycznej” - gdzie pozwalał przekazywać funkcje jako argumenty innym funkcjom. To wydaje się interesujące. Jednak wszystko, co czytałem o jego pracy (i Curry'ego z rozszerzenia) zdaje się nawiązywać do jednej rzeczy w takiej …
1
Wczesna historia niektórych wyników kompromisów czasoprzestrzennych?
Interesuje mnie wczesna historia opublikowanych wyników dotyczących kompromisów czasoprzestrzennych ogólnego przeznaczenia. W szczególności chcę wiedzieć, kto jako pierwszy opisał następujący typ algorytmu do oceny obliczeń posiadających dowolny wykres przepływu danych z O-stopniem (1), wykorzystujący przestrzeń proporcjonalną do głębokości (nie szerokości) wykresu przepływu danych (plus rozmiar danych wejściowych), wykonując prostą pierwszą …
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.