Halo para Penduduk! Sebuah raksasa dengan kaki tanah liat adalah apa yang Anda sebut programmer tanpa pelatihan di bidang Ilmu Komputer. Penguasaan dasar-dasar yang percaya diri memungkinkan Anda untuk tidak "menemukan kembali roda" dan membangun solusi efektif ke dalam arsitektur perangkat lunak. Semua ini menyelamatkan Anda dari kesalahan dan biaya yang berlebihan untuk pengujian dan pemfaktoran ulang.
Tidak masalah jika Anda merasa tidak pada tempatnya ketika programmer lain mendiskusikan perkiraan batasnya. Bahkan spesialis berpengalaman pun membuat kesalahan karena mereka telah melupakan Ilmu Komputer.
Mengapa buku ini dibutuhkan
Banyak kenalan saya (penulis) pengembang datang ke profesi ini dari berbagai bidang. Beberapa memiliki pendidikan tinggi dalam Ilmu Komputer; yang lain belajar fotografi, matematika, atau bahkan tidak lulus dari universitas.
Dalam beberapa tahun terakhir, saya memperhatikan bahwa para programmer semakin bersemangat untuk mempelajari Ilmu Komputer karena sejumlah alasan:
- menjadi programmer yang baik;
- untuk menjawab pertanyaan tentang algoritma selama wawancara;
- untuk memuaskan keingintahuan mereka di bidang Ilmu Komputer, atau akhirnya berhenti menyesali bahwa pada suatu waktu mereka tidak memiliki kesempatan untuk menguasai mata pelajaran ini.
Buku ini untuk Anda semua.
Banyak yang akan menemukan topik-topik yang menarik di sini. Saya mencoba untuk menunjukkan dalam situasi (non-akademis) nyata apa pengetahuan ini akan berguna. Setelah membaca buku ini, saya ingin Anda mendapatkan pengetahuan yang sama seperti setelah mempelajari mata kuliah dasar Ilmu Komputer, dan juga belajar bagaimana menerapkannya.
Sederhananya, tujuan dari buku ini adalah untuk membantu Anda menjadi programmer yang lebih terampil dan berpengalaman melalui pemahaman yang lebih baik tentang Ilmu Komputer. Saya tidak bisa memasukkan 20 tahun pengalaman mengajar di perguruan tinggi dan pengalaman profesional ke dalam satu buku ... tetapi saya akan berusaha melakukan yang terbaik. Saya harap Anda akan menemukan setidaknya satu topik di sini, yang dapat Anda katakan: "Ya, sekarang saya memahaminya" - dan menerapkan pengetahuan dalam pekerjaan Anda.
Apa yang tidak akan Anda temukan di edisi
Inti dari buku ini adalah untuk membantu pembaca lebih memahami Ilmu Komputer dan menerapkan pengetahuan dalam praktik, dan sama sekali bukan untuk sepenuhnya menggantikan empat tahun studi.
Secara khusus, ini bukan buku bukti. Memang, di jilid kedua buku ini , metode pembuktian dipertimbangkan, tetapi algoritme standar biasanya disajikan di sini tanpa pembuktian. Idenya adalah agar pembaca mengetahui tentang keberadaan algoritme ini dan mempelajari cara menggunakannya tanpa membahas secara detail. Sebagai buku bukti yang ditulis untuk mahasiswa sarjana dan pascasarjana, saya sangat merekomendasikan Pengantar Algoritma oleh Cormen, Leiserson, Rivest, dan Stein (penulis biasanya dikelompokkan dalam singkatan CLRS).
Ini juga bukan buku pemrograman: Anda tidak akan menemukan pedoman tentang kapan menggunakan bilangan bertipe int dan kapan harus menggunakan double, atau penjelasan tentang apa itu loop. Pembaca diharapkan dapat memahami daftar pseudocode yang digunakan untuk mendeskripsikan algoritma (semua program dalam buku ini ditulis dalam pseudocode berdasarkan bahasa C). Tujuan dari buku ini adalah untuk menghubungkan konsep Ilmu Komputer dengan teknik pemrograman yang sudah tidak asing lagi bagi pembaca.
10. Pemrograman dinamis
10.1. Masalah bidang hilang
Misalkan kita memiliki papan catur n × n yang kehilangan beberapa kotak. Bagaimana menemukan potongan papan kx terbesar tanpa bidang yang hilang?
Jika Anda belum pernah menghadapi masalah seperti itu sebelumnya, luangkan beberapa menit untuk menulis solusi dan tentukan waktu eksekusi algoritme Anda.
Menghadapi masalah ini, saya beralasan sebagai berikut. Setiap bidang papan catur dapat dimiliki oleh banyak area terbesar, tetapi hanya di salah satu area tersebut yang dapat berada di pojok kiri atas. Jika saya menandai setiap kotak dengan ukuran area utuh terbesar yang merupakan sudut kiri atas, maka bidang dengan tanda terbesar tersebut akan sesuai dengan area yang diinginkan.
Misalkan papan direpresentasikan sebagai matriks n × n, di mana setiap sel berisi 1 jika bidang yang sesuai ada dan 0 jika tidak ada. Jika nilai sel saat ini adalah 0, maka bidang terkait tidak ada dan tidak dapat menjadi bagian dari kawasan yang bersebelahan, sehingga tidak perlu diubah. Jika nilainya 1, maka kita dapat menggantinya dengan angka yang satu lebih dari nilai minimum ketiga sel yang terletak di bawah dan di sebelah kanan.
Kami mengubah setiap sel matriks sekali, termasuk memeriksa apakah nilai sel adalah nol, memeriksa nilai hingga tiga sel lagi, dan menulis nilai sel baru. Setiap operasi ini membutuhkan O (1) waktu, jadi waktu yang dibutuhkan untuk memproses keseluruhan papan catur adalah
Perhatikan bahwa ini linier, bukan kuadrat, waktu eksekusi algoritme - pada papan catur n (kami berasumsi bahwa n adalah jumlah total bidang, dan kami mematuhi konvensi biasa bahwa n adalah jumlah data input) bidang (beberapa di antaranya adalah absen), oleh karena itu total waktu yang dihabiskan oleh algoritme sebanding dengan jumlah bidang. Jika kita lebih akurat menyatakan ukuran papan catur sebagai √ n × √ n, maka kita mendapatkan n bidang dan total waktu eksekusi adalah O (n).
10.2. Bekerja dengan subtugas yang tumpang tindih
Pendekatan yang digunakan dalam bagian ini disebut pemrograman dinamis. Ini digunakan ketika suatu masalah dapat dibagi menjadi beberapa subtugas, yang solusinya masing-masing akan digunakan beberapa kali. Pendekatan ini berbeda dengan prinsip "bagi dan taklukkan", ketika masalah dibagi menjadi beberapa tugas yang diselesaikan secara independen satu sama lain. Dalam masalah papan catur, setiap sub-masalah bergantung pada solusi untuk tiga masalah lainnya, dan solusi untuk semua sub-masalah disimpan untuk digunakan lebih lanjut.
Pemrograman dinamis biasanya dilakukan dengan membangun tabel seperti yang ditunjukkan di atas. Ini berarti memecahkan masalah menggunakan pendekatan bottom-up, di mana kita mulai dengan menyelesaikan subproblem terkecil dan terus bekerja sampai kita menemukan jawaban. Metode lain adalah memoization, di mana kita pergi dari atas ke bawah, menyelesaikan sub-masalah sesuai kebutuhan dan menyimpan hasilnya untuk digunakan kembali. Membangun tabel adalah opsi yang disukai ketika Anda perlu menyelesaikan setiap subproblem (dalam contoh saya dengan papan catur, Anda perlu menemukan area utuh terbesar untuk setiap bidang papan), karena biaya metode ini lebih sedikit daripada dengan memoisasi. Jika beberapa subtugas dari area solusi tidak harus diselesaikan, maka memoization memungkinkan Anda menyelesaikan hanya subtugas yang benar-benar diperlukan.
Poin Kunci
Di mana divide and conquer melibatkan pembagian tugas menjadi beberapa subtugas independen, pemrograman dinamis berarti membagi tugas menjadi beberapa subtugas yang tumpang tindih. Solusi untuk setiap submasalah disimpan dalam cache untuk digunakan kembali nanti.
10.3. Pemrograman dinamis dan jalur terpendek
Pertimbangkan masalah menemukan jalur terpendek: untuk grafik tertentu dengan tepi berbobot, Anda perlu menemukan jalur dari satu node ke node lain yang memiliki biaya terendah.
Definisi
Grafik edge-weighted adalah grafik yang setiap edge memiliki bobot (biaya) sendiri-sendiri. Biaya jalur dari satu node ke node lainnya ditentukan oleh jumlah biaya semua tepi yang dilintasi.
Misalkan kita menemukan jalur antara node s dan t yang berisi node ketiga v. Kemudian lintasan dari s ke t harus berisi lintasan terpendek dari s ke v, karena jika tidak kita dapat mengganti segmen ini dengan lintasan yang lebih pendek dan mengurangi panjang lintasan terpendek dari s ke t, yang bertentangan dengan kondisi awal (inilah prinsip optimalitas Bellman).
( ) , . , . , .
, , .
Masalah dalam menemukan jalur terpendek adalah contoh yang mencolok dari pemrograman dinamis, karena properti optimal dari suatu substruktur jelas secara intuitif - jelas bahwa cara tercepat untuk pergi dari titik A ke titik C melalui titik B juga merupakan cara tercepat untuk pergi dari titik A ke titik B dan dari titik B dan dari titik B ke titik C.Jumlah algoritme berdasarkan prinsip ini mencakup metode Bellman - Ford, yang menemukan jalur terpendek dari titik awal ke titik mana pun pada grafik (atau dari titik mana pun pada grafik ke titik akhir) dan metode Floyd - Warshall - dengan bantuannya jalur terpendek antara setiap pasangan simpul grafik dihitung. Dalam kedua kasus, idenya adalah untuk memulai dengan subset kecil dari node yang dekat dengan node yang diinginkan, dan secara bertahap memperluas set ini menggunakan node yang sudah ditemukan untuk menghitung jarak baru.
10.4.
10.4.1. Git merge
Tugas lain yang biasanya digunakan untuk mendemonstrasikan pemrograman dinamis adalah menemukan Urutan Umum Terpanjang. Tugasnya adalah menemukan, untuk dua string A dan B yang diberikan, urutan terpanjang yang terjadi di kedua string sambil mempertahankan urutan karakter. String tidak harus berjajar; misalnya, jika A = {acdbef} dan B = {babdef}, maka {adef} akan menjadi urutan bersamanya.
Saat menggabungkan perubahan di Git (merge), ia mencari urutan umum terbesar untuk master dan cabang yang berfungsi. Karakter yang ada di master tetapi tidak ada di urutan umum terbesar akan dihapus; karakter yang ada di cabang yang berfungsi tetapi tidak ada dalam selanjutnya ditambahkan ke master.
10.4.2. LATEX
Sistem persiapan dokumen LATEX sering digunakan untuk membuat dokumen teknis. Salah satu tugas sistem pengetikan adalah meratakan teks secara bersamaan ke tepi kanan dan kiri; untuk melakukan ini, spasi antara kata dan karakter direntangkan atau dikecilkan sehingga semua baris memiliki panjang yang sama. Cara lain untuk meratakan teks adalah dengan membungkus kata terakhir sehingga bagian kata tersebut muncul di baris berikutnya. LATEX (Dari sudut pandang teknis, sistem input teks TEX melakukan hampir semua pekerjaan; LATEX dibangun di atas TEX. Di sini saya menggunakan LATEX untuk alasan kesederhanaan) mencoba menemukan titik jeda baris yang optimal untuk membuat teks terlihat bagus. Jika gagal, beberapa baris dalam satu baris akan diakhiri dengan tanda hubung kata, atau jarak antar kata di baris yang berbeda akan berbeda.LATEX memiliki seperangkat aturan untuk mengevaluasi "kegagalan" penyelarasan. Program ini berusaha menemukan opsi "paling tidak buruk".
Jika ada n kemungkinan titik hentian baris dalam sebuah paragraf, maka ada
kemungkinan opsi untuk memutus teks. "Kegagalan" pemilihan untuk setiap break point bergantung pada break point mana yang dipilih sebelumnya. Oleh karena itu, kami memiliki sub-tugas yang tumpang tindih lagi. Penggunaan teknik pemrograman dinamis mengurangi waktu eksekusi 
yang dapat ditingkatkan dengan metode tambahan.
»Rincian lebih lanjut tentang buku dapat ditemukan di situs web penerbit
» Daftar Isi
» Kutipan
Untuk Habitants diskon 25% untuk kupon - Ilmu Komputer
Setelah pembayaran untuk versi kertas dari buku tersebut, sebuah e-book dikirim ke email.