Materi Uji Olimpiade Sains Bidang Informatika/Komputer (SMA)

Bismillahirrahmaanirrahiim
Berikut ini merupakan contoh- contoh dan pembahasan  materi uji olimpiade sains bidang informatika/komputer  versi alpha-07-05-19 yang dibahas langsung oleh Bapak  Suryana Setiawan, Koordinator Pembina TOKI Pusat. Soal-soal ini saya dapatkan ketika akan mengikuti seleksi olimpiade sains bidang informatika/komputer sebagai perwakilan sekolah.

Berikut ini pembahasan dokumen tersebut:

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 sejenjang dan serentak di seluruh Indonesia, yaitu:

« tingkat kabupaten/kota, kemudian

« tingkat provinsi.

Tahun 2006, untuk bidang informatika di tingkat provinsi tercatat diikuti 480 siswa peserta 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 komputer . 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 yang tepat. Pemilihan metodologi akan menentukan efisiensi dari program yang dibuat saat dijalankan.

3. Metoda 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 sekolah sekolah 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 ntuk diadakan mengingat sejumlah alasan tertentu sehingga uji pemrograman disubstitusi dengan materi uji kemampuan algoritmika.3 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 Soal soal

Non programming

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. Aspek aspek yang terkait dengan pengetahuan dan bahasa pemrograman direduksi seminimal mungkin ke tingkat pseudocode.

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.Aspek aspek 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?

2. Memahami Sifat sifat Bilangan

Untuk sejumlah masalah, sifat sifat dari bilangan harus dipahami secara logis.

Contoh:

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

(A) n - p + 1

(B) np

(C) n2 + p2 - 1

(D) 3p + 5n

(E) (p - n)(n - p)

3. Mengkaitkan dengan Konteks Masalah

Konteks dari soal perlu diperhatikan dan konteks tersebut kadang kadang 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?

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-1) untuk setiap n > 0 dan f(0) = 1, maka berapakah f(10)/(f (7) x f(6)) ?

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?

6. Berpikir secara Cerdas

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

Contoh 1:

Berapa digit terakhir dari 22003? Apakah anda ingin menghitungnya sendiri (secara manual)?

Contoh 2:

Ketiga digit awal dari hasil perkalian 22002 x 52005 jika dijumlahkan adalah ?

Contoh 3:

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

C. Materi Uji Analitika dan Logika

Dalam pemodelan masalah pemrograman selain dengan model aritmatika, juga keterhubungan antara entitas/aspek dalam masalah perlu dipahami secara relational untuk mendapatkan model algoritmis yang lebih akurat. Kemampuan analitis tsb diperlukan dalam menghasilkan model keterhubungan/relasional tsb. Sayangnya tidak ada metodologi yang sistematik karena pada dasarnya sangat bergantung pada kreatifitas peserta uji. Namun, ada kesamaan umum dalam pemecahan masalahnya, yaitu (1)penggunaan model diagram sangat membantu untuk menggambarkan keterhubungannya secara menyeluruh berdasarkan keterhubungan yang fragmental (dari pernyataanpernyataan terpisah atau asumsi asumsi yang dibuat) (2) keterhubungan itu sendiri seringkali bersifat implisit sehingga perlu pemahaman yang hatihati dan perlu pemahaman akan gaya bahasa penceritaannya. (3) khususnya untuk asumsi yang dibuat segera dieliminasi jika kontradiksi dengan model diagram, dan model diagram yang telah dibentuk perlu diverifikasi (dikaji ulang) dengan pernyataan pernyataan yang diberikan agar terjaga konsistensi, dan selalu berpikir adanya kemungkinan yang tertinggal atau tersamar yang belum dikaji ke dalam model.

Contoh 1:

Terdapat 7 bilangan bulat A, B, C, D, E, F, dan G yang jika diurutkan membentuk deret bilangan cacah berurutan (misalnya 4,5,6,…..) dengan pernyataan pernyataan berikut:

(1) D berharga 3 kurangnya dari A

(2) B adalah angka di tengah jika semua diurutkan

(3) Kurangnya F dari B = kurangnya D dari C

(4) G lebih besar dari F

Jika diurutkan, urutannya adalah?

Contoh 2:

Delegasi delegasi dari negara W dan negara R duduk berhadap hadapan pada meja perundingan. Masing masing delegasi terdiri atas seorang ketua, dua atas militer dan dua wakil kamar dagang negara masingmasing. Delegasi W beranggotakan A, B, C, D, dan E. Delegasi R beranggotakan F, G, H, I, dan J. Masing masing delegasi berada pada sisi sisi memanjang berlainan (satu Negara pada sisi yang sama dan ketua duduk di tengah delegasinya). Batasan dalam mengatur urutan duduk mereka:

(1) Delegasi W menempatkan A dan B di kedua ujung barisannya.

(2) Kuping kanan G tuli shg ia harus paling kanan dari delegasi R.

(3) Baik D maupun F bukan ketua.

(4)Para atase militer W, salah seorangnya B, didudukkan berdampingan, dan tidak ada satupun yang berseberangan dengan atase militer R

(5) G bukan atase militer.

(6) C wakil dari kamar dagang, duduk berseberangan dengan H.

Manakah yang paling mungkin mengenai F berikut?

(A) Wakil kamar dagang yang duduk di sebelah I

(B) Wakil kamar dagang yang duduk di sebelah H

(C) Wakil kamar dagang yang duduk berseberangan dengan B

(D) Atase militer yang duduk di sebelah I

(E) Atase militer yang duduk di sebelah J

D. Materi Uji Algoritmika

Sebagaimana dalam penjelasan awal, materi uji algoritmika adalah selain menguji kemampuan dalam memahami suatu algoritma yang diberikan, juga menguji kemampuan merancang suatu algoritma pemecahan masalah yang diberikan. Namun, untuk tingkat OSK/OSP pada saat ini belum memungkinkan untuk dilakukan terutama terkendala masalah teknis pemeriksaan kebenaran jawabannya. Kemampuan dalam perancangan tersebut baru akan diujikan kemudian di tingkat OSN. Karena pada tingkat OSK/OSN ini peserta harus dapat memahami algoritma yang diberikan maka hal yang penting untuk dikuasai adalah penulisan notasi algoritma yang digunakan oleh soal soal. Penulisan algoritma mungkin menggunakan suatu cerita (bahasa sehari hari) atau mengikuti notasi/tatacara yang didefinisikan sebagai pseudopascal. Proses dari algoritma umumnya bersifat prosedural/imperatif saja.Aspek aspek yang biasanya diujikan adalah:

1. penggunaan variabel (berarti sifatsifatnya juga) dalam kaitannya dengan proses algoritma tetapi tidak berkaitan dengan sifat variabel yang spesifik pada bahasa pemrograman tertentu.

2. aliran kendali proses: blok begin end,pecabangan if then,pencabangan if then else,pencabangan case option,loop while do,loop repeat until,dan loop for.

3. ekspresi lojik dengan operator lojik and, or, xor, not,

4. pemanggilan prosedur dan fungsi dan

5. aliran proses dari algoritma (prosedur atau fungsi) rekursif

6. struktur array (satu dimensi atau lebih)

Contoh contoh

1. Diberikan fungsi berikut

function apaini(a: integer; b: integer): integer;

var x,y,r: integer;

begin

x := a;

y := b;

while (y <> 0) do

begin

r := x mod y;

x := y;

y := r;

end;

apaini := x;

end;

Pertanyaan: Jika fungsi tsb dipanggil dengan writeln (apaini(414, 662));¡¨ berapakah yang dicetaknya?

2. Diberikan fungsi berikut

function apaitu(a: integer; b: integer): integer;

begin

count := count + 1;

if (a > b) then apaitu := apaitu(b, a)

else if (a = 0) then apaitu := b

else apaitu := apaitu (b mod a, a)

end;

Pertanyaan: Jika fungsi tsb dipanggil dengan writeln (apaitu(1001, 1331));¡¨ berapakah yang dicetaknya?

3. Diberikan fungsi berikut

if (a and b) or ((not c) and d) then

if ((a or not b) and c) or (b and (not a)) then

writeln(1)

else

if (a or (d and b)) and (not b) then

writeln(2)

else

writeln(4)

else

10

if not (d and c) and (not a) then

writeln(5)

else

writeln(6);

Pertanyaan: Jika dijalankan dan ternyata mencetakkan harga 4 maka urutan harga harga a, b, c, d yang mungkin adalah?

(A) TRUE, FALSE, TRUE, FALSE

(B) TRUE, TRUE, TRUE, FALSE

(C) FALSE, FALSE, TRUE, TRUE

(D) TRUE, TRUE, FALSE, FALSE

(E) TRUE, FALSE, FALSE, TRUE

4. Suatu robot berdasarkan harga a bilangan positif yang diberikan, akan menjalankan sederetan perintah berikut (algoritma dengan penulisan bahasa seharihari):

begin

melangkah dengan jarak a ke depan,

memutar arah ke kanan tegak lurus,

melangkah sepanjang 2a,

memutar ke arah kiri tegak lurus,

melangkah sepanjang ½ a,

memutar ke arah kiri tegak lurus,

melangkah sepanjang 3½ a,

memutar ke arah kiri tegak lurus,

melangkah sepanjang a.

memutar ke arah kanan tegak lurus.

end;

Pertanyaan: ika posisi awal ada di (0, 0) dan robot sedang menghadap ke arah sumbu y positif, dengan a = 2 maka posisi akhir robot adalah ?

E. Materi Uji Programming

Pada tingkat OSN peserta akan diuji dalam materi pemrograman yang sebenarnya. Selain peserta harus menguasai pemrograman dengan bahasa yang digunakan yaitu FreePascal atau C atau C++, tetapi juga peserta harus mampu melakukan problem solving itu sendiri. Soal soal yang diberikan bukan berupa soal spesifikasi pemrograman yang eksplisit, namun permasalahan yang mana pemrograman hanya sebagai alat dalam pemecahan masalah itu sendiri. Kemampuan analitikal peserta diperlukan karena program yang nantinya dituliskan akan dijalankan dengan masukan yang sangat ekstrim sehingga dengan cara yang naif (tanpa analisis mendalam) program peserta tidak akan dapat berjalan dalam batas waktu yang diberikan. Aspek pertandingan lainnya adalah bahwa peserta harus mengerjakan soal ini dalam waktu yang terbatas pula!

Permasalahan: buatlah program yang dapat menghitung berapa banyak 0 di belakang bilangan N! dengan harga N yang sangat besar sekali (misalnya 1030) ?

Dengan contoh ini, hendak ditunjukkan bahwa masalah yang diberikan dalam materi pemrograman bukanlah semata masalah pemrograman itu saja melainkan masalah analitika yang mendalam kemudian pemrograman hanyalah sebagai realisasinya yang seringkali hanya dengan pembuatan program yang singkat/pendek semata.Pada tingkat kesulitan yang lebih tinggi hingga tingkat Olimpiade Internasional, berlaku cara berfikir demikian. Lihat pembahasan sejumlah soal contoh di website http://www.toki.or.id.

F. Penutup

Melalui dokumen ini penulis berharap peserta ataupun pembina peserta dapat menemukan intisari dan tujuan mengenai soal soal seleksi mulai dari tingkat Kabupaten/Kotamadya, tingkat Provinsi dan tingkat Nasional. Peserta yang lolos ke Tingkat Pelatihan Nasional (Pelatnas) diharapkan merupakan peserta yang memiliki kemampuan analitikal dan merancang algoritma yang tinggi. Referensi mengenai hal tersebut jauh lebih sulit ditemukan daripada referensi untuk pemrograman itu sendiri.

Tulisan awal ini merupakan versi yang perlu diolah lebih lanjut agar bisa menjadi referensi yang membantu para peserta namun diharapkan bisa memenuhi kebutuhan,sekurangnya sebagai petunjuk, bagaimana soal soal seleksi olimpiade sains bidang informatika dan komputer ini dibuat. Masukan untuk menyempurnakan tulisan ini sangat diharapkan untuk meningkatkan manfaat terutama para calon peserta dan pembina peserta dalam mempersiapkan diri menghadapi proses seleksi.