Computer

  1. Computer is a system
  2. It receives inputs, processes it, and produces outputs
  3. Without losing generality, we can restrict input as string of 0 and 1
    • Any object can be represented as string of 0 and 1
  4. Output of the system also string of 0 and 1
  5. In general, there’s no restriction on how the system mapping input to output
  6. Because of physical limitation, system can only receive input and produce output string in limited size at a time
  7. It is desirable for the system to be able to store the current output and feed it as an input for later processing
    • There’s feedback line from output to input.
    • Capability of storing outputs is done using memory of the system
  8. Because there are many strings stored in memory, the system should be able to distinguish one from the other
    • There’s an address for every place to put string in memory

Man Page of SRILM’s ngram-discount in PDF

For easy reading, i converted man page of SRILM’s ngram-discount to PDF with LaTeX. Enjoy.

Sebuah Permainan Simbol

Misalkan kita memiliki sekumpulan simbol berikut A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, ∧, ¬, ), dan (. Sebelum kita menentukan aturan-aturan dalam permainan ini, mari kita kelompokkan dulu simbol-simbol tersebut ke dalam 3 kelompok.

Kelompok simbol 1 kita sebut term. Term terdiri dari simbol-simbol A sampai dengan Z.
Kelompok simbol 2 kita sebut konektif. Konektif terdiri dari simbol-simbol ∧, dan ¬.
Kelompok terakhir atau kelompok simbol 3 kita sebut punctuation. Puncutation terdiri dari ( dan ).

Aturan Permainan

  1. Permainan ini dimainkan oleh 1 orang
  2. Tujuan dari permainan ini adalah untuk mencari kalimat, yaitu sekumpulan simbol yang dituliskan berdampingan, dari satu atau lebih kalimat asal yang kita sebut aksioma. Atau bisa juga untuk mencari nilai (0 atau 1) dari sebuah kalimat.
  3. Pembentukan kalimat dari simbol-simbol tidak dilakukan secara sembarang. Akan tetapi, harus sesuai aturan berikut.
    1. Kalimat baru dapat dibentuk dengan menambahkan konektif ¬ terhadap term. Contoh ¬A.
    2. Kalimat baru dapat dibentuk dengan menambahkan konektif ∧ terhadap dua term dengan ditambahkan punctuation di kiri dan kanannya. Contoh, (A ∧ B).
    3. Setiap kalimat baru yang terbentuk dapat disebut juga term. Dengan demikian, kita dapat membentuk kalimat seperti ini: ¬(A ∧ ¬B)
  4. Setiap term bernilai 1 atau 0
  5. Jika A bernilai 1, maka ¬A bernilai 0, dan kebalikannya.
  6. Jika A bernilai 0 dan B bernilai 0, maka (A ∧ B) bernilai 0.
  7. Jika A bernilai 0 dan B bernilai 1, maka (A ∧ B) bernilai 0.
  8. Jika A bernilai 1 dan B bernilai 0, maka (A ∧ B) bernilai 0.
  9. Jika A bernilai 1 dan B bernilai 1, maka (A ∧ B) bernilai 1.

Aturan 6 – 9 dapat dituliskan dalam bentuk Tabel 1.

Tabel 1. Aturan 6 – 9 dalam tabel
tabel1

Contoh 1. Carilah nilai dari kalimat (A ∧ ¬A)! Jawab: Jika A adalah 0, maka ¬A adalah 1 dan jika A adalah 1 maka ¬A adalah 0. Dengan demikian, nilai dari kalimat (A ∧ ¬A) dapat dilihat di Tabel 2.

Tabel 2. Contoh 1
tabel 2

Suatu kalimat yang selalu bernilai 0, disebut dengan kontradiksi

Contoh 2. Carilah nilai dari kalimat ¬(¬A ∧ ¬B)! Jawaban dapat dilihat di Tabel 3.

Tabel 3. Contoh 2
tabel3

Kita memperkenalkan konektif baru untuk menyingkat kalimat ¬(¬A ∧ ¬B) yaitu dengan konektif ∨. Dengan demikian, ¬(¬A ∧ ¬B) ditulis juga (A ∨ B). Jawaban untuk Contoh 2 dengan konektif ∨ dapat dilihat di Tabel 4.

Tabel 4. Contoh 2 dengan konektif ∨
tabel4

Contoh 3. Tentukan nilai dari kalimat (B ∨ ¬A)! Jawaban dapat dilihat di Tabel 5.

Tabel 5.  Contoh 3
tabel5

Kita memperkenalkan konektif baru untuk menyingkat kalimat (B ∨ ¬A). Konektif tersebut adalah konektif ⇒. Dengan demikian, (B ∨ ¬A) dapat ditulis (A ⇒ B). Perhatikan urutan A dan B!. Jawaban untuk Contoh 3 dengan notasi ⇒ dapat dilihat di Tabel 6.

Tabel 6. Contoh 3 dengan konektif ⇒
tabel6

Complete Fair Grading*

Pendahuluan

Untuk dapat menentukan seorang mahasiswa lulus, dosen biasanya menentukan nilai ambang tertentu, misal 80. Jadi misalnya, jika dalam ujian pilihan ganda terdapat 100 soal, siswa dapat lulus jika menjawab benar 80 soal dengan asumsi jawaban salah tidak dihitung minus.

Tulisan ini akan mengajukan suatu pendapat yang mengatakan bahwa pemberian ambang batas yang tetap tidaklah adil untuk mahasiswa. Hal ini disebabkan pemberian ambang batas seperti itu menafikan faktor yang dipengaruhi oleh kompetensi dosen dalam penguasaan dan penyampaian materi di kelas.

Tulisan ini akan dimulai dengan sedikit membahas esensi dari kegiatan belajar mengajar di dalam kelas di sebuah perguruan tinggi. Berbeda dengan tren yang muncul sekarang, yang memiliki kecenderungan untuk menilai kegiatan belajar mengajar di kelas seharusnya sebagai kegiatan yang bertujuan untuk mengembangkan potensi siswa, saya akan kembali ke sudut pandang lama, yang menyatakan bahwa kegiatan belajar mengajar di kelas di perguruan tinggi adalah sebuah kegiatan transfer pengetahuan.

Di bagian selanjutnya, saya akan membahas mengenai konsekuensi sudut pandang kegiatan belajar mengajar sebagai transfer pengetahuan terhadap penilaian siswa. Di bagian ini saya juga akan mendaftarkan faktor-faktor yang mempengaruhi kelulusan siswa dalam kegiatan belajar mengajar. Di sini saya akan menguraikan alasan cara penilaian yang ada sekarang tidaklah adil (fair) terhadap mahasiswa.

Di bagian terakhir, saya akan menguraikan usulan mengenai cara penilaiai yang lebih adil untuk mahasiswa dengan memperhatikan faktor-faktor yang mempengaruhi kelulusan mahasiswa dalam satu matakuliah.

Transfer Pengetahuan

Tujuan pendidikan tentu saja adalah untuk mengembangkan potensi dari peserta didik. Hal ini sangat disadari oleh para pendidik. Akan tetapi, bagaimana caranya? Tidak banyak yang tahu.

Di Sekolah Dasar hingga Menengah Atas, prinsip pengembangan potensi ini sangat bagus diterapkan. Di sini, tidak seharusnya siswa dibebani dengan materi pembelajaran yang terlalu banyak. Yang paling penting adalah pengembangan pola pikir dan karakter mereka. Inilah yang akan menjadi bekal mereka untuk bersaing di lapangan sesungguhnya.

Di perguruan tinggi, adalah salah kaprah jika kurikulum masih mengacu kepada pengembangan potensi siswa. Minat seharusnya sudah terpilah di tahap seleksi perguruan tinggi sehingga setiap siswa yang masuk perguruan tinggi seharusnya sudah berada di lapangannya masing-masing. Jika sudah ada di lapangannya masing-masing, tugas perguruan tinggi adalah mentransfer ilmu dan keterampilan sebanyak-banyaknya sehingga mereka menjadi cakap untuk hidup di lapangan yang sesungguhnya.

Apakah ini berarti pembentukan karakter mereka diabaikan? Tentu saja tidak. Pembentukan karakter adalah bagian dari interaksi antarmanusia. Pembentukan karakter dapat dilakukan dalam kehidupan sosial mahasiswa. Pembentukan karakter dapat dilakukan dalam kegiatan ekstrakurikuler, atau unit kegiatan mahasiswa. Pembentukan karakter, pembelajaran etika dan moral dapat disisipkan dalam aturan-aturan yang berlaku di perguruan tinggi tersbut.

Akan tetapi di kurikulum? Bukan tugas kurikulum di perguruan tinggi untuk membangun karakter mahasiswa, apalagi membentuk karakter. Karakter siswa haruslah sudah terbentuk yaitu di bangku sekolah dasar hingga sekolah menengah. Apalagi, apakah kita yakin, apakah dengan akal sehat kita sejujurnya sependapat, bahwa nilai-nilai dapat diterapkan melalui kegiatan belajar mengajar di dalam kelas?

Penilaian Mahasiswa

Dengan dikembalikannya sifat kegiatan belajar mengajar di kelas sebagai suatu kegiatan yang tujuannya adalah transfer ilmu, evaluasi terhadap keberhasilan transfer ilmu ini dapat dilakukan dengan cara ujian, baik tertulis maupun lisan atau praktik.

Seorang mahasiswa dikatakan lulus atau berhasil dalam proses transfer ilmu ini jika dia telah berhasil menyerap materi yang diajarkan di kelas. Pertanyaannya adalah, berapa banyak materi?

Seperti yang sudah disinggung di bagian Pendahuluan, dosen biasanya menentukan angka tertentu dalam ujian. Angka tersebut harus dilewati (atau minimal disamai) jika mahasiswa ingin lulus ujian. Pertanyaan berapa angka tersebut seharusnya, tidak pernah muncul menjadi bahan kajian dosen. Kalaupun sempat disinggung di rapat koordinasi, pembahasan hanya seperti menentukan angka tersebut berdasarkan perasaan masing-masing dosen. Angka muncul jadinya merupakan kesepakatan dosen tanpa penjelasan yang jelas dan valid mengenai alasan dipilihnya angka tersebut. Paling bagus angka itu didasarkan pada pengalaman dosen di tahun-tahun sebelumnya. Jika tahun sebelumnya dosen-dosen mendapatkan bahwa angka 80 terlalu tinggi, hasil rapat koordinasi hampir dapat dipastikan akan mengeluarkan nilai yang di bawah angka 80 tersebut. Lalu, bagaimana sebenarnya menentukan angka yang tepat sehingga angka yang menjadi penting ini, karena menentukan nasib mahasiswa, dapat dipertanggungjawabkan secara ilmiah?

Hal pertama yang dapat kita lakukan adalah mengetahui faktor-faktor yang mempengaruhi pencapaian nilai seorang mahasiswa. Faktor-faktor ini dapat berjumlah tak berhingga karena satu faktor akan dipengaruhi oleh banyak faktor yang lain sehingga sebenarnya semua faktor saling kait-mengait. Di daftar berikut ini, penulis berusaha untuk menuliskan faktor yang penting saja. Bukan tidak mungkin ada faktor yang terlewatkan oleh penulis.

  1. Tingkat kepintaran mahasiswa
  2. Minat mahasiswa (yang menentukan tingkat kerajinan)
  3. Suasana Lingkungan kelas dan rumah
  4. Kondisi saat ujian
  5. Tingkat kesulitan soal ujian
  6. Kemampuan dosen (kompetensi dan cara penyampaian)

Dari sekian faktor tersebut, hanya nomor 1 dan nomor 5 saja yang kurang lebih menjadi pertimbangan dosen untuk menentukan ambang batas nilai kelulusan. Nomor 2 rasanya tidak lagi menjadi wewenang dosen di dalam kelas, nomor 2 seharusnya menjadi kepedulian pihak institusi secara keseluruhan untuk menentukan bahwa mahasiswa yang diterima adalah mahasiswa yang memang tertarik dengan program studi yang diajarkan.

Nomor 3 dan 4 sifatnya sangat kondisinal, dan meski dapat berpengaruh terhadap hasil ujian seseorang, dosen dan institusi tidak terlalu dapat mengendalikan faktor ini. Yang paling menarik adalah nomor 6. Faktor inilah yang sebenarnya dilupakan. Padahal, faktor ini sangat dominan berperan untuk menentukan kelulusan seorang mahasiswa. Inilah mengapa saya mengatakan bahwa cara-cara lama untuk menentukan ambang batas kelulusan tidaklah adil untuk mahasiswa.

Complete Fair Grading

Kurikulum, dan turunannya, menentukan materi yang harus disampaikan di kelas. Mari kita kuantifikasi jumlah materi ini dengan angka 100%. Asumsikan bahwa seorang dosen telah menyampaikan materi tersebut seluruhnya. Dengan kata lain, dosen tersebut sudah menyampaikan materi 100%. Oleh karena kemampuan mahasiswa tidak sama, jumlah materi yang dapat diserap oleh mahasiswa tidaklah sama. Jumlah materi itu dapat berkisar antara 0%-100%.

Selain ditentukan oleh kemampuan mahasiswa, kemampuan dosen juga mempengaruhi jumlah materi yang dapat diserap oleh mahasiswa. Di gambar-gambar berikut ditunjukkan keadaan yang dapat terjadi dalam transfer pengetahuan ini.

gambar_1

Gambar 1: Model transfer pengetahuan ideal dari dosen ke mahasiswa

Di Gambar 1 ditunjukkan keadaan ideal. Dalam kasus ideal ini, seluruh materi (lingkaran paling kiri) dimengerti sepenuhnya oleh dosen (lingkaran tengah). Oleh karena kompetensi dan kemampuan menyampaikan yang baik, dosen dapat mentransfer dengan baik semua dari materi yang diajarkan (ditunjukkan dengan label pada garis antara Dosen dan Mahasiswa). Dengan tingkat kemampuan penyerapan mahasiswa yang tinggi, semua yang disampaikan oleh dosen pun dapat diterima (lingkaran paling kanan).

gambar_2

Gambar 2: Model transfer pengetahuan realistis dari dosen ke mahasiswa

Kejadian yang lebih realistis ditunjukkan Gambar 2. Di gambar ini, dosen bisa jadi tidak mengerti materi sepenuhnya, tapi hanya sebagian besar. Selain itu, dosen juga tidak sempurna dalam teknik penyampaian, terutama dalam materi yang rumit. Kemampuan mahasiswa juga tidak seluruhnya baik sehingga yang berhasil disampaikan dosen, tidak semua dapat diserap. Dengan demikian, hanya 70% materi yang dapat ditangkap oleh mahasiswa.

gambar_3

Gambar 3: Model transfer pengetahuan untuk dosen yang tidak kompeten

Meskipun kejadian di Gambar 2 adalah kejadian yang realistis, bukan tidak mungkin kejadian yang ditunjukkan di Gambar 3 juga terjadi. Di sini, dosen yang mengajar hanya menguasai setengah dari materi yang harus diajarkan.

Selain itu, kemampuan penyampaiannya yang kurang menyebabkan mahasiswa hanya mendapatkan porsi kecil dari pengetahuan yang harusnya didapatkan.

gambar_4

Gambar 4: Model transfer pengetahuan untuk mahasiswa dengan kemampuan rendah

Di Gambar 4 ditunjukkan jika mahasiswa tidak memiliki minat atau kemampuan yang cukup untuk menangkap materi yang disampaikan oleh dosen. Meskipun dosen yang mengajar sudah cukup baik, namun pada akhirnya porsi pegetahuan yang didapatkan oleh mahasiswa tetaplah kecil.

Dari kejadian-kejadian yang telah digambarkan, dapat dilihat bahwa kuantitas pengetahuan yang dapat diserap oleh mahasiswa, bergantung pada seberapa besar pengetahuan yang dapat disampaikan dengan baik oleh dosen. Bagaimana cara mengukur ini?

Andaikanlah mahasiswa terpintar di kelas dapat menyerap 100% persen dari materi efektif yang disampaikan oleh dosen. Jika materi yang disampaikan itu efektif 80%, maka mahasiswa terpintar itu hanya akan memiliki 80% dari materi yang diwajibkan di kurikulum.

Jika kita ingin memberikan ambang nilai yang adil, nilai batas tidak boleh lebih dari nilai materi yang efektif diberikan dosen. Artinya, jika dosen menyampaikan 80% materi, tidak boleh kita memberikan ambang di angka 90. Lebih dari itu, tidak adil juga untuk tidak mempertimbangkan mahasiswa yang kemampuannya rata-rata. Untuk itu, ada baiknya jika ambang ditentukan dengan cara menentukan persentasi dari materi efektif yang disampaikan oleh dosen.

Contoh, jika materi efektif itu 80%, dosen dapat memberikan ambang angka 60 untuk kelulusan. Artinya, mahasiswa dianggap lulus jika dia dapat memahami 60/80 × 100% = 75% dari materi efektif yang disampaikan oleh dosen. Bagimana cara menghitung materi efektif yang disampaikan oleh dosen? Caranya adalah dengan melihat nilai tertinggi ujian. Nilai tertinggi ini dapat diasumsikan didapat oleh mahasiswa paling pintar yang dapat menyerap 100% dari semua materi efektif yang disampaikan oleh dosen.

∗Ingo Molnar menulis algoritma Complete Fair Scheduler (CFS) untuk penjadwalan proses di Linux 2.6. Judul ini mengambil insipirasi dari nama algoritma tersebut.

Sudoku, Matematika, dan 1 Juta Dollar Amerika

Pernah bermain Sudoku? Jika pernah, mungkin Anda bermain Sudoku untuk mengisi waktu senggang. Atau mungkin karena Anda senang teka-teki yang menantang. Apapun itu, pernahkah terpikir oleh Anda bahwa Sudoku juga ternyata menarik bagi para peneliti di dunia?

Di balik Sudoku, terdapat pertanyaan-pertanyaan yang membuat greget para peneliti. Beberapa pertanyaan tersebut tidak bisa dijawab hingga saat ini.Sementara beberapa lain terjawab setelah dilakukan penghitungan superkomputer selama hampir 1 tahun. Begitu rumitkah Sudoku? Dan apa hubungan Sudoku, Matematika, dengan uang 1 juta dollar Amerika? Untuk menjawab pertanyaan itu, mari kita mulai dari apa itu Sudoku.

Sudoku adalah sejenis teka-teki. Dalam teka-teki ini, Anda diminta untuk mengisikan angka 1-9 ke dalam 81 kotak yang tersusun secara bujur sangkar berukuran 9 × 9. Anda tidak perlu mengisi seluruh kotak karena dalam setiap permainan, sebagian kotak sudah terisi angka. Perhatikan Gambar 1 yang memperlihatkan sebuah Sudoku yang kosong.

blank_sudoku
Gambar 1: Sudoku kosong

Tantangan dalam Sudoku muncul dari 3 aturan berikut.

  1. Setiap baris tidak boleh berisi 2 angka yang sama
  2. Setiap kolom tidak boleh berisi 2 angka yang sama
  3. Setiap blok, yang berukurn 3 × 3, tidak boleh berisi 2 angka yang sama

Tingkat kesulitan Sudoku ditentukan dari banyaknya kotak yang sudah terisi di awal permainan. Semakin banyak kotak yang sudah terisi, semakin mudah Sudoku diselesaikan.

Selain itu, susunan angka awal menentukan mudah sukarnya menyelesaikan Sudoku. Hal ini disebabkan setiap angka awal, akan mengurangi kemungkinan isi dari kotak yang masih kosong. Misalnya, jika 1 baris sudah terisi 7 kotak dengan angka 1-7, dua kotak sisa di baris tersebut dengan mudah dapat kita tebak berisi angka 8 atau 9. Sebagai contoh, Gambar 2 menunjukkan Sudoku untuk level mudah. Sebelum melanjutkan, Anda boleh mencoba untuk mengisi Sudoku ini.

easy_sudoku
Gambar 2: Sudoku yang mudah

Ada banyak cara menyelesaikan Sudoku. Aturan langkah per langkah atau algoritma untuk menyelesaikan teka-teki ini sudah tersedia. Dengan adanya algoritma ini, dapat dibuat program komputer yang otomatis menyelesaikan Sudoku. Penulis pernah menyelesaikan Sudoku menggunakan program komputer yang ditulis Peter Norvig , direktur riset Google Inc. Dengan program tersebut Sudoku tersulit pun dapat diselesaikan dalam hitungan milidetik.

Akan tetapi, tanpa komputer, tidak semua dari kita dapat mengerjakan Sudoku. Beberapa Sudoku dianggap sangat sulit sehingga yang bisa kita lakukan hanyalah melakukan trial and error.

Sebenarnya, dalam ilmu komputasi, masalah untuk menemukan pemecahan Sudoku termasuk ke dalam kelas yang disebut NP-Complete. Secara sederhana, permasalahan yang masuk ke dalam kelas ini adalah permasalahan yang tidak diketahui dapat diselesaikan secara cepat ataukah tidak. Namun, jika kita diberikan solusi terhadap permasalahan ini, kebenaran solusi itu dapat diperiksa dengan cepat.

Kita akan kembali menyinggung masalah NP-Complete saat membahas uang sebesar 1 juta dollar Amerika nanti. Sekarang kita beralih dulu pada fakta bahwa ilmuwan tertarik akan Sudoku karena ada beberapa pertanyaan yang menarik untuk dicari jawabannya. Di antara pertanyaan itu adalah:

  1. Berapa banyak kemungkinan Sudoku yang ada?
  2. Berapa jumlah angka awal minimal yang harus diisikan agar Sudoku memiliki solusi yang unik (hanya ada satu solusi)?
  3. Adakah algoritma yang dapat menyelesaikan dengan cepat Sudoku dengan sembarang ukuran (misal Sudoku 100 × 100 kotak)?

Jika kita pergi ke Google Scholar (atau dalam versi Bahasa Indonesia disebut Google Cendekia), lalu kita memasukkan kata kunci Sudoku, untuk pencarian tulisan di tahun 2012 saja, terdapat kurang lebih 1.360 daftar hasil pencarian. Ini menunjukkan bahwa minat para peneliti untuk masalah Sudoku sangatlah tinggi. Beberapa publikasi ternama pun mengangkat artikel mengenai Sudoku.

Contohnya Scientific American yang membahas Sudoku dalam satu artikelnya di tahun 2006 dengan judul “The Science Behind Sudoku”. Artikel itu ditulis oleh Jean-Paul Delahaye, seorang ahli Matematika dari Prancis. Selain itu, Nature Scientific Reports mempublikasikan artikel berjudul “The Chaos Within Sudoku” tanggal 11 Oktober 2012. Artikel ini ditulis dua orang ilmuwan Fisika dari Romania dan Amerika.

Kembali ke 3 pertanyaan yang menggusarkan para peneliti di atas. Jawaban untuk pertanyaan pertama ternyata adalah 5.472.730.538. Ini merupakan angka yang besar sekali sehingga rasanya pecandu Sudoku tidak perlu takut kehabisan teka-teki ini.

Pertanyaan kedua sempat menjadi topik riset para peneliti selama beberapa waktu. Saat itu diduga bahwa jawaban dari pertanyaan nomor 2 adalah 17. Gordon Royle, dari University of Western Australia, mengumpulkan sebanyak 38.000 Sudoku dengan 17 angka awal dan sejauh itu, setiap Sudoku tersebut memang menghasilkan 1 solusi yang unik. Di samping itu, diketahui beberapa Sudoku dengan 16 angka awal yang menghasilkan 2 solusi.

Untuk memeriksa kemungkinan adanya Sudoku dengan 16 angka awal yang memiliki solusi unik, Gary McGuire, seorang ahli Matematika dari University College Dublin, melakukan eksperimen menggunakan superkomputer. Superkomputer tersebut melakukan pemeriksaan terhadap setiap kemungkinan Sudoku 16 angka untuk mencari jika ada yang memiliki solusi unik. Setelah melakukan penghitungan menggunakan 320 komputer paralel, masing-masing 2 prosesor dengan 16 core Xeon E5650 dan RAM masing-masing 24GB, dan dilakukan tanpa henti dari Januari 2011 hingga Desember 2011, McGuire menemukan bahwa tidak ada Sudoku 16 angka yang menghasilkan solusi unik. Jadi, hingga saat ini jawaban dari pertanyaan nomor 2 adalah 17 kecuali jika suatu hari seseorang menemukan Sudoku 17 angka yang memiliki paling sedikit 2 solusi.

Dari 3 pertanyaan, nomor 3 lah yang sebenarnya pertanyaan utama yang hingga saat ini belum dapat diselesaikan siapa pun. Seperti yang disebutkan sebelumnya, permasalahan Sudoku termasuk ke dalam NP-Complete atau lebih umumnya NP. Artinya, tidak diketahui apakah ada atau tidak ada algoritma untuk menyelesaikan permasalahan ini dengan cepat.

Sampai di sini mungkin Anda agak sedikit bingung. Jika Sudoku masuk ke dalam NP, mengapa dapat dibuatkan program komputer untuk menyelesaikan Sudoku dengan cepat? Jawabannya adalah, algoritma yang ada untuk menyelesaikan Sudoku, tidak dapat mencari solusi Sudoku dengan cepat saat ukuran Sudoku bertambah, tidak lagi 9 × 9. Penambahan sedikit saja ukuran Sudoku, waktu yang dibutuhkan untuk menyelesaikan Sudoku akan meningkat tajam.

Ini bukan berarti bahwa Sudoku untuk sembarang ukuran tidak bisa dipecahkan secara cepat. Kita hanya tidak tahu apakah ada algoritma yang lebih cepat untuk menyelesaikan Sudoku sembarang ukuran ini. Jika kita dapat menemukan algoritma yang cepat ini, permasalahan Sudoku tidak lagi berada di kelas NP, tapi berada di kelas P, yaitu kelas permasalahan yang dapat diselesaikan relatif cepat dan waktu penyelesaiannya tidak akan meningkat tajam saat ukuran permasalahan sedikit bertambah. Jika semua permasalahan yang berada di kelas NP ternyata dapat dicarikan algoritmanya yang cepat, itu berarti, NP sama dengan P atau ditulis P = NP. Dan sebaliknya, jika tidak ada algoritma yang mampu untuk menyelesaikan semua masalah di NP dengan cepat, ini berarti P = NP.

Nah, bagian yang menariknya adalah, pertanyaan apakah P = NP dianggap sebagai salah satu pertanyaan terbesar milenium ini. Bagi orang yang dapat menyelesaikan permasalahan ini, Clay Mathematics Institute akan memberikan hadiah berupa uang sebesar 1 juta dollar Amerika. Tertarik?

Demikianlah Sudoku yang menjadi permasalahan seksi bagi para peneliti dunia. Sebelum mengakhiri cerita ini, Anda mungkin tertarik untuk mencoba menyelesaikan Sudoku yang diklaim sebagai salah satu Sudoku tersulit di dunia. Sudoku ini dibuat oleh Arto Inkala, seorang ahli Matematika dari Finlandia. Selamat mencoba.

hardest_sudoku
Gambar 3: Arto Inkala, seorang ahli Matematika asal Finlandia, mengklaim bahwa Sudoku ini adalah Sudoku tersulit di dunia.

Plagiarism Detection Using MD5 Message-Digest Algorithm and Words Comparison

Plagiarism is the practice of taking someone else’s work or ideas and passing them off as one’s own. In this paper, we show automatic plagiarism detection using two methods. First method is MD5 message-digest algorithm and second method is words comparison. Our experiments showed that first method succeeded in detecting same paragraphs (or with a slight modification) with 100% accuracy. This kind of plagiarism occurs when one copies and pastes other’s paragraph into his/her own writing. Our second method succeeded in detecting in average of 40.7% similarity between two paragraphs which one is paraphrased version of the other. We propose that these two methods combined could make a novel classifier for plagiarism detection. [pdf]

0x7C00: Tempat Bootloader Berlabuh

Di tutorial sebelumnya, kita membuat bootloader sederhana yang dijalankan di VirtualBox. Jika Anda lihat kembali, baris kedua dari bootloader kita tertulis seperti berikut.

Baris kedua tersebut menyatakan bahwa awal binary dari bootloader kita, yaitu boot.bin akan diletakkan di alamat memori 0x7c00. Mengapa di alamat itu? Karena CPU akan langsung mengeksekusi instruksi yang ada di 0x7c00 setelah melakukan POST. Penjelasan yang bagus terdapat di sini.

Untuk lebih meyakinkan lagi, mari kita dump 64 byte isi memori komputer kita mulai dari alamat 0x7c00. Untuk itu, Anda dapat menggunakan program berikut.

Setelah di-compile, kita lihat binary program ini menggunakan Bless Hex Editor. Berikut adalah hasilnya. Perhatikan 64 byte pertama dari binary ini.

Lalu, boot virtual machine kita, maka akan muncul tampilan seperti ini.

Perhatikan byte per byte dari karakter yang muncul di virtual machine dan di Bless Hex Editor terutama bagian yang berisi 0x00 dan Hello World.

Byte pertama berisi 0xBE, di virtual machine muncul karakter aneh. Byte ke-2 berisi 0x00, di virtual machine muncul spasi. Byte ke-6 berisi 0x00, di virtual machine muncul spasi. Dan seterusnya.

Karena program kita melakukan dump untuk isi memori alamat 0x7c00 – 0x7c40, dan isi dari memori mulai dari alamat 0x7c00 sama dengan isi dari program kita dilihat dari Bless Hex Editor, dapat disimpulkan bahwa program boot.ini (yang binary-nya dimulai dengan 0xBE) memang di-load ke 0x7c00.

Menambahkan Bootloader ke VirtualBox Disk Image (Vdi)

Di Internet, banyak sekali tutorial membuat bootloader sendiri, mulai dari bootloader yang tidak melakukan apa-apa hingga bootloader yang dapat memanggil kernel dari hard disk. Kelemahan tutorial yang ada di Internet adalah kebanyakan harus melakukan emulasi floppy disk di Virtual Machine (biasanya Qemu atau Bosch). Oleh karena Qemu dan Bosch kurang populer untuk kalangan awam, di sini saya akan tunjukkan cara menggunakan VirtualBox untuk mencoba bootloader buatan sendiri.

Bootloader adalah program yang berukuran 512 byte dan terletak di sektor pertama sebuah hard disk (yang disebut juga dengan boot sector). Tugas dari bootloader adalah untuk meload kernel (sistem operasi). Salah satu ciri program bootloader adalah 2 byte terakhirnya, yaitu byte ke 511 dan 512, berisi bilangan heksadesimal 0xAA dan 0x55.

Berikut adalah contoh program bootloader (boot.asm) yang mencetak “Hello World” di layar ketika dijalankan.

Untuk penjelasan setiap baris dapat dilihat di sini.

Program bootloader ini dapat di-compile menggunakan Netwide Assembler (NASM), yaitu dengan mengetikkan perintah berikut:

compile_bootloader1

Hasil dari kompilasi adalah program binary boot.bin. Anda dapat melihat bahwa ukuran program ini tepat 512 byte.

Selanjutnya adalah meletakkan boot.bin di 512 byte pertama dari VirtualBox disk image yang kita gunakan. Saya asumsikan bahwa Anda dapat membuat satu virtual machine dari VirtualBox ini dan menggunakan disk image tipe Vdi.

Langkah terakhir adalah dengan menyalin byte demi byte dari program boot.bin ke sector pertama dari Vdi. Untuk itu, Anda membutuhkan sebuah program Hex Editor. Saya sendiri menggunakan Bless Hex Editor. Berikut adalah screenshot dari isi Vdi yang saya buat (Saya buat Vdi fixed-size sebesar 32MB).

vdi_hex_content

Dari Bless Hex Editor terlihat bahwa isi byte-byte pertama dari Vdi bukanlah bootsector. Lalu, di manakah letak bootsector dari Vdi? Untuk mengetahuinya, saya melakukan penghitungan berikut.

Saya menciptakan hard disk 32 MB, yang artinya terdapat 1024 * 1024 * 32 byte = 33.554.432 byte.  Selanjutnya, di Bless Hex Editor saya lihat bahwa offset byte terakhir adalah 0x2001FFF byte atau samadengan terdapat 33.562.624 byte dalam Vdi. Dengan demikian, terdapat selisih 8192 byte (8KB). Saya berkesimpulan bahwa 8KB ini digunakan untuk metadata Vdi. Sector hard disk dimulai di byte ke 8193, atau offset 0x2000.

Dengan pengetahuan ini, saya buka boot.bin di Bless Hex Editor, lalu saya salin semua 512 byte ke Vdi dimulai di byte ke 8193 (atau offset 0x2000 – ingat offset mulai dari 0x00). Lalu, periksa jika ukuran Vdi sekarang bertambah 512 byte. Jika ya, hapus 512 byte tambahan yang berisi 0x00 sehingga jumlah byte di Vdi tetap seperti sebelumnya, yaitu 33.562.624 byte.

Setelah Anda simpan file Vdi, cobalah boot Virtual Machine Anda. Seharusnya sekarang Virtual Machine Anda akan booting ke teks “Hello World”.

hello_world