Berpikir Komputasional

Sistem komputer pada pada hakikatnya meniru dunia ini untuk dijadikan dunia digital sehingga bisa membantu atau menggantikan manusia dalam melakukan pekerjaanpekerjaan yang sulit maupun membosankan.

Berpikir komputasional (Computational Thinking) adalah metode menyelesaikan persoalan dengan menerapkan teknik ilmu komputer (informatika).

Ada 4 fondasi berpikir komputasional yang dikenal dalam ilmu  Informatika, yaitu Abstraksi, Algoritma, Dekomposisi, dan Pola, yang sangat mendasar dan secara garis besar dijelaskan sebagai berikut

1. Abstraksi, yaitu menyarikan bagian penting dari suatu permasalahan dan mengabaikan yang tidak penting  sehingga memudahkan fokus kepada solusi.
2. Algoritma, yaitu menuliskan otomasi solusi melalui berpikir algoritmik (langkah-langkah yang terurut) untuk mencapai suatu tujuan (solusi). Jika langkah yang runtut ini diberikan ke komputer dalam bahasa yang dipahami oleh komputer,  kalian akan dapat “memerintah” computer mengerjakan langkah tersebut.
3. Dekomposisi dan formulasi persoalan  sedemikian rupa sehingga dapat diselesaikan dengan cepat dan eisien                serta      optimal dengan menggunakan   komputer sebagai alat bantu. Persoalan yang sulit apalagi besar  akan menjadi mudah jika diselesaikan sebagian-sebagian secara sistematis.
4. Pengenalan pola persoalan, generalisasi serta mentransfer proses penyelesaian persoalan ke persoalan lain yang sejenis.

A. Pencarian (Searching)

Apa itu mencari? Mencari adalah menemukan “sesuatu” yang bisa berupa benda, angka, konsep, informasi yang memenuhi kriteria tertentu dalam suatu ruang pencarian.

B. Pengurutan (Sorting)

Terdapat beberapa teknik (algoritma) untuk melakukan pengurutan seperti bubble sort, insertion sort, quick sort, merge sort, dan selection sort.  Pada unit ini, hanya akan diberikan penjelasan untuk setiap tiga teknik ialah sebagai berikut.

1. Insertion Sort

Insertion Sort adalah salah satu algoritma yang digunakan untuk permasalahan pengurutan dalam list (daftar objek). Sesuai namanya, insertion sort mengurutkan sebuah list dengan cara menyisipkan elemen satu per satu sesuai dengan urutan besar kecilnya elemen hingga semua  elemen menjadi list yang terurut.

 

Ilustrasi Insertion Sort

Terdapat sebuah deret bilangan seperti berikut: 2, 3, 7, 6, 5 yang direpresentasikan dengan menggunakan kartu. Urutkan bilangan tersebut secara menaik dengan menggunakan algoritma insertion sort.

Proses Iterasi Pertama

Langkah pertama, tinjau bilangan kedua, bandingkan bilangan pertama dan kedua, yaitu 2 dan 3. Didapatkan 2 lebih kecil dari 3, maka urutan bilangantersebut tetap (2,3). (2, 3, 7, 6, 5) menjadi (2, 3, 7, 6, 5)

Proses Iterasi Kedua

Pada iterasi selanjutnya, kita mengambil bilangan ketiga, yaitu 7. Lalu bandingkan dengan bilangan sebelumnya. Karena 3 lebih kecil dari 7,  urutan tetap.

(2, 3, 7, 6, 5) menjadi (2, 3, 7, 6, 5)

Proses Iterasi Ketiga

Pada iterasi selanjutnya, kita mengambil bilangan keempat, yaitu 6. Lalu, bandingkan dengan bilangan sebelumnya. Didapatkan bahwa 7 lebih besar dari 6.

Oleh  karena itu, selanjutnya, kita akan membandingkan dengan bilangan-bilangan sebelumnya, lalu menukarnya apabila bilangan tersebut lebih besar. Pertama, kita akan membandingkan 6 dan 7. Apakah 6 lebih kecil dari 7? Karena iya,  kita akan menukar 6 dengan 7. Lalu, kita akan membandingkan lagi dengan bilangan sebelumnya, yaitu 3. Apakah 6 lebih kecil dari 3? Karena 6 tidak lebih kecil dari 3, maka 6 sudah berada pada posisi yang benar, yaitu sebelum 7 dan setelah 3.

Proses memindahkan 6 di antara 3 dan 7 ini biasa disebut penyisipan (insertion) sehingga nama algoritma ini disebut insertion sort. (2, 3, 7, 6, 5) menjadi (2, 3, 6, 7, 5)

Proses Iterasi Keempat

Pada iterasi selanjutnya, kita mengambil bilangan kelima, yaitu 5. Didapatkan bahwa 7 lebih besar dari 5. Oleh karena itu, selanjutnya, kita akan membandingkan dengan bilangan-bilangan sebelumnya, lalu menukarnya apabila bilangan tersebut lebih besar. Pertama, kita akan membandingkan 5 dan 6. Apakah 5 lebih kecil dari 6? Karena iya,  kita akan menukar 5 dengan 6. Setelah itu, kita akan mengecek dengan bilangan sebelumnya lagi, yaitu 3. Apakah 5 lebih kecil dari 3? Karena 5 tidak lebih kecil dari 3, maka 5 sudah pada posisi seharusnya, yaitu setelah 3 dan sebelum 6. Terjadi lagi proses penyisipan kartu 5 di antara 3 dan 6. (2, 3, 6, 7, 5) menjadi (2, 3, 5, 6, 7)

2. Selection sort

Selection sort merupakan algoritma pengurutan yang juga cukup sederhana, dengan algoritma mencari (menyeleksi) bilangan terkecil/terbesar (bergantung pada urut naik atau turun) dari daftar bilangan yang belum terurut dan meletakkannya dalam daftar bilangan baru yang dijaga keterurutannya.

Algoritma ini membagi daftar bilangan menjadi dua bagian, yaitu bagian terurut dan bagian yang belum terurut. Bagian yang terurut di sebelah kiri dan bagian yang belum terurut di sebelah kanan. Awalnya, semua elemen bilangan dalam daftar ialah bagian yang belum terurut, dan bagian yang terurut kosong.

1. Cari bilangan terkecil yang ada pada bagian belum terurut.
2. Tukar bilangan tersebut dengan bilangan pertama bagian belum terurut, lalu masukkan ke bagian terurut.
3. Ulangi langkah 1 dan 2 sampai bagian yang belum terurut habis

Ilustrasi urut-urutan selection sort dapat dilihat pada tabel berikut.

Secara rinci, algoritma selection sort yang dikaitkan dengan pemrograman  dijelaskan sebagai berikut.

Terdapat sebuah daftar bilangan tidak terurut seperti berikut: 2, 3, 7, 6, 5. Urutkan bilangan tersebut secara menaik dengan menggunakan algoritma selection sort.

Proses Iterasi Pertama

Data Awal:

Cari bilangan terkecil di bagian belum terurut: ditemukan 2 sebagai bilangan terkecil.

Tukar bilangan 2 dengan bilangan pertama bagian belum terurut. Geser  batas bagian yang sudah terurut ke kanan  sehingga 2 menjadi bagian yang sudah terurut. Dalam ilustrasi ini, angka yang dicetak tebal menunjukkan bilangan yang sudah terurut.

Proses Iterasi Kedua

Cari bilangan terkecil di bagian belum terurut, ditemukan angka 3 sebagai bilangan terkecil.

Tukar bilangan 5 dengan bilangan pertama bagian belum terurut, yaitu 7. Geser batas bagian yang sudah terurut ke kanan, sehingga 5 menjadi bagian yang sudah terurut.

Proses Iterasi Keempat

Cari bilangan terkecil di bagian belum terurut, ditemukan angka 6 sebagai bilangan terkecil.

C. Tumpukan (Stack) dan Antrean (Queue)

Kita akan mempelajari dua buah konsep cara penyimpanan data / objek dalam sebuah struktur yang akan menentukan urutan pemrosesan data/objek tersebut, yaitu tumpukan (stack) dan antrean (queue). Kedua konsep ini memiliki prosedur yang berbeda dalam menyimpan dan mengeluarkan data. Kedua konsep tersebut masing-masing memiliki peranan yang berbeda dan digunakan pada situasi yang berbeda pula.

Bayangkan sebuah loket di sebuah rumah sakit, di mana para pasien yang akan berobat diminta untuk mendaftar lebih dahulu di loket penerimaan serta mengisi formulir pendaftaran. Setelah formulir tersebut diisi, para pasien akan mengembalikan formulir ke loket dan menunggu dipanggil oleh petugas. Kebetulan, di pagi hari, dokter yang bertugas belum dating sehingga para pasien harus menunggu. Ketika sang dokter tiba, petugas loket akan memanggil para pasien satu per satu untuk mendapat layanan.

Perhatikan sekarang bagaimana urutan pasien itu dipanggil oleh petugas loket.

1. Misalkan, petugas loket menumpuk formulir-formulir tersebut di mana formulir yang baru diterima diletakkan di atas formulir yang sudah diterima sebelumnya, kemudian ketika Ketika memanggil pasien, petugas tersebut memanggil dengan urutan mulai dari formulir yang berada di atas tumpukan. Menurut kalian, apakah urutan tersebut adil/sesuai dengan yang diharapkan para pasien? Mengapa?
2. Bagaimana cara petugas menyusun tumpukan formulir dan/atau cara urutan memanggil para pasien dari tumpukan formulir sedemikian rupa sehingga pasien yang datang dan mengisi formulir lebih dulu, akan dipanggil lebih dulu juga (dan sebaliknya)?

Dalam dunia komputasi/informatika, terkadang, kita perlu untuk menyimpan data/objek dalam suatu urutan tertentu, untuk kemudian/sewaktu-waktu diambil/ dikeluarkan kembali, mungkin untuk diproses lebih lanjut atau untuk tujuan-tujuan lain. Ada dua cara utama kita dapat melakukan penyimpanan ini.

1. Antrean (queue): pada metode ini, objek-objek disimpan dalam metode penyimpanan yang berupa sebuah antrean sehingga objek yang pertama/ lebih dulu datang, juga akan lebih dulu keluar/selesai, layaknya sebuah antrean di loket, pintu masuk, dll. Prinsip ini disebut prinsip First In First Out (FIFO). Dalam sebuah antrean orang, misalnya, jelas orang yang pertama datang akan berada di depan antrean, dan harus menjadi yang pertama yang mendapat pelayanan.
2. Tumpukan (stack): pada metode ini, objek-objek disimpan dalam metode penyimpanan yang menyerupai sebuah tumpukan (misal: tumpukan piring). Dengan demikian, objek yang pertama/lebih dulu disimpan justru akan menjadi yang terakhir keluar. Prinsip ini disebut juga Last In First Out (LIFO). Dalam tumpukan piring, misalnya, piring pertama yang diletakkan akan berada di posisi paling bawah, dan jika kita ambil piring satu per satu dari tumpukan itu, tentunya piring yang berada di posisi paling bawah tersebut akan menjadi yang terakhir diambil. Baik dalam kehidupan sehari-hari maupun dalam dunia informatika, kedua konsep urutan penyimpanan data tersebut memiliki peran dan kegunaan masing-masing.

Ada permasalahan-permasalahan/situasi di mana antrean (FIFO) lebih cocok digunakan. Sebaliknya, ada juga permasalahan-permasalahan di mana tumpukan (LIFO) lebih tepat diterapkan.