rangkuman buku Python Data Structures and Algorithms

 Prinsip Desain Algoritma 

Agoritma adalah dasar dari semua komputasi. Mesin Turing pada dasarnya adalah model matematika yang, dengan menggunakan seperangkat aturan yang telah ditentukan, menerjemahkan sekumpulan masukan menjadi satu set keluaran. Mesin Turing bersifat mekanis dan generasi berikutnya mungkin melihat sirkuit logika digital digantikan oleh sirkuit kuantum atau yang serupa.

Terlepas dari platformnya, algoritme memainkan peran utama utama. Aspek lain adalah efek algoritma dalam inovasi teknologi. Sebagai contoh nyata, pertimbangkan algoritma pencarian peringkat halaman, variasi yang didasarkan pada mesin pencari Google. Menggunakan algoritme ini dan algoritme serupa memungkinkan peneliti, ilmuwan, teknisi, dan lainnya untuk dengan cepat mencari informasi dalam jumlah besar dengan sangat cepat.

Studi tentang algoritma juga penting karena melatih kita untuk berpikir secara spesifik tentang masalah tertentu. Ini dapat berfungsi untuk meningkatkan kemampuan mental dan pemecahan masalah kita dengan membantu kita mengisolasi komponen masalah dan menentukan hubungan antara komponen-komponen ini. 

1. Mereka penting untuk ilmu komputer dan sistem cerdas.
2. Mereka penting di banyak domain lainnya.
3. Mereka berperan dalam inovasi teknologi.
4. Mereka meningkatkan pemecahan masalah dan pemikiran analitis.

Algoritme, dalam bentuknya yang paling sederhana, hanyalah urutan tindakan, daftar instruksi. Ini mungkin hanya konstruksi linier dari bentuk do x, lalu lakukan y, lalu lakukan z, lalu selesaikan. Namun, untuk membuatnya lebih berguna kita menambahkan klausa ke efek, x lalu do y, dalam Python pernyataan if-else. Di sini, tindakan di masa depan bergantung pada beberapa kondisi; katakanlah keadaan struktur data. Untuk ini kami juga menambahkan operasi, iterasi, while, dan untuk pernyataan .Memperluas literasi algoritmik kami lebih jauh, kami menambahkan rekursi . Rekursi sering kali dapat mencapai hasil yang sama seperti iterasi, namun pada dasarnya berbeda . Fungsi rekursif memanggil dirinya sendiri, menerapkan fungsi yang sama ke input yang semakin kecil .

Masukan dari setiap langkah rekursif adalah keluaran dari langkah rekursif sebelumnya .

algoritma terdiri dari empat elemen berikut :

• operasi berurutan
• tindakan berdasarkan status struktur data
• iterasi, mengulangi tindakan beberapa kali
• rekursi, memanggil dirinya sendiri pada subset input 

Algorithm design paradigms

secara umum, kita dapat membedakan tiga pendekatan luas untuk desain algoritma. yaitu :

• memecahkan dan menaklukkan 
• algoritma serakah
• pemrograman dinamis 

Seperti namanya, paradigma divide and conquer melibatkan pemecahan masalah menjadi sub masalah yang lebih kecil, dan kemudian dengan cara tertentu menggabungkan hasil untuk mendapatkan solusi global. Pendekatan pemrograman dinamis berguna ketika sub masalah kita tumpang tindih. Daripada memecah masalah kami menjadi sub masalah independen, dengan pemrograman dinamis, hasil antara disimpan dalam cache dan dapat digunakan dalam operasi selanjutnya. Ini dapat memiliki keunggulan kinerja dibandingkan divide and conquer untuk beberapa masalah karena seringkali lebih cepat untuk mengambil hasil yang dihitung sebelumnya dari memori daripada harus menghitung ulang.

Rekursi dan mundur 

Rekursi sangat berguna untuk membagi dan menaklukkan masalah; Namun, mungkin sulit untuk memahami dengan tepat apa yang terjadi, karena setiap panggilan rekursif itu sendiri berputar dari panggilan rekursif lainnya. Masalah sederhana yang secara alami cocok untuk solusi rekursif adalah menghitung faktorial. Implementasi tipikal adalah sebagai berikut:

def factorial(n):

#test for a base case

if n==0:

return 1

# make a calculation and a recursive call

f= n*factorial(n-1)

print(f)

return(f)

factorial(4)

Kode ini mencetak angka 1, 2, 4, 24. Untuk menghitung 4 membutuhkan empat panggilan rekursif ditambah panggilan induk awal. Pada setiap rekursi, salinan variabel metode disimpan dalam memori.

Iterasi berhenti sampai masalah selesai. Rekursi memecah masalah menjadi potongan-potongan yang lebih kecil dan lebih kecil dan kemudian menggabungkan hasilnya. Iterasi seringkali lebih mudah bagi pemrogram, karena kontrol tetap lokal ke loop, sedangkan rekursi dapat lebih mewakili konsep matematika seperti faktorial.