[ Garis Waktu ]
Pertanyaan ini memiliki semangat yang sama tentang makalah apa yang harus dibaca semua orang dan video apa yang harus ditonton semua orang . Ia meminta buku-buku luar biasa di berbagai bidang ilmu komputer teoretis.
Buku-buku itu bisa berorientasi matematika, tetapi Anda mungkin merasa hebat untuk seorang ilmuwan komputer. Contoh:
- Kemungkinan; Peluang; probabilitas
- Ketidaksetaraan
- Logika
- Teori grafik
- Kombinatorik
- Desain & Analisis Algoritma
- Teori Komputasi / Teori Kompleksitas Komputasi
Harap berikan setiap jawaban untuk buku-buku dengan subjek yang sama (mis. Buku tentang kombinatorik).
Catatan: Judulnya mungkin menyesatkan. Berikut ini klarifikasi: Biarkan X dan Y menjadi dua bidang dalam ilmu komputer. Ada buku yang semuanya
- di bidang X harus membaca.
- di bidang Y harus membaca.
- di kedua bidang harus membaca.
Pertanyaan ini mencari 3 kasus. Dengan kata lain, itu TIDAK khusus untuk kasus yang terakhir.
Sunting: Seperti yang disarankan oleh Dai Le , harap sorot alasan Anda menyukai buku ini juga.
Topik-topik yang berkaitan:
- Referensi untuk teknik bukti TCS
- Buku-buku tentang teori automata untuk belajar sendiri
- Buku untuk probabilitas
- Buku matematika populer favorit
- Panduan pemula untuk derandomisasi
- Referensi pada batas bawah sirkuit
- Survei artikel tentang teori fungsi rekursif
- Buku tentang Pemrograman Semantik Bahasa
- Apa buku TCS terbaru yang konsepnya tersedia online
- Buku tentang kemungkinan
sumber
Jawaban:
Kompleksitas Komputasi:
Jika Anda mencari buku teks kompleksitas terbaru. Dua berikut ini harus dimiliki.
Kompleksitas Komputasi: Suatu Pendekatan Modern oleh Sanjeev Arora dan Boaz Barak ( beranda Buku Teks )
Kompleksitas Komputasi: Perspektif Konseptual oleh Oded Goldreich ( beranda Buku Teks )
Mayoritas konten antara kedua buku ini sebanding. Namun, ada beberapa perbedaan utama: Goldreich menyediakan lebih banyak ruang untuk mengeksplorasi dasar konsep dan teori filosofis kompleksitas, sedangkan Arora / Barak mencakup pilihan topik yang lebih luas, termasuk model kompleksitas konkret, perhitungan kuantum, dan batas bawah sirkuit yang sebagian besar tidak ada dari mantan.
Opsi lain, buku teks yang lebih tua namun tidak lekang oleh waktu dalam kompleksitas adalah:
Buku Papadimitriou terkenal untuk bab-bab yang mencakup logika tingkat pertama serta kelas SNP, MaxSNP , dan APX (fondasi teoritis kekerasan pendekatan), yang hilang dari teks-teks yang lebih modern.0
Klasik lain (komparatif) yang lama, tetapi cukup terkenal adalah:
Ini adalah salah satu dari sedikit / pertama buku teks yang secara eksplisit memasukkan "Ide Bukti:" antara "Teorema:" dan "Bukti:", dan merupakan salah satu buku teks matematika matematika terbaik yang ditulis pada topik apa pun . Di sisi lain, ini hanya pengantar kompleksitas, hanya menyediakan satu bab 50 halaman untuk "topik lanjutan" (termasuk perkiraan, algoritma probabilistik, IP = PSPACE, dan crypto). Sebagai buku pertama tentang kompleksitas, atau sebagai contoh penulisan yang benar-benar bagus, buku ini hebat .
Scott Aaronson menulis bahwa buku ini memiliki "kesenangan dari sebuah buku populer dengan bobot intelektual dari sebuah buku teks." Ini bercerita dan memberikan banyak contoh dan referensi yang menghibur (Game of Life, dan banyak contoh lainnya untuk mesin Turing-complete). Itu tidak masuk terlalu jauh ke dalam teori kompleksitas tetapi memiliki luas luas. Yang perlu diperhatikan adalah hubungannya dengan fisika statistik.
sumber
NP-Completeness:
Ya, saya kira Komputer dan Ketidakterbatasan Garey dan Johnson : Panduan untuk Teori Kelengkapan NP akan ditemukan di antara buku-buku teratas dalam daftar ini.
sumber
Desain & Analisis Algoritma:
Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, dan Clifford Stein. Pengantar Algoritma.
R. Motwani, P. Raghavan. Algoritma acak.
Saya menemukan buku ini disarankan oleh Ryan Williams di MathOverflow: Algorithm Design oleh Kleinberg & Tardos .
Buku bagus lainnya adalah Pengantar Algoritma: Pendekatan Kreatif oleh Udi Manber . Buku ini bukan katalog algoritma; melainkan, ia mencoba memberi intuisi kepada pembaca untuk "mengenali struktur matematika dalam masalah-masalah abstrak." (dikutip dari ulasan)
sumber
Matematika Umum untuk Ilmu Komputer:
Matematika Beton: Yayasan Ilmu Komputer oleh Graham, Knuth, dan Patashnik.
Princeton Companion to Mathematics oleh Gowers et al.
Bukti dari BUKU oleh Aigner dan Ziegler.
sumber
Jenis Sistem dan Pemrograman Semantik Bahasa:
Jenis dan Bahasa Pemrograman Benjamin Pierce dan volume lanjutan Topik Lanjutan dalam Jenis dan Bahasa Pemrograman . Mereka memberikan gambaran yang solid namun komprehensif tentang peran teori tipe dalam desain bahasa pemrograman, bersama dengan menggunakan semantik operasional untuk mengekspresikan semantik bahasa pemrograman.
sumber
Ketidaksetaraan:
Buku lain yang berharga bagi siapa pun dalam ilmu komputer yang ingin mengikat kuantitas apa pun (jadi, semuanya!) Adalah: Kelas Master Cauchy-Schwarz: Pengantar Seni Ketimpangan Matematika oleh Michael Steele.
Buku ensiklopedis tentang topik ini adalah A Dictionary of Inequalities . Meskipun ini bukan buku untuk dibaca secara langsung, ada baiknya Anda memilikinya. Lihat juga suplemen buku ini.
Selain itu, Wikipedia memiliki daftar ketidaksetaraan yang sangat baik .
Untuk topik tertentu, Anda dapat berkonsultasi:
sumber
Menarik. Tidak ada yang menyebutkan volume The Art of Computer Programming oleh Donald E. Knuth . Perawatan topik yang sangat terperinci dengan latihan yang sangat baik.
Saya menemukan permata seperti 'resorvoir sampling' dalam buku ini hanya untuk menyebutkan satu contoh.
sumber
Seperti yang Sylvain Peyronnet sebutkan, logika adalah bagian penting dari ilmu komputer teoretis. Namun, itu tidak cukup untuk belajar logika dari buku pelajaran yang dirancang untuk ahli matematika murni. Dengan kata lain, penting juga untuk belajar logika dari perspektif yang lebih "ilmu komputer".
Teori Model Hingga
Kami ingin mempelajari teknik yang berhubungan dengan struktur hingga. Hal ini juga diketahui bahwa banyak alat-alat tradisional dari model teori, misalnya, kekompakan dan Löwenheim-Skolem Teorema, yang tidak berlaku untuk HINGGA model. Ini membawa kita ke studi tentang Teori Model Hingga . Untuk area ini, saya merekomendasikan buku-buku bagus berikut:
Sub-area dari teori model hingga adalah kompleksitas deskriptif , di mana kami ingin mengkarakterisasi kelas kompleksitas dengan jenis logika yang diperlukan untuk mendefinisikan bahasa. Referensi definitif untuk kompleksitas deskriptif adalah:
Kompleksitas Bukti
Bidang logika penting lainnya dalam ilmu komputer adalah Proof Complexity , studi hubungan tiga arah antara kelas kompleksitas, sistem logis yang lemah, dan sistem bukti proposisional. Dua aspek terkait berikut dipertimbangkan: (i) kerumitan bukti formula proposisional, dan (ii) studi tentang teori aritmatika yang lemah, yang disebut aritmatika terbatas .
Aspek (i) berkaitan dengan pertanyaan berikut: "Apakah ada sistem bukti proposisional di mana setiap tautologi memiliki bukti polinomial ukuran dalam ukuran tautologi?"
Aspek (ii) mempelajari sistem logis yang menggunakan penalaran terbatas berdasarkan konsep dari kompleksitas komputasi. Dengan kata lain, kita menetapkan dengan masing-masing kelas kompleksitas teori logis , di mana provably keseluruhan fungsi dalam persis fungsi di kelas kompleksitas . Salah satu pengembangan baru-baru ini adalah program penelitian baru yang disebut "matematika terbalik terbatas" yang diusulkan oleh Stephen Cook dan Phuong Nguyen, di mana tujuannya adalah untuk mengklasifikasikan teorema (minat dalam ilmu komputer) berdasarkan pada kompleksitas konsep komputasi minimal yang diperlukan untuk membuktikannya. .V C V C CC VC VC C
Aspek (i) dan (ii) sangat terkait dengan gagasan terjemahan proposisional yang diusulkan dalam makalah Cook tahun 1975 , yang memperkenalkan teori persamaan untuk fungsi polytime dan menunjukkan bagaimana teorema dalam dapat diterjemahkan ke dalam keluarga tautologi yang memiliki bukti panjang polinomial dalam sistem bukti Frege yang diperluas.P VPV PV
Untuk survei yang sangat baik tentang kompleksitas bukti, saya merekomendasikan dua buku berikut:
Buku karya Cook dan Nguyen pada dasarnya mandiri, dan semua latar belakang logika yang diperlukan diberikan dalam Bab 2 dan 3. Bab 9 sangat menarik karena penulis memperkenalkan metode yang sangat mudah untuk mendefinisikan teori Anda sendiri untuk setiap kelas kompleksitas dalam . Dalam metode ini, kita hanya perlu menambahkan satu aksioma tambahan ke teori dasar , di mana aksioma hanya menyatakan keberadaan solusi untuk masalah lengkap dari kelas kompleksitas. Luar biasa!V 0P V0
Buku karya Krajíček sedikit lebih menantang karena ia menganggap para pembaca sudah terbiasa dengan logika matematika dan teori model (atau cukup bersedia untuk mempelajari latar belakang yang dibutuhkan di sepanjang jalan). Tetapi Anda akan belajar banyak dari membaca dan memahami buku ini.
sumber
Algoritma Acak:
Probabilitas dan Komputasi: Algoritma Acak dan Analisis Probabilistik oleh Michael Mitzenmacher dan Eli Upfal.
Buku bagus untuk menjelaskan dasar-dasar algoritma acak. Contoh dan bukti dijelaskan dengan sangat jelas, dan mudah diikuti. Juga, latihannya sangat menyenangkan untuk dilakukan.
(dijawab oleh Marcos Villagra)
Analisis Algoritma Acak:
Siapa pun yang bekerja dalam algoritma harus memiliki Konsentrasi Pengukuran untuk Analisis Algoritma Acak , yang juga tersedia untuk diunduh dalam format PDF di sini .
sumber
Kriptografi:
Buku dua jilid Foundation of Cryptography by Oded Goldreich ( Volume 1: Basic Tools dan Volume 2: Basic Applications ) adalah buku yang luar biasa untuk subjek ini. (Draf awal tersedia di beranda penulis .) Versi singkat dari buku ini juga tersedia.
Buku bagus lainnya adalah Pengantar Kriptografi Modern: Prinsip dan Protokol oleh Katz & Lindell.
Bagi mereka yang tertarik pada latar belakang matematika dari kriptografi, Sebuah Pengantar Kriptografi Matematika oleh Hoffstein et al. adalah pilihan alami.
Buku-buku bagus lainnya adalah:
Topik Khusus:
sumber
Pemrograman Fungsional
sumber
Algoritma Perkiraan
Buku Algoritma Approximation oleh Vazirani adalah buku terbaik tentang subjek ini. Buku lain adalah Algoritma Aproksimasi untuk Masalah NP-Hard oleh Hochbaum.
Berikut adalah perbandingan dari dua pengulas:
dan
Sebuah buku terbaru adalah Desain algoritma aproksimasi oleh Williamson dan Shmoys.
sumber
Kombinatorik
Buku pengantar. Buku-buku berikut dapat berfungsi sebagai pengantar yang sangat baik untuk subjek:
Teks lebih maju.
sumber
Kombinatorik
Saya ingin mengutip Analytic Combinatorics , oleh Philippe Flajolet dan Robert Sedgewick. Ini memberikan latar belakang matematika yang kuat untuk penghitungan dan analisis algoritma. Saya juga ingin memberi penghormatan kepada Philippe Flajolet, yang meninggal dua hari yang lalu dan merupakan ahli matematika dan ilmuwan komputer yang hebat.
sumber
Verifikasi Program
sumber
Teori Informasi
Teori Informasi, Inferensi, dan Algoritma Pembelajaran oleh David MacKay
Buku teks terkenal lainnya tentang teori informasi dapat ditemukan di Wikipedia .
sumber
Algoritma terdistribusi
Algoritma Terdistribusi oleh Nancy Lynch Ini adalah teks klasik yang ditulis oleh pelopor komputasi terdistribusi;
Pengantar Algoritma Terdistribusi oleh Gerard Tel Pengantar yang sangat baik, juga cocok untuk kursus tingkat sarjana; berfokus pada model penyampaian pesan
Komputasi Terdistribusi: Dasar-dasar, Simulasi, dan Topik Tingkat Lanjut oleh Hagit Attiya dan Jennifer Welch Ini berisi bahan-bahan canggih, cocok untuk kursus tingkat PhD; kedua model message-passing dan shared-memory dibahas
Desain dan Analisis Algoritma Terdistribusi Oleh Nicola Santoro Buku yang relatif baru, dapat digunakan baik di tingkat sarjana dan PhD; bahan disajikan dengan penekanan pada desain protokol
sumber
Komputasi Quantum
Komputasi Quantum dan Informasi Quantum oleh Nielsen dan Chuang , adalah buku referensi yang bagus , ideal bagi mereka yang ingin meneliti di lapangan. Namun, untuk pemula, sulit untuk belajar dari, dan itu pasti bukan untuk pelajar mandiri. Karena buku ini tidak memiliki contoh yang bagus, saya sarankan buku berikut:
Masalah & Solusi dalam Komputasi Quantum & Informasi Quantum oleh Steeb & Hardy . Buku ini memuat banyak contoh, tetapi buku ini masih belum untuk pemula yang absolut. Sebagai permulaan, buku berikut ini disarankan:
Komputasi Quantum Sejak Democritus oleh Scott Aaronson . Tur-kekuatan lebih dari komputasi kuantum, dengan hubungan dengan fisika, filsafat, dll.
Dua buku pengantar yang sangat baik tentang masalah ini adalah:
sumber
Optimasi
Saya menyukai Paul Nahin's When Least is Best.
Pada dasarnya sejarah lucu tentang pengoptimalan melalui masalah dan kepribadian. Ada ulasan bagus di halaman 32-36 di salah satu kolom Bill Gasarch.
sumber
Kompleksitas komunikasi:
Kompleksitas Komunikasi oleh Eyal Kushilevitz dan Noam Nisan.
Ini adalah buku klasik dan ditulis dengan sangat baik. Meskipun sedikit tua sekarang, masih buku pengantar terbaik ke lapangan. Juga, latihan ini sangat menyenangkan, dan diberikan tepat setelah menjelaskan konsep sehingga Anda dapat memperbaiki apa yang baru saja Anda pelajari.
Bagian dari kompleksitas komunikasi acak harus dilengkapi dengan bagian-bagian dari buku pertama.
Kompleksitas Komunikasi dan Komputasi Paralel oleh Juraj Hromkovič.
Sangat lengkap, meski terkadang agak sulit dibaca. Penjelasan intuitif sangat jelas, dan latihan yang sangat bagus. Pada bagian kedua ini menyajikan koneksi ke komputasi paralel.
sumber
Buku-buku karya Matousek & Chazelle on Discrepancy sangat bagus.
Hampir semua buku karya Matousek , pada kenyataannya, layak dibaca sampai batas tertentu.
Buku Douglas West tentang Graph Theory ( [1] dan [2] ) bagus.
sumber
Aljabar Komputasi
Seperti yang dikatakan Siwa dalam jawaban ini , literatur di bidang ini tersebar di mana-mana, tanpa terminologi umum. Orang dapat menemukan referensi yang berguna dengan mencari "perhitungan simbolik", "teori kompleksitas aljabar", "aljabar komputer" atau "aljabar komputasi". Seperti yang disarankan dalam jawaban untuk pertanyaan ini ,
Analisis Komputasi
Bidang yang menarik juga, yang berkaitan dengan komputasi dalam fungsi nyata. Juga dikenal sebagai "analisis yang dapat dihitung" atau "kalkulus yang dapat dihitung".
sumber
Kombinatorik
menghasilkanfungsiologi , oleh Herbert S. Wilf, adalah pengantar yang sangat baik untuk teori fungsi menghasilkan, ditulis dengan cara yang halus dan dikemas dengan latihan. Jika dia menulis semua bukunya seperti itu, saya tidak sabar untuk memulai yang lain.
Enumerative Combinatorics oleh Richard Stanley adalah referensi yang bagus (lanjutan).
Combinatorics: topik, teknik, algoritma oleh Peter Cameron dan Invitation to Discrete Mathematics oleh Matousek dan Nesetril adalah perkenalan yang bagus untuk combinatorics.
Combinatorics Terapan oleh Roberts dan Tesman adalah referensi ensiklopedi tentang kombinatorika terapan.
sumber
Logika:
Ini adalah kata demi kata dari jawaban saya untuk pertanyaan ini .
Pengetahuan tentang logika matematika dasar, menurut saya, merupakan nilai tambah. Anda dapat melihat dua buku karya Cori dan Lascar.
Logika Matematika: Kursus dengan Latihan Bagian I
Logika Matematika: Kursus dengan Latihan Bagian II
sumber
Penulisan Logika / Bukti:
sumber
Teori Angka
Saya menemukan beberapa buku yang sering dikutip di banyak makalah. Mereka sangat baik dalam hal ini, tetapi beberapa dari mereka sudah cukup tua. Berikut daftar yang saya ingat:
sumber
Hypergraphs
Tidak banyak buku yang dikhususkan untuk hypergraphs. Salah satu buku itu adalah
Berge C. Hypergraphs: kombinasi set terbatas .
sumber
Teori Bukti
Buku Troelstra dan Schwichtenberg Basic Proof Theory adalah teks de facto tentang topik tersebut sekarang.
Girard, Taylor & LaFont's Proofs and Types adalah buku yang lebih pendek tentang masalah ini, dan versi itu tersedia untuk diunduh di http://www.paultaylor.eu/stable/Proofs%2BTypes.html
sumber
Teori grafik
Untuk pengantar teori grafik: Pengantar Teori Grafik oleh Barat
Lebih lanjut tentang teori grafik: Teori Grafik oleh Bondy dan Murty
Buku komprehensif yang berisi perkembangan baru serta hasil klasik lama dalam teori grafik:
Teori grafik: Reinhard Diestel .
Untuk grafik pada permukaan dengan pendekatan kombinatorial:
Grafik Pada Permukaan
Dan untuk digraf:
Digraphs: Teori, Algoritma dan Aplikasi
sumber
Desain VLSI
Saya tidak suka hardware. Namun, karena FAQ memasukkan VLSI sebagai salah satu sub-bidang TCS, saya bertanya kepada seorang ahli tentang buku-buku terkenal dalam desain VLSI. Di sini mereka:
sumber