Jakie artykuły każdy powinien przeczytać?

454

To pytanie jest (zainspirowane) / (wstydliwie skradzione) podobnym pytaniem w MathOverflow , ale spodziewam się, że odpowiedzi tutaj będą zupełnie inne.

Wszyscy mamy ulubione artykuły z naszych własnych obszarów teorii. Od czasu do czasu pojawia się artykuł tak zdumiewający (np. Ważny, przekonujący, zwodniczo prosty itp.), Że chce się nim dzielić ze wszystkimi. Wymień te papiery tutaj! Nie muszą pochodzić z informatyki teoretycznej - wszystko, co Twoim zdaniem może spodobać się społeczności, jest dobrą odpowiedzią.

Możesz udzielić tyle odpowiedzi, ile chcesz; proszę umieścić jeden artykuł na odpowiedź ! Zauważ też, że jest to wiki społeczności, więc głosuj na wszystko, co lubisz!

(Uwaga: poprzednie pytanie dotyczyło artykułów w teorii złożoności rekurencyjnej, ale jest to dość wyspecjalizowane).

Ryan Williams
źródło
65
W odpowiedziach chciałbym położyć większy nacisk na to, czy naprawdę warto dziś czytać oryginalny artykuł (lub czy bardziej sensowne jest czytanie jego współczesnego podręcznika). Zbyt często widziałem artykuły TCS, które są naprawdę przełomowe, ale wolę ocalić moich kolegów od bólu związanego z rozszyfrowaniem oryginalnego tekstu - który jest zbyt często pospiesznie napisanym streszczeniem 10-stronicowej konferencji z odniesieniami do „pełnej wersji”, która nigdy się nie pojawiła…
Jukka Suomela,
7
Tak, mam nadzieję, że jasne jest, że tego rodzaju artykuły nie są dobre dla listy (jeśli chcesz się nią podzielić ze wszystkimi, to nie powinno być problemu z czytaniem)
Ryan Williams
30
Zbyt wiele osób publikuje tylko jedno-linijki. Każdy może zamieścić setki unikatowych dokumentów bez zastanowienia. Napisz, dlaczego uważasz, że każdy powinien przeczytać te artykuły. Oznacza to usprawiedliwienie, dlaczego powinni przeczytać ten artykuł zamiast czyjegoś zapisu tego wyniku , i co jest tak niesamowitego w tym papierze, że każdy powinien go przeczytać.
Robin Kothari,
Dobre pytanie. Moim zdaniem, jeśli chcesz zrozumieć umysły wynalazców i być może rozumiesz, jak wymyślać rzeczy, musisz przeczytać ich własne słowa. Im więcej pracujesz, tym bardziej zbliżasz się do ich faktycznego procesu myślowego.
ixtmixilix

Odpowiedzi:

164

„Matematyczna teoria komunikacji” Claude'a Shannona, klasyka teorii informacji. Bardzo czytelny.

( Lustro )

Grigorij Jarosławiec
źródło
Najbezpieczniejszą ogólną charakterystyką Internetu jest to, że składa się on z serii przypisów do tego artykułu.
Celal Ergün
145

Artykuł z 1936 r., Który prawdopodobnie rozpoczął samą informatykę:

  • Alan Turing, „O liczbach obliczalnych z wnioskiem do Entscheidungsproblem”, Proceedings of the London Mathematical Society s2-42, 230–265, 1937. doi: 10.1112 / plms / s2-42.1.230

Na zaledwie 36 stronach Turing formułuje (ale nie wymienia) Maszynę Turinga, przekształca słynne Twierdzenie Pierwszej Niekompletności Gödela pod względem obliczeń, opisuje pojęcie uniwersalności, a w dodatku pokazuje, że obliczalność przez maszyny Turinga jest równoważna obliczalności przez -definiowalne funkcje (badane przez Churcha i Kleene).λ

András Salamon
źródło
7
Jest również bardzo dostępny i czytelny ...
Sariel Har-Peled,
25
a wraz z nim Annotated Turing Charlesa Petzolda [Gorąco polecam]
Pratik Deoghare
123

Refleksje na temat zaufania ” Kena Thompsona . Krótki, słodki i oszałamiający.

Jɛ ff E.
źródło
5
Również bardzo przystępny. Przeczytałem go jakiś czas temu, kiedy zasadniczo nie miałem doświadczenia w CS, nie miałem doświadczenia w programowaniu i nawet nie wiedziałem, co to jest kompilator.
Jörg W Mittag,
1
„W ubiegłym tygodniu Googler Ken Thompson otrzymał Nagrodę Japonii w zakresie informacji i komunikacji za swoją wczesną pracę nad systemem operacyjnym UNIX.” (src: Buzz post z Life at Google)
Sebastián Grignoli
4
Sądzę, że ten artykuł byłby dość trudny do strawienia bez przynajmniej wiedzy na temat kompilatora.
Fixee
2
W pracy uważam, że liczby 2.1 i 2.2 zostały zamienione.
Dennis
1
Nie zgadzam się - w tym artykule nie ma nic niesamowitego ani oszałamiającego. TL; DR 6 stron z połowy lat 80. o „potrzebie zmiany kodu karnego, aby zacząć karać hakerów [podobnie jak złodzieje lub włamywacze]”. O tak, wspomina o quinie , nie nazywając go po imieniu.
c69,
94

Co każdy informatyk powinien wiedzieć o arytmetyki zmiennoprzecinkowej

Ten artykuł wyjaśnia i wzmacnia pogląd, że zmiennoprzecinkowa nie jest magią. Wyjaśnia przepełnienie, niedopełnienie, jakie są liczby zdormalizowane, czym są NaN, czym jest inf i wszystkie rzeczy, które to implikuje. Po przeczytaniu tego artykułu dowiesz się, dlaczego a == a + 1.0 może być prawdziwe, dlaczego a == a może być fałszywe, dlaczego uruchomienie kodu na dwóch różnych maszynach może dać dwie różne odpowiedzi, dlaczego sumowanie liczb w innym Porządek może dać ci różnicę wielkości rzędu i wszystkie zwariowane rzeczy, które zdarzają się w świecie mapowania niezliczonych nieskończonych liczb na zbiór skończony.

Wersja edytowana jest również dostępna w Internecie.

Rick Weber
źródło
3
Proszę naprawić link. Jest uszkodzony.
Oscar Mederos
1
Od momentu przejęcia firmy Sun firma Sun zniszczyła większość linków ze strony internetowej firmy Sun. Chociaż możesz dotrzeć do oryginalnego papieru stąd .
systemowy
1
Naprawiono uszkodzony link.
Ryan
85

Jak Keshav czytać gazetę . Możesz również pobrać papier tutaj .

Dai Le
źródło
Naprawdę fajna lektura.
Anthony Labarre
Zawsze myślę, że prace badawcze CS są napisane w jakimś obcym języku.
Berlin Brown,
3
Bardzo dobre! Warto umieścić na sloganie na stronie, aby mieć pewność, że nikt nie przeoczy tego.
Vag
Drugi link jest obecnie zerwany
Christopher Manning
2
To mój ulubiony z listy. Należy również pamiętać, że jest to żywy dokument, w przeciwieństwie do większości artykułów, które nie są aktualizowane po opublikowaniu.
Dennis
67

Ścieżki, drzewa i kwiaty J. Edmondsa. Ten artykuł na temat klasycznego problemu optymalizacji kombinatorycznej jest nie tylko dobrze napisany, ale także stwierdza, że ​​pojęcie „algorytmów czasu wielomianowego” jest w zasadzie synonimem wydajności.

ilyaraz
źródło
61

Redukowalność wśród problemów kombinatorycznych autorstwa Richarda Karpa. Artykuł zawiera coś, co często określa się jako „oryginalne problemy 21 kompletnych NP” Karpa. Pod wieloma względami ten dokument naprawdę zmotywował badanie kompletności NP, pokazując jego zastosowanie do szerszej dziedziny. Bardzo czytelny.

Daniel Apon
źródło
6
Podoba mi się ten artykuł, ale niektóre redukcje są naprawdę szkicowe i trudne do naśladowania. Zobacz dowolny tekst złożoności, aby uzyskać więcej szczegółów.
András Salamon,
2
@Andras Salamon Zgadzam się w 100%.
Tayfun Zapłać
52

Hartmanis i Stearns, „O złożoności obliczeniowej algorytmów” , Transactions of the American Mathematical Society 117: 285–306 (1965)

Był to pierwszy artykuł, który poważnie podjął się badania złożoności czasu, i z pewnością był głównym impulsem do przyznania wspólnej nagrody Turinga przez Hartmanisa i Stearnsa. Choć ich początkowe definicje nie są dokładnie tym, czego używamy dzisiaj, artykuł pozostaje niezwykle czytelny. Naprawdę masz wrażenie, jak było na starej granicy „Dzikiego Zachodu” lat 60-tych.

Ryan Williams
źródło
Link roboczy. pdfs.semanticscholar.org/1ce8/…
scott m gardner
51

Komputery mechaniki kwantowej (PDF) autorstwa Richarda Feynmana.

Wprowadza ideę obliczeń kwantowych, opisuje obwody kwantowe, wyjaśnia, w jaki sposób można symulować obwody klasyczne za pomocą obwodów kwantowych, a także pokazuje, w jaki sposób obwody kwantowe mogą obliczać funkcje bez dużej ilości śmieciowych kubitów (przy użyciu obliczeń nieobliczalnych).

Następnie pokazuje, jak każdy klasyczny obwód można zakodować w niezależnym od czasu hamiltonianie! Jego dowód dotyczy również obwodów kwantowych, dlatego też pokazuje, że ewolucja czasu Hamiltonianów jest trudna w BQP! Jego konstrukcja hamiltonowska jest również używana w dowodzie kwantowej wersji twierdzenia Cooka-Levina, udowodnionego przez Kitaeva, który pokazuje, że k-lokalny hamiltonian jest kompletny QMA.

Robin Kothari
źródło
Link jest nieprawidłowy. Czy masz inne źródło? edytuj> Szukano w google: wjzeng.net/Ref/Feynman_QuantumMechanicalComputers.pdf Czy to jest to?
Klaim
To jest to. Dodałem nowy link i link do jego strony w witrynie wydawcy.
Robin Kothari
Czy pojęcia BQP i QMA istniały, gdy Feynman napisał ten artykuł? Czy jest jakiś najnowszy artykuł, który czerpie to połączenie? Wszelkie odniesienia / wyjaśnienia tego faktu, że k-local Hamiltonian jest QMA, są kompletne?
Anirbit
48

Wykresy ekspanderów i ich zastosowania, S. Hoory, N. Linial i A. Wigderson to niezwykle ładne badanie dotyczące wykresów ekspanderów. Nic dziwnego, że zdobył nagrodę AMS Conant w 2008 roku.

Chcę przypomnieć, że wykresy ekspanderów są kluczowym składnikiem ostatnich przełomów w TCS, np.

i nie tak niedawno:

Dai Le
źródło
1
Powinieneś uważać na kombinatoryjne lub wspierające warunki wstępne. Wykresy ekspanderów są dziś nawet używane w analizie numerycznej.
shuhalo,
44

Dziwi mnie, że nikt nie wymyślił „Some Optimal Inapproximability Results” Hastada (JACM 2001; pierwotnie STOC 1997). Ten przełomowy artykuł został napisany tak dobrze, że możesz do niego dojść z niewielką dojrzałością matematyczną i sprawi, że będziesz chciał dobrze nauczyć się kilku rzeczy, takich jak techniki Fouriera, równoległe powtarzanie, gadżety i tak dalej.

użytkownik 289
źródło
44

O((losolN.)3))O(exp((649b)13)(logb)2)3)))

Pratik Deoghare
źródło
42

Les Valiant's Theory of the Learnable (1984) ustalił program teorii uczenia się na dziesięciolecia i jest to miły i czytelny artykuł!

W artykule znajduje się również dość intuicyjne wyjaśnienie, które sprawia, że ​​jest zabawny i atrakcyjny. Różne części tego artykułu są nadal rutynowo cytowane w rozmowach COLT / ALT.

Lev Reyzin
źródło
37

Złożoność procedur dowodzących twierdzeń Stephena A. Cooka. Artykuł ten dowodzi, że wszystkie języki ustalone przez niedeterministyczne maszyny Turinga z okresu polityczno-politycznego można (Cook-) zredukować do zestawu tautologii zdań.

Znaczenie tego wyniku jest (przynajmniej) dwojakie: po pierwsze pokazuje, że istnieją problemy w NP, które są co najmniej tak trudne jak cała klasa, problemy NP ; ponadto stanowi konkretny przykład takiego problemu, który można następnie sprowadzić do innych w celu udowodnienia, że ​​są kompletne.

Obecnie redukcje Karp są częściej stosowane niż redukcje Cooka, ale główny dowód tego dokumentu można łatwo dostosować, aby wykazać, że SAT jest NP- kompletny w odniesieniu do redukcji Karp.

Antonio E. Porreca
źródło
7
Jest to jeden z tych artykułów konferencyjnych, dla których nigdy nie ukazała się żadna wersja czasopisma, ale zdecydowanie warto wrócić do: dobrze napisanego i pełnego świetnych komentarzy bocznych.
András Salamon,
36

CAR Hoare, Aksjomatyczna podstawa programowania komputerowego .

Z streszczenia: W niniejszym artykule podjęto próbę zbadania logicznych podstaw programowania komputerowego za pomocą technik, które zostały po raz pierwszy zastosowane w badaniach geometrii, a następnie zostały rozszerzone na inne gałęzie matematyki.

Ma sześć stron, które można dość łatwo śledzić.

Radu GRIGore
źródło
34

Alon, Matias i Szegedy, Złożoność przestrzenna aproksymacji momentów częstotliwości , JCSS 58 (1): 137-147, 1999.

Ten dość magiczny papier był pierwszym, który sformalizował algorytmy przesyłania strumieniowego i udowodnił rygorystyczne górne i dolne granice podstawowych zadań w modelu przesyłania strumieniowego. Jego techniki są proste, dowody są piękne, a ich wpływ był ogromny. Praca zdobyła nagrodę Gödela dla Alona, ​​Matiasa i Szegedy w 2005 roku.

arnab
źródło
cholera Chciałem to dodać :)
Suresh Venkat
30

Artykuł Immermana dowodzący twierdzenia znanego obecnie jako twierdzenie Immermana – Szelepcsényi jest doskonałym przykładem łatwego do odczytania, mądrego i krótkiego artykułu. Uwielbiam historię opowiedzianą we wstępie.

N. Immerman, Przestrzeń niedeterministyczna jest zamknięta pod uzupełnieniem, SIAM Journal on Computing 17, 1988, ss. 935–938.

Michaël Cadilhac
źródło
1
Szczerze mówiąc, artykuł Szelepcsényiego „Metoda wymuszonego wyliczania dla niedeterministycznych automatów” jest równie przyjemny.
Lew Reyzin
30

fa(n)log(n)

NSPACE(fa(n))DSPACE((fa(n))2)).

NPSPACE=PSPACEP.NP

Savitch, Walter J. (1970), „Relacje między niedeterministycznymi i deterministycznymi złożonościami taśm”, Journal of Computer and System Sciences 4 (2): 177–192.

Sadeq Dousti
źródło
27

Russell Impagliazzo Osobisty pogląd na złożoność średnich przypadków . Jest to świetny artykuł, ponieważ jest sprytnie napisany i podsumowuje stan rzeczy w pięciu „światach”, w których nasze domysły na temat złożoności są rozwiązywane na różne sposoby, dając w każdym przypadku rzeczywiste konsekwencje.

Steve Flammia
źródło
24

Ekstraktory i generatory pseudolosowe Luca Trevisan. W tym artykule opracowano dobry ekstraktor losowości za pomocą kodów korygujących błędy i konstrukcji kombinatorycznych. Konstrukcja jest dość łatwa do zrozumienia, ale całkowicie oszałamiająca, ponieważ wcale nie jest oczywiste, jaki jest związek między ekstraktorami, kodami i projektami.

W końcu jest to dobry przykład wyniku w TCS, który wymaga wymyślnej kombinatoryki.

ilyaraz
źródło
24

Jak napisać dowód , autorstwa Leslie Lamport.

Anthony Labarre
źródło
5
Przeczytałem to i przeczytałem Lament matematyka autorstwa Lockharta ( maa.org/devlin/LockhartsLament.pdf ). IMHO Uważam, że strategia, którą sugeruje Lamport, jest sprzeczna z tym, co Lockhart argumentuje na temat piękna matematyki.
Marcos Villagra,
5
Bardzo ciekawa lektura. Rozumiem twoją opinię, ale jeśli się nie mylę, Lamport kieruje swoje przesłanie do ludzi, którzy są bardziej „wykształceni matematycznie” niż ci, których dotyczy Lockhart, który ma na celu pomóc uczniom w polubieniu matematyki. Przyznaję również, że przestrzeganie ścisłego formatu sprawia, że ​​dowody są dość nudne do odczytania, ale zgadzam się z Lamportem co do idei dowodów według poziomów: nie zawsze chcesz / potrzebujesz / masz czas, aby przeczytać wszystko szczegółowo, a nawet kiedy zrobić, mając podsumowanie tego, co ma nadejść, może być bardzo pomocne. Znacznie więcej niż te „łatwe do zobaczenia / wyraźnie / wlog / ...” ;-)
Anthony Labarre
19

Jeśli mogę zacytować Sarah Palin w tej sprawie: „Wszyscy”.

Mówiąc poważniej, uważam, że większości artykułów nie należy czytać w oryginale. W miarę upływu czasu ludzie wymyślają lepszy sposób zrozumienia i przedstawienia oryginalnego problemu / rozwiązania. Z wyjątkiem oryginalnego papieru Turinga, który ma znaczenie historyczne, nie polecałbym czytania większości oryginalnych artykułów, jeśli zostały oczyszczone kolejne prace. W szczególności wiele rzeczy jest prezentowanych w książkach znacznie lepiej niż w oryginale.

Sariel Har-Peled
źródło
16
Ten komentarz jest ogólnie prawdziwy, ale Ryan wyraźnie prosi o przykłady, dla których nie jest to prawdą. Istnieje wiele klasycznych artykułów, które zawierają przypuszczenia, które nie zostały jeszcze udowodnione, techniki, które zostały przeoczone lub wyniki, które zwykle są zapominane, ale mogą zostać odkurzone i wykorzystane w nowych zastosowaniach.
András Salamon,
12
Nie zgadzam się. Prawdą jest, że oryginalne prace są czasami nieczytelne, a prace drugorzędne lepiej prezentują wyniki, ale czasem oryginalne prace zawierają pomysły, które zostały pominięte w późniejszych pracach. Również czytanie oryginalnych artykułów może nauczyć nas, jak autor wpadł na ten pomysł. Spójrz na ten post Timothy Chow na MO: mathoverflow.net/questions/28268/do-you-read-the-masters
Kaveh
4
Wspaniale jest, gdy tak się dzieje. Po prostu twierdzę, że jest to dość rzadkie.
Sariel Har-Peled
6
Mówisz „Wszyscy”, ale czy nie kłócisz się o „Żadne z nich”?
Peter Taylor
2
@Peter Taylor, myślę, że właśnie dlatego wspomina się o Sarah. :)
Radu GRIGore
18

Chomsky analizuje, w jaki sposób można zastosować modele matematyczne do opisu języka naturalnego z językowego punktu widzenia.

András Salamon
źródło
3
Nawiasem mówiąc, nie zalecam tego artykułu - właśnie zredagowałem, aby naprawić literówki i dodać link. Wolę papier Golda, jeśli ktoś chce klasycznej gazety o języku.
András Salamon,