Seberapa pentingkah mengetahui cara memprogram untuk TCS?

Berasal dari latar belakang yang lebih matematis, saya tidak pernah benar-benar belajar cara membuat kode. Saya memulai PhD di TCS dan banyak orang terkejut dengan betapa sedikit yang saya ketahui tentang pemrograman (dan tentang komputer pada umumnya). Saya dapat menulis algoritma dalam pseudo-code, tetapi saya tidak benar-benar tahu bahasa pemrograman.

Saya dapat membayangkan bahwa suatu hari nanti saya mungkin harus mengimplementasikan beberapa algoritma untuk pekerjaan saya, tetapi kemudian bisakah saya menunggu saat ini? Atau ada sesuatu yang lebih?

Seberapa pentingkah mengetahui cara membuat kode dalam TCS (dalam bidang di mana pemrograman tidak terlibat langsung): adakah alasan yang dapat membawa ahli teori CC (misalnya) untuk mengetahui cara membuat kode? Apakah layak menghabiskan banyak waktu mempelajari cara membuat kode? Dan jika ada, apakah ada kategori (fungsional, imperatif, berorientasi objek ..) bahasa pemrograman yang akan lebih cocok?

Ilmu komputer teoretis adalah bidang yang luas dan pentingnya pemrograman tergantung pada apa yang Anda lakukan di TCS. Saya akan menyebutkan dua cara di mana pemrograman dapat membantu Anda, tanpa menyiratkan bahwa ini adalah satu-satunya cara.

Pertama, jika Anda merancang algoritme untuk masalah yang praktis penting, menerapkan algoritme Anda dan membuat kode tersedia untuk orang lain bisa menjadi nilai tambah besar. Misalnya, masalah cembung lambung muncul di banyak bidang, dan orang-orang menggunakan paket perangkat lunak seperti cdd oleh Komei Fukuda dan lrs oleh David Avis untuk menyelesaikan masalah ini. Jika mereka menerbitkan algoritme mereka hanya di kertas, mungkin lebih sedikit orang yang akan menggunakan algoritme mereka. Lebih banyak pengguna berarti lebih banyak umpan balik dan mungkin juga lebih banyak peluang untuk berkolaborasi, yang sangat berharga.

Kedua, bahkan jika Anda tidak bekerja dalam algoritma, menulis kode satu kali membantu Anda untuk menguji dugaan sederhana ketika dugaan tersebut cocok untuk perhitungan numerik. Sebagai contoh, jika Anda bertanya-tanya apakah produk dari tiga matriks pasti positif selalu memiliki jejak positif, mudah untuk menulis kode untuk mengujinya untuk beberapa pilihan acak 2 × 2 atau 3 × 3 matriks pasti positif dan menemukan sampel berlawanan. Meskipun Anda tidak mengiklankan bahwa Anda menulis program apa pun untuk menguji dugaan itu, pemrograman dapat menghemat waktu yang seharusnya dihabiskan dengan sia-sia mencoba membuktikan pernyataan yang salah.

Bahasa pemrograman untuk dipilih tergantung pada apa yang ingin Anda lakukan dengan pemrograman, dan itu bisa menjadi topik untuk seluruh buku menurut saya. Tetapi jika Anda merancang algoritma dan ingin mengimplementasikan algoritma Anda sehingga orang lain dapat menggunakan implementasinya, maka salah satu faktor penting adalah ketersediaan. Meskipun Anda dapat berharap bahwa sebagian besar pengguna potensial kode Anda memiliki akses ke kompiler C, Anda tidak dapat berharap bahwa orang yang sama memiliki akses ke kompiler Haskell. Untuk program satu kali, pilihannya lebih didasarkan pada perpustakaan yang tersedia, dan termasuk lingkungan seperti Matlab.

Omong-omong, pemrograman juga bisa menyenangkan.

Saya merasa harus mengutip Doron Zeilberger tentang ini:

Opini 37 : Pemrograman Lebih Menyenangkan daripada Membuktikan, dan, Lebih Penting Itu Memberi Sebanyak, Jika Tidak Lebih, Wawasan dan Pemahaman.

Baca pendapat, itu penuh permata (tapi dia cenderung provokatif dengan sengaja). Misalnya, "Cara terbaik untuk memahami sesuatu adalah dengan mengajarkannya. Tetapi bahkan lebih baik mengajarkannya kepada manusia adalah dengan mengajarkannya ke komputer".

Pengalaman pribadi saya adalah bahwa bahkan ketika melakukan pekerjaan teoritis murni Anda akan memerlukan beberapa alat komputasi. Saya menghindari banyak manipulasi aljabar rutin yang membosankan dengan Mathematica. Saya menguji dugaan setengah matang saya dengan memaksa contoh kecil pada Matlab atau Python. Saya telah menulis bersama satu makalah yang merupakan kombinasi murni, dan itulah pekerjaan yang paling diuntungkan dari menjalankan eksperimen komputer yang luas untuk memahami apa yang terjadi. Euler membuat tabel besar perhitungan yang membosankan untuk mendapatkan wawasan tentang masalah. Kami berutang kepadanya untuk menggunakan alat kami untuk mengotomatisasi proses ini ketika kami melakukan matematika.

Selain itu, jika Anda akan bekerja pada algoritma dan struktur data, pemrograman akan memberikan perspektif yang tak tergantikan pada masalah efisiensi dan kegunaan. Pendapat saya di sini agak berbeda dengan yang lain. Saya pikir belajar bahasa fungsional sehingga Anda bisa menulis bukti bahwa mengetik dengan benar adalah buang-buang waktu (saya pikir itu poin bagus bahwa orang-orang yang memiliki pengalaman dengan bahasa yang sangat diketik mungkin cenderung untuk menulis bukti terstruktur yang lebih hati-hati; saya hanya tidak pikir itu bernilai waktu Anda untuk pergi melalui latihan itu). Pemrograman fungsional mengaburkan masalah desain algoritme dan waktu berjalan serta menekankan masalah logika dan semantik (dan, tentu saja, mempelajari pemrograman fungsional mungkin suatu keharusan dan akan datang secara alami jika Anda tertarik pada semantik logika / PL). Demikian pula, Saya pikir masuk ke rincian OO Java dan C ++ juga bukan cara yang optimal untuk menghabiskan waktu Anda, karena tujuan OO adalah untuk menulis kode modular yang dapat digunakan kembali. Ini cara untuk pergi jika Anda akan menghasilkan kode untuk digunakan orang lain. Tetapi jika Anda ingin mendapatkan wawasan tentang efisiensi dan waktu berjalan, jika Anda peduli dengan algoritma dan struktur data yang sangat efisien, saya sarankan untuk melihat ke C. Ini memungkinkan Anda tetap dekat dengan mesin sambil tetap memberikan tingkat abstraksi yang wajar . Dengan cara ini Anda merasakan apa yang cepat dan lambat, apa itu struktur data yang masuk akal, dll. Tetapi jika Anda ingin mendapatkan wawasan tentang efisiensi dan waktu berjalan, jika Anda peduli dengan algoritma dan struktur data yang sangat efisien, saya sarankan untuk melihat ke C. Ini memungkinkan Anda tetap dekat dengan mesin sambil tetap memberikan tingkat abstraksi yang wajar . Dengan cara ini Anda merasakan apa yang cepat dan lambat, apa itu struktur data yang masuk akal, dll. Tetapi jika Anda ingin mendapatkan wawasan tentang efisiensi dan waktu berjalan, jika Anda peduli dengan algoritma dan struktur data yang sangat efisien, saya sarankan untuk melihat ke C. Ini memungkinkan Anda tetap dekat dengan mesin sambil tetap memberikan tingkat abstraksi yang wajar . Dengan cara ini Anda merasakan apa yang cepat dan lambat, apa itu struktur data yang masuk akal, dll.

Anda bisa menjadi ilmuwan komputer teoretis yang cukup sukses tanpa pemrograman. Untuk beberapa orang, pemrograman cukup sulit, dan jika Anda salah satunya, Anda tidak boleh putus asa dan beralih bidang.

Namun, bagi sebagian besar mahasiswa pascasarjana matematika dan ilmu komputer, belajar ke program tidak terlalu sulit, dan merupakan keterampilan yang sangat berguna. Anda harus belajar bahasa pemrograman, dan jika Anda menikmatinya, Anda harus mencoba untuk mendapatkan latihan yang cukup untuk menjadi mahir dalam hal itu. Kemudian, ketika titik datang (dan itu akan) bahwa itu akan berguna dalam penelitian Anda untuk menulis sebuah program, Anda akan dapat melakukannya.

Jika Anda tidak belajar memprogram sekarang, sangat mungkin bahwa ketika Anda akhirnya perlu menulis sebuah program, Anda tidak akan punya waktu untuk belajar, sehingga Anda mungkin tidak benar-benar menulisnya, dan akhirnya menjadi kurang efektif dalam penelitian. Walaupun mendapatkan mahasiswa pascasarjana atau sarjana untuk melakukan ini untuk Anda tidak terlalu sulit, ada banyak waktu ketika lebih mudah dan lebih sedikit waktu untuk melakukannya sendiri daripada menjelaskan masalahnya kepada mereka.

Bahasa apa yang harus Anda pelajari? Saya akan merekomendasikan bahasa berorientasi objek, karena ini adalah yang saat ini paling banyak digunakan, dan saya menduga ini akan lebih benar di masa depan. Mungkin Python atau Java — keduanya bahasa berorientasi objek, dan sementara mereka lebih jarang digunakan dalam praktik daripada C ++, kesan saya adalah keduanya jauh, lebih mudah dipelajari. (Peringatan: Saya tidak tahu C ++, meskipun pernah bekerja di Bell Labs, jadi mungkin saya salah tentang ini.)

Ada jawaban lain yang belum pernah dibicarakan oleh siapa pun. Pemrograman benar-benar dapat mengarah pada teori yang menarik. Banyak perkembangan baru-baru ini dalam hashing (terutama tabulasi hashing) dimotivasi bukan oleh masalah teoretis semata, tetapi oleh kenyataan bahwa algoritma yang secara teoritis optimal tidak begitu bagus dalam praktiknya. Ini tentu saja adalah sesuatu yang tidak Anda ketahui kecuali Anda dapat menulis kode.

Bahkan dalam bidang algoritma waktu eksponensial yang tepat, suatu motivasi menghasilkan algoritma yang benar-benar dapat bekerja. Pemecah SAT adalah contoh kanonik ini.

Singkatnya, kemampuan kode memungkinkan Anda untuk menyadari kekurangan dan kelemahan dalam apa yang mungkin terlihat seperti hasil teoritis yang optimal, dan yang pada gilirannya membuka arah penelitian teoritis baru.

Tiga poin:

1) Ada pendekatan untuk matematika yang disebut Matematika Eksperimental (lihat juga wikipedia: // Bukti berbantuan komputer ) di mana Anda menggunakan program komputer untuk menyelidiki tentang pola dan struktur objek untuk menghasilkan bukti analitik tentang objek-objek ini. Untuk pendekatan ini, Anda sebaiknya tahu cara memprogram. Anda dapat yakin bahwa Anda akan membutuhkan pendekatan ini untuk membuktikan pernyataan yang sangat teoretis. Saya percaya bahwa keangkuhan terhadap pemrograman seringkali ternyata tidak terlalu membantu dalam penelitian TCS.

2) Ketika Anda belajar cara memprogram, sebagai produk sampingan Anda belajar keterampilan yang berguna dalam TCS. Salah satu contoh di atas semua: Saya menemukan bahwa orang-orang dengan latar belakang pengkodean cenderung mengetik-memeriksa bukti mereka lebih banyak. Bahkan lebih baik, mereka cenderung sangat sering mendefinisikan jenis objek yang mereka pertimbangkan (mis .: "mari kita pertimbangkan operator dan ). Ini bagus untuk pembaca naskah. Kompiler (dan penerjemah) mengubah kita menjadi ilmuwan yang baik :) Untuk keterampilan semacam ini, saya merasa menyarankan beberapa bahasa fungsional yang sangat diketik.B ∈ L ( Y , C $A \in L(X,Y)$$B \in L(Y,C)$

3) Ketika Anda mengatakan "ke program" apakah Anda juga bermaksud "untuk program linear " atau "ke program semidefinite "? :)

Terima kasih Gopi untuk pertanyaan ini. Saya ingin memperluas banyak jawaban menarik di dimensi lain yang belum disebutkan.

Penelitian bukan satu-satunya hal yang kami lakukan di universitas: jika Anda ingin tetap di dunia akademis, pada akhirnya Anda harus mengajar. Jika Anda beruntung, Anda harus mengajarkan kursus yang cukup jauh dari bidang spesialisasi Anda. Sangat mungkin Anda akan diberikan kursus dengan komponen pemrograman yang substansial. Di sinilah bahkan kemampuan moderat untuk memprogram membantu secara substansial: Anda akan menjadi guru yang jauh lebih baik jika Anda tahu cara memprogram. Pertama dan terutama, Anda akan lebih nyaman dengan materi, Anda akan dapat menjawab pertanyaan siswa dengan lebih baik, dan Anda memahami kesulitan yang siswa miliki dengan belajar ke program, karena Anda sendiri sudah mengalami proses belajar ini. Selain itu, Anda dapat menghasilkan bahan pengajaran yang lebih baik. Misalnya Anda dapat menguji latihan pemrograman sendiri sebelum memberikannya kepada siswa,

Ada dimensi pragmatis tambahan: mengajar melibatkan berbagai tugas berulang yang sering dapat dilakukan oleh programmer yang terampil, seperti dengan cepat membuat situs web yang dapat digunakan siswa untuk mengirimkan tugas kuliah, dan membuatnya dinilai secara otomatis (sesuai dengan jumlah tes otomatis yang diloloskan oleh kode).

Pemrograman adalah cara yang baik untuk meningkatkan pemahaman Anda tentang berbagai konsep, tetapi juga merupakan waktu yang berbahaya.

Argumen tipikal terhadap pemrograman adalah membuat Anda menghabiskan waktu dengan detail yang tidak penting; argumen umum untuk pemrograman adalah membuat Anda menyadari bahwa detail yang Anda pikir tidak penting sebenarnya penting. Menjadi ahli dalam pemrograman terutama berarti mampu menangani bagian-bagian yang tidak penting dengan cepat. Menjadi baik membutuhkan waktu yang lama .

Adapun bahasa pemrograman untuk belajar: "semuanya" adalah jawaban (lidah-di-pipi) saya.

Saya terlambat ke pesta, dan ini semua jawaban yang bagus, tapi saya punya alasan lain:

Visualisasi.

Ya, seringkali Anda akan bekerja dengan hal-hal yang tidak dapat divisualisasikan, tetapi sering kali Anda akan bekerja dengan hal-hal yang bisa. Mengetahui cara memprogram sangat diperlukan untuk tugas ini, dan visualisasi dapat memberi Anda banyak wawasan tentang suatu masalah.

Poin singkatnya: mengetahui cara memprogram memberi saya alat tambahan dalam penelitian teori. Ketika saya memiliki algoritme yang saya pikir akan berfungsi, jika cukup mudah, saya mungkin kode itu dan memeriksa apakah itu benar-benar. Jika ide saya tidak (bahkan) bekerja dalam praktek, itu tidak mungkin bekerja secara teori, dan pendekatan ini sering menyelamatkan saya dari tenggelamnya waktu yang sangat besar untuk mencoba membuktikan sesuatu yang salah.

Tidak ada seorang pun di sini yang membahas masalah praktis mengapa seseorang yang mempelajari TCS harus belajar pemrograman.

Jika Anda berencana untuk mengambil gelar PhD di TCS di departemen Ilmu Komputer, ada kemungkinan Anda perlu mengambil beberapa mata kuliah non-teori, dan itu hampir pasti akan sangat intensif pemrograman. Bergantung pada program yang Anda ikuti, Anda mungkin perlu pengetahuan tentang mata pelajaran non-teori untuk lulus ujian kualifikasi Anda.

Ketika Anda menyelesaikan PhD, sebagian besar peluang kerja untuk TCS ada di dunia akademis. Jika Anda bekerja di dunia akademis, Anda akan diharapkan untuk mengajar, dan Anda mungkin diharapkan untuk mengajar kelas CS tingkat sarjana tingkat dasar yang akan lebih banyak pemrograman daripada teori. Bahkan jika Anda mengajar kelas teori untuk undergrads, seperti Algoritma, Anda dapat berharap bahwa siswa Anda akan tahu lebih banyak tentang pemrograman daripada teori, dan tanpa mengetahui apa yang diketahui siswa Anda, akan sulit bagi Anda untuk menjembatani kesenjangan dalam pemahaman mereka. . Saya ngeri membayangkan undergrad CS yang diajarkan oleh seseorang yang tidak tahu pemrograman!

Jika Anda tidak peduli dengan masalah praktis ini, maka Anda mungkin bisa melakukan riset tanpa benar-benar tahu apa-apa tentang pemrograman. Tentu saja Anda memiliki banyak perusahaan dalam komunitas TCS, tetapi jarak tempuh akan bervariasi tergantung pada area teori mana Anda bekerja. Misalnya, jika Anda melakukan teori kompleksitas komputasi murni, membuktikan batas bawah pada kelas yang tidak ada yang memiliki pernah mendengar, maka kemungkinan pemrograman tidak akan berguna bagi Anda. Tetapi jika Anda melakukan sesuatu yang lebih algoritmik, maka saya merasa bisa menulis kode kerja bersih yang baik akan memperkuat intuisi Anda jika tidak ada yang lain.

Saya merekomendasikan belajar C (bukan C ++). Ambil salinan K&R dan bacalah dari depan ke belakang. C tidak memiliki banyak fitur mewah bahasa modern, tetapi memang memiliki sintaksis dan semantik yang sederhana namun elegan, yang harus Anda pelajari secara keseluruhan. Namun, bahkan ketika Anda memahami bahasa secara keseluruhan, masih perlu latihan untuk menguasai penulisan kode bebas bug yang bagus dan elegan di C. Namun demikian, jika Anda dapat menguasai pengkodean dalam C, Anda akan dapat menguasai bahasa pemrograman yang Anda temui. Selain itu, disiplin itu akan membantu Anda berpikir bagaimana perangkat keras berpikir, yang akan bermanfaat saat merancang algoritma.

Gagasan seperti pointer sangat penting bagi siapa saja yang mendesain algoritma, tetapi sayangnya, bahasa seperti Java dan Python mengaburkannya dari Anda, jadi itu sebabnya saya tidak merekomendasikan mereka sebagai bahasa pertama bagi seseorang dengan latar belakang matematika. OOP lebih penting bagi orang yang harus memelihara proyek perangkat lunak besar, bukan seseorang yang merancang algoritma.

Saya menyarankan agar Anda tidak menunggu permulaan program studi Anda karena ilmu komputer pada level apa pun melibatkan penerapan algoritma melalui komputer untuk mencapai / memverifikasi / memecahkan teori yang harus Anda hadapi di seluruh program studi Anda, TERUTAMA pada level Anda.

Saya harus memprogram di kelas 10 (sekolah menengah) pertama, dan saya sudah tahu cara menggunakan baris perintah dan ini sangat membantu (ini untuk menunjukkan kepada Anda bagaimana keterampilan pemrograman "dasar" dipertimbangkan dalam CS).

Keheranan rekan-rekan Anda cukup beralasan, karena kodesemu dan algoritma adalah salah satu hal pertama yang harus dipelajari untuk diprogram.

Namun, Anda tidak akan benar-benar tersesat dalam kursus Anda yang akan datang karena Anda dapat menggunakan keterampilan matematika Anda yang lebih luas (sendiri) atas keuntungan Anda untuk melewatkan pemrograman berorientasi objek untuk mengejar lebih cepat belajar bahasa pemrograman fungsional.

• Pemrograman fungsional SANGAT berorientasi pada matematika, dianggap lebih sulit untuk dipelajari karena latar belakang matematika yang dibutuhkan, dianggap sangat kuat (dalam "sederhana", cara matematika untuk menyelesaikan masalah sulit melalui cara yang elegan dan "bersih").
• Orientasi objek baik ketika Anda tidak ingin memahami algoritma dan prinsip implementasi yang mendasarinya dan hanya ingin "menggunakan kembali" objek yang sudah ada.

Saya pikir Anda bisa menangani Haskell (biasanya bukan bahasa pertama) karena itu murni matematika, fungsional dan pada dasarnya dapat melakukan apa pun yang Anda inginkan. Mempelajari Haskell akan menempatkan Anda pada level di mana Anda tidak perlu belajar lebih banyak untuk mengikutinya, dan bahkan akan menempatkan Anda dalam situasi kontrol dan kekuasaan atas program studi Anda. Jika Anda menyukai statistik, belajar R adalah nilai tambah, tetapi tidak sedekat Haskell. Saya telah melihat laporan dari matematikawan yang menyatakan betapa terkejutnya mereka tentang kedekatannya dengan matematika dan bagaimana hal itu merangkul cara berpikir mereka.

Juga, tantangan yang perlu ditangani (untuk membuat tangan Anda terbiasa dengan lingkungan pemrograman yang cepat) adalah menginstal dan menggunakan Linux (Ubuntu Linux akan melakukannya). Percayalah, Anda akan belajar banyak dengan bermain dengannya ...

Nasihat ini adalah cara terbaik yang saya tahu untuk mengejar ketinggalan dengan cepat dan tentunya untuk seorang ahli matematika dalam ilmu komputer. Selain itu, komunitas open source sangat ramah dan membantu dan jika Anda buntu, IRC menjadi cara paling langsung untuk berbicara tentang subjek apa pun melalui saluran khusus (terhubung di FreeNode). Ingat: bertanya adalah satu-satunya cara untuk menyelesaikan pertanyaan, baik itu untuk diri sendiri, forum, mesin pencari, atau di ruang obrolan.

Contoh implementasi C ++ dari sistem bukti interaktif adalah makalah berikut ini: Bukti Interaktif Waktu-Optimal Untuk Evaluasi Sirkuit, oleh Justin Thaler. Ini tersedia di http://people.seas.harvard.edu/~jthaler/ . Tampaknya menjadi langkah menuju tujuan mengembangkan implementasi praktis sistem bukti interaktif tujuan umum.

Makalah serupa dan kode sumber terkait muncul di situs web yang disebutkan di atas.