Buku apa yang harus dibaca semua orang?


[ 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:


Karena saya tidak bisa menjawab pertanyaan saya akan melakukannya di sini. Matematika Terpisah - TTC: Matematika Terpisah oleh Arthur T. Benjamin. Ini adalah kumpulan kuliah tentang berbagai topik dari Set Theory ke Graphs and Probability.
Pithikos

Mungkin menarik untuk membandingkan daftar buku yang luar biasa ini dengan daftar buku pengantar dari Apakah ada daftar buku pengantar kanonik yang mencakup cabang-cabang utama ilmu komputer? pertanyaan di reddit / compsci. Ada beberapa yang tumpang tindih, tetapi untungnya perbedaannya cukup signifikan.
Thomas Klimpel

Jawaban:


Kompleksitas Komputasi:

Jika Anda mencari buku teks kompleksitas terbaru. Dua berikut ini harus dimiliki.

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.


2
Sebagai tambahan bagi mereka yang tertarik pada bagaimana buku-buku ini dibandingkan satu sama lain, saya juga dapat menawarkan ulasan buku ini tentang Arora / Barak dan Goldreich yang baru-baru ini saya tulis untuk kolom ulasan buku SIGACT.
Daniel Apon

1
lihat juga daftar buku Komputasi Kompleksitas favorit Lance Fortnow di Amazon: amzn.com/l/22R1UX0Y9YRT2
Alessandro Cosentino

5
Satu-satunya komentar pada buku Sipser adalah bahwa ia kadang-kadang menggunakan nama yang tidak standar saat meliput teori komputabilitas. Misalnya, ia menggunakan "dapat dikenali" alih-alih "semi-decidable". Tapi saya kira karena buku teks itu sudah banyak digunakan, mungkin sudah menjadi standar sekarang.
Dai Le

4
Sebenarnya, itu komentar yang sangat bagus secara umum, @Dai Le. Saya bisa memikirkan perbedaan serupa antara Goldreich dan Arora / Barak. Misalnya, Goldreich menggunakan nama dan Arora / Barak menggunakan nama , meskipun mereka berdua berbicara tentang konsep yang sama. F N PPCFNP
Daniel Apon

1
Saya telah menemukan Sipser jauh lebih berguna daripada Papadimitriou untuk benar-benar mengajarkan teori kompleksitas, ymmv.
Jeff Burdges

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.


6
Masih pengantar teori kompleksitas terbaik setelah 30 tahun.
Emil

1
setelah berpuluh-puluh tahun buku ini masih merupakan daftar paling lengkap dari masalah lengkap NP di satu tempat, tampaknya, hampir merupakan ensiklopedia, dan banyak peneliti cs tampaknya berbagi sudut pandang ini
vzn

1
merekomendasikan ini ditambahkan ke FAQ untuk pertanyaan umum, "apakah masalah saya X NP selesai?" dengan jawaban, "periksa dulu buku ini ke-1, lalu kembalilah pada kami"
vzn

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)


7
"Pengantar Analisis Algoritma" oleh Sedgewick dan Flajolet sangat bagus.
Jay

Daniel Spielman menggunakan buku karya Kleinberg dan Tardos dalam kursus "Desain dan Analisis Algoritma" -nya. Saya mengambilnya, dan sangat menyukai buku itu. Saya merasa jauh lebih mudah didekati daripada CLRS.
Alex Reinking


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.


7
Untuk perspektif yang lebih matematis tentang teori jenis, "Ceramah tentang Curry-Howard Isomorphism" oleh Sorensen dan Urzyczyn adalah awal yang baik, memberikan gambaran yang baik tentang kalkulus lambda-diketik sampai ke Kalkulus Konstruksi, dan seterusnya.
Dominic Mulligan

4
Saya akan menyarankan Yayasan John Mitchell untuk Bahasa Pemrograman pada topik ini. Seperti dalam komentar sebelumnya, ini lebih matang secara matematis.
Artem Pelenitsyn

2
Suara positif untuk TAPL. FYI Benjamin Pierce adalah salah satu penulis buku baru "Software Foundation" yang menggunakan Coq.
kunjan kshetri

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:


1
Jika saya dapat menambahkan tautan ke sesuatu yang saya kumpulkan sendiri (dari banyak sumber yang berbeda termasuk beberapa di atas), berikut ini adalah lembar contekan dari ketidaksetaraan yang umum: lkozma.net/inequalities_cheat_sheet
László Kozma

1
Hardy, Littlewood, Polya, "Ketimpangan", permata dari tahun 1930-an (?)
kodlu

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.


4
TAOCP masih relevan dan Vol. 4A baru saja dirilis.
dbasnett

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 CCVCVCC

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 VPVPV

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 0PV0

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.


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 .


3
Buku ini disarankan dalam topik lain (saya pikir oleh Suresh). Saya merasa sangat baik. Terima kasih kepada Aaron karena menyebutkannya di sini.
MS Dousti

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:


2
Sejak diperkenalkan pada tahun 1993, nubuat acak telah banyak digunakan dalam literatur; khususnya dalam skema tanda tangan. Saya tidak tahu buku yang membahas area ini dengan tepat. Saran diterima.
MS Dousti

1
Sebuah buku tentang nubuat acak akan sangat membantu. Saya tidak melakukan pekerjaan di crypto, tapi saya sudah membaca Katz / Lindell front-to-back. Transisi dari buku teks ke literatur crypto adalah kasar karena alasan spesifik ini. Juga, @Sadeq, karena penasaran: Apakah ada buku yang sudah Anda baca yang memiliki liputan yang baik untuk rewinding?
Daniel Apon

1
@Aniel: Tesis Martin Gagné "A Study of Random Oracle Model" (UC Davis, 2008) adalah referensi yang relatif baik tentang nubuat acak (meskipun masih jauh dari lengkap). Mengenai pertanyaan "memutar": Saya tidak tahu buku tentang itu, namun saya pikir saya sudah benar-benar memahami itu. Bisakah Anda jelaskan bagian mana yang tampaknya bermasalah bagi Anda? Anda bahkan dapat menanyakannya pada topik terpisah.
MS Dousti

@ Sadq, saya cenderung tidak memulai pertanyaan independen tentang hal itu, karena itu akan berjumlah sedikit lebih dari "Bantuan, apa yang memutar?" :) Bagian yang bermasalah adalah rewinding tidak ada dalam buku teks yang digunakan dalam kursus crypto yang saya ambil (yaitu Katz / Lindell), jadi saya belum pernah melihat pengantar konsep. Saya sadar itu muncul secara teratur dalam literatur kripto, tetapi sebagai seseorang yang tidak aktif terlibat dalam penelitian kripto, saya ragu saya akan cukup membaca makalah untuk mendapatkan pemahaman yang kuat tentang memundurkan hanya dengan menjumpainya cukup banyak. Mungkin saya bisa mengajukan pertanyaan tentang asal-usul memutar itu ...
Daniel Apon

3
@Aniel: Pengantar buku saya bersamaan pengetahuan nol menjelaskan rewinding dan kesulitan yang disebabkan olehnya dalam konteks komposisi protokol. Sumber lain adalah: (1) Oded Goldreich, Hugo Krawczyk: Tentang Komposisi Sistem Bukti Pengetahuan Nol. SIAM J. Comput. 25 (1): 169-192 (1996) dan (2) Cynthia Dwork, Moni Naor, Amit Sahai: Concurrent zero-knowledge. J. ACM 51 (6): 851-898 (2004).
Alon Rosen

Pemrograman Fungsional

  • Struktur Data Murni Fungsional oleh Chris Okasaki . Sebagian besar buku tentang struktur data menggunakan bahasa imperatif seperti C atau C ++. Namun, struktur data untuk bahasa ini tidak selalu diterjemahkan dengan baik ke bahasa fungsional. Buku ini adalah salah satu paparan terbaik tentang penerapan struktur data & algoritma dalam bahasa fungsional.
  • Pemrograman Fungsional: Praktek dan Teori oleh Bruce J. Maclennan . Terlepas dari namanya, buku ini lebih berorientasi pada teori daripada berorientasi pada praktik. Mereka yang membaca buku ini akan memiliki pandangan yang jauh lebih baik tentang subjek daripada mereka yang mempelajarinya dengan pemrograman ad-hoc.
  • Mutiara Algoritma Desain Fungsional oleh Richard Bird . Eksposisi baru pada subjek, yang mengambil pendekatan pemecahan masalah, dan menunjukkan keindahan lapangan dengan menunjukkan ide-ide menarik dalam desain algoritma fungsional.
  • Pemrograman Bersertifikat dengan Jenis Tanggungan oleh Adam Chlipala . Ini adalah salah satu sumber daya terbaik dalam pembelajaran Coq, dan berfokus khususnya pada cara mengotomatisasi sertifikasi program dan pembuktian teorema menggunakan sistem berbasis logika / aturan. Contohnya luas dan mudah diikuti.

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:

Saya telah menggunakan buku Dorit Hochbaum tentang algoritma perkiraan untuk masalah NP-Hard sebagai pedoman untuk pekerjaan saya. Buku Hochbaum, tanpa diragukan, hebat. Namun, format survei mengkompromikan aliran yang lancar demi menyatukan orang-orang terbaik di lapangan. Buku Vazirani mengoreksi hal ini dengan menjadi begitu halus dan elegan dari awal hingga akhir. Kumpulan masalah yang sangat baik, petunjuk yang sangat baik untuk sebagian besar masalah, dan ada bagian di akhir buku yang ditujukan untuk membuka masalah, yang merupakan fitur yang sangat keren.

dan

Saya telah mencari buku-buku yang berkaitan dengan pemecahan masalah NP-complete dan NP-hard sekitar. Ada buku lain dari Hochbaum dan saya juga memilikinya. Sayangnya, buku itu lebih merupakan buku yang berorientasi penelitian karena ditulis oleh beberapa peneliti. Ini seperti membaca beberapa makalah penelitian dalam dua sampul keras. Ini berarti bahwa seseorang perlu memiliki semacam tingkat pengalaman menengah dengan algoritma aproksimasi.

Sebuah buku terbaru adalah Desain algoritma aproksimasi oleh Williamson dan Shmoys.


Kombinatorik

Buku pengantar. Buku-buku berikut dapat berfungsi sebagai pengantar yang sangat baik untuk subjek:

Teks lebih maju.


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.


Verifikasi Program


1
Beberapa buku (Manna dan Apt et al.) Cukup bertanggal (Manna berasal dari 1977 dan Apt et al dari 1991), bidang verifikasi program berbasis logika telah melihat kemajuan besar dalam dekade terakhir. Sayangnya, tidak ada teks terbaru yang tersedia.
Martin Berger

@ MartinBerger Ada petunjuk tentang di mana kemajuan besar ini dapat dipelajari, jika tidak ada dalam buku pelajaran terbaru?
Mitch

@Mitch Saya khawatir belum ditulis di buku pelajaran. Mungkin lihat beberapa literatur tentang alat interaktif seperti Isabelle / HOL dan Coq. Lihat juga alat verifikasi otomatis terbaru seperti "kesimpulan" dari Facebook dan teori di baliknya.
Martin Berger

Huth & Ryan sangat ramah-pemula. Untuk seseorang yang tidak terlalu terbiasa dengan semua matematika ketat di CS itu adalah awal yang baik. Ini adalah buku pertama yang saya baca tentang sisi formal CS dan membuat saya ketagihan sejak itu! Ini juga buku teks pertama yang saya benar-benar menyelesaikan semua bacaan.
RexYuan

Teori Informasi

Teori Informasi, Inferensi, dan Algoritma Pembelajaran oleh David MacKay

Buku teks terkenal lainnya tentang teori informasi dapat ditemukan di Wikipedia .


Judulnya adalah "Buku Apa Yang Seharusnya Dibaca Semua Orang?", Jadi rekomendasinya harus selektif. Siapa pun dapat menemukan daftar besar buku tentang "teori informasi" dari Amazon / perpustakaan, tetapi jika Anda hanya memiliki 2-3 pilihan, akan seperti apa mereka? Anda hanya harus merekomendasikan buku atau artikel yang telah Anda baca dengan cukup hati-hati dan dipersempit menjadi favorit mutlak Anda!
Dai Le

1
@Dai Le: Anda benar. Saya pikir daftarnya harus dipersempit. (Saya pribadi bertanggung jawab untuk membengkak daftar!) Namun, ini adalah pos wiki komunitas . Saya menambahkan daftar panjang yang menunjukkan siapa kandidat itu. Harap potong daftar untuk hanya menyertakan buku-buku yang paling tepat.
MS Dousti

1
@ Sadq: Saya khawatir jarang terjadi bahwa satu orang akan memangkas daftar orang lain. Selama postingan masih dalam bentuk saat ini, itu sama sekali tidak berharga sehubungan dengan tujuan posting.
Dai Le

@Dai: Anda benar. Tapi, karena saya bukan ahli dalam "teori info," saya tidak bisa memotong daftar sendiri. Saya dapat: 1) menghapus daftar yang saya tambahkan sekaligus (meninggalkan daftar asli), atau 2) Menambahkan pemberitahuan dalam teks untuk menarik perhatian ahli. Apa yang Anda sarankan?
MS Dousti

@ Sadq: Saya juga tidak bekerja pada teori informasi, kalau tidak saya akan membantu untuk memangkas daftar. Saya tahu bahwa buku "Thomas M. Cover, Joy A. Thomas. Elemen-elemen teori informasi" direkomendasikan oleh banyak orang termasuk Lance Fortnow. Tetapi saya tidak yakin apakah semua orang harus membacanya atau tidak. Saya pikir kita harus menghormati poster asli karena buku itu mungkin yang paling favoritnya. Jadi menghapus seluruh daftar adalah pilihan yang bagus. Saya benar-benar minta maaf karena terlalu berterus terang. Bisakah Anda meminta orang untuk menjelaskan mengapa mereka menyarankan buku-buku mereka?
Dai Le

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


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:

  • 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:



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.



Satu lagi, bagus untuk analisis Boolean Fourier (seperti judulnya) dan mencakup dasar-dasar, topik yang lebih maju dan (banyak) aplikasi, adalah Analisis Fungsi Boolean , oleh Ryan O'Donnell (2014). Ini tersedia online secara gratis di sini juga.
Clement C.

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".


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.




3
Bagaimana ini dibandingkan dengan "Bagaimana menyelesaikannya" oleh G. Polya? Saya pikir saya membaca saran bahwa Polya adalah yang asli dan jauh lebih baik, tapi saya tidak yakin dan tidak dapat
menolaknya

2
"How to Solve It" (HTSI) Polya membahas topik yang berbeda dari buku Velleman. Polya adalah semacam rumusan tentang bagaimana menemukan solusi untuk masalah-masalah sulit, sedangkan Velleman adalah buku teks tentang cara memformalkan solusi menggunakan konvensi dan bahasa matematika. HTSI memang memiliki informasi tentang bukti, tetapi disajikan dalam semacam bentuk "glosarium" tanpa struktur, sedangkan Velleman memberi Anda kurikulum sistematis dengan latihan. Keduanya layak dibaca, tetapi yang satu tidak menggantikan yang lain.
Nate CK

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:


Apa pendapat Anda tentang buku Rosen, atau cetak ulang Dover?
Mark C

@ Mark: Mereka juga bagus. Mengapa tidak mengedit kiriman, dan menambahkan buku-buku itu juga?
MS Dousti



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


1
Ada juga The Theory of Graphs oleh Claude Berge, salah satu pendiri teori graf. Dan Grafik dan Algoritma oleh Michel Minoux dan Michel Gondran.
Lamine

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.