Saya seorang mahasiswa pascasarjana dalam matematika, dan ilmu komputer teoretis adalah domain yang saya tidak pernah mengerti tentang apa itu karena saya tidak dapat menemukan bacaan yang baik tentang topik tersebut. Saya ingin tahu apa sebenarnya domain ini, topik apa yang terkait, prasyarat apa yang diperlukan untuk memulai, dll. Untuk saat ini, saya hanya ingin tahu:
Apa buku pengantar yang bagus untuk ilmu komputer teoretis?
Mengingat bahwa ada hal seperti itu. Jika tidak, di mana seharusnya seorang ahli matematika yang memiliki pengetahuan dasar tentang ilmu komputer (yaitu mereka tahu dasar-dasar satu atau dua bahasa pemrograman) mulai jika mereka ingin memahami apa itu ilmu komputer teoritis tentang? Apa yang kamu sarankan?
Terima kasih!
Jawaban:
Pertama, "ilmu komputer teoretis" memiliki arti yang berbeda bagi setiap orang. Saya pikir untuk sebagian besar pengguna di situs ini, karikatur sejarah (yang mencerminkan beberapa kecenderungan sosiologis modern) adalah bahwa ada "Teori A" dan "Teori B" (tanpa ada hubungan keteraturan yang tersirat di antara mereka): Teori A terdiri dari teori algoritma, teori kompleksitas, kriptografi, dan sejenisnya. Teori B terdiri dari hal-hal seperti teori bahasa pemrograman, teori automata, dll. Tergantung pada selera Anda dalam matematika, Anda dapat memilih satu dari yang lainnya (atau sama-sama menyukai keduanya). Saya lebih akrab dengan "Teori A," jadi izinkan saya memberikan beberapa referensi di sana:
Mulailah dengan buku Sipser. Ini akan memberi Anda pengenalan yang baik untuk automata, mesin Turing, komputabilitas, kompleksitas Kolmogorov, P vs NP, dan beberapa kelas kompleksitas lainnya. Ini sangat ditulis dengan baik (menurut saya, itu adalah salah satu buku teknis terbaik yang pernah ditulis )
Untuk algoritme, saya memiliki preferensi sedikit untuk Kleinberg-Tardos, tetapi ada banyak buku pengantar yang bagus di luar sana. Anda mungkin terutama tertarik pada geometri komputasi, yang memiliki kumpulan buku-buku bagus.
Mengingat bahwa Anda adalah seorang mahasiswa pascasarjana matematika, cabang utama TCS yang hilang dari buku-buku ini adalah teori kompleksitas aljabar , yang sering terkait erat dengan aljabar (baik komutatif maupun non-komutatif), teori representasi, teori grup, dan geometri aljabar . Ada teks kanonik di sini, yaitu Burgisser-Clausen-Shokrollahi. Hal ini agak ensiklopedis, jadi tidak mungkin pengantar terbaik, tapi aku tidak yakin ada adalah sebuah buku yang benar-benar pengantar di daerah ini. Anda juga dapat memeriksa survei oleh Chen-Kayal-Wigderson dan Shiplka-Yehudayoff.
Setelah itu, saya sarankan browsing melalui buku-buku lebih lanjut tentang topik-topik tertentu, tergantung pada selera matematika Anda:
Arora-Barak adalah teori kompleksitas yang lebih modern (berlanjut di tempat buku Sipser berakhir, jadi untuk berbicara), memberi Anda rasa teknik yang terlibat (campuran kombinatorik dan aljabar, sebagian besar)
Buku Jukna tentang kompleksitas fungsi Boolean memiliki kemiripan, tetapi lebih mendalam untuk kompleksitas sirkuit Boolean pada khususnya (sangat kombinatorial dalam rasa)
Teori kompleksitas geometris. Lihat di sini atau pengantar Landsberg untuk geometer .
Buku O'Donnell's Analisis Fungsi Boolean memiliki kecenderungan yang lebih Fourier-analitik.
Kriptografi. Aspek matematika yang lebih maju di sini biasanya teori bilangan dan geometri aljabar. Sementara aspek-aspek matematika murni ini hanya mewakili sebagian kecil dari kriptografi, mereka adalah aspek penting yang mungkin menarik bagi Anda. Bukan sebagai daerah saya, saya tidak yakin apa buku awal yang bagus di sini.
Teori pengkodean. Di sini, teori matematika berkisar dari pengemasan bola (lihat buku karya Conway dan Sloane) hingga geometri aljabar (misalnya, buku karya Stichtenoth). Sekali lagi, bukan daerah saya, jadi saya tidak yakin apakah ini adalah titik awal terbaik, tetapi membolak-baliknya Anda akan dengan cepat mendapatkan rasa dan memutuskan apakah Anda ingin menggali lebih dalam.
Dan kemudian ada banyak topik matematika lain yang hanya muncul dalam literatur penelitian, seperti koneksi dengan busa, teori graf, C * -gebra (biarkan saya mengarahkan Anda ke dugaan Kadison-Singer ), teori invarian, teori representasi, kuadratur, dan terus dan terus. Lihat juga pertanyaan terkait ini
sumber
The Nature of Computation oleh Cristopher Moore dan Stephan Mertens.
sumber