Sumber belajar mandiri teoretis ilmu komputer untuk programmer

14

Saya seorang insinyur perangkat lunak yang cukup mahir, tetapi saya tidak tahu banyak teori. Saya ingin belajar lebih banyak teori. Topik khusus yang saya minati adalah: kompleksitas komputasi, bahasa formal, dan teori jenis. Tetapi saya bingung bagaimana cara mulai belajar tentang bidang-bidang ini.

Sumber daya apa yang akan Anda rekomendasikan kepada seseorang yang ingin belajar lebih banyak teori melalui belajar mandiri? Apakah ada panduan belajar-sendiri ilmu komputer teoretis untuk insinyur perangkat lunak?

soft-question teaching books Henry H.
sumber
3
Itu tergantung apa yang ingin Anda pelajari. Arora-Barak memberikan pengantar menyeluruh untuk teori kompleksitas komputasi (dan tersedia secara online gratis). Jadi itu adalah tempat yang bagus untuk memulai.
Thomas mendukung Monica
4
Sudahkah Anda mengikuti kursus teori di perguruan tinggi / universitas seperti struktur data, algoritma, dll.? Jika Anda belum mengambil kursus teori sarjana yang biasanya diperlukan maka buku teks untuk kursus tersebut akan menjadi titik awal yang baik. Setelah itu Anda dapat melihat artikel wikipedia, daftar buku dan daftar video kami , kursus online di Coursera / Udacity / EdX / ... Coursera memiliki kursus teori yang cukup bagus.
Kaveh
Apa yang kamu pelajari di kampus?
Omar Shehab
Bahasa apa yang Anda programkan? Banyak CS teoritis dapat dipelajari bersama dengan sesuatu yang konkret. Sebagai contoh jika Anda ingin mempelajari lebih lanjut tentang bahasa formal, bahasa / ekspresi reguler (yaitu regexp) adalah tempat yang baik untuk memulai sebagaimana mempelajari tentang untuk kompiler. Untuk teori jenis, Anda mungkin ingin bermain dengan bahasa yang diketik secara statis seperti haskell, F # atau ML.
Baby Dragon
coba New Turing Omnibus oleh Dewdney sebagai bagian / survei / lintas intro luas / dapat diakses. lihat juga buku-buku sains pop yang menginspirasi TCS
vzn

Jawaban:

7

Ini adalah bidang yang luas dengan beberapa area yang sangat berbeda.

Saya akan mulai dengan beberapa ide paling mendasar tentang apa itu komputer: Hopcroft dan Ullman, "Pengantar Teori Automata, Bahasa dan Komputasi."

Alasan saya merekomendasikan hal itu khususnya, adalah penekanan mereka pada bukti. Mereka membimbing Anda melalui cara berpikir yang keras. Itulah perbedaan antara program penulisan dan menjadi ilmiah.

Kate F
sumber
1
Terima kasih! Saya tidak tahu apakah ini mengubah sesuatu, tetapi saya benar-benar memiliki latar belakang dalam matematika berbasis bukti (saya mungkin seharusnya menyebutkan itu dalam pertanyaan). Saya telah melakukan analisis nyata berbasis bukti, topologi set-point, dan aljabar abstrak.
Henry H.
Maka Anda akan dapat menyelesaikannya dengan sangat cepat :)
Kate F
nya suatu perbedaan tapi tidak dengan perbedaan. CS mencakup banyak prinsip lain
vzn
Saya tidak berpikir bahwa kebutuhan akan ketelitian benar-benar merupakan perbedaan antara pemrograman dan matematika. Memprogram dan membuktikan teorema adalah tugas yang sangat terkait (lih. Curry-Howard Isomorphism), dan hampir tidak ada tugas non-matematika yang membutuhkan lebih banyak ketelitian daripada pemrograman. Kompiler jauh lebih tidak memaafkan tentang kesalahan daripada manusia yang membaca bukti.
Jan Johannsen
2
@JanJohannsen Saya sangat tidak setuju - misalnya, lihat Perilaku Tidak Terdefinisi untuk C.
Kate F
9

Ada beberapa cara untuk belajar tentang teori tipe. Untuk seorang programmer yang bekerja, Jenis dan Bahasa Pemrograman oleh B. Pierce adalah awal yang baik. Yayasan Praktis untuk Bahasa Pemrograman oleh R. Harper mungkin juga baik. Jika Anda ingin sedikit latar belakang yang mudah dibaca tentang semantik operasional, saya sarankan G. Winskel, The Semantik Resmi Bahasa Pemrograman: Sebuah Pendahuluan . Dengan T. Nipkow, G. Klein, Semantik Beton, varian buku Winskel telah diformalkan untuk asisten bukti interaktif Isabelle / HOL. Saya curiga sangat sulit untuk memahami sebuah prover hanya dari buku ini (atau apa saja), Anda ingin seorang ahli terdekat untuk mengajukan pertanyaan. Jika Anda menginginkan pendekatan yang lebih matematis pada teori tipe, Anda dapat melihat JR Hindley, JP Seldin, Lambda-Calculus dan Combinators: An Introduction , atau H. Barendregt's, Lambda Calculi with Types . Meskipun saya tidak akan merekomendasikan mulai dari Barendregt.

Jika Anda menginginkan satu rekomendasi, saya akan mengatakan baca semua Pierce kecuali Bagian VI (Sistem Orde Tinggi), dan terapkan bahasa mainan yang dibahas buku ini. Anda akan berakhir dengan landasan kuat dalam teori tipe, dan mungkin programmer yang lebih baik juga.

Martin Berger
sumber
2

Saya merekomendasikan Computability, Complexity, dan Languages oleh Martin Davis, Ron Sigal dan Elaine Weyuker.

valepert
sumber
Itu buku yang bagus untuk TCS old-skool. Kecuali untuk bagian dari teori semantik teori, yang dapat dilewati.
Martin Berger
1

Saya penggemar berat Teori dan Algoritma. Saya pernah memiliki kesempatan untuk mengunjungi Ilmu Komputer Teoritis di Institut Teknologi India, Madras (IIT-M), India. Saya telah mengetahui banyak ahli teori di IIT-M. Ketika saya pergi ke sana, saya tidak tahu apa itu Teori, tetapi hari ini saya benar-benar menyukainya.

Terima kasih kepada @Kate F untuk penunjuknya, ya Hopcroft dan Ullman adalah tempat yang bagus untuk memulai.

Namun di sini adalah bagaimana saya memulai,

  1. Baca Pengantar Algoritma oleh Cormen. <\ Br> Ini adalah tempat yang bagus untuk memulai. Ketika Anda belajar, cobalah untuk memahami setiap bukti sejauh mungkin. Jika Anda memahami buktinya dengan baik, coba kode logika yang sama dalam bahasa apa pun yang Anda pilih. (Dibutuhkan sedikit lebih lama tetapi patut dicoba)

  2. Ikuti konferensi teratas dalam Teori seperti
    FOCS
    SODA
    STOC
    EC (Perdagangan Elektronik) - Teori Permainan Algoritma
    COLT (Konferensi tentang Teori Belajar) - Teori Belajar
    CRYPTO - Kriptografi
    SOCG (Simposium tentang Geometri Komputasi) - Geometri Komputasi
    CCC (Konferensi mengenai Computational Complexity) - Teori Kompleksitas

Bahkan jika Anda tidak mengerti banyak cobalah untuk membaca dan BERPIKIR sebanyak mungkin. Anda harus melakukan bukti sebanyak mungkin ..

  1. Ini adalah tempat yang menakjubkan untuk melihat jika Anda berpikir tentang kompleksitas komputasi pada khususnya ( Ini dari Stanford ).
  2. Ikuti Prof. Sanjeev Arora, Boaz Barak, Jelani Nelson, Madhu Sudan
  3. Berikut adalah seperangkat informasi yang disintesis di bidang Kompleksitas Komputasi
Jaugust
sumber