Apa Catatan Kuliah Yang Harus Dibaca Semua Orang?

113

Ada beberapa pertanyaan dengan skema yang sama seperti ini:

Saya enggan mengirim satu lagi, tetapi catatan kuliah tentang algoritma Jeff Erickson berubah pikiran. Saya berpikir: Ya ampun! Bertahun-tahun dan saya belum melihat catatan yang luar biasa ini!

Jadi, saya pikir mungkin ada catatan kuliah hebat lainnya, yang benar-benar layak dibaca. Jadi, untuk setiap bidang ilmu komputer ( struktur data, algoritma, teori komputasi, kompleksitas komputasi, kriptografi , dll.), Rekomendasikan catatan kuliah pilihan Anda yang luar biasa, dan katakan mengapa menurut Anda itu unggul.

Satu aturan sederhana untuk menjaganya tetap rapi: Satu jawaban untuk setiap subbidang. (Ini akan menjadi wiki komunitas, sehingga Anda dapat mengedit jawaban yang ada, dan menambahkan rekomendasi Anda.)

reference-request soft-question big-list M.S. Dousti
sumber
9
Anda mendapatkan suara saya. Andai saja daftar seperti itu ada kembali ketika saya masih menjadi mahasiswa ...
Anthony Labarre
7
Terima kasih atas tautan ke catatan hebat Jeff Erickson!
Standa Zivny
2
Haruskah pertanyaan ini juga menjadi wiki komunitas?
Dave Clarke
@ Dave: Ya, saya sudah menandainya sebagai CW. Itu membutuhkan perhatian mod.
MS Dousti
Saya berharap saya bisa memperbaiki ini lebih dari satu kali.
Vivek Bagaria

Jawaban:

31

Teori Probabilitas Dan Algoritma Acak

Derrick Stolee
sumber
2
Tautan ini sekarang mati. Bisakah Anda memperbaiki atau itu akan dihapus?
Dave Clarke
5
@Dave, sepertinya tidak ada lagi tautan dari halaman web Ryan ke kursus. Tapi saya tidak berpikir menghapus entri adalah ide yang bagus, dia mungkin akan mengembalikan tautan itu pada suatu saat. Komentar Anda bahwa tautan rusak adalah IMO yang cukup.
Kaveh
@DaveClarke Tautan sudah diperbaiki. Yay!
Jardine
24

Perhitungan dan informasi kuantum

Beberapa catatan kuliah luar biasa dari bidang ini:

Kursus pengantar tentang komputasi kuantum. Cukup bagus untuk dijadikan buku. Saya kenal beberapa peneliti yang memiliki cetakan dari catatan ini di rak buku mereka.

Kursus lanjutan tentang informasi kuantum. Beberapa catatan kuliah terbaik yang pernah saya baca.

Kursus lanjutan tentang algoritma kuantum. Sumber daya yang sangat baik untuk algoritma kuantum terbaru. Jika kertas asli pada beberapa algoritma kuantum sulit dimengerti, ini adalah tempat saya akan memeriksa selanjutnya.

Saya tidak bisa meringkas kursus ini dalam satu baris. Baca deskripsi di halaman web kursus.

Termasuk pengantar umum untuk Quantum Computing, serta topik khusus crypto seperti Distribusi Kunci Quantum, Komitmen Quantum, Model Penyimpanan Quantum Terikat, dan Quantum Zero-Knowledge.

Robin Kothari
sumber
Sangat menarik, terima kasih. Saya selalu ingin belajar komputasi kuantum, tetapi tidak punya cukup waktu untuk membaca buku. Apakah Anda tahu kursus yang dikhususkan untuk kriptografi kuantum ? Saya menemukan satu di sini , tetapi sayangnya, catatan tidak tersedia online.
MS Dousti
@ Sadq: Maaf, tidak tahu.
Robin Kothari
23

Kompleksitas Komputasi

Ada banyak kursus bagus tentang topik ini. Berikut ini hanyalah puncak gunung es. Untuk memilih satu, saya sarankan untuk melihat materi yang dibahas dalam setiap kursus, serta tingkat yang ditawarkan:

MS Dousti
sumber
22

A Theorist's Toolkit oleh Sanjeev Arora.

Saya suka catatan ini karena memberi Anda seperangkat alat yang agak lengkap untuk menyerang masalah dalam teori kompleksitas. Misalnya, dimensi VC digunakan secara luas untuk membuktikan batas bawah dalam model komunikasi, dan catatan ini menjelaskannya dengan sangat baik dan dari dasar-dasarnya.

Marcos Villagra
sumber
20

Teori Informasi

Derrick Stolee
sumber
17

PCP & Hardness of Approximation

Sadeq Dousti
sumber
Manakah dari mereka yang Anda baca sendiri?
Thomas Ahle
17

Matematika diskrit

Matematika Terpisah untuk Ilmu Komputer oleh Lehman, Leighton, dan Meyer ( versi lebih lama )

Jeffε
sumber
Saya mendapatkan 403 Forbidden error pada tautan Anda.
Derrick Stolee
@Derrick: Kesalahan hilang atau tautannya diperbaiki.
MS Dousti
Ya, kedua tautan berfungsi sekarang .....
Derrick Stolee
Oleh karena itu tautan ke versi yang lebih lama.
Jeff
1
Versi saat ini lebih terkini: courses.csail.mit.edu/6.042/spring15/mcs.pdf . Rasanya seperti menemukan tautan yang tepat di tengah banyak cermin usang telah menjadi masalah NP-lengkap ...
darij grinberg
16

Keacakan acak

Kursus terbaik tentang hal ini ditawarkan oleh Salil Vadhan . Lihat juga topik ini untuk konsep buku Salil tentang pseudorandomness.

M.S. Dousti
sumber
15

Kriptografi

Ada sejumlah catatan kuliah yang sangat baik tentang masalah ini, semua oleh orang-orang terkenal di lapangan. Anda dapat memilih satu (atau dua) dari yang berikut untuk dipelajari; semuanya tergantung pada lingkungan, latar belakang, dan persyaratan Anda:

MS Dousti
sumber
11

DUDUK

Saya mengunjungi kursus SAT beberapa tahun yang lalu dengan Profesor Welzl. Catatan kuliahnya sejauh ini merupakan yang terbaik yang pernah saya lihat sepanjang seluruh studi saya.

Sayangnya, hanya versi 2005 yang online, termasuk daftar pendek pembaruan .

(Algoritma SAT tercepat serta bukti konstruktif dari lemma lokal Lovász berasal dari orang-orang dalam kelompoknya.)

Sacha
sumber
9

Kursus "Mutiara Algoritma". Bagian 3 : Analisis Probabilistik dan Algoritma Acak. The kuliah catatan berada di analisis merapikan . Saya terutama menyukai gambar 1.1 di halaman ketiga.

Oleksandr Bondarenko
sumber