Salah satu buku Python kami yang paling menarik selama setahun terakhir adalah Masalah Ilmu Komputer Klasik dengan Python oleh David Kopec.
Bagi yang belum sempat membiasakan diri dengan buku ini, kami tawarkan reviewnya, yang ditulis sesuai edisi aslinya pada Oktober 2019. Anda juga dapat melihat diskusi kecil di Reddit . Selain itu, setiap orang dapat mengomentari pencetakan tambahan - untuk ini, surat suara ditempatkan di akhir artikel.
Saya sangat menyukai buku "Masalah Ilmu Komputer Klasik dengan Python" oleh David Kopec. Ini benar-benar membahas banyak masalah yang berbeda, informasi terperinci yang belum pernah saya temukan sebelumnya. Hanya beberapa contoh: jaringan saraf, masalah kepuasan kendala, algoritma genetika, algoritma minimum. Tidak seperti banyak buku lain tentang algoritme dan masalah pemrograman, buku ini menunjukkan program lengkap (tapi kecil) yang dapat Anda jelajahi sendiri dengan mudah.
Saya menikmati algoritma belajar. Saya mengerjakan buku " Programmer's Career ", mengambil beberapa kursus MOOC, khususnya, " Desain dan Analisis Algoritma " dari profesor Tim Rafgarden . Namun demikian, dalam buku Kopec juga terdapat algoritma seperti itu, yang penyebutannya belum pernah saya lihat sebelumnya.
BAB YANG PALING SAYA SUKA
Jaringan saraf . Bagian favorit saya dalam buku ini adalah tentang jaringan saraf. Penulis menjelaskan pembuatan jaringan saraf yang lengkap. Sementara itu, ia menjelaskan bagaimana semua bagiannya bekerja - secara umum dan khususnya. Menjelaskan bagaimana neuron dan lapisan diatur, bagaimana fungsi aktivasi bekerja, bagaimana propagasi mundur digunakan selama pembelajaran, bagaimana bobot dikoreksi.
Akhirnya, jaringan saraf digunakan sebagai contoh iris mata Fisher. Ini adalah kumpulan data klasik, dikumpulkan pada tahun 1930-an, dengan 150 spesimen bunga yang termasuk dalam berbagai jenis iris (masing-masing 50 spesimen). Setiap spesimen disertai dengan empat nilai numerik: panjang lobus perianth luar; lebar lobus perianth luar; panjang lobus perianth bagian dalam; lebar lobus perianth bagian dalam. Nilai dinormalisasi terlebih dahulu. Kemudian jaring tiga lapis dibuat. Ada empat neuron di lapisan masukan (satu untuk setiap kategori nilai masukan dari sampel), di lapisan tersembunyi ada enam neuron, dan di lapisan keluaran ada tiga neuron (satu untuk setiap jenis iris yang dipertimbangkan).
140 dari 150 sampel dipilih secara acak, yang kemudian digunakan untuk melatih jaringan. Pelatihan dijalankan lebih dari 140 sampel dalam 50 iterasi. Jaringan tersebut kemudian digunakan untuk memprediksi mana dari tiga spesies iris yang dimiliki 10 sampel yang tersisa. Dalam kebanyakan kasus, jaringan mengidentifikasi dengan benar setidaknya 8 dari 10 sampel, dan cukup sering - dan semuanya 10.
Saya sangat menyukai pengalaman ini: memprogram seluruh jaringan saraf dari awal tanpa menggunakan pustaka pembelajaran mesin. Saya bereksperimen dengan program ini untuk sementara waktu (semua kode untuk buku tersebut diposting di GitHub). Misalnya, saya mencetak cetakan semua bobot di semua neuron setelah jaringan sepenuhnya terlatih. Saya ingin melihat apakah akan ada kemiripan antara bobot antara lari yang berbeda. Bobot tersebut ternyata sangat berbeda dari lari ke lari, meskipun keberhasilan prediksi di semua kasus tetap sama. Mungkin ini adalah kebenaran yang mendasar, tapi saya sangat tertarik untuk melihatnya sendiri.
Pencarian permusuhan... Dalam bab ini, kita diperkenalkan dengan algoritma minimax. Dia menemukan langkah terbaik dalam permainan zero-sum dengan dua lawan. Idenya adalah untuk menganalisis gerakan potensial, berbicara atas nama satu atau lawan lainnya; setiap lawan bereaksi terhadap gerakan terakhir yang dilakukan hingga permainan selesai (atau kedalaman rekursi maksimum tercapai). Dalam contoh pertama dari buku tersebut, AI memainkan tic-tac-toe. Dalam hal ini, seluruh urutan gerakan dapat sepenuhnya dianalisis, karena ukuran lapangan hanya 3 kali 3 sel.
Seperti pada bab-bab lain, struktur umum dikembangkan terlebih dahulu di sini, yang kemudian dibahas dalam kaitannya dengan kasus-kasus kompleks. Setelah contoh dengan tic-tac-toe, game " Empat berturut-turut . " Dalam kasus ini, penilaian gerakan jauh lebih sulit daripada di "Tic-Tac-Toe", jadi di sini pencarian kedalaman dibatasi pada tiga gerakan. Saya sering membuka bab ini, karena saya belum pernah melihat deskripsi algoritma minimax sebelumnya.
Tugas Kepuasan... Kerangka umum juga dikembangkan di sini, yang kemudian digunakan untuk menyelesaikan beberapa masalah. Inti dari struktur ini adalah kemunduran rekursif. Masalah pertama yang dipecahkan dalam bab ini adalah tugas mewarnai peta Australia. Apakah mungkin untuk bertahan hanya dengan tiga warna dan mewarnai peta sehingga area yang berdekatan di kedua sisi perbatasan antar wilayah memiliki warna yang berbeda? (Jawaban: ya). Tugas kedua adalah menempatkan delapan ratu di papan catur, memastikan tidak ada ratu yang diserang dari yang lain. Tugas ketiga adalah menyusun daftar kata dalam grid menjadi kotak untuk pencarian kata. Akhirnya, struktur tersebut digunakan untuk memecahkan teka-teki aritmatika kripto klasik KIRIM + LEBIH BANYAK = UANG. Tujuannya adalah untuk mengetahui digit mana yang sesuai dengan setiap huruf sehingga persamaan aritmatika yang dihasilkan benar.
Saya menyukai bab ini karena berisi banyak contoh yang sangat beragam, dan juga karena saya sebelumnya tidak pernah menggunakan pendekatan ini untuk memecahkan masalah semacam itu (setidaknya secara sistematis).
Algoritme genetik . Sebelum saya membaca bab ini, saya hanya memiliki gambaran yang sangat umum tentang bagaimana algoritma genetika bekerja. Kode untuk bab ini menunjukkan kelas kromosom yang dipakai oleh gen yang dipilih secara acak. Sebuah kromosom dapat menilai kemampuan adaptasinya sendiri terhadap lingkungan dan melaksanakan perkawinan silang (kombinasi dirinya dengan kromosom lain dari jenis yang sama), dan juga bermutasi (membuat perubahan kecil yang sepenuhnya acak dengan sendirinya).
Algoritme dimulai dengan populasi acak. Dalam setiap generasi populasi ini, algoritme memeriksa (menggunakan fungsi kebugaran) apakah ada solusi yang cukup baik (kesesuaian di atas nilai ambang yang diberikan). Jika tidak ada solusi seperti itu, maka generasi baru akan tercipta melalui operasi berulang dari persilangan pasangan individu (semakin tinggi kebugaran masing-masing individu, semakin besar kemungkinan individu tersebut akan beraksi). Selanjutnya, beberapa individu dipilih untuk dimutasi. Sekarang individu-individu baru ini melahirkan populasi baru dan, sekali lagi, fungsi kebugaran mereka diuji. Siklus ini berulang selama beberapa generasi.
Tugas berikut dianggap sebagai contoh: memaksimalkan ekspresi matematika, teka-teki "KIRIM + LEBIH BANYAK = UANG" yang disebutkan di atas, dan mengurutkan item dalam daftar untuk meminimalkan ukuran daftar saat dikompresi. Manfaat bab ini, seperti banyak bab lainnya, adalah bahwa semua konsep ditampilkan dalam konteks solusi yang kompak namun lengkap.
Cari... Algoritme dalam bab ini bukanlah hal baru bagi saya (kecuali A *), tetapi bab ini masih menarik berkat contoh yang diberikan di dalamnya. Penulis mendemonstrasikan prinsip Breadth First Search dan Depth First Search menggunakan contoh keluar dari labirin. Labirin adalah sel kotak berukuran 9x9 biasa, di mana rintangan ditempatkan secara acak. Ditampilkan di layar hanya menggunakan karakter ASCII. Dengan bantuan algoritma, jalur melalui grid ditemukan, berjalan secara diagonal, sambil menghindari rintangan. Jalan yang ditemukan juga ditarik melalui labirin.
Anda dapat dengan mudah mengubah program ini untuk menguji bagaimana algoritme bekerja dalam skenario yang berbeda. Setelah mengenal Breadth First Search, penulis membahas tentang A *. Perbedaannya adalah bahwa jalur digambar menggunakan heuristik (jarak Euclidean), yang digunakan sebagai pedoman dan memberi tahu Anda jalur mana yang akan digambar terlebih dahulu. Contoh terakhir dalam bab ini menggunakan fungsi pencarian untuk membantu Anda membawa tiga misionaris dan tiga ogre dengan sampan menyeberangi sungai. Batasannya adalah bahwa jumlah kanibal tidak boleh melebihi jumlah misionaris baik di pantai maupun di kapal, jika tidak, kanibal akan memakan misionaris. Saya rasa ini adalah aplikasi algoritma pencarian yang sangat pintar dan menarik.
BAB LAIN
Bab lain berisi algoritme yang sudah saya kenal.
Tugas sederhana (bab pertama). Bab pertama berisi banyak contoh kecil. Ini pertama kali menjelaskan berbagai cara menghitung bilangan Fibonacci (khususnya, rekursif, dengan memoization, iterative, dan dengan generator Python). Bagian selanjutnya membahas manipulasi bit untuk kompresi dan cipher XOR. Terakhir, kita membutuhkan rekursi dalam bab ini untuk menyelesaikan masalah Menara Hanoi.
Masalah grafik . Bab 4 membahas algoritma grafik untuk menemukan jalur terpendek dan pohon rentang minimum, menggunakan peta Amerika Serikat sebagai contoh. Algoritma Dijkstra juga dipertimbangkan.
Pengelompokan K-Means... Bab ini menunjukkan cara mengelompokkan titik data ke dalam sejumlah cluster yang telah ditentukan berdasarkan jarak relatif dari setiap titik ke pusat cluster. Bagi saya, contoh-contoh dalam bab ini tidak semenarik contoh-contoh dari bab-bab lain.
Tugas lainnya . Bab terakhir membahas masalah ransel, masalah penjual keliling, dan mnemonik nomor telepon.
APA YANG AKAN ANDA LAMPIRKAN
Semua program menggunakan petunjuk tipe Python. Saya memiliki sikap ganda terhadap tip semacam itu. Di satu sisi, tipe berkontribusi pada pemahaman yang lebih baik tentang program. Tetapi di sisi lain, saya tidak terbiasa melihatnya dengan Python, dan terkadang saya harus mencari tahu petunjuk ini terlebih dahulu sebelum saya dapat memahami logika program.
Jika Anda ingin mengeluh tentang suatu bagian, maka bagian yang berbicara tentang pemrograman dinamis. Menurut saya kurang lengkap. Pemrograman dinamis adalah hal yang rumit, dan jika Anda akan menggunakannya dalam solusi dunia nyata, Anda memerlukan contoh tambahan tentang topik ini.
KESIMPULAN
Alasan utama mengapa saya sangat menyukai buku ini adalah luasnya algoritme yang dipertimbangkan, lengkap (pada saat yang sama, solusi ringkas) yang mudah diselidiki sendiri, serta contoh menarik yang dipilih untuk mengilustrasikan algoritme.