Makalah apa yang harus dibaca semua orang?


Pertanyaan ini (terinspirasi oleh) / (dicuri secara memalukan dari) pertanyaan serupa di MathOverflow , tapi saya berharap jawabannya di sini akan sangat berbeda.

Kita semua memiliki makalah favorit dalam bidang teori masing-masing. Sekali-sekali, seseorang menemukan kertas yang sangat mencengangkan (mis. Penting, meyakinkan, sederhana, dan lain-lain) sehingga seseorang ingin membaginya dengan semua orang. Jadi daftarkan kertas-kertas ini di sini! Mereka tidak punya dari ilmu komputer teoretis - apa pun yang menurut Anda mungkin menarik bagi masyarakat adalah jawaban yang bagus.

Anda dapat memberikan jawaban sebanyak yang Anda inginkan; tolong tulis satu kertas per jawaban ! Juga, perhatikan ini adalah wiki komunitas, jadi pilih semua yang Anda suka!

(Perhatikan ada pertanyaan sebelumnya tentang makalah dalam kompleksitas rekursi-teori tetapi itu cukup khusus.)


65
Dalam jawabannya, saya ingin melihat lebih banyak penekanan pada apakah itu benar-benar ide yang baik untuk membaca makalah asli saat ini (atau jika lebih masuk akal untuk membaca eksposisi buku teks modern itu). Saya sudah terlalu sering melihat makalah TCS yang benar-benar mani, tetapi saya lebih suka menyelamatkan kolega saya dari kesusahan mencoba menguraikan tulisan asli - yang terlalu sering ditulis dalam abstrak konferensi 10 halaman yang ditulis dengan tergesa-gesa, dengan referensi ke "versi lengkap" yang tidak pernah muncul ...
Jukka Suomela

7
Ya, saya harap jelas bahwa makalah jenis ini tidak baik untuk daftar (jika Anda ingin membaginya dengan semua orang, maka seharusnya tidak merepotkan untuk dibaca)
Ryan Williams

30
Terlalu banyak orang yang hanya memposting satu baris. Siapa pun dapat memposting 100-an makalah unik tanpa memikirkannya. Silakan kirim mengapa Anda pikir semua orang harus membaca makalah itu. Ini berarti membenarkan mengapa mereka harus membaca makalah itu alih-alih orang lain menuliskan hasil itu , dan apa yang sangat mengagumkan tentang makalah itu sehingga setiap orang harus membacanya.
Robin Kothari

Pertanyaan bagus. Pendapat saya adalah bahwa jika Anda ingin memahami pikiran para penemu, dan mungkin memahami cara menemukan sesuatu, Anda harus membaca kata-kata mereka sendiri. Semakin banyak Anda bekerja, semakin dekat Anda dengan proses berpikir mereka yang sebenarnya.
ixtmixilix

Jawaban:



Makalah 1936 yang bisa dibilang memulai ilmu komputer itu sendiri:

  • Alan Turing, "Pada Nomor yang Dapat Dihitung, dengan Aplikasi ke Entscheidungsproblem", Prosiding London Mathematical Society s2-42, 230–265, 1937. doi: 10.1112 / plms / s2-42.1.230

Hanya dalam 36 halaman, Turing merumuskan (tetapi tidak menyebutkan nama) Mesin Turing, menampilkan kembali Teorema Ketidaklengkapan Pertama Gödel yang terkenal dalam hal perhitungan, menggambarkan konsep universalitas, dan dalam lampiran menunjukkan bahwa kemampuan komputasi oleh mesin Turing setara dengan kemampuan komputasi oleh fungsi yang dapat didefinisikan (seperti dipelajari oleh Gereja dan Kleene).λ


7
Ini juga sangat mudah diakses dan dibaca ...
Sariel Har-Peled

25
dan dengan itu The Annotated Turing oleh Charles Petzold [Sangat Dianjurkan]
Pratik Deoghare


Ken Thompson " Reflections on Trusting Trust ". Pendek, manis, dan mengejutkan.


5
Juga, sangat mudah didekati. Saya membacanya beberapa waktu yang lalu, ketika pada dasarnya saya tidak memiliki latar belakang CS, tidak memiliki pengalaman pemrograman dan bahkan tidak tahu apa itu kompiler.
Jörg W Mittag

1
"Minggu lalu, Googler Ken Thompson dianugerahi Hadiah Jepang dalam Informasi dan Komunikasi untuk pekerjaan awalnya pada sistem operasi UNIX." (src: Buzz postingan dari Life at Google)
Sebastián Grignoli

4
Saya pikir makalah ini akan sangat sulit untuk dicerna tanpa setidaknya mengetahui apa itu kompiler.
Fixee

2
Di koran, saya pikir angka 2.1 dan 2.2 ditukar.
Dennis

1
Disagree - tidak ada yang mengagumkan atau membingungkan di tulisan ini. TL; DR 6 halaman dari pertengahan 80-an tentang "perlu mengubah kode kriminal untuk mulai menghukum peretas [seperti pencuri atau pencuri]". O ya, sebutkan quine , tanpa menyebut namanya.
c69

Apa Yang Harus Diketahui Setiap Ilmuwan Komputer Tentang Aritmatika Titik Apung

Makalah ini menjelaskan dan memperkuat gagasan bahwa floating point bukanlah sihir. Ini menjelaskan overflow, underflow, apa angka denormalized, apa NaN, apa inf, dan semua hal ini menyiratkan. Setelah membaca makalah ini, Anda akan tahu mengapa a == a + 1.0 bisa benar, mengapa a == a bisa salah, mengapa menjalankan kode Anda pada dua mesin yang berbeda dapat memberi Anda dua jawaban berbeda, mengapa menjumlahkan angka dalam berbeda order dapat memberi Anda urutan perbedaan yang sangat besar dan semua hal aneh yang terjadi di dunia pemetaan sekumpulan angka tak terbatas yang tak terhingga jumlahnya ke himpunan terbatas yang tak terhitung jumlahnya.

Versi yang diedit juga tersedia di web.


3
Tolong, perbaiki tautannya. Itu rusak.
Oscar Mederos

1
Sejak Oracle mengakuisisi Sun, itu merusak sebagian besar tautan dari halaman web Sun. Meskipun Anda dapat mencapai kertas asli dari sini .
systemsfault


1
Memperbaiki tautan yang rusak.
Ryan

Cara Membaca Keshav dari Keshav . Anda juga dapat mengunduh kertas dari sini .


Memang enak dibaca.
Anthony Labarre

Saya selalu berpikir bahwa makalah penelitian CS ditulis dalam beberapa bahasa asing.
Berlin Brown

3
Baik sekali! Layak untuk diletakkan di banner tagline di situs untuk memastikan tidak ada siswa yang melewatkannya.
Vag

Tautan kedua saat ini rusak
Christopher Manning

2
Ini adalah favorit saya dari daftar. Perhatikan juga bahwa ini adalah dokumen yang hidup, tidak seperti kebanyakan kertas yang tidak menerima pembaruan setelah dipublikasikan.
Dennis

Paths, Trees and Flowers oleh J. Edmonds. Makalah ini tentang masalah optimasi kombinatorial klasik tidak hanya ditulis dengan baik, tetapi juga menyatakan bahwa gagasan "algoritma waktu polinomial" pada dasarnya adalah sinonim untuk efisiensi.


Reducibilitas Diantara Masalah Kombinatorial oleh Richard Karp. Makalah ini berisi apa yang sering disebut sebagai Karp "masalah 21 NP-lengkap asli". Dalam banyak hal, makalah ini benar-benar memotivasi studi kelengkapan NP dengan menunjukkan penerapannya ke domain yang lebih luas. Sangat mudah dibaca.


6
Saya suka makalah ini, tetapi beberapa pengurangan benar-benar samar dan sulit diikuti. Lihat teks kompleksitas untuk detail lebih lanjut.
András Salamon

2
@Andras Salamon Saya setuju 100%.
Tayfun Bayar

Hartmanis dan Stearns, "Tentang kompleksitas algoritma" , Transaksi Masyarakat Matematika Amerika 117: 285–306 (1965)

Ini adalah makalah pertama yang mengambil studi kompleksitas waktu dengan serius, dan tentu saja merupakan dorongan utama untuk penghargaan Turing bersama Hartmanis dan Stearns. Sementara definisi awal mereka tidak cukup seperti yang kita gunakan hari ini, makalah tetap sangat mudah dibaca. Anda benar-benar merasakan bagaimana keadaan di perbatasan "Wild West" tahun 60-an.



Quantum Mechanical Computers (PDF) oleh Richard Feynman.

Dia memperkenalkan ide komputasi kuantum, menjelaskan sirkuit kuantum, menjelaskan bagaimana sirkuit klasik dapat disimulasikan oleh sirkuit kuantum, dan menunjukkan bagaimana sirkuit kuantum dapat menghitung fungsi tanpa banyak qubit sampah (menggunakan uncomputation).

Dia kemudian menunjukkan bagaimana sirkuit klasik mana pun dapat dikodekan menjadi Hamiltonian yang independen terhadap waktu! Buktinya berlaku untuk sirkuit kuantum juga, karena itu menunjukkan bahwa Hamiltonians yang berevolusi waktu adalah BQP-keras! Konstruksi Hamiltoniannya juga digunakan dalam pembuktian versi kuantum teorema Cook-Levin, dibuktikan oleh Kitaev, yang menunjukkan bahwa Hamiltonian k-local adalah QMA-complete.


Tautan tidak valid. Apakah Anda memiliki sumber lain? sunting> Dicari di google: wjzeng.net/Ref/Feynman_QuantumMechanicalComputers.pdf Apakah ini yang ini?
Klaim

Itu dia. Saya menambahkan tautan baru dan tautan ke halaman itu di situs web penerbit.
Robin Kothari

Apakah pengertian BQP dan QMA ada ketika Feynman menulis makalah ini? Atau ada kertas terbaru yang menggambarkan hubungan ini? Adakah referensi / paparan fakta ini bahwa Hamiltonian k-local sudah lengkap?
Anirbit

Grafik expander dan aplikasinya, S. Hoory, N. Linial, dan A. Wigderson adalah survei yang sangat bagus pada grafik expander. Tidak mengherankan bahwa ia memenangkan Hadiah Conant AMS 2008.

Saya ingin mengingat bahwa grafik expander adalah bahan utama dalam terobosan baru-baru ini di TCS, misalnya.

dan tidak begitu baru:


1
Anda harus memperhatikan kombinatorial atau mendukung prasyarat. Grafik expander bahkan digunakan dalam analisis numerik hari ini.
shuhalo


Saya terkejut bahwa tidak ada yang datang dengan Hastad's "Some Optapproximability Results" ( Hasil Ketidaksuksesan yang Optimal) (JACM 2001; awalnya STOC 1997). Makalah tengara ini telah ditulis dengan sangat baik, Anda dapat datang ke sana dengan sedikit selain kematangan matematika dan itu akan membuat Anda ingin belajar beberapa hal dengan baik, seperti teknik Fourier, pengulangan paralel, gadget, dan yang lainnya.



Teori Pembelajaran Les Valiant (1984) menetapkan agenda untuk belajar teori selama beberapa dekade, dan ini adalah makalah yang bagus dan mudah dibaca!

Ada juga sedikit penjelasan intuitif di koran yang membuatnya menyenangkan dan menarik. Berbagai bagian dari makalah ini masih dikutip secara rutin dalam pembicaraan COLT / ALT.




Kompleksitas prosedur pembuktian teorema oleh Stephen A. Cook. Makalah ini membuktikan bahwa semua bahasa yang diputuskan oleh mesin Turing polytime nondeterministic dapat (Cook-) dikurangi menjadi seperangkat tautologi proposisional.

Pentingnya hasil ini adalah (setidaknya) dua kali lipat: pertama, ini menunjukkan bahwa ada masalah dalam NP yang setidaknya sekeras seluruh kelas, masalah NP- lengkap; lebih jauh lagi, ini memberikan contoh konkret dari masalah seperti itu, yang kemudian dapat direduksi menjadi yang lain untuk membuktikannya lengkap.

Saat ini pengurangan Karp lebih umum digunakan daripada pengurangan Cook, tetapi bukti utama dari makalah ini dapat dengan mudah disesuaikan untuk menunjukkan bahwa SAT adalah NP- lengkap sehubungan dengan pengurangan Karp.


7
Ini adalah salah satu makalah konferensi di mana tidak ada versi jurnal yang pernah muncul, tetapi yang ini layak untuk kembali ke: ditulis dengan baik dan penuh dengan komentar sampingan.
András Salamon


CAR Hoare, Suatu Dasar Aksiomatik untuk Pemrograman Komputer .

Dari abstrak: Dalam makalah ini upaya dibuat untuk mengeksplorasi dasar-dasar logis pemrograman komputer dengan menggunakan teknik yang pertama kali diterapkan dalam studi geometri dan kemudian diperluas ke cabang matematika lainnya.

Ini memiliki enam halaman yang cukup mudah diikuti.


Alon, Matias dan Szegedy, Kompleksitas ruang mendekati momen frekuensi , JCSS 58 (1): 137-147, 1999.

Makalah ini agak ajaib adalah yang pertama untuk memformalkan algoritma streaming dan membuktikan batas atas dan bawah yang ketat untuk tugas-tugas dasar dalam model streaming. Tekniknya sederhana, buktinya indah, dan pengaruhnya sangat besar. Karya itu memenangkan Alon, Matias, dan Szegedy the Gödel Prize pada 2005.


dang. Saya akan menambahkan yang ini :)
Suresh Venkat

Makalah Immerman yang membuktikan teorema yang sekarang dikenal sebagai teorema Immerman-Szelepcsényi, adalah contoh yang bagus untuk makalah yang mudah dibaca, pintar dan pendek. Saya suka kisah yang diceritakan dalam intro.

N. Immerman, ruang Nondeterministic ditutup di bawah komplementasi, SIAM Journal on Computing 17, 1988, hlm. 935-938.


1
Agar adil, makalah Szelepcsényi, "Metode penghitungan paksa untuk automata nondeterministic," sama bagusnya.
Lev Reyzin




Extractors dan Generator Pseudorandom oleh Luca Trevisan. Dalam makalah ini ekstraktor acak yang baik dibangun dengan cara kode koreksi kesalahan dan desain kombinatorial. Konstruksi cukup mudah dimengerti tetapi benar-benar menakjubkan, karena tidak jelas sama sekali apa hubungan antara ekstraktor, kode dan desain.

Bagaimanapun, ini adalah contoh yang baik dari hasil TCS yang memerlukan beberapa kombinatorik mewah.


Cara Menulis Bukti , oleh Leslie Lamport.


5
Saya membaca ini dan saya membaca Ratapan Matematikawan oleh Lockhart ( maa.org/devlin/LockhartsLament.pdf ). IMHO Saya percaya bahwa strategi yang disarankan Lamport bertentangan dengan apa yang dikemukakan Lockhart tentang keindahan matematika.
Marcos Villagra

5
Sangat menarik dibaca. Saya mengerti pendapat Anda, tetapi jika saya tidak salah, Lamport mengarahkan pesannya kepada orang-orang yang lebih "berpendidikan matematis" daripada yang ditargetkan oleh Lockhart, yang bertujuan membantu siswa mengembangkan selera matematika. Saya juga akan mengakui bahwa mengikuti format yang ketat membuat bukti cukup membosankan untuk dibaca, tetapi saya setuju dengan Lamport pada gagasan pembuktian berdasarkan level: Anda tidak selalu ingin / butuh / punya waktu untuk membaca semuanya secara terperinci, dan bahkan ketika Anda lakukan, memiliki ringkasan tentang apa yang akan datang bisa sangat membantu. Jauh lebih banyak daripada yang "mudah dilihat / jelas / wlog / ..." ;-)
Anthony Labarre


Jika saya dapat mengutip Sarah Palin tentang masalah ini: "Semuanya".

Lebih serius, saya pikir sebagian besar makalah tidak boleh dibaca dalam aslinya. Seiring berjalannya waktu orang mencari cara yang lebih baik untuk memahami dan menyajikan masalah / solusi asli. Kecuali untuk kertas asli Turing, yang merupakan sejarah penting, saya tidak akan merekomendasikan membaca sebagian besar kertas asli jika ada karya lanjutan yang membersihkannya. Secara khusus, banyak hal disajikan jauh lebih baik di buku daripada di aslinya.


16
Komentar ini benar secara umum, tetapi Ryan secara eksplisit meminta contoh yang ini tidak benar. Ada banyak makalah klasik yang mengandung dugaan yang belum terbukti, teknik yang telah diabaikan, atau hasil yang cenderung dilupakan tetapi bisa disingkirkan dan dimanfaatkan untuk penggunaan baru.
András Salamon

12
Saya tidak setuju. Memang benar bahwa makalah asli kadang-kadang tidak dapat dibaca dan karya sekunder memberikan paparan hasil yang lebih baik, tetapi kadang - kadang makalah asli berisi ide-ide yang dihilangkan dalam karya-karya selanjutnya. Juga membaca makalah orisinal dapat mengajari kita bagaimana penulis mengemukakan gagasan itu. Lihatlah posting Timothy Chow ini di MO: mathoverflow.net/questions/28268/do-you-read-the-masters
Kaveh

4
Sangat bagus ketika ini terjadi. Saya hanya mengklaim itu agak jarang.
Sariel Har-Peled

6
Anda mengatakan "Semua dari mereka", tetapi tidakkah Anda kemudian berdebat untuk "Tidak satu pun dari mereka"?
Peter Taylor

2
@ Peter Taylor, saya pikir itu sebabnya Sarah disebutkan. :)
Radu GRIGore

Chomsky menganalisis bagaimana model matematika dapat digunakan untuk menggambarkan bahasa alami, dari sudut pandang linguistik.


3
Omong-omong, saya tidak menganjurkan makalah ini - hanya diedit untuk memperbaiki kesalahan ketik dan menambahkan tautan. Saya lebih suka kertas Gold jika ada yang menginginkan kertas klasik tentang bahasa.
András Salamon

Dengan menggunakan situs kami, Anda mengakui telah membaca dan memahami Kebijakan Cookie dan Kebijakan Privasi kami.
Licensed under cc by-sa 3.0 with attribution required.