Banyak tugas di bidang Ilmu Komputer, yang sekilas tampak baru atau unik, sebenarnya berakar pada algoritma klasik, metode pengkodean, dan prinsip pengembangan. Dan teknik yang sudah ada masih merupakan cara terbaik untuk menyelesaikan masalah seperti itu!
Buku ini akan memberi Anda kesempatan untuk mempelajari bahasa Python lebih dalam, menguji diri sendiri pada tugas, latihan, dan algoritme yang telah teruji waktu. Anda harus menyelesaikan banyak tugas pemrograman: dari yang paling sederhana (misalnya, menemukan item daftar menggunakan penyortiran biner) ke yang kompleks (mengelompokkan data menggunakan metode k-means). Bekerja melalui contoh-contoh yang ditujukan untuk pencarian, pengelompokan, grafik, dll., Anda akan ingat apa yang telah Anda lupakan dan kuasai teknik klasik untuk memecahkan masalah sehari-hari.
Untuk siapa buku ini?
Buku ini ditujukan untuk programmer tingkat menengah dan tinggi. Para profesional berpengalaman yang ingin memperdalam pengetahuan mereka tentang Python akan menemukan tugas-tugas di sini yang sudah biasa sejak mereka mengajar ilmu komputer atau pemrograman. Pemrogram tingkat menengah akan terbiasa dengan tugas-tugas klasik ini dalam bahasa pilihan mereka - Python. Bagi pengembang yang sedang mempersiapkan wawancara pemrograman, publikasi ini kemungkinan akan menjadi bahan persiapan yang berharga.
Selain programmer profesional, buku ini dapat dianggap berguna oleh siswa yang belajar untuk program sarjana dalam ilmu komputer dan tertarik pada Python. Itu tidak mengklaim sebagai pengantar yang ketat untuk struktur data dan algoritma. Ini bukan tutorial tentang struktur data dan algoritma. Anda tidak akan menemukan bukti teorema atau penggunaan banyak notasi besar di halamannya. Sebaliknya, buku ini diposisikan sebagai panduan praktis yang dapat diakses untuk metode untuk memecahkan masalah yang seharusnya menjadi produk akhir dari mempelajari struktur data, algoritma dan kelas kecerdasan buatan.
Saya tekankan lagi: diasumsikan bahwa pembaca sudah familiar dengan sintaksis dan semantik Python. Pembaca dengan pengalaman nol pemrograman kemungkinan tidak akan mendapat manfaat dari buku ini, dan seorang programmer dengan nol pengalaman dalam Python mungkin akan sulit. Dengan kata lain, "Tugas Ilmu Komputer Klasik dengan Python" adalah buku untuk programmer Python dan mahasiswa ilmu komputer.
Kutipan. 1.5. Menara Hanoi
Ada tiga kolom vertikal yang tinggi (selanjutnya - menara). Kami akan menunjuk mereka A, B dan C. Disk dengan lubang di tengah digantung di menara A. Disk terluas - kami akan menyebutnya disk 1 - terletak di bawah. Disk yang tersisa yang terletak di atasnya ditandai dengan peningkatan jumlah dan secara bertahap meruncing. Misalnya, jika kami memiliki tiga disk, yang terluas di antaranya, yang di bawah, akan memiliki nomor 1. Disk terluas berikutnya, di nomor 2, akan berada di atas disk 1. Akhirnya, disk yang paling sempit, di nomor 3 akan berbaring di disk 2.
Tujuan kami adalah memindahkan semua drive dari menara A ke menara C, dengan mempertimbangkan batasan berikut.
- Disk hanya dapat dipindahkan satu per satu.
- Satu-satunya drive yang tersedia untuk bergerak adalah yang terletak di bagian atas menara apa pun.
- Drive yang lebih luas tidak pernah dapat ditempatkan di atas yang lebih sempit.
Secara skematis, tugas ditunjukkan pada Gambar. 1.7.
1.5.1. Tower Modeling
Tumpukan adalah struktur data yang dimodelkan pada prinsip last-in-first-out (LIFO). Hal terakhir yang ada di stack menjadi yang pertama diambil dari sana. Dua operasi utama stack adalah push (put) dan pop (extract). Operasi dorong mendorong item baru ke tumpukan, dan pop menghapusnya dari tumpukan dan mengembalikan item terakhir yang dimasukkan. Anda dapat dengan mudah memodelkan tumpukan dengan Python menggunakan daftar sebagai penyimpanan cadangan (Listing 1.20).
Listing 1.20. hanoi.py
from typing import TypeVar, Generic, List T = TypeVar('T') class Stack(Generic[T]): def __init__(self) -> None: self._container: List[T] = [] def push(self, item: T) -> None: self._container.append(item) def pop(self) -> T: return self._container.pop() def __repr__(self) -> str: return repr(self._container)
Kelas Stack yang disajikan mengimplementasikan metode __repr __ (), yang membuatnya mudah untuk memeriksa isi menara. __repr __ () adalah apa yang akan dihasilkan ketika fungsi print () diterapkan pada stack.
Seperti yang dinyatakan dalam pengantar, jenis anotasi digunakan dalam buku. Mengimpor Generik dari modul input memungkinkan Stack menjadi kelas parametrik untuk jenis tertentu dalam anotasi jenis. Tipe T yang berubah-ubah didefinisikan dalam T = TypeVar ('T'). T bisa jenis apa saja. Ketika anotasi tipe selanjutnya digunakan untuk Stack dalam menyelesaikan masalah menara Hanoi, prompt akan menjadi Stack [int], yaitu, tipe int akan digunakan sebagai ganti T. Dengan kata lain, di sini tumpukan adalah tumpukan bilangan bulat. Jika Anda kesulitan mengetik anotasi, lihat Lampiran B.
Tumpukan sempurna untuk tantangan menara Hanoi. Untuk memindahkan disk ke menara, kita bisa menggunakan operasi push. Untuk memindahkan disk dari satu menara ke menara lainnya, kita dapat mendorongnya dari yang pertama (pop) dan meletakkannya di yang kedua (mendorong).
Tentukan menara sebagai objek Stack dan isi yang pertama dengan disk (Listing 1.21).
Listing 1.21. hanoi.py (lanjutan)
num_discs: int = 3 tower_a: Stack[int] = Stack() tower_b: Stack[int] = Stack() tower_c: Stack[int] = Stack() for i in range(1, num_discs + 1): tower_a.push(i)
1.5.2. Memecahkan Masalah Menara Hanoi
Bagaimana saya bisa menyelesaikan masalah menara Hanoi? Misalkan kita mencoba memindahkan hanya satu drive. Maka kita akan tahu bagaimana melakukan ini, bukan? Bahkan, memindahkan satu disk adalah kasus dasar untuk solusi rekursif untuk masalah ini. Memindahkan banyak drive adalah kasus rekursif. Poin kuncinya adalah bahwa kita, pada kenyataannya, memiliki dua skenario yang perlu dikodekan: memindahkan satu disk (base case) dan memindahkan beberapa disk (recursive case).
Untuk memahami kasus rekursif, pertimbangkan contoh khusus. Misalkan kita memiliki tiga disk - atas, tengah dan bawah, terletak di menara A, dan kami ingin memindahkannya ke menara C. (Selanjutnya, ini akan membantu untuk secara skematis menggambarkan masalahnya.) Pertama kita bisa memindahkan disk atas ke menara C. Lalu - pindahkan cakram tengah ke menara B, dan kemudian cakram atas dari menara C ke menara B. Sekarang kita memiliki cakram bawah yang masih terletak di menara A dan dua cakram atas di menara B. Pada dasarnya, kita sudah berhasil memindahkan dua berkendara dari satu menara (A) ke yang lain (B). Memindahkan disk yang lebih rendah dari A ke C adalah kasus dasar (memindahkan satu disk). Sekarang kita dapat memindahkan dua disk bagian atas dari B ke C menggunakan prosedur yang sama seperti dari A ke B. Kita memindahkan disk bagian atas ke A, disk tengah ke C, dan akhirnya disk bagian atas dari A ke C.
Di kelas ilmu komputer, model kecil menara ini sering ditemukan, dibuat dari pin dan disk plastik. Anda dapat membuat model sendiri dengan tiga pensil dan tiga lembar kertas. Mungkin ini akan membantu Anda memvisualisasikan solusinya.
Dalam contoh dengan tiga disk, ada kasus dasar sederhana memindahkan satu disk dan kasus rekursif memindahkan disk yang tersisa (dalam hal ini dua) menggunakan menara ketiga sementara. Kami dapat memecahkan kasus rekursif ke dalam langkah-langkah berikut.
- Pindahkan drive n - 1 teratas dari menara A ke menara B (sementara), menggunakan C sebagai menara perantara.
- Pindahkan drive yang lebih rendah dari A ke C.
- Pindahkan disk n-1 dari menara B ke menara C, menara A adalah perantara.
Anehnya, algoritma rekursif ini bekerja tidak hanya untuk tiga, tetapi untuk sejumlah disk. Encode sebagai fungsi hanoi (), yang bertanggung jawab untuk memindahkan disk dari satu menara ke menara lainnya menggunakan menara sementara ketiga (Listing 1.22).
Daftar 1.22. hanoi.py (lanjutan)
def hanoi(begin: Stack[int], end: Stack[int], temp: Stack[int], n: int) -> None: if n == 1: end.push(begin.pop()) else: hanoi(begin, temp, end, n — 1) hanoi(begin, end, temp, 1) hanoi(temp, end, begin, n - 1)
Setelah memanggil hanoi (), Anda perlu memeriksa menara A, B, dan C untuk memastikan bahwa disk telah berhasil dipindahkan (Listing 1.23).
Listing 1.23. hanoi.py (lanjutan)
if __name__ == "__main__": hanoi(tower_a, tower_c, tower_b, num_discs) print(tower_a) print(tower_b) print(tower_c)
Anda akan menemukan bahwa drive memang telah dipindahkan. Ketika mengkode solusi untuk masalah menara Hanoi, tidak perlu memahami setiap langkah yang diperlukan untuk memindahkan beberapa disk dari menara A ke menara C. Kami memahami algoritma rekursif umum untuk memindahkan sejumlah disk dan mensistematisasinya, memungkinkan komputer melakukan sisanya. Ini adalah kekuatan dari merumuskan solusi rekursif untuk masalah: kita sering dapat membayangkan solusi secara abstrak, tanpa membuang energi pada representasi mental dari setiap tindakan individu.
By the way, fungsi hanoi () akan dieksekusi secara eksponensial tergantung pada jumlah disk, yang membuat solusi untuk masalah bahkan untuk 64 disk tidak cocok. Anda dapat mencoba menjalankannya dengan jumlah disk yang berbeda dengan mengubah variabel num_discs. Ketika jumlah disk meningkat, jumlah langkah untuk menyelesaikan tugas menara Hanoi tumbuh secara eksponensial, lebih banyak detail dapat ditemukan di banyak sumber. Jika Anda tertarik untuk mempelajari lebih lanjut tentang matematika di balik solusi rekursif dari masalah ini, lihat penjelasan Karl Birch dalam artikel
"Di Menara Hanoi" .
1.6. Aplikasi nyata
Berbagai metode yang disajikan dalam bab ini (rekursi, memoisasi, kompresi, dan manipulasi pada level bit) begitu luas dalam pengembangan perangkat lunak modern sehingga tanpa mereka tidak mungkin membayangkan dunia komputasi. Terlepas dari kenyataan bahwa tugas dapat diselesaikan tanpa mereka, seringkali lebih logis atau lebih bijaksana untuk menyelesaikannya dengan menggunakan metode ini.
Secara khusus, rekursi tidak hanya mendasari banyak algoritma, tetapi bahkan seluruh bahasa pemrograman. Dalam beberapa bahasa pemrograman fungsional, seperti Skema dan Haskell, rekursi menggantikan loop yang digunakan dalam bahasa imperatif. Namun, harus diingat bahwa segala sesuatu yang dapat dicapai dengan menggunakan metode rekursif juga dapat dilakukan secara iteratif.
Memoisasi telah berhasil digunakan untuk mempercepat pekerjaan parser - program yang menafsirkan bahasa. Ini berguna dalam semua tugas di mana hasil perhitungan terbaru kemungkinan akan diminta lagi. Bidang tindakan lain untuk memoisasi adalah runtime bahasa pemrograman. Beberapa runtime ini, misalnya, untuk versi Prolog, secara otomatis menyimpan hasil pemanggilan fungsi (auto-mash), sehingga fungsi tersebut tidak harus dieksekusi di waktu berikutnya dengan panggilan yang sama. Ini mirip dengan dekorator @lru_cache () di fib6 ().
Kompresi telah membuat dunia Internet, dengan bandwidth yang terbatas, lebih tertahankan. Metode bit string yang dibahas dalam Bagian 1.2 berlaku untuk tipe data sederhana di dunia nyata yang memiliki jumlah nilai yang mungkin terbatas, yang bahkan 1 byte adalah redundan. Namun, sebagian besar algoritma kompresi bekerja dengan mencari pola atau struktur dalam dataset yang menghilangkan informasi duplikat. Mereka jauh lebih rumit daripada yang dijelaskan di bagian 1.2.
Cipher sekali pakai tidak cocok untuk kasus enkripsi umum. Mereka mengharuskan encoder dan decoder memiliki salah satu kunci (data dummy dalam contoh kami) untuk mengembalikan data asli, yang terlalu rumit dan dalam sebagian besar skema enkripsi tidak memungkinkan untuk mencapai tujuan menjaga kerahasiaan kunci. Tetapi Anda mungkin tertarik untuk mengetahui bahwa nama "cipher sekali pakai" ditemukan oleh mata-mata yang selama Perang Dingin menggunakan notebook kertas nyata dengan data fiktif yang direkam di dalamnya untuk membuat pesan terenkripsi.
Metode-metode ini adalah blok bangunan program, algoritma lain didasarkan pada mereka. Dalam bab-bab berikut, Anda akan melihat seberapa luas penerapannya.
Tentang penulis
David Kopec adalah Dosen Senior Ilmu Komputer dan Inovasi di Champlain College di Burlington, Vermont. Dia adalah pengembang perangkat lunak yang berpengalaman dan penulis Classic Computer Science Problems in Swift (Manning, 2018) dan Dart for Absolute Beginners (Apress, 2014). David meraih gelar sarjana di bidang ekonomi dan gelar master di bidang ilmu komputer dari Dartmouth College. Anda dapat menghubunginya di Twitter melalui @davekopec.
»Informasi lebih lanjut tentang buku ini dapat ditemukan di
situs web penerbit»
Isi»
KutipanKupon diskon 25% untuk penjaja -
PythonSetelah pembayaran versi kertas buku, sebuah buku elektronik dikirim melalui email.