Contohcontoh dan Pembahasan Materi Uji Olimpiade Sains Bidang Informatika/Komputer

Versi: (alpha¡V07¡V05¡V19)

Oleh: Suryana Setiawan, Koordinator Pembina TOKI Pusat

A. Pengantar

1.Olimpiade Sains Nasional

Dalam beberapa tahun terakhir Departemen Pendidikan Nasional telah meyelenggarakan Olimpiade Sains Nasional (OSN) yang di antaranya terdapat bidang Informatika. Pemilihan peserta yang akan bertanding di OSN dilakukan melalui seleksi bejenjang dan serentak di seluruh Indonesia, yaitu:

« tingkat kabupaten/kota, kemudian

« tingkat provinsi.

Tahun 2006, untuk bidang informatika di tingkat provinsi tercatat diikuti 1480 siswa eserta seleksi sementara di tingkat kabupaten/kota tentunya sekian kali lebih banyak lagi (estimasi kasar ada di atas 8 ribuan siswa1). Hasil dari seleksi tingkat propinsi menentukan siapa yang akan menjadi salah seorang dari ke 90 siswa peserta OSN.

Selain sebagai ajang prestasi tingkat nasional, OSN bertujuan juga untuk mendapatkan calon peserta pembinaan dan seleksi lebih lanjut hingga dipilih empat siswa terbaik alias anggota TOKI (Team Komputer Indonesia). Mereka itulah yang akan mewakili negara dan bangsa untuk bertanding di tingkat dunia yaitu International Olympiad in Informatics (IOI).

2.International Olympiad in Informatics

IOI sendiri adalah lomba yang menguji kemampuan peserta dalam problem solving dengan pemrograman komputer2. Setiap peserta dalam waktu yang amat terbatas harus mengerjakan sejumlah masalah yang diberikan, mulai dari memahami masalahnya, merancang solusinya, dan memindahkan solusinya dengan menuliskannya sebagai suatu program komputer. Pemecahan masalahnya harus komprehensif (meliputi berbagai kasus) yang harus diidentifikasi sendiri oleh setiap peserta, programnya harus efisien

saat dijalankan (dalam waktu yang singkat untuk setiap kasus), dan tentunya menghasilkan keluaran yang sesuai dengan yang diharapkan.
Kemampuan dalam coding (menulis program) hanyalah salah satu aspek saja, yang sulit adalah dalam melakukan problem solving itu sendiri termasuk memilih metodologi.
 1. Ini hanya dugaan saja karena di tingkat kabupaten/kota, penyelenggaraan beserta proses seleksi    diserahkan ke masingmasing kabupaten/kota yang bersangkutan sehingga data peserta tidak tercatat dengan    lengkap. Sementara, di tingkat propinsi, proses seleksi di lakukan di pusat sehingga bisa diketahui jumlah   keseluruhan peserta.

 2. Harap bagian yang digarisbawahi tersebut dipahami secara lengkap; bukan HANYA menguji kemampuan membuat program komputer, bukan pula HANYA menguji kemampuan memecahkan masalah, tetapi KEDUANYA!! yang tepat. Pemilihan metodologi akan menentukan efisiensi dari program yang dibuatmsaat dijalankan.

3. Metode dan Proses Seleksi di OSN

Proses seleksinya idealnya adalah mengacu ke IOI. Namun berbeda dengan bidang OSN lain seperti Fisika, Matematika, Kimia dan Biologi, bidang informatika khususnya pemrograman belum menjadi pelajaran resmi. Kalaupun ada, hanya di sekolahsekolah tertentu saja dan itupun belum tentu mengajarkan pemrograman. Oleh sebab itu, materi uji disesuaikan agar peserta potensial secara akademis/skolastik tinggi masih dapat terjaring untuk diberikan pembinaan yang intensif. Penyesuaiannya adalah mengurangi aspek yang sangat bergantung pada ketrampilan peserta dalam pemrograman dan sebagai gantinya, digunakan materi yang biasanya disebut sebagai materi uji ¡§analisa dan logika¡¨. Pada dasarnya materi ini menguji potensi akademis/skolastik peserta yang menjadi bagian terpenting dalam kemampuan problem solving peserta.

4. Metoda dan Proses Seleksi pra OSN

Di tingkat kabupaten/kota serta propinsi komponen uji pemrograman tidak mungkin untuk diadakan mengingat sejumlah alasan tertentu sehingga uji pemrograman disubstitusi dengan materi uji kemampuan algoritmika.
Selain itu, metoda pengujiannya pun tidak bisa dihindari bersifat test obyektif (pilihan ganda). Metoda ini memang banyak sekali kelemahannya yaitu memungkinkan jawaban asal tapi benar, namun, memungkinkan pemeriksaan yang segera. Dampak negatif tersebut bisa dikurangi dengan pembuatan soal dan pilihan jawaban yang dirancang dengan matang.

5. Klasifikasi Soalsoal

Nonprogramming

Secara umum materi uji tertulis terbagi atas tiga komponen utama: materi uji analitika dan logika, materi uji aritmatika, dan materi uji algoritmika.

„« Materi analitika dan logika bertujuan untuk menguji potensi akademis (skolastik) peserta namun sedapat mungkin memiliki relevansi yang tinggi dengan problem solving dan elemen penting dalam menguasai pemrograman komputer. Kemampuan ini merupakan faktor penting dalam memahami persoalan yang diberikan dan merancang algoritma pemecahan masalahnya.

„« Materi arimatika sebenarnya sejalan dengan analitika dan logika di atas karena soal aritmatika disini bukan sekedar menguji ketrampilan dalam hitungmenghitung, tetapi lebih pada cara berpikir yang logis dan analitis namun dengan soal bertemakan aritmatika.
„« Materi algoritmika bertujuan untuk menguji kemampuan peserta dalam memahami dan menyusun suatu algoritma. Aspekaspek yang terkait dengan pengetahuan dan bahasa pemrograman direduksi seminimal mungkin ke tingkat pseudocode.

Uji pemrograman di tingkat provinsi, apalagi di tingkat kabupaten/kota, masih perlu beberapa tahun lagi hingga infrastruktur di setiap daerah sudah merata.

B. Materi Uji Aritmatika

Sekali lagi, walaupun mengambil topik mengenai aritmatika, aspek terpenting dari materi ini bukan pada hitung menghitungnya tetapi pada uji kemampuan analitisnya. Aspekaspek

analitis dalam persoalan aritmatika dijelaskan pada bagian berikut ini. 

1. Mampu Membentuk Model Aritmatika/Matematika serta melakukan deduksi/induksi Model

Dalam problem solving, seringkali diperlukan tahapan pemodelan masalah yang sebagian menggunakan model matematika/aritmatika dan menyederhanakannya sehingga menjadi model yang lebih sederhana dan siap dikomputasikan dalam bentuk algoritma. Model yang tidak tepat berakibat pada kegagalan dalam pemecahan masalah.

Contoh:

Uang Amir lebih banyak dari uang Ali. Jika dijumlahkan uang keduanya lebih dari 50 ribu rupiah, sementara selisih uang Amir dengan uang Ali lebih dari 30 ribu rupiah. Berapakah kemungkinan uang Amir yang paling tepat? Model permasalahan: Uang Amir = x, Uang Ali = y, dan dari deskripsi di atas

„« PersI:

x > y

„« PersII:

x+y > 50000

„« PersIII:

|xy|

> 30000

Dari PersI

dan PersIII:

menghasilkan PersIV:

xy

> 30000

Dari PersII

dan PersIV:

jika dijumlahkan menghasilkan 2x>80000.

Maka, x > 40000

2. Memahami Sifatsifat Bilangan

Untuk sejumlah masalah, sifatsifat dari bilangan harus dipahami secara logis

Contoh:

Jika n dan p adalah dua bilangan bulat, dan n + p berharga ganjil, manakah dari berikut ini bil ganjil?

(A) n ¡V p + 1

(B) np

(C) n2 + p2 ¡V 1

(D) 3p + 5n

(E) (p ¡V n)(n ¡V p)

A bukan, karena (n+p) adalah ganjil maka dari n dan p salah satu ganjil dan yang lain genap. Selisih antara n dan p pasti ganjil sehingga jika ditambah 1 menjadi genap.

B bulan karena perkalian antara suatu bilangan genap dengan bilangan apapun akan menjadi genap. C bukan karena pangkat bulat positif berapapun dari bilangan genap, tetap genap, dan ganjil tetap ganjil, kemudian ganjil ditambah genap dan dikurang ganjil menjadi genap.

D bukan karena pangkat bulat positif berapapun dari bilangan ganjil tetap bilangan ganjil, dan jumlah dua bilangan ganjil menjadi genap.
E benar, karena perkalian antara dua bilangan ganjil menghasilkan bilangan ganjil.

3. Mengkaitkan dengan Konteks Masalah

Konteks dari soal perlu diperhatikan dan konteks tersebut kadangkadang hanya tersirat saja. Yang dimaksud dengan konteks disini adalah pemahaman umum akan sesuatu yang sewajarnya diketahui pula.

Contoh:

jika lonceng berdentang setiap 1 detik, dalam jumlah dentang yang sesuai waktu yang ditunjukkan, maka tepat pada pukul berapa dentang terakhir yang menunjukkan jam 6? Apakah pukul 6:00:06?

Salah, seharusnya pukul 6:00:05 karena dentang dentang tsb pada pukul 6:00:00, pukul 6:00:01, pukul 6:00:02, pukul 6:00:03, pukul 6:00:04 dan pukul 6:00:05!! Konteks disini adalah dentang pertama terjadi pada tepat pukul 6, dan penomoran detik/menit dimulai dari 0, 1, ... dst.

4. Memahami Formula Rekursif

Banyak masalah pemodelan dengan tingkat kesulitan yang tinggi atau pemrogramannya sendiri memerlukan pemecahan dengan algoritma rekursif. Pemahaman fungsi rekursif membantu dalam pemahaman memahami bagaimana bekerjanya algoritma rekursif.
Contoh:

Jika didefinisikan f(n) = n f(n¡V1) untuk setiap n > 0 dan f(0) = 1, makaberapakah f(10)/(f (7) x f(6)) ?

Pahami perilaku fungsi rekursif tsb, sbb,

f(n) = n.f(n¡V1) = n.(n¡V1).f(n¡V2) = n.(n¡V1).(n¡V2).f(n¡V3) = ... = n(n¡V1)(n¡V2)(n¡V

3)....2.1 = n!

Sehingga, f(10) = 10! dan f(7) = 7! serta f(6) = 6!.

10!/7! = (10.9.8.7.6.5.4.3.2.1)/(7.6.5.4.3.2.1) = 10.9.8

Dan (10.9.8) /(6.5.4.3.2.1) = 1

5. Eksplorasi dalam Masalah Kombinatorik

Dalam problem solving seringkali masalah yang diberikan bersifat kombinatorik (mendapatkan setiap kemungkinan kombinasi / permutasi jawaban). Untuk memecahkannya terkadang seluruh kemungkinan tersebut harus diperiksa untuk mendapatkan pemecahan yang umum.
Contoh:

Jika diketahui dalam perkalian matriks A (mxn) dengan B (nxp) diperlukan biaya mnp. Sementara untuk perkalian tiga matriks A.B.C dengan A(mxn), B(nxp) dan C(pxq) ternyata terdapat dua kemungkinan biaya yang bergantung pada urutannya:

Urutan

(A.B).C (yaitu A dikali B dahulu kemudian dikali C), dan

urutan

A.(B.C) (yaitu B dikali C dahulu kemudian dikali A).

Urutan (A.B).C memerlukan harga mnp + mpq sementara urutan A.(B.C)

memerlukan harga npq + mnq. Kedua harga bisa berbeda sesuai dengan hargaharga

m, n, p, q tsb. Pertanyaannya, untuk perkalian empat matriks A.B.C.D

dengan A(10x4), B(4x15), C(15x2), dan D(2x20) manakah urutan dengan biaya

minimum?

Kemungkinankemungkinan

urutan adalah (diperoleh dengan permutasi ketiga

tanda perkalian ¡§.¡¨):

urutan

(((A.B).C).D), biaya 10x4x15+10x15x2+10x2x20 = 1300

urutan

((A.B).(C.D)), biaya10x4x15+15x2x20+10x15x20 = 4200

urutan

((A.(B.C)).D), biaya 4x15x2+10x5x2+10x2x20 = 600

urutan

(A.((B.C).D)), biaya 4x15x2+4x2x20+10x4x20 = 1080

urutan

((A.B).(C.D)), biaya 15x2x20+10x4x15+10x15x20 = 4200

urutan

(A.(B.(C.D))), biaya 15x2x20 + 4x15x20+10x4x20 = 4200

6. Berpikir secara ¡§Cerdas¡¨

Jika menghadapi suatu masalah komputasi yang kelihatannya tidak mungkin, pasti adasesuatu di balik itu!! Dapatkanlah dengan bantuan pemahaman akan sifatsifat operasi aritmatika untuk mendapatkan model matematis yang lebih sederhana.

Contoh 1:

Berapa digit terakhir dari 22003? Apakah anda ingin menghitungnya sendiri (secara manual)? Tentu tidak, pasti ada penyederhanaannya. Dengan mengubah n=1,2,3¡Kdst, perhitungan 2n menghasilkan deret 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, dst. Amati angka terakhir dari setiap bilangan, kita mendapatkan perulangan dari 6 ¡V 2 ¡V 4 ¡V 8 pada n mod 4 = 0, 1, 2, 3. Jadi jika n=2003, diperoleh 2003 mod 4 = 3, yaitu memiliki digit terakhir 8.

Contoh 2:

Ketiga digit awal dari hasil perkalian 22002 x 52005 jika dijumlahkan adalah? Ini juga tidak mungkin dihitung manual. Perhatikan bilangan dasarnya 2 dan 5 yang jika dikalikan menjadi 10. Karena setiap pasang faktor 2 dan 5 menghasilkan 10 berarti hanya menambah 0 di digit terkanan. Ada 2002 pasang faktorfaktor

tsb sehingga 22002 x 52005 = 53 x 102002= 125 102002. Penjumlahan tiga digit awal 1+2+5=8

Contoh 3:

Hitunglah (80! x 38!) /(77! x 40!).

Menggunakan sifat sbb untuk a dan b bulat positif, a > b, maka a!/b! = a.(a ¡V

1).(a ¡V 2)¡K(b + 1). Maka

(80! x 38!) /(77! x 40!) = (80!/77!) / (40!/38!)

= (80x79x78) / (40x39)

= (80/40) x (78/39) x 79

= 2 x 2 x 79 = 316

yang dapat dihitung tanpa kalkulator.