Strategi Algoritma dan Pemrograman (SAP)

Strategi algoritmik, pemrograman, penyelesaian masalah.

A. Proses Pemrograman

Program dapat menjadi solusi dari suatu permasalahan. Untuk menghasilkan program yang benar dan dapat membantu manusia dalam melakukan tugasnya, ada empat langkah yang dilakukan pada saat melakukan pemrograman, yaitu:

1. Menganalisis permasalahan (Analyzing): pemrogram menganalisis suatu kebutuhan atau keadaan saat ini untuk menghasilkan definisi permasalahan yang perlu diselesaikan dengan program, Permasalahan yang dianalisis hisa berupa masalah yang bero acaа ремукопротивл solusi yang sudah ada. Kemampuan berpikir komputasiall digunakan untuk mencari abstraksi dari perman yang akan diselesaikan. Permasalahan yang kompleks dapat didekomposisi ke beberapa masalah yang lebih kecil, namun saling berkaitan. Hingga akhirnya, pemrogram akan mengenali pola permasalahan tersebut sebagai sebua variasi dari problem generik. Tahap ini menghasilkan pernyataan masalah (problem statement) yang menjelaskan masukan (input), keluaran (output), serta batasan-batasen (constraint) dari program yang akan dilouar.

2. Mendesain solusi (Problem Solving dari pernyataan masalah ini, pemrogram merencanakan strategi untuk menghasilkan keluaran berdasarkan masukan yang diterima. Pemrogram tidak harus merencanakan solusi dari awal. Mereka dapat menggunakan solusi atau potongan solusi yang sudah ada dari permasalahan yang telah diselesaikan sebelumnya. Bahkan, jika problem generik telah ditemukan, pemrogram dapat memodifikasi algoritma generik agar sesuai dengan permasalahan. Proses ini akan menghasilkan algoritma berupa narasi, pseudocode, atau diagram alir. Pada tahap ini, pemrogram juga akan mengevaluasi algoritma yang dibuat arituk memenuhi batasan dari permasalahan. Misalnya, apakah program dapat bekerja dengan cepat (kurang dari 1 detik) saat diberikan masukan yang berukuran besar, karena menunggu membuat pengguna tidak nyaman.

3. Mengimplementasikan solusi dalam bentuk program (Coding): Pada tahap ini, pemrogram akan menulis kode program untuk menjalankan solusi yang telah direncanakan sebelumnya dengan menggunakan tara bahasa pemrograman. Memilih bahasa pemrograman menjadi pertimbangan di tahap ini. Selain itu, mengubah algoritma menjadi kode program juga melibatkan banyak pertimbangan teknis (misalnya: tipe data, struktur kontrol yang digunakan, dan lain-lain).

4. Menguji program (Testing): Setelah program dapat dijalankan, program tersebut harus diuji untuk memastikan program berjalan dengan benar, sesuai dengan batasan- batasan yang diberikan. Pengujian dapat dilakukan dengan menggunakan berbagai strategi pengujian. Salah satu yang telah kalian pelajari di Kelas X adalah menguji program menggunakan kasus uji (test case) yang dibuat sedemikan rupa sehingga mewakili seluruh kemungkinan masukan dari program.

B. Berpikir Komputasional

Berpikir komputasional ini merupakan suatu kerangka dan proses berpikir yang mencakup perangkat keras, perangkat lunak, dan menalar (reasoning) mengenai sistem dan persoalan. Moda berpikir (thinking mode) ini didukung dan dilengkapi dengan pengetahuan teoritis dan praktis, serta teknik untuk menganalisis, memodelkan dan menyelesaikan persoalan. Berikut ini pembahasan beberapa konsep dan strategi berpikir komputasional yang biasa digunakan dalam menyelesaikan persoalan komputasi.

1. Rekursi

Pada bagian ini kalian akan mempelajari tentang konsep rekursi dan beberapa contoh permasalahan yang dapat diselesaikan dengan menggunakan konsep tersebut, salah satunya adalah barisan Fibonacci.

2. Algoritma Greedy

Greedy secara harfiah berarti rakus atau tamak. Meskipun dalam pengertian sehari-hari, kata "rakus" dan "tamak" memiliki konotasi negatif, namun dalam konteks Informatika, kita mengartikan greedy dalam konteks sebagai sebuah strategi penyelesaian masalah yang dapat berguna dalam merancang sebuah algoritma atau solusi bagi sebuah permasalahan komputasional. Oleh karena itu, diharapkan tidak ada konotasi negatif pada kata greedy dalam konteks ini.

Teknik greedy adalah salah satu teknik penyelesaian masalah yang biasa digunakan untuk menyelesaikan permasalahan optimasi. Permasalahan optimasi berarti kita ingin menghitung sebuah hasil yang terbaik dari sebuah proses tertentu. Terbaik disini dapat berarti nilai yang paling kecil ataupun paling besar, tergantung dari jenis permasalahannya. Dalam menyelesaikan permasalahan optimasi seperti ini, algoritma greedy akan menerapkan prinsip "mengambil serangkaian langkah terbaik pada setiap saat".

3. Pemrograman Dinamis Saat menyelesaikan sebuah permasalahan optimasi

(mencari nilai terbesar/terkecil), terkadang kita harus memperhitungkan beberapa kemungkinan pengambilan langkah untuk menyelesaikan permasalahan tersebut Kemungkinan-kemungkinan tersebut mungkin memiliki akibat/konsekuensi terhadap langkah-langkah selanjutnya, sehingga pendekatan seperti teknik greedy mungkin tidak akan menghasilkan jawaban yang optimal. Dalam hal ini, teknik pemrograman dinamis atau dynamic programming (DP) mungkin akan lebih sesuai diterapkan. Teknik DP mengandung dua unsur utama, yaitu:

1. Optimasi (mencari nilai terkecil/terbesar) melalui serangkaian pilihan. Serupa dengan teknik greedy, kita harus menentukan rangkaian langkah apa yang akan menghasilkan nilai optimal di akhir. Namun, berbeda dengan permasalahan yang dapat diselesaikan dengan teknik greedy, permasalahan yang sesuai untuk teknik DP memiliki struktur sedemikian rupa sehingga pilihan langkah terbaik saat ini belum tentu merupakan pilihan terbaik secara keseluruhan, sehingga prinsip greedy belum tentu dapat diterapkan, dan semua kemungkinan kombinasi pilihan langkah harus diperhitungkan.

2. Nilai optimal yang diinginkan untuk permasalahan tersebut biasanya dapat dinyatakan sebagai kombinasi optimal dari sub-sub permasalahan yang sama, tetapi dengan ukuran yang lebih kecil (atau dengan kata lain, dapat dinyatakan secara rekursif). Namun, sub-sub permasalahan yang harus dipertimbangkan, biasanya memiliki overlap (persinggungan) sehingga dalam proses perhitungannya, diperlukan cara yang efisien untuk menghitung solusi untuk sub-sub permasalahan yang diperlukan, agar tidak terjadi perulangan/duplikasi dalam proses perhitungan. Cara yang umum digunakan adalah dengan menyimpan semua solusi dari subproblem yang sudah diketahui dalam sebuah tempat penyimpanan/ tabel. Teknik ini biasa disebut sebagai teknik memorisasi.

C. Algoritma dan Pemrograman 

1. Larik (array)

Pada praktiknya, program digunakan untuk mengolah data yang berukuran besar dan membutuhkan waktu yang sangat lama jika dikerjakan manual oleh manusia. Misalnya kalian perlu menghitung statistika deskriptif (seperti rata. rata, nilai minimal, nilai maksimal, standar deviasi, dan sebagainya) dari data seluruh penduduk Indonesia. Walaupun masalahnya sederhana, namun dikarenakan jumlah data yang diolah sangat banyak dan berukuran besar mengakibatkan waktu pengerjaan pun menjadi sangat lama bagi manusia untuk menyelesaikannya. Bahkan ada kemungkinan data berukuran besar tersebut tidak dapat diolah menggunakan aplikasi pengolah data (spreadsheet) yang tidak dirancang untuk mengolah data sebesar itu. Untuk solusinya kalian dapat menggunakan program khusus untuk mengolah data berukuran besar atau membuat program sendiri yang mampu menyimpan dan mengolah data berukuran besar. memiliki suatu alat untuk menyimpan himpunan data ke dalam satu nama variabel yang diberikan indeks. Salah satunya disebut sebagai larik atau array.

2. Karakter dan String

Selain angka, masukan dari program dapat berupa karakter atau memasukkan rangkaian karakter seperti kata. Hal ini telah lazim kalian temui misalnya ketika mengetikkan kata kunci untuk melakukan pencarian di mesin pencari atau ketika kalian kata sandi saat login. Oleh karena itu, program dilengkapi dengan kemampuan untuk membaca, menyimpan, mengolah, dan mencetak rangkaian karakter tersebut. Rangkaian karakter tersebut dalam pemrograman disebut sebagai string.

Definisi string dalam pemrograman adalah rangkaian karakter. Karakter sendiri merupakan suatu data berupa huruf, angka, simbol, dan karakter lain yang mengikuti suatu standar tertentu seperti "American Standard Code for Information Interchange" (ASCII) atau Unicode. Karakter pada pemrograman pada umumnya diimplementasikan dalam program menggunakan tipe data char. Di sisi lain, ada beberapa cara yang lazim digunakan untuk mengimplementasikan string dalam pemrograman.

D. Latihan Strategi Algoritmik dan Pemrograman Lintas Bidang

Pada bagian ini kalian akan membuat berbagai program berdasarkan permasalahan yang tersedia, tiap permasalahan memiliki sub permasalahannya tersendiri yang tingkat kesulitannya meningkat. Kalian akan membuat program dimulai dari perancangan, yaitu merancang algoritma untuk menyelesaikan permasalahan tersebut. Selanjutnya algoritma tersebut kalian terjemahkan ke dalam bahasa pemrograman yang kalian kuasai, misalnya bahasa C, Python,dsb. Permasalahan tersebut akan meningkatkan kemampuan programming kalian dengan mempelajari bagian ini dengan menyelesaikan berbagai sub permasalahan yang tersedia.

1. Problem Simulasi Burung

Problem: Program Simulasi Burung Boro adalah seekor burung yang terjatuh dari sarangnya di sebuah pohon saat sedang tidur. Saat terjatuh, sayap Boro menghantam tanah dan ia sangat merasa kesakitan. Boro harus kembali ke sarangnya, namun karena sayapnya terluka, ia tidak dapat terbang sebagaimana mestinya. Tak jauh dari tidur tempat Boro jatuh, terdapat ketapel raksasa yang biasa digunakan oleh pemilik lahan untuk kegiatan sirkus. Ketapel tersebut biasa digunakan untuk kegiatan menembak dengan menggunakan buah semangka.

Subproblem 1: Menghitung jarak Horizontal Terjaut

Deskripsi:

Pada subproblem ini, kalian akan diminta untuk menghitung jarak horizontal terjauh yang dapat ditempuh oleh Boro apabila Boro ikut berdiri di atas semangka yang akan diluncurkan oleh pemilik lahan.

Format Masukan:

Baris pertama adalah sebuah bilangan bulat S yang menggambarkan sudut peluncuran. Nilai S ini bernilai 0-90. Baris kedua adalah V yang merupakan kecepatan awal Boro saat meluncur dengan menggunakan ketapel.

Asumsikan bahwa nilai gravitasi adalah 10

Format Keluaran:

Keluaran berupa bilangan yang menunjukkan jarak terjauh Boro mendarat di tanah.

Subproblem 2: Menghitung Waktu

Deskripsi:

Pada subproblem ini, kalian akan diminta untuk menghitung waktu yang diperlukan Boro untuk mencapai jarak horizontal terjauh apabila Boro ikut berdiri di atas semangka yang akan diluncurkan oleh pemilik lahan.

Format Masukan:

Baris pertama adalah sebuah bilangan bulat S yang menggambarkan sudut peluncuran. Nilai S ini bernilai 0-90. Baris kedua adalah V yang merupakan kecepatan wal Boro saat meluncur dengan menggunakan ketapel. Asumsikan bahwa nilai gravitasi adalah 10

Format Keluaran:

Keluaran berupa bilangan yang menunjukkan waktu yang ditempuh Boro untuk mencapai jarak terjauh dengan format 3 angka di belakang koma.

Subproblem 3: Prediksi Ketinggian Dicapai Boro

Deskripsi:

Pada subproblem ini, kalian akan diminta untuk memberikan prediksi apakah Boro dapat mencapai ketinggian lebih tinggi daripada tinggi pohon tempat ia bersarang, apabila Boro ikut berdiri di atas semangka yang akan diluncurkan oleh pemilik lahan.

Format Masukan:

Baris pertama adalah sebuah bilangan bulat S yang menggambarkan sudut peluncuran. Nilai S ini bernilai 0-90. Baris kedua adalah V yang merupakan kecepatan awal Boro saat meluncur dengan menggunakan ketapel Baris ketiga adalah T yang merupakan tinggi pohon tempat Boro Bersarang. Asumsikan bahwa nilai gravitasi adalah 10.

Format Keluaran:

Keluaran berupa bilangan yang menunjukkan status ketinggian Boro dibandingkan dengan tinggi pohon tempat sarang Boro. 1 apabila Boro dapat mencapai ketinggian sama dengan tinggi pohon tempat sarangnya berada atau lebih, 0 apabila Boro tidak mampu mencapai ketinggian yang sama dengan pohon tersebut. Serta ketinggian maksimum yang dapat diperoleh oleh Boro saat meluncur dengan menggunakan ketapel.

Subproblem 4: Prediksi Ketinggian Dicapai Boro dan Teman-temannya

Deskripsi:

Pada subproblem ini, kalian akan diminta untuk memberikan prediksi apakah Boro dan teman-temannya dapat mencapai ketinggian lebih tinggi daripada tinggi pohon tempat ia bersarang. Pada subproblem ini, burung yang akan menumpang semangga tidak hanya Boro, namun terdapat burung lain yang akan menumpang semangka tersebut secara bergantian.

Format Masukan:

Baris pertama adalah sebuah bilangan bulat N yang menggambarkan jumlah burung yang akan ikut peluncuran. Baris kedua adalah S yang menggambarkan sudut peluncuran. Nilai S ini bernilai 0-90. Baris ketiga adalah V yang merupakan kecepatan awal Burung saat meluncur dengan menggunakan ketapel. Baris keempat adalah T yang merupakan tinggi pohon tempat burung bersarang. Asumsikan bahwa nilai gravitasi adalah 10.

Format Keluaran:

Keluaran berupa urutan burung lalu bilangan yang menunjukkan status ketinggian burung dibandingkan dengan tinggi pohon tempat sarang burung tersebut. 1 apabila burung dapat mencapai ketinggian sama dengan

tinggi pohon tempat sarangnya berada atau lebih, o apabila burung tidak mampu mencapai ketinggian yang sama dengan pohon tersebut. Serta ketinggian maksimum yang dapat diperoleh oleh burung saat meluncur dengan menggunakan ketapel.

E. Proyek Praktik Lintas Bidang (PLB)

Tujuan utama dari proyek lintas bidang ini adalah menghasilkan sebuah program (dalam Bahasa C/C++) yang dapat menyelesaikan permasalahan knapsack (baik yang berjenis rational knapsack maupun 0-1 knapsack) dengan menerapkan prinsip-prinsip penyelesaian masalah yang telah dipelajari pada bagian Berpikir Komputasional. Hasil akhir yang diharapkan adalah berupa dua hal:

• Laporan analisis dan perancangan program

• Kode program yang dapat dijalankan dan memberikan solusi dari setiap masukan yang diberikan 

1. Penjelasan Permasalahan Permasalahan yang akan diselesaikan pada PLB ini adalah salah contoh dari sebuah permasalahan optimasi. Dalam dunia informatika, optimasi adalah suatu tipe permasalahan dimana kita ingin mencari nilai yang optimal (paling baik) untuk sebuah kasus permasalahan tertentu. Konsep "paling baik" dapat berarti dua hal: paling kecil (minimal) atau paling besar (maksimal), sehingga secara umum ada dua jenis permasalahan optimasi, yaitu optimasi untuk mencari nilai maksimum dan optimasi untuk mencari nilai minimum. Nilai atau besaran yang ingin dioptimalkan (minimal atau maksimal) biasa disebut sebagai fungsi tujuan (fungsi obyektif).

2. dan 0-1 Knapsack Ter Rational dan variasi dari permasalahan knapsack. Yang pertama adalah yang disebut sebagai rational knapsack. Pada permasalahan ini, setiap barang dapat dianggap sebagai barang dapat dipecah, artinya, boleh diambil sebagian saja (tidak harus semuanya). Contoh barang seperti ini adalah misalnya: air, minyak, beras, pasir, dan lain-lain. Jika Anda memiliki 10 kg minyak, Anda dapat memilih untuk mengambil hanya 7 kg dari minyak tersebut, sehingga nilai yang Anda dapatkan adalah 7/10 dari nilai total keseluruhan minyak. Karena setiap barang sifatnya dapat dipecah dan diambil sebagian, maka permasalahan rational knapsack biasanya lebih mudah diselesaikan, karena kita dapat mengatur untuk setiap barang, berapa bagian yang ingin kita ambil.