ANALISIS DAN IMPLEMENTASI ALGORITMA LINEAR SEARCH PADA PERMAINAN WORD SCRAMBLE
SKRIPSI
AMMAHLI FAKAR TARIGAN 071401071
PROGRAM STUDI S1 ILMU KOMPUTER DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2012
UNIVERSITAS SUMATERA UTARA
ANALISIS DAN IMPLEMENTASI ALGORITMA LINEAR SEARCH PADA PERMAINAN WORD SCRAMBLE
SKRIPSI
Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Komputer
AMMAHLI FAKAR TARIGAN 071401071
PROGRAM STUDI S1 ILMU KOMPUTER DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2012
UNIVERSITAS SUMATERA UTARA
PERSETUJUAN
Judul
Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas
: ANALISIS DAN IMPLEMENTASI ALGORITMA LINEAR SEARCH PADA PERMAINAN WORD SCRAMBLE : SKRIPSI : AMMAHLI FAKAR TARIGAN : 071401071 : SARJANA (S1) ILMU KOMPUTER : ILMU KOMPUTER : MATEMATIKA DAN ILMU PENGETAHUAN ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA
Diluluskan di Medan, 24 Mei 2012 Komisi Pembimbing : Pembimbing II,
Pembimbing I,
M. Andri Budiman, ST, MCompSc, MEM NIP. 197510082008011001
Dr. Poltak Sihombing, M.Kom NIP. 196203171991031001
Program Studi S1 Ilmu Komputer Ketua,
Dr. Poltak Sihombing, M.Kom NIP. 196203171991031001
UNIVERSITAS SUMATERA UTARA
PERNYATAAN
ANALISIS DAN IMPLEMENTASI ALGORITMA LINEAR SEARCH PADA PERMAINAN WORD SCRAMBLE
SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan, 13 April 2012
Ammahli Fakar Tarigan 071401071
UNIVERSITAS SUMATERA UTARA
PENGHARGAAN
Alhamdulillahirabbil’alamin penulis ucapkan kepada Allah SWT yang telah melimpahkan rahmat dan karunia-Nya sehingga skripsi ini berhasil diselesaikan dalam waktu yang telah ditetapkan. Skripsi ini merupakan salah satu syarat yang wajib diselesaikan guna meraih gelar Sarjana Komputer pada jurusan S1 Ilmu Komputer Universitas Sumatera Utara. Adapun judul yang diangkat penulis dalam skripsi ini adalah Analisis dan Implementasi Algoritma Linear Search pada Permainan Word Scramble. Tidak dapat dipungkiri bahwa dalam penyelesaian skripsi ini tidak luput dari campur tangan banyak pihak yang telah memberikan bantuan dan motivasi bagi penulis. Maka, dalam kesempatan ini, penulis mengucapkan terima kasih kepada: 1. Bapak Dr. Poltak Sihombing, M.Kom selaku Ketua Jurusan S1 Ilmu Komputer serta pembimbing I dan Bapak M. Andri Budiman, S.T., M.Comp.Sc., M.E.M selaku pembimbing II yang telah memberikan panduan dan penuh kepercayaan kepada penulis untuk menyelesaikan skripsi ini. 2. Ibu Dian Rachmawati, S.Si, M.Kom dan Bapak Dahlan Sitompul M.Eng selaku dosen penguji yang telah memberikan panduan ringkas, padat dan profesional kepada penulis guna menyempurnakan skripsi ini. 3. Sekretaris Jurusan S1 Ilmu Komputer Ibu Maya Silvi Lydia, B.Sc., M.Sc., Dekan dan Pembantu Dekan Fakultas MIPA beserta para pegawai/staf S1 Ilmu Komputer. 4. Keluarga tercinta, Ayahanda Drs. H. Enda Tarigan dan Ibunda Dra. Hj. Nilva Yenisda, Ammamiarihta, Ammazizzaky Tarigan, dan Ammanawwara yang selalu memberikan doa, dukungan, perhatian, kasih sayang yang tulus, pengorbanan yang tidak ternilai harganya serta dukungan moril maupun materiil selama kehidupan penulis. 5. Dely Utari, S.Kom yang selalu memberikan doa, perhatian, kasih sayang, motivasi dan semangat yang luar biasa bagi penulis. 6. Teman-teman setim Istiqlal FC khususnya Fatih, Wahyu, Safri, Hanafi, Febrian dan Faisal, yang selama ini telah berbagi semangat dan canda tawa dengan penulis, serta sahabat-sahabat lain yang pernah mengisi perjalanan hidup penulis yang tidak dapat disebutkan satu per satu. 7. Teman-teman seperjuangan, mahasiswa S1 Ilmu Komputer stambuk 2007 khususnya Jenita Heptani, Fitri Rahayu, dan Yoga Nugraha yang telah banyak berbagi ilmu, memberikan bantuan, saran, kritikan, semangat, inspirasi, dukungan serta mewarnai kenangan selama masa kuliah yang tak akan terlupakan bagi penulis.
UNIVERSITAS SUMATERA UTARA
8. Semua pihak yang terlibat langsung ataupun tidak langsung yang tidak dapat penulis ucapkan satu per satu yang telah membantu penyelesaian skripsi ini. Semoga Allah SWT memberikan limpahan karunia kepada semua pihak yang telah memberikan bantuan, perhatian serta kerja samanya kepada penulis dalam menyelesaikan tugas akhir ini. Penulis menyadari bahwa dalam penyelesaian skripsi ini masih jauh dari sempurna. Untuk itu penulis sangat mengharapkan kritik dan saran yang membangun guna penyempurnaan di masa mendatang. Akhirnya penulis berharap semoga skripsi ini dapat bermanfaat bagi pribadi penulis, keluarga, masyarakat, organisasi dan negara.
Medan, 13 April 2012
Penulis
UNIVERSITAS SUMATERA UTARA
ABSTRAK
Permainan adalah salah satu solusi alternatif untuk pembelajaran murid. Tidak sedikit murid yang merasa bosan ketika belajar sehingga dapat menghambat proses belajar mengajar. Permainan dapat membantu dan menyemangati banyak murid untuk dapat terus menjaga ketertarikan mereka untuk belajar. Word Scramble termasuk salah satu jenis permainan kata yang dapat menambah wawasan kosakata Bahasa Inggris. Permainan ini menuntut kemampuan berpikir pemain untuk mencari kosakata yang bisa disusun dari huruf acak di papan permainan. Huruf-huruf yang diperoleh harus terhubung langsung secara horizontal, vertikal, atau diagonal. Kata tebakan pemain diperiksa oleh komputer apakah kata tersebut terdapat di dalam kamus yang sudah ditentukan dengan menggunakan algoritma pencarian Linear Search. Penelusuran dimulai dengan membandingkan kata tebakan dengan kata pada indeks pertama di dalam kamus yang berbentuk array. Apabila kedua kata tersebut sama, maka data telah ditemukan dan jawaban pemain benar. Jika tidak, penelusuran dilakukan pada kata pada indeks selanjutnya hingga ditemukan jawaban yang benar. Algoritma Linear Search dapat diimplementasikan pada permainan ini untuk mencocokkan jawaban dan tidak perlu dilakukan pengurutan data sehingga penelusuran dapat langsung dilakukan.
Kata Kunci : Scramble, Permainan, Pengacakan, Pencarian, Linear Search
UNIVERSITAS SUMATERA UTARA
ANALYSIS AND IMPLEMENTATION OF BRUTE FORCE ALGORITHM ON WORD SCRAMBLE GAME
ABSTRACT
Game is one of the alternative solutions for student learning. Not a few students feel bored when learning that can hinder the learning process. Games can help and encourage more students to be able to maintain their interest in learning. Word Scramble is one kind of word game that can add insight into the English vocabulary. This game requires player’s thinking ability to find the word that can be composed from the letters results of randomization on the game’s board. The letters must be directly connected horizontally, vertically, or diagonally. Player’s guess word is checked by the computer whether the word is found in the dictionary that has been determined by using Linear Search Algorithm. Search begins by comparing the guess word with the first word at the first index in the dictionary. If those two words are equals, the data have been found and the player answers correctly. If not, search performed on the next word at the next index until the correct answer is found. Linear Search algorithm can be implemented in this game to match the answers and doesn’t need to sort the data so the searches can be performed directly.
Keyword : Scramble, Game, Randomization, Searching, Linear Search
UNIVERSITAS SUMATERA UTARA
DAFTAR ISI
Halaman Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar
ii iii iv vi vii viii x xi
Bab 1 Pendahuluan 1.1 Latar Belakang 1.2 Rumusan Masalah 1.3 Batasan Masalah 1.4 Tujuan Penelitian 1.5 Manfaat Penelitian 1.6 Metodologi Penelitian 1.7 Sistematika Penulisan
1 1 2 2 2 3 3 4
Bab 2 Landasan Teori 2.1 Algoritma 2.2 Algoritma Pencarian 2.3 Algoritma Pencarian Linear 2.3.1 Karakteristik Algoritma Pencarian Linear 2.3.2 Cara Kerja Algoritma Pencarian Linear 2.3.3 Pseudocode Algoritma Pencarian Linear 2.3.4 Kompleksitas Algoritma Pencarian Linear 2.4 Pengacakan Huruf 2.5 Word Scramble 2.5.1 Aturan Permainan Word Scramble 2.6 Penilaian Kualitas Aplikasi
5 5 6 7 7 8 8 8 9 11 11 12
Bab 3 Analisis dan Perancangan 3.1 Analisis Sistem 3.1.1 Analisis Permainan 3.1.2 Analisis Algoritma 3.1.2.1 Flowchart Alur Permainan 3.1.2.2 Flowchart HurufAcak() 3.1.2.3 Flowchart HurufTerpilih() 3.1.2.4 Flowchart Ketetanggaan() 3.1.2.5 Flowchart KataBaru() 3.1.2.6 Flowchart PeriksaKata() 3.1.2.7 Flowchart SudahKetemu()
13 13 13 14 21 21 23 24 25 25 27
UNIVERSITAS SUMATERA UTARA
3.1.2.8 Flowchart CariKata() 3.1.2.9 Flowchart Nilai() 3.2 Perancangan Sistem 3.2.1 Perancangan Aplikasi Permainan 3.2.2 Perancangan Antarmuka
28 29 30 30 31
Bab 4 Implementasi dan Pengujian 4.1 Implementasi Sistem 4.1.1 Spesifikasi Perangkat Lunak 4.1.2 Spesifikasi Perangkat Keras 4.1.3 Implementasi Rancangan Fungsi 4.1.4 Implementasi Rancangan Antarmuka 4.1.4.1 Tampilan Utama 4.1.4.2 Tampilan Arena Permainan 4.1.4.3 Tampilan Aturan Permainan 4.1.4.4 Tampilan Tentang Permainan 4.2 Pengujian Aplikasi 4.2.1 Pengujian Integrasi Aplikasi 4.2.1.1 Proses pada Tampilan Utama 4.2.1.2 Proses pada Tampilan Arena Permainan 4.2.1.3 Proses pada Tampilan Aturan Permainan 4.2.1.4 Proses pada Tampilan Tentang Permainan 4.2.2 Pengujian Responden 4.2.2.1 Aspek Antarmuka Aplikasi 4.2.2.2 Aspek Penggunaan Aplikasi 4.2.2.3 Aspek Penilaian Aplikasi
35 35 35 35 36 36 36 37 38 39 39 40 40 41 41 42 42 42 44 45
Bab 5 Kesimpulan dan Saran 5.1 Kesimpulan 5.2 Saran
47 47 48
Daftar Pustaka
49
LAMPIRAN A: LISTING PROGRAM LAMPIRAN B: HASIL KUISIONER
UNIVERSITAS SUMATERA UTARA
DAFTAR TABEL
Halaman 2.1 Daftar Nilai Frekuensi Huruf yang Akan Diacak
10
3.1 Hasil Daftar Nilai 4.1 Hasil Evaluasi Proses pada Tampilan Utama 4.2 Hasil Evaluasi Proses pada Tampilan Arena Permainan 4.3 Hasil Evaluasi Proses pada Tampilan Aturan Permainan 4.4 Hasil Evaluasi Proses pada Tampilan Tentang Permainan 4.5 Hasil Kuisioner Aspek Antarmuka Aplikasi 4.6 Hasil Kuisioner Aspek Penggunaan Aplikasi 4.7 Hasil Kuisioner Aspek Penilaian Aplikasi
14 40 41 41 42 43 44 45
UNIVERSITAS SUMATERA UTARA
DAFTAR GAMBAR
Halaman 2.1 Papan Permainan Word Scramble 3.1 Langkah 1 3.2 Langkah 3 3.3 Flowchart Alur Permainan 3.4 Flowchart HurufAcak() 3.5 Flowchart HurufTerpilih() 3.6 Flowchart Ketetanggaan 3.7 Flowchart KataBaru() 3.8 Flowchart PeriksaKata() 3.9 Flowchart Flowchart SudahKetemu() 3.10 Flowchart CariKata() 3.11 Flowchart Nilai() 3.12 Flowchart Aplikasi 3.13 Frame Menu 3.14 Frame Arena Permainan 3.15 Frame Aturan Permainan 3.16 Frame Tentang Permainan 4.1 Tampilan Utama 4.2 Tampilan Arena Permainan 4.3 Tampilan Arena Permainan Ketika Permainan Sedang Berlangsung 4.4 Tampilan Arena Permainan Ketika Permainan Selesai 4.5 Tampilan Aturan Permainan 4.6 Tampilan Tentang Permainan
12 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 36 37 37 38 38 39
UNIVERSITAS SUMATERA UTARA
