Berpikir Komputasional dan Algoritma

Berpikir Komputasional dan Algoritma

Satu persoalan hampir selalu punya lebih dari satu cara penyelesaian. Mencari nama di daftar kontak bisa dilakukan dengan membaca satu per satu dari atas, atau dengan langsung melompat ke huruf awalnya. Keduanya benar, tetapi tidak sama cepatnya. Di kelas X dan XI kalian sudah belajar memecah masalah dan menulis program. Di kelas XII, fokusnya bergeser: membandingkan beberapa strategi algoritmik, menilai mana yang paling efisien, lalu menuliskannya sebagai program yang rapi dan modular.

Bab ini berangkat dari empat pilar berpikir komputasional yang sudah kalian kenal, yaitu dekomposisi, pengenalan pola, abstraksi, dan algoritma. Dari sana kalian akan mengenal strategi seperti brute force, greedy, divide and conquer, rekursi, dan pemrograman dinamis. Setiap strategi punya kelebihan dan keterbatasan, dan tugas kalian adalah memberi alasan mengapa satu strategi lebih layak dipilih untuk persoalan tertentu.

Gambar pengantar. Satu persoalan dapat diselesaikan dengan beberapa strategi algoritmik. Bab ini melatih kalian memilih solusi yang paling efisien dan optimal, bukan sekadar solusi yang jalan.

Bagian kedua bab ini membawa kalian ke praktik pemrograman. Program yang besar akan sulit dipelihara jika ditulis sebagai satu blok panjang. Karena itu kalian akan memakai prosedur, fungsi, dan array untuk memecah program menjadi bagian-bagian yang bisa diuji dan dipakai ulang. Kalian juga akan mengenal algoritma standar seperti pencarian dan pengurutan, serta melihat bagaimana algoritma berbasis kecerdasan buatan (AI) dipakai untuk persoalan yang tidak bisa diselesaikan dengan aturan sederhana.

Kurikulum tidak menentukan bahasa pemrogramannya. Contoh di bab ini ditulis dalam pseudocode dan Python agar mudah dibaca, tetapi gagasannya sama jika kalian memakai C, C++, atau papan Arduino.

Tujuan Pembelajaran

Setelah mempelajari bab ini, kamu diharapkan dapat:

1. mengkaji suatu persoalan dengan beberapa strategi algoritmik dan menghasilkan lebih dari satu alternatif solusi;
2. memberi alasan tentang efisiensi, kelebihan, dan keterbatasan tiap alternatif solusi;
3. memilih dan menerapkan solusi yang paling efisien dan optimal untuk dikembangkan menjadi program;
4. menjelaskan makna modularisasi dan menulis program yang memakai prosedur, fungsi, dan array;
5. mengenal proses standar sederhana seperti pencarian, pengurutan, dan penghitungan agregat;
6. menjelaskan gagasan dasar algoritma berbasis kecerdasan buatan dan kapan algoritma seperti itu diperlukan; serta
7. menilai algoritma berdasarkan performa, kemampuan dipakai ulang, dan kemudahan implementasi.

Pertanyaan Pemantik

1. Jika dua program menghasilkan jawaban yang sama, apa yang membuat salah satunya "lebih baik"?
2. Mengapa memilih pilihan yang terbaik pada setiap langkah tidak selalu menghasilkan jawaban terbaik secara keseluruhan?
3. Kapan sebuah program sebaiknya dipecah menjadi beberapa fungsi, dan kapan cukup ditulis lurus saja?
4. Mengapa pencarian di data yang sudah terurut jauh lebih cepat daripada di data yang acak?
5. Persoalan seperti apa yang membuat kita beralih dari aturan tertulis ke algoritma yang "belajar" dari data?

Peta Singkat Bab

Alur bab ini dapat diringkas sebagai berikut:

persoalan → dekomposisi, pola, abstraksi → beberapa strategi algoritmik → analisis efisiensi → solusi terpilih → program modular (prosedur, fungsi, array) → algoritma standar dan algoritma berbasis AI → penilaian performa, reuse, dan kemudahan implementasi

Bagian teori membahas tiap tahap di atas dengan contoh persoalan kecil yang bisa kalian coba sendiri. Bagian soal melatih kalian membandingkan strategi, menelusuri jalannya program, dan menulis fungsi sederhana.

Buku Pilihan

Kurikulum tidak menentukan bahasa pemrogramannya, dan Python termasuk pilihan yang cocok untuk praktik bab ini.

Belajar Python untuk Pemula

Panduan 21 bab dari nol sampai bikin proyek sendiri, dalam bahasa Indonesia yang santai. Bekal untuk bab ini ada di bagian fungsi, list (bentuk array di Python), modul, dan library, sampai proyek aplikasi dan game. Setiap contoh kode bisa langsung dijalankan di IDE online tanpa instalasi. Tersedia dalam format PDF dan EPUB.

Lihat detail buku →

---

Tim simu.konsep sedang menyiapkan simulasi interaktif untuk bab ini. Stay tuned!

Teori: Berpikir Komputasional dan Algoritma

1. Empat Pilar Berpikir Komputasional

Berpikir komputasional adalah cara memandang persoalan agar dapat diselesaikan secara sistematis, baik oleh manusia maupun oleh komputer. Cara pandang ini bertumpu pada empat pilar yang saling melengkapi.

Pilar	Pertanyaan yang diajukan	Hasilnya
Dekomposisi	Bagian-bagian kecil apa yang menyusun persoalan ini?	Daftar submasalah yang bisa dikerjakan terpisah
Pengenalan pola	Apa yang berulang atau mirip dengan persoalan yang pernah diselesaikan?	Kesamaan yang bisa dimanfaatkan
Abstraksi	Detail mana yang penting dan mana yang bisa diabaikan?	Model persoalan yang lebih sederhana
Algoritma	Langkah apa saja, dalam urutan apa, yang menghasilkan solusi?	Urutan langkah yang jelas dan dapat diulang

Keempat pilar ini tidak selalu dijalankan berurutan. Saat merancang algoritma, sering kali kita kembali ke dekomposisi karena menemukan bagian yang masih terlalu besar.

Gambar 1. Empat pilar berpikir komputasional. Proses ini berulang: hasil dari satu pilar sering membuat kita meninjau ulang pilar yang lain.

Contoh singkat. Persoalan: menyusun jadwal piket kelas selama sebulan.

• Dekomposisi: daftar siswa, daftar hari, aturan (tidak dua kali berturut-turut, beban merata).
• Pengenalan pola: jadwal minggu kedua mirip minggu pertama dengan urutan digeser.
• Abstraksi: nama siswa cukup diwakili nomor urut; warna seragam dan tempat duduk tidak relevan.
• Algoritma: putar daftar nomor urut setiap hari, lewati yang baru saja piket.

2. Menyatakan Algoritma

Algoritma adalah urutan langkah yang terbatas, jelas, dan berakhir, untuk menyelesaikan suatu persoalan. Ada tiga bentuk penulisan yang umum dipakai.

Bentuk	Kelebihan	Keterbatasan
Kalimat deskriptif	Mudah dipahami siapa saja	Bisa ambigu, sulit untuk langkah bercabang
Pseudocode	Dekat dengan bahasa pemrograman, tetap bebas dari aturan sintaks	Perlu kesepakatan gaya penulisan
Flowchart (diagram alur)	Alur bercabang dan berulang terlihat jelas	Menjadi besar untuk algoritma panjang

Contoh pseudocode untuk mencari nilai terbesar dalam sebuah daftar:

ALGORITMA CariMaks
MASUKAN: daftar bilangan A dengan n elemen
KELUARAN: nilai terbesar

maks <- A[0]
UNTUK i DARI 1 SAMPAI n-1
    JIKA A[i] > maks MAKA
        maks <- A[i]
KEMBALIKAN maks

Gambar 2. Flowchart untuk algoritma mencari nilai terbesar. Bagian yang berulang tampak sebagai panah yang kembali ke pemeriksaan kondisi.

Sifat yang harus dipenuhi algoritma yang baik:

• benar: menghasilkan keluaran yang sesuai untuk semua masukan yang sah;
• terbatas: berhenti setelah sejumlah langkah;
• jelas: setiap langkah hanya punya satu tafsir; dan
• efisien: memakai waktu dan memori secukupnya.

Dua sifat pertama adalah syarat mutlak. Dua sifat berikutnya yang membedakan solusi biasa dari solusi yang baik.

3. Ragam Strategi Algoritmik

Untuk satu persoalan, biasanya ada beberapa strategi yang bisa dipakai untuk menyusun algoritmanya. Berikut strategi yang paling sering dijumpai.

Brute force (coba semua)

Semua kemungkinan diperiksa satu per satu. Strategi ini paling sederhana dan pasti menemukan jawaban jika kemungkinannya terbatas, tetapi jumlah kemungkinan bisa meledak. Memeriksa semua urutan kunjungan 10 kota berarti memeriksa 3.628.800 urutan.

Greedy (serakah)

Pada setiap langkah, pilih opsi yang tampak paling menguntungkan saat itu, tanpa meninjau ulang. Cepat dan mudah ditulis, tetapi tidak selalu menghasilkan jawaban terbaik secara keseluruhan.

Contoh: memberi kembalian Rp 6.000 dengan pecahan 5.000, 1.000, dan 500. Greedy mengambil 5.000 lalu 1.000, total dua lembar, dan itu memang optimal. Namun jika pecahannya 4.000, 3.000, dan 1.000, greedy mengambil 4.000 lalu 1.000 dua kali (tiga lembar), padahal 3.000 dua kali hanya dua lembar.

Divide and conquer (bagi dan taklukkan)

Persoalan dibagi menjadi beberapa bagian yang lebih kecil dan sejenis, tiap bagian diselesaikan, lalu hasilnya digabung. Pencarian biner dan merge sort memakai strategi ini.

Rekursi

Algoritma memanggil dirinya sendiri untuk versi persoalan yang lebih kecil, sampai mencapai kasus dasar yang jawabannya langsung diketahui. Rekursi adalah cara alami menuliskan divide and conquer.

def faktorial(n):
    if n <= 1:          # kasus dasar
        return 1
    return n * faktorial(n - 1)   # kasus rekursif

Pemrograman dinamis (dynamic programming)

Jika submasalah yang sama muncul berulang kali, hasilnya disimpan agar tidak dihitung ulang. Menghitung bilangan Fibonacci ke-40 secara rekursif murni memerlukan ratusan juta pemanggilan; dengan menyimpan hasil, cukup 40 langkah.

Backtracking (runut balik)

Solusi dibangun langkah demi langkah. Begitu satu langkah terbukti tidak mungkin menghasilkan solusi, langkah itu dibatalkan dan dicoba pilihan lain. Cocok untuk teka-teki seperti sudoku atau penempatan jadwal dengan banyak batasan.

Gambar 3. Empat strategi algoritmik pada persoalan yang serupa. Perbedaannya terletak pada cara ruang kemungkinan dijelajahi.

Ringkasan kelebihan dan keterbatasan:

Strategi	Kelebihan	Keterbatasan	Cocok untuk
Brute force	Pasti benar, mudah ditulis	Sangat lambat untuk masukan besar	Masukan kecil, pembanding untuk menguji solusi lain
Greedy	Cepat, sederhana	Bisa salah jika pilihan lokal tidak menjamin optimal global	Persoalan yang terbukti punya sifat greedy
Divide and conquer	Efisien untuk data besar	Perlu langkah penggabungan yang tepat	Pencarian, pengurutan
Pemrograman dinamis	Menghindari hitung ulang	Perlu memori untuk menyimpan hasil	Persoalan dengan submasalah berulang
Backtracking	Menemukan semua solusi yang memenuhi batasan	Bisa lambat tanpa pemangkasan yang baik	Teka-teki, penjadwalan berbatasan

4. Mengukur Efisiensi

Dua algoritma yang sama-sama benar dibandingkan dari waktu (berapa banyak langkah) dan memori (berapa banyak ruang penyimpanan). Karena kecepatan komputer berbeda-beda, yang dibandingkan bukan detik, melainkan bagaimana jumlah langkah tumbuh ketika ukuran masukan $n$ bertambah. Pertumbuhan ini ditulis dengan notasi $O$ (dibaca "big-O").

Notasi	Sebutan	Contoh	Jika $n$ menjadi 2 kali lipat, langkah menjadi
$O(1)$	konstan	mengambil elemen ke-$i$ dari array	tetap
$O(\log n)$	logaritmik	pencarian biner	bertambah 1 langkah
$O(n)$	linear	pencarian berurutan, mencari nilai terbesar	2 kali lipat
$O(n \log n)$	linearitmik	merge sort	sedikit lebih dari 2 kali lipat
$O(n^2)$	kuadratik	bubble sort, selection sort	4 kali lipat
$O(2^n)$	eksponensial	mencoba semua himpunan bagian	kuadrat dari sebelumnya

Contoh perbandingan. Mencari satu nama di daftar berisi $n$ nama:

• Pencarian berurutan memeriksa dari awal sampai ketemu. Kasus terburuk memeriksa semua $n$ nama, jadi $O(n)$.
• Pencarian biner hanya bisa dipakai jika daftar sudah terurut. Setiap langkah membuang setengah daftar, sehingga banyaknya langkah kira-kira

Untuk $n = 1.000.000$, pencarian berurutan bisa sampai satu juta pemeriksaan, sedangkan pencarian biner cukup sekitar 20 pemeriksaan.

Gambar 4. Pertumbuhan jumlah langkah untuk beberapa kelas efisiensi. Perbedaan yang kecil pada $n$ kecil menjadi sangat besar pada $n$ besar.

Catatan penting: notasi $O$ menggambarkan kasus terburuk dan mengabaikan konstanta. Untuk data yang sangat kecil, algoritma $O(n^2)$ yang sederhana bisa saja lebih cepat daripada algoritma $O(n \log n)$ yang rumit.

5. Memilih Solusi Terbaik

"Terbaik" tidak selalu berarti "paling cepat". Pemilihan solusi mempertimbangkan beberapa hal sekaligus.

1. Kebenaran: apakah solusi benar untuk semua masukan yang sah, termasuk kasus tepi seperti daftar kosong atau nilai negatif?
2. Efisiensi waktu: bagaimana pertumbuhannya untuk ukuran data yang sebenarnya akan dihadapi?
3. Efisiensi memori: apakah memerlukan penyimpanan tambahan, dan apakah itu tersedia?
4. Kemudahan implementasi: seberapa besar peluang salah tulis, dan seberapa mudah orang lain memahaminya?
5. Kemampuan dipakai ulang: apakah solusinya bisa dipakai untuk persoalan serupa tanpa banyak perubahan?

Solusi yang optimal adalah solusi yang memberi hasil terbaik menurut ukuran yang ditetapkan (misalnya jumlah lembar kembalian paling sedikit). Solusi yang efisien adalah solusi yang mencapai hasil itu dengan sumber daya paling hemat. Keduanya perlu dibedakan: greedy pada contoh kembalian tadi efisien, tetapi tidak selalu optimal.

Kebiasaan yang baik: mulailah dengan solusi brute force yang pasti benar untuk masukan kecil, lalu pakai hasilnya untuk menguji solusi yang lebih cepat.

6. Modularisasi: Prosedur, Fungsi, dan Array

Program yang panjang sulit dibaca, diuji, dan diperbaiki. Modularisasi memecah program menjadi bagian-bagian kecil yang masing-masing punya satu tugas jelas.

Prosedur dan fungsi

• Prosedur adalah blok perintah bernama yang mengerjakan sesuatu, misalnya mencetak tabel.
• Fungsi adalah blok bernama yang menerima masukan (parameter) dan mengembalikan nilai.

Di Python keduanya ditulis dengan kata kunci yang sama, def. Perbedaannya pada ada tidaknya nilai balik.

def rata_rata(nilai):          # fungsi: mengembalikan nilai
    return sum(nilai) / len(nilai)

def cetak_laporan(nama, nilai):   # prosedur: hanya menampilkan
    print(nama, "rata-rata:", rata_rata(nilai))

Manfaat modularisasi:

Manfaat	Penjelasan
Mudah diuji	Tiap fungsi bisa diuji sendiri dengan masukan kecil
Mudah diperbaiki	Kesalahan dicari di satu fungsi, bukan di seluruh program
Dipakai ulang	Fungsi yang sama dipanggil dari banyak tempat, atau dipakai di program lain
Mudah dibaca	Nama fungsi menjelaskan maksud, tanpa perlu membaca isinya

Pedoman praktis: satu fungsi mengerjakan satu hal, namanya berupa kata kerja yang jelas, dan panjangnya cukup pendek untuk dibaca dalam satu layar.

Array (larik)

Array menyimpan sekumpulan data sejenis dalam satu nama, diakses dengan indeks yang dimulai dari 0. Di Python peran ini dijalankan oleh list. Di C atau Arduino, array dideklarasikan dengan ukuran tetap.

suhu = [31.5, 32.0, 30.8, 33.1]
print(suhu[0])        # 31.5
print(len(suhu))      # 4
for s in suhu:        # menelusuri seluruh elemen
    print(s)

Array memungkinkan satu algoritma yang sama dipakai untuk 4 data maupun 4 juta data, tanpa mengubah kodenya.

Gambar 5. Program modular. Program utama hanya mengatur urutan pemanggilan; pekerjaan sebenarnya dilakukan oleh fungsi-fungsi kecil yang bisa diuji terpisah.

7. Algoritma Standar

Beberapa proses muncul di hampir semua program, sehingga algoritmanya sudah baku dan sebaiknya dikenali.

Proses	Algoritma umum	Efisiensi	Catatan
Pencarian	pencarian berurutan	$O(n)$	data boleh acak
Pencarian	pencarian biner	$O(\log n)$	data harus terurut
Pengurutan	bubble sort, selection sort, insertion sort	$O(n^2)$	sederhana, cocok untuk data kecil
Pengurutan	merge sort, quick sort	$O(n \log n)$	untuk data besar
Agregasi	jumlah, rata-rata, nilai terbesar dan terkecil	$O(n)$	satu kali lewat
Penghitungan	menghitung frekuensi kemunculan	$O(n)$	memakai tabel atau kamus

Contoh pencarian biner sebagai fungsi:

def cari_biner(data, target):
    kiri, kanan = 0, len(data) - 1
    while kiri <= kanan:
        tengah = (kiri + kanan) // 2
        if data[tengah] == target:
            return tengah
        elif data[tengah] < target:
            kiri = tengah + 1
        else:
            kanan = tengah - 1
    return -1      # tidak ditemukan

Contoh selection sort, yang tiap putaran memilih nilai terkecil dan menaruhnya di depan:

def urutkan_seleksi(data):
    n = len(data)
    for i in range(n - 1):
        idx_min = i
        for j in range(i + 1, n):
            if data[j] < data[idx_min]:
                idx_min = j
        data[i], data[idx_min] = data[idx_min], data[i]
    return data

Bahasa pemrograman modern menyediakan fungsi bawaan untuk proses ini, misalnya sorted() di Python. Memakai fungsi bawaan biasanya lebih cepat dan lebih aman. Namun memahami algoritmanya tetap penting agar kalian bisa memilih dan menilai fungsi mana yang tepat.

8. Algoritma Berbasis Kecerdasan Buatan

Algoritma yang dibahas sejauh ini bekerja dengan aturan yang ditulis lengkap oleh pemrogram. Ada persoalan yang aturannya terlalu rumit atau tidak diketahui, misalnya mengenali tulisan tangan atau memilah surel spam. Untuk persoalan seperti ini dipakai algoritma kecerdasan buatan (AI), khususnya pembelajaran mesin (machine learning), yang menyusun aturannya sendiri dari contoh data.

Perbedaan pendekatannya:

Aspek	Algoritma berbasis aturan	Algoritma berbasis AI
Sumber aturan	ditulis pemrogram	dipelajari dari data contoh
Masukan utama	data yang akan diproses	data latih berlabel, lalu data baru
Hasil	pasti sama untuk masukan yang sama	berupa perkiraan dengan tingkat keyakinan
Cocok untuk	aturan jelas dan terbatas	pola rumit, data banyak

Beberapa algoritma AI yang sederhana untuk dikenali:

• k-tetangga terdekat (k-NN): data baru diberi label yang sama dengan mayoritas dari $k$ data latih yang paling mirip dengannya. Kemiripan diukur dengan jarak, misalnya jarak Euclid antara dua titik $(x_1, y_1)$ dan $(x_2, y_2)$:

• Pohon keputusan: serangkaian pertanyaan ya/tidak yang disusun dari data, mirip flowchart yang dibuat otomatis.
• Pencarian heuristik: pencarian jalur yang memakai perkiraan jarak ke tujuan untuk memilih langkah berikutnya, dipakai pada peta digital dan permainan.

Dalam praktik, algoritma ini tidak ditulis dari nol, melainkan dipanggil dari library siap pakai. Peran pemrogram adalah menyiapkan data, memilih algoritma, dan menilai hasilnya.

Gambar 6. Klasifikasi dengan k-tetangga terdekat. Data baru diberi label berdasarkan mayoritas tetangga terdekatnya.

Yang perlu dinilai pada algoritma berbasis AI bukan hanya kecepatan, tetapi juga akurasi pada data yang belum pernah dilihat, dan keadilan terhadap kelompok data yang jarang muncul. Hasilnya berupa perkiraan, sehingga harus diperlakukan sebagai bantuan pengambilan keputusan, bukan kebenaran mutlak.

9. Menilai dan Memilih Algoritma

Bab ini ditutup dengan kemampuan yang paling dituntut di kelas XII: memberi alasan mengapa satu algoritma dipilih. Gunakan tiga ukuran berikut sebagai kerangka penilaian.

Ukuran	Pertanyaan pemandu	Bukti yang bisa dikumpulkan
Performa	Seberapa cepat dan hemat memori untuk ukuran data yang nyata?	Kelas $O$, hasil pengukuran waktu pada beberapa ukuran masukan
Kemampuan dipakai ulang	Bisakah dipakai untuk persoalan serupa tanpa ditulis ulang?	Fungsi dengan parameter jelas, tidak bergantung data tertentu
Kemudahan implementasi	Seberapa mudah ditulis, dibaca, dan diperbaiki oleh orang lain?	Panjang kode, jumlah kasus khusus, kejelasan nama

Contoh penerapan. Sebuah aplikasi sekolah perlu mencari nama siswa dari daftar 500 nama, dan daftar itu jarang berubah.

• Pencarian berurutan: implementasi paling mudah, performa $O(n)$, untuk 500 nama masih sangat cepat.
• Pencarian biner: performa $O(\log n)$, tetapi daftar harus dijaga tetap terurut setiap ada perubahan.
• Keputusan yang masuk akal: untuk 500 nama, pencarian berurutan sudah cukup dan lebih mudah dipelihara. Jika daftar tumbuh menjadi ratusan ribu nama, pencarian biner atau tabel hash layak dipertimbangkan.

Kesimpulan penting dari contoh ini: algoritma yang "paling canggih" belum tentu pilihan terbaik. Pilihan terbaik adalah yang sesuai dengan ukuran persoalan, batasan sumber daya, dan orang yang akan memeliharanya.

Rangkuman

• Berpikir komputasional bertumpu pada dekomposisi, pengenalan pola, abstraksi, dan algoritma.
• Algoritma dapat ditulis sebagai kalimat deskriptif, pseudocode, atau flowchart; harus benar, terbatas, jelas, dan sebaiknya efisien.
• Satu persoalan bisa diselesaikan dengan beberapa strategi: brute force, greedy, divide and conquer, rekursi, pemrograman dinamis, backtracking. Masing-masing punya kelebihan dan keterbatasan.
• Efisiensi dibandingkan lewat pertumbuhan jumlah langkah terhadap ukuran masukan, ditulis dengan notasi $O$.
• Modularisasi dengan prosedur, fungsi, dan array membuat program mudah diuji, diperbaiki, dan dipakai ulang.
• Pencarian, pengurutan, dan agregasi adalah algoritma standar yang perlu dikenali walau sudah tersedia sebagai fungsi bawaan.
• Algoritma berbasis AI menyusun aturannya dari data dan hasilnya berupa perkiraan, sehingga perlu dinilai akurasinya.
• Algoritma dipilih berdasarkan performa, kemampuan dipakai ulang, dan kemudahan implementasi, sesuai ukuran persoalan yang nyata.