Analisis Struktur Data dan Algoritma Python (Edisi 2)

📚 Ringkasan Konten

Buku ini merupakan buku teks klasik yang menjelaskan struktur data dan algoritma menggunakan Python. Meliputi ulangan dasar Python, analisis algoritma (notasi O besar), struktur data dasar (tumpukan, antrian, daftar), rekursi, pencarian dan pengurutan, algoritma pohon serta graf. Dengan daftar kode praktis, buku ini membantu pembaca memahami bagaimana mengimplementasikan berbagai tipe data abstrak secara efisien menggunakan Python.

Hanya dengan memahami struktur data dan algoritma secara mendalam, seseorang benar-benar dapat menguasai Python.

Penulis: Bradley Miller (Profesor Emeritus Ilmu Komputer di Luther College, Amerika Serikat), David Ranum (Insinyur Perangkat Lunak Kognitif IBM Watson)

Ucapan Terima Kasih: Terima kasih kepada rekan kerja Steve Hubbard atas umpan balik yang sangat banyak untuk edisi pertama serta bahan baru untuk edisi terbaru, serta kepada para kolega dari berbagai tempat yang telah mengirim email tentang kesalahan dan memberikan masukan. Terima kasih juga kepada Mary, Bob, dan staf lainnya di kafe Java John's di Decora, yang memperbolehkan kami menjadi "penulis tetap" saat liburan. Selain itu, terima kasih kepada seluruh staf Franklin, Beedle & Associates (terutama Jim Leisy dan Tom Sumner) atas kolaborasi yang menyenangkan. Terakhir, ucapan terima kasih khusus kepada istri kami, Jane Miller dan Brenda Ranum, yang cinta dan dukungan mereka membuat buku ini akhirnya menjadi kenyataan.

🎯 Tujuan Pembelajaran

1. Memahami hubungan antara ilmu komputer, algoritma, dan pemrograman, serta menguasai konsep tipe data abstrak (ADT) dan penyembunyian informasi.
2. Mahir menggunakan tipe data koleksi bawaan Python (daftar, tuple, himpunan, kamus) serta struktur kontrol (perulangan, percabangan, penanganan ekssepsi).
3. Menguasai inti pemrograman berbasis objek Python: termasuk definisi kelas, metode konstruktor, overloading operator (seperti penjumlahan pecahan), aplikasi algoritma Euclidean, serta perbedaan antara kesamaan dalam dan luar.
4. Perbandingan berbagai solusi algoritma: mampu menjelaskan empat pendekatan deteksi kata anagram (penghitungan, pengurutan, brute force, penghitungan frekuensi) beserta kompleksitas waktu masing-masing.
5. Pengukuran performa container Python: menguasai efisiensi notasi O besar pada operasi utama Python list (List) dan dictionary (Dict), serta mampu membedakan perbedaan performa pop() dan pop(i).
6. Kemampuan verifikasi performa: mampu menggunakan modul timeit untuk merancang eksperimen yang memverifikasi konsistensi antara kompleksitas teoritis dan waktu eksekusi aktual.
7. Memahami dan mampu membedakan karakteristik logis struktur data linear (tumpukan, antrian, deque, daftar).
8. Mampu menggunakan koleksi dasar Python (seperti daftar) untuk mengimplementasikan tumpukan, antrian, dan deque kustom.
9. Memahami penerapan tumpukan dalam pemrosesan ekspresi (konversi infix ke postfix, evaluasi postfix) serta penerapan antrian dalam simulasi sistem (simulasi printer).
10. Menguasai prinsip dasar rekursi: mampu mengidentifikasi dan menulis fungsi rekursif yang mencakup kondisi dasar, evolusi status, dan pemanggilan diri sendiri.

🔹 Pelajaran 1: Dasar Pemrograman Python dan Abstraksi Berorientasi Objek

Ringkasan: Modul pelajaran ini bertujuan membimbing peserta belajar dari teori dasar ilmu komputer menuju praktik pemrograman Python. Pelajaran dimulai dengan mendefinisikan konsep inti ilmu komputer, algoritma, dan tipe data abstrak (ADT), kemudian menjelajahi lebih jauh koleksi bawaan Python, struktur kontrol, dan penanganan ekssepsi. Akhirnya, melalui pembuatan kelas Fraction dan hierarki pewarisan "gerbang logika", ditunjukkan kekuatan pemrograman berorientasi objek (OOP) dalam abstraksi proses dan data.

Hasil Pembelajaran:

• Memahami hubungan antara ilmu komputer, algoritma, dan pemrograman, serta menguasai konsep tipe data abstrak (ADT) dan penyembunyian informasi.
• Mahir menggunakan tipe data koleksi bawaan Python (daftar, tuple, himpunan, kamus) serta struktur kontrol (perulangan, percabangan, penanganan ekssepsi).
• Menguasai inti pemrograman berbasis objek Python: termasuk definisi kelas, metode konstruktor, overloading operator (seperti penjumlahan pecahan), aplikasi algoritma Euclidean, serta perbedaan antara kesamaan dalam dan luar.

🔹 Pelajaran 2: Analisis Algoritma dan Performa Container Python

Ringkasan: Pelajaran ini mendalami cara mengevaluasi efisiensi algoritma menggunakan notasi O besar, serta menunjukkan evolusi kompleksitas dari O(n!) hingga O(n) melalui contoh deteksi kata anagram. Di samping itu, pelajaran melakukan analisis kuantitatif terhadap performa operasi umum struktur data inti Python (daftar dan kamus), bertujuan membantu pengembang membuat pilihan optimal terhadap container dan desain algoritma dalam pemrograman nyata.

Hasil Pembelajaran:

• Perbandingan berbagai solusi algoritma: mampu menjelaskan empat pendekatan deteksi kata anagram (penghitungan, pengurutan, brute force, penghitungan frekuensi) beserta kompleksitas waktu masing-masing.
• Pengukuran performa container Python: menguasai efisiensi notasi O besar pada operasi utama Python list (List) dan dictionary (Dict), serta mampu membedakan perbedaan performa pop() dan pop(i).
• Kemampuan verifikasi performa: mampu menggunakan modul timeit untuk merancang eksperimen yang memverifikasi konsistensi antara kompleksitas teoritis dan waktu eksekusi aktual.

🔹 Pelajaran 3: Struktur Linear Dasar: Tumpukan, Antrian, dan Daftar Berkait

Ringkasan: Pelajaran ini mendalami empat struktur data linear dasar: tumpukan (Stack), antrian (Queue), deque (Double-ended Queue), dan daftar (List). Inti struktur linear adalah urutan relatif antar elemen; perbedaan utamanya terletak pada cara menambah dan menghapus elemen. Dengan mengimplementasikan tipe data abstrak (ADT) ini menggunakan Python, peserta akan mempelajari bagaimana memanfaatkan prinsip LIFO (Last In First Out) dan FIFO (First In First Out) untuk menyelesaikan masalah algoritma nyata seperti konversi ekspresi, simulasi sistem, serta manajemen memori daftar berkait.

Hasil Pembelajaran:

• Memahami dan mampu membedakan karakteristik logis struktur data linear (tumpukan, antrian, deque, daftar).
• Mampu menggunakan koleksi dasar Python (seperti daftar) untuk mengimplementasikan tumpukan, antrian, dan deque kustom.
• Memahami penerapan tumpukan dalam pemrosesan ekspresi (konversi infix ke postfix, evaluasi postfix) serta penerapan antrian dalam simulasi sistem (simulasi printer).

🔹 Pelajaran 4: Prinsip Algoritma Rekursi dan Pengantar Dinamis Program

Ringkasan: Pelajaran ini mendalami prinsip inti algoritma rekursi, mulai dari prinsip tiga dasar rekursi, melalui contoh seperti konversi numerik, geometri fraktal, dan penyelesaian teka-teki klasik (Menara Hanoi dan labirin), mengungkap mekanisme dasar pemanggilan rekursif—yaitu frame tumpukan. Akhirnya, pelajaran memperkenalkan konsep pemrograman dinamis (Dynamic Programming), menunjukkan bagaimana teknik memoisasi dapat menyelesaikan masalah perhitungan berulang dalam rekursi, sehingga menciptakan peningkatan signifikan dalam efisiensi algoritma.

Hasil Pembelajaran:

• Menguasai prinsip tiga dasar rekursi: mampu mengidentifikasi dan menulis fungsi rekursif yang mencakup kondisi dasar, evolusi status, dan pemanggilan diri sendiri.
• Memahami mekanisme eksekusi dasar: memahami bagaimana tumpukan pemanggilan Python (Stack Frame) mengelola variabel lokal dan jalur kembali selama proses rekursi.
• Mampu memodelkan masalah kompleks: mampu menggunakan pendekatan rekursi dan backtracking untuk menyelesaikan masalah non-linear seperti Menara Hanoi dan pencarian jalan di labirin.

🔹 Pelajaran 5: Teknik Pencarian, Hashing, dan Algoritma Pengurutan

Ringkasan: Modul pelajaran ini berfokus pada teknologi pemrosesan data inti dalam ilmu komputer: pencarian, hashing (Hashing), dan pengurutan. Materi mencakup dari pencarian berurutan dasar hingga pencarian biner yang efisien, mendalami prinsip pembuatan tabel hash (Hash Tables), metode penanganan tabrakan, serta implementasi tipe data abstrak Map. Di samping itu, dianalisis secara detail logika dan performa algoritma pengurutan seperti bubble sort, shell sort, dan merge sort.

Hasil Pembelajaran:

• Memahami dan mampu membandingkan skenario penggunaan serta kompleksitas waktu antara pencarian berurutan dan pencarian biner (O(n) vs O(\log n)).
• Menguasai desain fungsi hash (metode lipatan, metode kuadrat tengah) serta mekanisme penanganan tabrakan (deteksi linear, deteksi kuadrat, metode chaining).
• Mampu mensimulasikan dan mengimplementasikan secara manual bubble sort, shell sort, dan merge sort, serta memahami penerapan strategi bagi dan taklukkan (divide and conquer) dalam pengurutan.

🔹 Pelajaran 6: Struktur Pohon: Heap Biner, Pohon Pencarian, dan Pohon Seimbang (AVL)

Ringkasan: Pelajaran ini mendalami struktur data paling inti dalam ilmu komputer—pohon. Kami memulai dari istilah dasar dan implementasi pohon biner, lalu berkembang ke aplikasi lanjutan pohon biner, termasuk pohon ekspresi dan metode traversal-nya. Setelah itu, kami mempelajari dua varian efisien: heap biner untuk antrean prioritas dan pohon pencarian biner (BST) untuk pencarian yang efisien. Akhirnya, kami meneliti pohon AVL, yang menggunakan rotasi untuk mempertahankan faktor keseimbangan, menyelesaikan masalah degradasi performa BST pada kasus terburuk.

Hasil Pembelajaran:

• Mampu mendefinisikan istilah inti pohon (akar, sisi, lintasan, tinggi) secara tepat serta menggambarkan sifat rekursif pohon biner.
• Menguasai algoritma inti dalam implementasi pohon biner, pohon pencarian biner, dan pohon AVL menggunakan Python (seperti sisipan, penghapusan, rotasi, dan re-balancing).
• Mampu menjalankan dan menjelaskan tiga algoritma traversal pohon, serta menggunakan pohon analisis untuk menyelesaikan ekspresi matematika.

🔹 Pelajaran 7: Algoritma Teori Graf: Pencarian, Jalur Terpendek, dan Minimum Spanning Tree

Ringkasan: Pelajaran ini mendalami teori dasar teori graf dan implementasinya secara efisien dalam Python. Materi mencakup tipe data abstrak graf (matriks ketetanggaan dan daftar ketetanggaan), algoritma pencarian dasar (BFS dan DFS) serta aplikasi klasiknya. Akhirnya, pelajaran berkembang ke algoritma jalur terpendek (Dijkstra) dan minimum spanning tree (Prim) pada graf berbobot.

Hasil Pembelajaran:

• Memahami dan mampu membandingkan dua representasi utama graf (matriks ketetanggaan dan daftar ketetanggaan) dalam hal performa dan skenario penggunaan.
• Menguasai prinsip algoritma BFS dan DFS, serta mampu menyelesaikan masalah pencarian jalur dan jelajah.
• Mampu menerapkan algoritma graf untuk menyelesaikan masalah dependensi logika kompleks (urutan topologis) serta konektivitas jaringan (komponen kuat terhubung, minimum spanning tree).

🔹 Pelajaran 8: Ujian Khusus: Enkripsi RSA, Skip List, dan Kuantisasi Warna dengan Octree

Ringkasan: Pelajaran ini mendalami pergeseran aplikasi dari struktur data dasar hingga algoritma kompleks dalam ilmu komputer. Materi mencakup implementasi dasar Python list (ArrayList) dan analisis amortisasi, algoritma rekursif berbasis teori bilangan untuk mendukung enkripsi RSA, pembuatan skip list untuk meningkatkan efisiensi pencarian kamus, serta prinsip penerapan octree dalam kuantisasi warna gambar digital.

Hasil Pembelajaran:

• Memahami susunan memori ArrayList serta derivasi matematis analisis amortisasi (Amortized Analysis).
• Menguasai prinsip matematis inti enkripsi RSA, termasuk teorema kongruensi, residu pangkat, dan algoritma Euclidean perluasan.
• Mampu menjelaskan struktur lapisan skip list, proses pembentukan berbasis probabilitas, serta efisiensi pencarian O(\log n).