IMPLEMENTASI ALGORITMA BRANCH AND BOUND PADA PENENTUAN MENU MAKANAN PENDERITA ASAM URAT SKRIPSI HEDI HERMAWAN HARAHAP 111421069
PROGRAM STUDI EKSTENSI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2014
Universitas Sumatera Utara
IMPLEMENTASI ALGORITMA BRANCH AND BOUND PADA PENENTUAN MENU MAKANAN PENDERITA ASAM URAT SKRIPSI Diajukan untuk melengkapi tugas akhir dan memenuhi syarat memperoleh ijazah Sarjana Ilmu Komputer
HEDI HERMAWAN HARAHAP 111421069
PROGRAM STUDI EKSTENSI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2014
Universitas Sumatera Utara
ii
PERSETUJUAN
Judul
: IMPLEMENTASI ALGORITMA BRANCH AND BOUND PADA PENENTUAN MENU MAKANAN PENDERITA ASAM URAT Kategori : SKRIPSI Nama : HEDI HERMAWAN HARAHAP Nomor Induk Mahasiswa : 111421069 Program Studi : EKSTENSI S1 ILMU KOMPUTER Departemen : ILMU KOMPUTER Fakultas : ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA Diluluskan di Medan, 11 Februari 2014 Komisi Pembimbing
:
Pembimbing 2
Pembimbing 1
Dian Rachmawati, S.Si, M.Kom NIP. 19830723 200912 2 004
Dr. Poltak Sihombing, M.Kom NIP. 19620317 199103 1 001
Diketahui/Disetujui oleh Program Studi S1 Ilmu Komputer Ketua,
Dr. Poltak Sihombing, M.Kom NIP. 19620317 199103 1 001
Universitas Sumatera Utara
iii
PERNYATAAN
IMPLEMENTASI ALGORITMA BRANCH AND BOUND PADA PENENTUAN MENU MAKANAN PENDERITA ASAM URAT
SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil karya saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing telah disebutkan sumbernya.
Medan, 11 Februari 2014
Hedi Hermawan Harahap 111421069
Universitas Sumatera Utara
iv
PENGHARGAAN
Alhamdulillah, puji dan syukur ke hadirat Allah SWT, yang hanya dengan rahmat dan izin-Nya penulis dapat menyelesaikan penyusunan skripsi ini, sebagai syarat untuk memperoleh gelar Sarjana Komputer, pada Program Studi S1 Ilmu Komputer Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara. Ucapan terima kasih penulis sampaikan kepada: 1.
Bapak Dr. Poltak Sihombing, M.Kom selaku Ketua Program Studi S1 Ilmu Komputer dan selaku Dosen Pembimbing I yang telah memberikan bimbingan, saran dan masukan kepada penulis dalam pengerjaan skripsi ini.
2.
Ibu Dian Rachmawati, S.Si, M.Kom selaku Dosen Pembimbing II yang telah memberikan bimbingan, saran dan masukan kepada penulis dalam pengerjaan skripsi ini.
3.
Bapak M. Andri Budiman, ST, M.Comp.Sc, MEM selaku Dosen Pembanding I yang telah memberikan kritik dan saran dalam penyempurnaan skripsi ini.
4.
Bapak Handrizal, S.Si, M.Comp.Sc selaku Dosen Pembanding II yang telah memberikan kritik dan saran dalam penyempurnaan skripsi ini.
5.
Seluruh tenaga pengajar dan pegawai di Program Studi S1 Ilmu Komputer Fasilkom-TI USU.
6.
Ayahanda Drs. Hamron Harahap, Ibunda Fadillah Hasibuan S.Pd serta kakanda Fadli Hardiansyah Harahap S.Kep, Ns yang selalu memberikan kasih sayang dan dukungannya kepada penulis.
7.
Keluarga besar Ekstensi Ilmu Komputer, khususnya semua teman dan sahabat angkatan 2011 yang tidak dapat disebutkan satu persatu, terima kasih atas ide, saran, dan kerja samanya selama ini.
Semoga Allah SWT melimpahkan berkah kepada semua pihak yang telah memberikan bantuan, perhatian, serta dukungan kepada penulis dalam menyelesaikan skripsi ini. Akhirnya, semoga skripsi ini bermanfaat bagi pribadi, keluarga, masyarakat, organisasi dan negara. Medan, Penulis
Februari 2014
Hedi Hermawan Harahap
Universitas Sumatera Utara
v
ABSTRAK
Penyakit asam urat erat kaitannya dengan pola makan. Jika pola makan tidak dirubah, kadar asam urat dalam darah yang berlebihan akan menimbulkan penumpukan kristal asam urat. Apabila kristal terbentuk dalam cairan sendi, maka akan terjadi penyakit gout (asam urat). Kendala yang dialami oleh penderita asam urat dalam menentukan pola makan adalah ketidakmampuan dalam menentukan jumlah kalori yang dibutuhkannya dan pengetahuan yang kurang tentang pola makan sehat dan konsumsi gizi yang tepat pada penderita asam urat. Penentuan menu makanan dapat diselesaikan dengan menggunakan algoritma Branch and Bound dengan memperhatikan Tabel Angka Kecukupan Gizi dan Daftar Komposisi Bahan Makanan (DKBM). Proses optimasi dilakukan terhadap menu makanan pilihan user yang telah dihitung jumlah karbohidrat, lemak, protein, dan kadar purin yang cocok sesuai dengan kalori perhari. Implementasi sistem menggunakan bahasa pemrograman PHP dan MySQL. Hasil penelitian adalah algoritma Branch and Bound telah berhasil diterapkan untuk mengoptimasi masalah sehingga mampu menghasilkan daftar makanan yang dapat dikonsumsi oleh user. Kata Kunci: Asam Urat, Branch and Bound, pola makan, kalori, optimasi.
Universitas Sumatera Utara
vi
THE IMPLEMENTATION OF ALGORITHMS BRANCH AND BOUND IN THE DETERMINATION OF CUISINES PATIENTS OF URIC ACID
ABSTRACT
Uric acid disease closely related to diet. If the diet is not changed, the levels of uric acid in the blood will cause excessive buildup of uric acid crystals. When the crystals form in joints of liquid, then there will be disease gout (uric acid). The constraints experienced by sufferers of gout in determining the pattern of eating is the inability to determine the number of calories that it needs and knowledge that is less about the pattern of healthy eating and proper nutrition consumption in people with gout. Determination of food menu can be solved using Branch and Bound algorithm with attention to the Tabel Angka Kecukupan Gizi and Daftar Komposisi Bahan Makanan (DKBM). The optimization process done to the food menu selection the user who has calculated the amount of carbohydrates, fats, proteins, and the levels of matching according to purin calories per day. System implementation using the programming language PHP and MySQL. Research results are Bound and Branch algorithms have been successfully applied to optimizing problems so it is able to generate a list of foods that can be consumed by the user. Keywords: uric acid, Branch and Bound, diet, calorie, optimization.
Universitas Sumatera Utara
vii
DAFTAR ISI
Hal. Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar Daftar Lampiran
ii iii iv v vi vii ix 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 2 2 3 3 3 4
Bab 2 Landasan Teori 2.1 Algoritma 2.2 Algoritma Pencarian 2.3 Pohon 2.4 Pencarian Buta 2.4.1 Algoritma Depth First Search (DFS) 2.4.2 Algoritma Breadth-First Search (BFS) 2.4.3 Algoritma Best First Search 2.5 Algoritma Optimasi 2.5.1 Algoritma Branch and Bound 2.6 Knapsack Problem 2.6.1 Knapsack dengan Algoritma Greedy 2.6.2 Knapsack dengan Algoritma Branch and Bound 2.7 Asam Urat 2.7.1 Defenisi Asam Urat 2.7.2 Gejala Penyebab Asam Urat 2.7.3 Tahapan Asam Urat 2.7.4 Penggolongan Asam Urat
5 6 6 7 7 9 10 11 12 13 14 15 17 17 18 19 19
Universitas Sumatera Utara
viii
Bab 3 Analisis dan Perancangan Sistem 3.1 Analisis Sistem 3.1.1 Analisis Masalah 3.1.2 Analisis Kebutuhan 3.1.2.1 Kebutuhan Fungsional 3.1.2.2 Kebutuhan Nonfungsional 3.2 Perancangan Algoritma Branch and Bound 3.2.1 Pengkategorian Kalori Berdasarkan Umur 3.2.2 Penggolongan Asam Urat Berdasarkan Kadar Purin 3.2.3 Perhitungan Nilai Kalori Setiap Bahan Makanan 3.2.4 Proses Perhitungan Algoritma Branch And Bound 3.2.5 Pseudocode 3.3 Flowchart Sistem Secara Umum 3.4 Data Flow Diagram (DFD) 3.4.1 Diagram Konteks 3.4.2 Data Flow Diagram Level 1 3.4.3 Data Flow Diagram Level 2 Proses 4 3.5 Kamus Data 3.6 Perancangan Antarmuka (Interface) 3.6.1 Daftar 3.6.2 Data Lengkap 3.6.3 Edit Data 3.6.4 Pemilihan Menu Makanan 3.6.5 Hasil Pemilihan 3.6.6 Daftar Menu Makanan
21 21 22 22 22 23 23 24 25 27 30 32 33 34 35 37 38 43 43 43 44 45 46 47
Bab 4 Implementasi Program 4.1 Spesifikasi Perangkat 4.1.1 Perangkat Keras 4.1.2 Perangkat Lunak 4.2 Penggunaan Program 4.2.1 Halaman Utama 4.2.1.1 Halaman Login 4.2.1.2 Halaman Daftar 4.2.1.3 Halaman Edit Data 4.2.2 Halaman Pemilihan Makanan 4.2.3 Halaman Administrator 4.3 Pengujian Sistem
48 48 49 49 49 50 51 52 52 53 53
Bab 5 Kesimpulan dan Saran 5.1 Kesimpulan 5.2 Saran
56 56
Daftar Pustaka
57
Universitas Sumatera Utara
ix
DAFTAR TABEL
Hal. Tabel 2.1 Tabel 2.2 Tabel 3.1 Tabel 3.2 Tabel 3.3 Tabel 3.4 Tabel 3.5 Tabel 3.6 Tabel 3.7 Tabel 3.8 Tabel 3.9 Tabel 3.10 Tabel 3.11 Tabel 3.12 Tabel 3.13 Tabel 3.14 Tabel 3.15
Algoritma greedy pada knapsack Contoh persoalan knapsack Kalori Berdasarkan Umur Keterangan Kalori, Protein dan pi/bi Kode Program Untuk Membuat Algoritma Branch and Bound Tabel Admin Tabel akg_men Tabel bb_temp Tabel dkbm Tabel jenisk Tabel modul Tabel pasien Tabel kelompok Tabel umur Tabel food_temp Tabel golongan Tabel kalori_temp
15 15 24 28 30 38 39 39 39 40 40 41 41 41 42 42 42
Universitas Sumatera Utara
x
DAFTAR GAMBAR
Hal. Gambar 2.1 Gambar 2.2 Gambar 2.3 Gambar 2.4 Gambar 2.5 Gambar 2.6 Gambar 2.7 Gambar 2.8 Gambar 2.9 Gambar 3.1 Gambar 3.2 Gambar 3.3 Gambar 3.4 Gambar 3.5 Gambar 3.6 Gambar 3.7 Gambar 3.8 Gambar 3.9 Gambar 3.10 Gambar 3.11 Gambar 3.12 Gambar 4.1 Gambar 4.2 Gambar 4.3 Gambar 4.4 Gambar 4.5 Gambar 4.6 Gambar 4.7 Gambar 4.8 Gambar 4.9 Gambar 4.10 Gambar 4.11 Gambar 4.12 Gambar 4.13
Struktur Data dari Pohon Tahapan pembentukan pohon DFS Matriks bidak Pohon ruang status yang terbentuk pencarian DFS Persoalan menyusun mainan yang terdiri atas 3 buah blok Pohon ruang status yang dibentuk selama pencarian solusi dengan metode BFS Langkah-langkah yang dilakukan oleh algoritma Best First Search Ilustrasi permasalahan knapsack pada penyakit asam urat Pohon ruang status yang terbentuk penyelesaian knapsack Diagram Ishikawa Masalah Penelitian Pohon ruang status penyelesaian knapsack dengan algoritma branch and bound Flowchart Sistem Secara Umum Diagram Konteks DFD Level 1 DFD Level 2 Proses 4 Branch and Bound Halaman Daftar Halaman Data Lengkap Halaman Edit Data Halaman Pemilihan Menu Makanan Halaman Hasil Pemilihan Menu Makanan Halaman Daftar Menu Makanan Halaman Utama Halaman Login Halaman Informasi Login Kembali Halaman Daftar Halaman Data User Halaman Edit Data Halaman Pemilihan Menu Makanan Halaman Data Makanan Administrator Halaman Daftar User Baru Halaman Profil User Halaman Halaman Pemilihan Menu Makanan Halaman Keterangan Makanan Halaman Daftar Makanan
7 7 8 8 9 10 11 14 16 21 29 33 34 35 37 43 44 45 46 46 47 49 50 50 51 51 52 52 53 53 54 54 55 55
Universitas Sumatera Utara
xi
DAFTAR LAMPIRAN
Hal. Listing Program Daftar Kandugan Bahan Makanan (DKBM) Tahun 2005 Tabel Angka Kecukupan Gizi 2004 bagi Orang Indonesia Daftar Makanan Yang Harus Dipantang Dan Diperbolehkan Bagi Penderita Asam Urat E. Ukuran Rumah Tangga (URT) F. Curriculum Vitae A. B. C. D.
A-1 B-1 C-1 D-1 E-1 F-1
Universitas Sumatera Utara
