PERANCANGAN DAN IMPLEMENTASI SISTEM PENILAIAN JAWABAN ESAI OTOMATIS MENGGUNAKAN ALGORITMA RABIN-KARP KOMPETENSI REKAYASA PERANGKAT LUNAK
SKRIPSI
I PUTU DHARMA ADE RAHARJA NIM. 1108605037
PROGRAM STUDI TEKNIK INFORMATIKA JURUSAN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS UDAYANA BUKIT JIMBARAN 2015
SURAT PERNYATAAN KEASLIAN KARYA ILMIAH Yang bertanda tangan di bawah ini menyatakan bahwa naskah Skripsi dengan judul: ……………………………………………………………………………………… ……………………………………………………………………………………… ……………………………………………………………………………………… ……………………………………………………………………………………… Nama
: I Putu Dharma Ade Raharja
NIM
: 1108605037
Program Studi : Teknik Informatika E-mail
:
[email protected]
Nomor telp/HP : 085792102887 Alamat
: Br. Dangin Pangkung, Desa Tista, Kerambitan, Tabanan
Belum pernah dipublikasikan dalam dokumen skripsi, jurnal nasional maupun internasional atau dalam prosiding manapun, dan tidak sedang atau akan diajukan untuk publikasi di jurnal atau prosiding manapun. Apabila di kemudian hari terbukti terdapat pelanggaran kaidah-kaidah akademik pada karya ilmiah saya, maka saya bersedia menanggung sanksi-sanksi yang dijatuhkan karena kesalahan tersebut, sebagaimana diatur oleh Peraturan Menteri Pendidikan Nasional Nomor 17 Tahun 2010 tentang Pencegahan dan Penanggulangan Plagiat di Perguruan Tinggi. Demikian Surat Pernyataan ini saya buat dengan sesungguhnya untuk dapat dipergunakan bilamana diperlukan. Denpasar, 16 September 2015 Yang membuat pernyataan,
( I Putu Dharma Ade Raharja ) NIM. 1108605037
LEMBAR PENGESAHAN TUGAS AKHIR Judul
: Perancangan Dan Implementasi Sistem Penilaian Jawaban Esai Otomatis Menggunakan Algoritma Rabin-Karp
Kompetensi
: Rekayasa Perangkat Lunak
Nama
: I Putu Dharma Ade Raharja
NIM
: 1108605037
Tanggal Seminar
: 11 Agustus 2015 Disetujui oleh:
Pembimbing I
Penguji I
Ida Bagus Gede Dwidasmara, S.Kom., M.Cs NIP. 198503152010121007
Drs. I Wayan Santiyasa, M.Si NIP. 196704141992031002
Pembimbing II
Penguji II
Ngurah Agus Sanjaya ER, S.Kom, M.Kom NIP. 197803212005011001
Agus Muliantara, S.Kom, M.Kom NIP. 198006162005011001 Penguji III
I Putu Gede Hendra Suputra, S.Kom, M.Kom NIP. 198812282014041001 Mengetahui, Jurusan Ilmu Komputer FMIPA UNUD Ketua,
Drs. I Wayan Santiyasa, M.Si NIP. 196704141992031002
ii
Judul
: Perancangan Dan Implementasi Sistem Penilaian Jawaban Esai Otomatis Menggunakan Algoritma Rabin-Karp
Nama
: I Putu Dharma Ade Raharja
NIM
: 1108605037
Pembimbing I : Ida Bagus Gede Dwidasmara, S.Kom., M.Cs Pembimbing II : Ngurah Agus Sanjaya ER, S.Kom., M.Kom
ABSTRAK E-learning merupakan suatu metode baru dalam proses belajar mengajar yang menggunakan media elektronik khususnya internet sebagai sistem pembelajarannya. Sebagai media pembelajaran e-learning memerlukan proses evaluasi belajar dalam pelaksanaannya. Evaluasi dalam proses belajar mengajar dapat memiliki bermacam – macam bentuk dalam pelaksanaannya seperti dengan memberikan soal berbentuk pilihan ganda, jawaban singkat dan soal berbentuk jawaban esai. Namun apabila ketiga jenis evaluasi belajar tersebut dibandingkan, jawaban esai merupakan cara yang paling tepat untuk evaluasi belajar. Namun dengan masih sedikitnya sistem pembantu yang memungkinkan untuk melakukan penilaian jawaban esai secara otomatis, menimbulkan beberapa kelemahan yang menyulitkan proses evaluasi dilakukan sehingga diperlukan suatu sistem yang mampu menilai jawaban esai secara ototmatis. Sistem penilai jawaban esai otomatis merupakan suatu sistem yang dapat memudahkan dan mempercepat proses pemeriksaan dan penilaian jawaban esai. Dengan menerapkan algoritma penghitungan text similarity, dapat diketahui seberapa besar keterkaitan antara dokumen jawaban esai dengan kunci jawabannya. Salah satu algoritma text similarity yang dapat digunakan dalam masalah ini adalah Algoritma Rabin-Karp. Algoritma Rabin-Karp merupakan algoritma pencarian string yang menggunakan hashing untuk menemukan sebuah substring dalam sebuah teks. Berdasarkan pada penelitian yang dilakukan, sistem penilaian jawaban esai otomatis dengan menerapkan Algoritma Rabin-Karp varian Chillar-Kochar memberikan nilai atas tingkat kesamaan antar jawaban dengan kunci jawaban dengan rata – rata perbedaan dari penilaian sistem dengan penilaian pengajar sebesar 1,01 pada soal pertama dan 3,09 pada soal kedua. Kata Kunci : E-learning, Rabin-Karp, Sistem Penilaian Jawaban Esai Otomatis
iii
Title
: The Design and Implementation of Automated Essay Answer Scoring System by Using the Rabin-Karp Algorithm
Name
: I Putu Dharma Ade Raharja
NIM
: 1108605037
First Supervisor
: Ida Bagus Gede Dwidasmara, S.Kom., M.Cs
Second Supervisor : Ngurah Agus Sanjaya ER, S.Kom., M.Kom
ABSTRACT E-learning is a new method of teaching and learning by using electronic media, especially the internet as a learning system. As a medium of learning, it requires learning evaluation process in its implementation. Evaluation of the learning process may have a variety of forms in its application such as to provide multiple choice, short answer and essay questions. However, if the three types of learning evaluation are compared, essay is the most appropriate way to evaluate learning. However, with the small number of assisting systems that enable us for the assessment of essay automatically, causing some disadvantages that complicate the evaluation process carried out, so we need a system that is able to assess essay tasks automatically. Automated essay scoring system is a system which can facilitate and speed up the process of examination and assessment of essay answers. By applying the text similarity calculation algorithm, it can be seen how much the relationship between documents of essay answers with the answer key. One of the text similarity algorithms that can be used in this problem is the Rabin-Karp algorithm. RabinKarp algorithm is a string searching algorithm that uses hashing to find a substring in a text. Based on the research that has been conducted, the automated essay scoring system by applying the Rabin-Karp algorithm variants Chillar-Kochar was based on the degree of similarity between the answers with the answer key with the average difference of teacher assessment with the assessment system of 1.01 to about 3.09 respectively in the first and the second questions. Keywords: E-learning, Rabin-Karp, Automated Essay Answer Scoring System
iv
KATA PENGANTAR Penelitian dengan judul “Perancangan dan Implementasi Sistem Penilaian Jawaban Esai Otomatis Menggunakan Algoritma Rabin-Karp” ini disusun dalam rangkaian kegiatan pelaksanaan Tugas Akhir di Jurusan Ilmu Komputer FMIPA UNUD. Sehubungan dengan telah terselesaikannya penelitian ini, maka diucapkan terimakasih dan penghargaan kepada berbagai pihak yang telah membantu penyusun, antara lain : 1. Bapak Ida Bagus Gede Dwidasmara, S.Kom., M.Cs. selaku Pembimbing I yang telah membimbing dan membantu menyempurnakan penelitian ini. 2. Bapak Ngurah Agus Sanjaya ER, S.Kom., M.Kom. selaku Pembimbing II yang telah banyak membantu dan meluangkan waktu untuk penelitian ini. 3. Bapak Drs. I Wayan Santiyasa, M.Si selaku Ketua Jurusan Ilmu Komputer Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Udayana yang telah banyak memberikan masukan dan motivasi sehingga memperlancar dalam proses pelaksanaan penelitian ini. 4. Bapak-bapak dan ibu-ibu dosen di Jurusan Ilmu Komputer yang bersedia meluangkan waktunya untuk memberikan masukan dalam penyempurnaan penelitian ini. 5. Rekan-rekan mahasiswa di Jurusan Ilmu Komputer khususnya angkatan 2011 yang telah memberi dukungan, motivasi, semangat dan kerja sama dalam penelitian ini. Penulis menyadari bahwa tugas akhir ini masih belum sempurna, untuk itu kritik dan saran yang bermanfaat demi kesempurnaan tugas akhir ini sangat penyusun harapkan. Bukit Jimbaran, Agustus 2015 Penyusun
I Putu Dharma Ade Raharja
v
DAFTAR ISI Halaman Judul .........................................................................................................i LEMBAR PENGESAHAN TUGAS AKHIR ......................................................... ii ABSTRAK ............................................................................................................. iii ABSTRACT ........................................................................................................... iv KATA PENGANTAR .............................................................................................. v DAFTAR ISI .......................................................................................................... vi DAFTAR TABEL................................................................................................... ix DAFTAR GAMBAR .............................................................................................. x BAB I ...................................................................................................................... 1 PENDAHULUAN .................................................................................................. 1 1.1 Latar Belakang .................................................................................................. 1 1.2 Rumusan Masalah ............................................................................................. 2 1.3 Tujuan................................................................................................................ 3 1.5 Batasan Masalah................................................................................................ 3 1.5 Manfaat ............................................................................................................. 3 1.6 Metodelogi Penelitian ....................................................................................... 3 1.6.1 Desain Penelitian ................................................................................ 3 1.6.2 Pengumpulan Data ............................................................................. 4 1.6.3 Pengolahan Data Awal ........................................................................ 4 1.6.4 Metode yang Digunakan .................................................................... 4 1.6.5 Eksperimen dan Pengujian Sistem ..................................................... 5 1.6.6 Evaluasi dan Validasi Hasil ................................................................ 6 BAB II ..................................................................................................................... 9 TINJAUAN PUSTAKA .......................................................................................... 9 2.1 Algoritma Rabin-Karp....................................................................................... 9 2.2 Peningkatan Performa Algoritma Rabin-Karp ................................................ 12 2.3 Text Preprocessing .......................................................................................... 13 2.3.1 Case Folding ..................................................................................... 13 2.3.2 Tokenizing ........................................................................................ 14
vi
2.3.3 Filtering ............................................................................................ 15 2.3.4 Stemming ......................................................................................... 16 2.4 Metode Pengembangan Waterfall ................................................................... 17 2.5 Pengujian Sistem ............................................................................................. 19 2.5.1 Static Testing .................................................................................... 19 2.5.2 Blackbox Testing .............................................................................. 20 2.5.3 Whitebox Testing.............................................................................. 20 2.6 Tinjauan Studi ................................................................................................. 21 BAB III ................................................................................................................. 23 ANALISIS DAN PERANCANGAN SISTEM .................................................... 23 3.1 Pengumpulan Kebutuhan ................................................................................ 23 3.1.1 Kebutuhan Fungsional...................................................................... 23 3.1.2 Kebutuhan Non Fungsional .............................................................. 24 3.2 Perancangan Sistem ........................................................................................ 24 3.2.1 Use Case Diagram ............................................................................ 24 3.2.2 Activity Diagram .............................................................................. 27 3.2.3 Class Diagram .................................................................................. 33 3.2.4 Sequence Diagram ............................................................................ 36 3.2.5 Entity Relationship Diagram ............................................................ 46 3.3 Perancangan Antarmuka.................................................................................. 47 BAB IV ................................................................................................................. 51 HASIL PEMBAHASAN....................................................................................... 51 4.1 Implementasi Database ................................................................................... 51 4.2 Implementasi Antarmuka ................................................................................ 51 4.3 Implementasi Sistem ....................................................................................... 54 4.4 Pengujian Sistem ............................................................................................. 57 4.4.1 Static Testing .................................................................................... 57 4.4.2 Blackbox Testing .............................................................................. 58 4.4.3 Whitebox testing............................................................................... 59 4.4.3 Pengujian Sistem ............................................................................. 62 BAB V ................................................................................................................... 65
vii
KESIMPULAN DAN SARAN ............................................................................. 65 5.1 Kesimpulan ..................................................................................................... 65 5.2 Saran ................................................................................................................ 65 DAFTAR PUSTAKA ............................................................................................ 66
viii
DAFTAR TABEL Tabel 1.1 Rancangan Tabel Static Testing ............................................................... 7 Tabel 1.2 Rancangan Tabel Whitebox Testing ......................................................... 7 Tabel 1.3 Rancangan Tabel Blackbox Testing ......................................................... 8 Tabel 1.4 Rancangan Tabel Pengujian Penilaian .................................................... 8 Tabel 2.1 Hubungan Cyclomatic Complexity dan resiko ...................................... 21 Tabel 3.1 Tabel Kebutuhan Fungsional ................................................................. 23 Tabel 3.2 Kebutuhan Non-Fungsional .................................................................. 24 Tabel 3.3 Deskripsi Aktor ..................................................................................... 25 Tabel 3.4 Deskripsi Use Case ............................................................................... 25 Tabel 3. 5 Hubungan Class dengan Use Case....................................................... 35 Tabel 4.1 Kode preprocessing ............................................................................... 54 Tabel 4.2 Kode pembentukan k-gram dan hashing teks ....................................... 56 Tabel 4.3 Kode penghitungan similarity ............................................................... 57 Tabel 4.4 Hasil Static Testing ................................................................................ 58 Tabel 4.5 Hasil Blackbox Testing .......................................................................... 58 Tabel 4.6 Alur proses preprocessing ..................................................................... 60 Tabel 4.7 Alur proses penilaian similarity............................................................. 62 Tabel 4.8 Hasil pengujian sistem .......................................................................... 62 Tabel 4. 9 Pengaruh kesalahan penulisan .............................................................. 63
ix
DAFTAR GAMBAR Gambar 2.1 Flowchart Algoritma Rabin-Karp ....................................................... 9 Gambar 2.2 Flowchart Algoritma Rabin-Karp varian Chillar - Kochar ............... 12 Gambar 2.3 Tahapan Text Preprocessing .............................................................. 13 Gambar 2.4 Flowchart Case Folding.................................................................... 14 Gambar 2.5 Flowchart Tokenizing ........................................................................ 15 Gambar 2.6 Flowchart Filtering ........................................................................... 16 Gambar 2. 7 Flowchart Stemming Nazief – Adriani ............................................ 17 Gambar 2.8 Model proses waterfall ...................................................................... 18 Gambar 3.1 Use Case Diagram Sistem Penilaian Jawaban Esai Otomatis........... 25 Gambar 3.2 Activity Diagram Tambah Data User ................................................. 27 Gambar 3.3 Activity Diagram Edit Data User ....................................................... 28 Gambar 3.4 Activity Diagram Hapus Data User ................................................... 29 Gambar 3.5 Activity Diagram Membuat Ujian ..................................................... 30 Gambar 3.6 Activity Diagram Mengikuti Ujian .................................................... 31 Gambar 3.7 Activity Diagram Hitung Nilai Kesamaan ......................................... 32 Gambar 3.8 Activity Diagram Melihat Daftar Nilai .............................................. 33 Gambar 3.9 Class Diagram Sistem Peniliaian Jawaban Esai Otomatis ................ 34 Gambar 3.10 Sequence Diagram Melihat Data User ............................................ 36 Gambar 3.11 Sequence Diagram Tambah Data User ............................................ 37 Gambar 3.12 Sequence Diagram Edit Data User .................................................. 38 Gambar 3.13 Sequence Diagram Hapus Data User .............................................. 39 Gambar 3.14 Sequence Diagram Melihat Agenda Ujian ...................................... 39 Gambar 3.15 Sequence Diagram Membuat Ujian................................................. 40 Gambar 3.16 Sequence Diagram Tambah Soal ..................................................... 41 Gambar 3.17 Sequence Diagram Edit Soal ........................................................... 42 Gambar 3.18 Sequence Diagram Delete Soal ....................................................... 43 Gambar 3.19 Sequence Diagram Melihat Daftar Nilai ......................................... 43 Gambar 3.20 Sequence Diagram Mengikuti Ujian ............................................... 44 Gambar 3. 21 Sequence Diagram Hitung Nilai Kesamaan ................................... 45
x
Gambar 3.22 Entity Relationship Diagram Sistem Penilaian Jawaban Esai Otomatis ............................................................................................................................... 46 Gambar 3.23 Rancangan Antarmuka Login .......................................................... 47 Gambar 3.24 Rancangan Antarmuka Pengelolaan Data Utama............................ 48 Gambar 3.25 Rancangan Antarmuka Agenda Ujian ............................................. 48 Gambar 3.26 Rancangan Antarmuka Ujian .......................................................... 49 Gambar 3.27 Rancangan Antarmuka Buat Ujian .................................................. 49 Gambar 3.28 Rancangan Antarmuka Daftar Nilai ................................................ 50 Gambar 4.1 Skema Database Sistem Penilaian Jawaban Esai Otomatis.............. 51 Gambar 4.2 Antarmuka Login............................................................................... 52 Gambar 4.3 Antarmuka Admin ............................................................................. 52 Gambar 4.4 Antarmuka Daftar Ujian .................................................................... 53 Gambar 4.5 Antarmuka Ujian ............................................................................... 53 Gambar 4. 6 Flowgraph Preprocessing ................................................................ 60 Gambar 4. 7 Flowgraph Penghitungan Nilai Similarity ....................................... 61
xi
