APLIKASI INTERPRETER SAMLIN UNTUK MENYELESAIKAN SISTEM PERSAMAAN LINIER
TUGAS AKHIR
Diajukan untuk melengkapi persyaratan guna mendapatkan gelar sarjana strata satu
Oleh: Mursid Dwi Hastomo / 4150412-056
PROGRAM STUDI TEKNIK INFORMATIKA FAKULTAS ILMU KOMPUTER UNIVERSITAS MERCU BUANA 2008
LEMBAR PENGESAHAN
APLIKASI INTERPRETER SAMLIN UNTUK MENYELESAIKAN SISTEM PERSAMAAN LINIER TUGAS AKHIR
Diajukan untuk melengkapi persyaratan guna mendapatkan gelar sarjana strata satu
Oleh: Mursid Dwi Hastomo / 4150412-056
Disetujui Oleh: Dosen Pembimbing,
Dosen Penguji,
Abdusy Syarif, MT
Raka Yusuf, ST, MTI
Jakarta, 29 Maret 2008 Diketahui dan Disahkan Oleh :
Ketua Program Studi Teknik Informatika
Abdusy Syarif, MT
ABSTRAK
Pada dasarnya komputer tidak memahami sistem persamaan linier. apalagi mengenali koefisien, variabel, dan konstanta pada sistem persamaan linier yang merupakan masukan untuk menyelesaikan sistem persamaan linier yang akan diselesaikan. Jadi, permasalahannya adalah bagaimana memberikan kemampuan pada komputer melalui sebuah program komputer agar komputer dapat mengenali koefisien, variabel, dan konstanta pada sistem persamaan linier. Setelah bagian-bagian sistem persamaan linier seperti koefisien, variabel, dan konstanta pada setiap persamaan diketahui, maka komputer harus dapat menggunakan bagian-bagian tersebut untuk mencari jawaban atau solusi dari sistem persamaan linier tersebut dengan cepat dan akurat. Interpreter yang nanti akan dibuat terdiri dari dua bagian utama. Bagian pertama bertugas menguraikan sistem persamaan linier yang harus diselesaikan menjadi array seperti manusia mengubah sistem persamaan linier ke dalam perkalian matriks. Sedangkan bagian kedua bertugas menganalisis array yang dihasilkan oleh bagian pertama agar dapat ditemukan solusi sistem persamaan linier tersebut. Kata kunci : Persamaan linear, Interpreter.
i
KATA PENGANTAR
Alhamdulillah puji dan syukur penulis panjatkan atas kehadirat Allah SWT, untuk rahmat dan karunia yang telah diberikan sehingga pada akhirnya penulis dapat menyelesaikan tugas akhir ini. Adapun tugas akhir ini dibuat sebagai salah satu syarat untuk meraih gelar sarjana dalam program studi strata satu (S1) jurusan teknik informatika di Universitas Mercu Buana, Jakarta. Dalam melaksanakan tugas akhir sampai pembuatan laporan ini, penulis banyak mendapat bimbingan, dorongan maupun bantuan dari berbagai pihak. Pada kesempatan ini, penulis sampaikan rasa terima kasih yang sebesar-besarnya, terutama kepada Yth :
1. Bapak Abdusy Syarif, MT selaku ketua Program Studi Teknik Informatika Universitas Mercu Buana, Jakarta. 2. Bapak Abdusy Syarif, MT selaku Dosen Pembimbing yang telah banyak sekali memberikan bimbingan dan pengarahan kepada penulis, atas waktu dan kesempatan yang diberikan hingga semuanya terjadwal dengan baik tanpa suatu halangan yang berarti. 3. Mama tercinta yang selalu memberikan dorongan, kasih sayang dan perhatian serta nasihat untuk menjaga kesehatan dan tidak lupa pemberiannya sampai saat ini. 4. Istri tercina Dian Ayuningtyas yang telah memberikan semangat dan bimbingan. 5. Teman teman IT yang terlibat dalam skripsi ini, Sofyan, Rizqon Fahcrudin, Bagus Handhaka selaku system support untuk ide aplikasinya, dan teman teman lain yang turut membantu.
Dan kepada semua pihak yang tidak dapat penulis sebutkan satu persatu, penulis ucapkan terima kasih. Harapan penulis, semoga Laporan Tugas Akhir ini dapat bermanfaat bagi siapa saja, baik itu bagi penulis maupun bagi mahasiswa lainnya dan semoga semua pihak yang telah membantu penulis dalam penyelesaian laporan ini mendapat berkah yang berlimpah dari Allah SWT. Amin.
Bekasi, Februari 2008
Mursid Dwi Hastomo
ii
DAFTAR ISI
Abstraksi ........................................................................................................................i Kata Pengantar ..........................................................................................................................ii Daftar Isi ..................................................................................................................................iii Daftar Tabel .............................................................................................................................v Daftar Gambar ..........................................................................................................................vi Daftar Simbol ..........................................................................................................................vii Bab I. Pendahuluan I.1 Latar Belakang ........................................................................................................1 I.2 Batasan Masalah .....................................................................................................3 I.3 Tujuan Penulisan .....................................................................................................3 I.4 Metodelogi Penelitian .............................................................................................4 I.5 Sistematika Penulisan .............................................................................................5 Bab II. Landasan Teori II.1 Teori Bahasa ..........................................................................................................6 II.2 Predictive Parser ....................................................................................................7 II.3 Interpreter ..............................................................................................................8 II.4 Sistem Persamaan Linier .....................................................................................10 Bab III. Spesifikasi Bahasa Samlin Script dan Rancangan Interpreter Samlin III.1 Spesifikasi SAMLIN script ..............................................................................14 III.1.1 Spesifikasi Leksikal .................................................................................14 III.1.2 Spesifikasi Sintaksis ................................................................................15 III.1.3 Spesifikasi Semantik ...............................................................................16 III.2 Garis Besar Algoritma Interpreter SAMLIN .....................................................16 III.3 Rancangan Interpreter SAMLIN ........................................................................17 III.3.1 Bentuk Pengurai (Parser) .........................................................................17 III.3.2 Rancangan Bentuk Masukan (input), Keluaran (Output) dan Antarmuka (Interface).................................................................................................20 III.3.3 Algoritma Sumber SAMLIN dan Flowchart ...........................................21 Bab IV. Implementasi Interpreter SAMLIN dan Pengujian ....................................................29 IV.1 Tampilan Layar ..................................................................................................29 IV.1.1 Tampilan Awal dan Tampilan Utama Program ......................................29 IV.1.2 Tampilan Input dan Output .....................................................................33 IV.2.2 Spesifikasi Hardware dan Software untuk Uji Kasus .............................37 IV.2 Pengujian Aplikasi SAMLIN .............................................................................38
iii
IV.3 Skenario Pengujian .............................................................................................38 IV.4 Penjelasan Skenario Pengujian ..........................................................................38 IV.4.1 Penyelesaian dengan Jawaban Unik / Tunggal Nonhomogen ................38 IV.4.2 Penyelesaian dengan Jawaban Nonhomogen Banyak / Tak Terhingga ..49 IV.4.3 Penyelesaian dengan Jawaban Nonhomogen Tiada Penyelesaian / Tidak Ada Jawaban.............................................................................................54 IV.4.4 Syntax Error..............................................................................................56 IV.5 Analisis Hasil Pengujian ....................................................................................60 Bab V Penutup .......................................................................................................................65 V.1 Kesimpulan ..........................................................................................................65 V.2 Saran – saran ........................................................................................................66
iv
DAFTAR TABEL Halaman Tabel 2.1
: Regular Grammar …………………………………………………....7
Tabel 4.1
: Tabel Proses Linked List Contoh Kasus-1 …………………………40
Tabel 4.2
: Tabel Array Contoh Kasus-1……………………………………….40
Tabel 4.3
: Tabel Proses Linked List Contoh Kasus-2…………………………46
Tabel 4.4
: Tabel Proses Linked List Contoh Kasus-2…………………………46
Tabel 4.5
: Tabel Contoh Kasus-3…………………………………………….. 48
Tabel 4.6
: Tabel Contoh Kasus-1 NonHomogen dengan jawaban banyak……50
v
DAFTAR GAMBAR Halaman Gambar
3.1
: Graf Sintaks Parser.............................................................18
Gambar
3.2
: Graf Sintaks Hasil Modifikasi............................................19
Gambar
3.3
: Rancangan Interface SAMLIN…………………………...21
Gambar
3.4
: Flowchart SAMLIN………………………………………25
Gambar
4.1
: Tampilan Muka Aplikasi SAMLIN....................................30
Gambar
4.2
: Tampilan tombol Eksekusi……………………………….33
Gambar
4.3
: Gambar sebelum tombol clear input di tekan…………….34
Gambar
4.4
: Sesudah tombol clear ditekan…………………………….35
Gambar
4.5
: Tampilan tombol Keluar………………………………….36
Gambar
4.6
: Daftar proses Linked list.....................................................39
Gambar
4.7
: Layout hasil eksekusi Aplikasi SAMLIN...........................43
Gambar
4.8
: Gambar balok-balok saling menempel...............................44
Gambar
4.9
: Gambar Masing-masing balok terpisah..............................44
Gambar
4.10
: Daftar proses Linked List...................................................45
Gambar
4.11
: Penyelesaian dengan Aplikasi SAMLIN............................47
Gambar
4.12
: Penyelesaian dengan Aplikasi SAMLIN…………………50
Gambar
4.13
: Penyelesaian dengan Aplikasi SAMLIN…………………53
Gambar
4.14
: Penyelesaian dengan Aplikasi SAMLIN…………………55
Gambar
4.15
: Penyelesaian dengan Aplikasi SAMLIN............................56
Gambar
4.16
: Penyelesaian dengan Aplikasi SAMLIN…………………58
Gambar
4.17
: Penyelesaian dengan Aplikasi SAMLIN............................60
Gambar
4.18
: Kesalahan Pada penulisan………………………………...63
vi
DAFTAR SIMBOL
SIMBOL
NAMA
ARTI
Proses
Menggambarkan proses atau kegiatan tertentu
Connection
Digunakan menghubungkan modul dengan lainnya
untuk suatu modul
Decision
Menggambarkan suatu keputusan atau tindakan yang harus diambil pada kondisi tertentu
Input atau Output
Menggambarkan kegiatan suatu masukan atau keluaran
Terminator
Menggambarkan kegiatan awal atau akhir suatu proses
Off Page Connector
Penghubung pada halaman yang berbeda
On Page Connector
Penghubung pada halaman yang sama
Predifined process
Menggambarkan suatu proses, seperti subroutine atau modul
vii
BAB I PENDAHULUAN I.1.
Latar Belakang Persoalan yang sering muncul dalam kehidupan sehari-hari, sering kali persoalan
tersebut dapat dirumuskan dengan memakai model matematika yang di antaranya berbentuk sistem persamaan linier. Persoalan tersebut bisa diselesaikan dengan sistem persamaan linier tersebut secara manual, bila masalahnya sederhana atau jumlah variabelnya sedikit. Tetapi, bila jumlah variabel dan jumlah persamaan tersebut banyak ditambah lagi bila pekerjaan tersebut harus dilakukan berulang-ulang, maka penyelesaian secara manual akan sangat melelahkan. Salah satu alternatif yang dapat ditempuh untuk mengatasi hal ini adalah dengan menggunakan komputer. Contoh kasus Sebuah toko komputer menjual tiga jenis barang, yaitu monitor, printer, dan scanner. Jumlah penerimaan pada penjualan 10 unit monitor dan 8 unit printer sebesar Rp 8.200.000. Jumlah penerimaan pada penjualan 5 unit monitor dan 3 unit scanner sebesar Rp 4.300.000. Sedangkan jumlah penerimaan pada penjualan 2 unit printer dan 2 unit scanner sebesar Rp 2.000.000. Dari data-data tersebut ingin diketahui harga per unit masing-masing untuk monitor, printer, dan scanner. Persoalan ini dapat dirumuskan dengan sistem persamaan linier, berikut ini : 10 Monitor + 8 Printer = 8200000 5 Monitor + 3 Scanner = 4300000 2 Printer + 2 Scanner = 2000000
10x + 8y = 8.200.000 -4y + 3z = 200.000 3,5z = 2.100.000 3,5z = 2.100.000 z = 2.100.000 = 600.000 3,5
1
2
-4y + 3 X 600.000 = 200.000 -4y = 200.000 – 1.800000 = -1.600.000 -4y = -1.600.000 y = -1.600.000 = 400.000 -4
10x + 8y = 8.200.000 10x + 8 X 400.000 – 3.200.000 10x = 5000.000 x = 5000.000 = 500.000 10 dimana x = Monitor y = Printer z = Scanner Untuk menyelesaikan sistem persamaan linier tersebut dengan interpreter SAMLIN, maka sistem persamaan linier tersebut harus ditulis sebagai berikut : SAMLIN {
10*Monitor + 8*Printer = 8200000; 5*Monitor + 3*Scanner = 4300000; 2*Printer + 2*Scanner = 2000000; }
Seterusnya hasil-hasil tersebut direpresentasikan dalam bentuk string yang diperlakukan sebagai keluaran interpreter SAMLIN seperti berikut : Persamaan bersifat nonhomogen. Karena r(A) = r(A,B) = 3 dan r = n = 3 jadi, jawaban tuggal. Jawabannya adalah sebagai berikut : Monitor = 500000 Printer = 400000 Scanner = 600000
3
Keterangan : r(A): rank baris matriks koefisien r(A,B): rang baris augmented matrix r = r(A,B) n = jumlah variable I.2
Batasan Masalah Ada beberapa masalah yang ditemukan dan harus diselesaikan dengan sistem
persamaan linier yaitu : a. Pada dasarnya komputer tidak memahami sistem persamaan linier. apalagi mengenali koefisien, variabel, dan konstanta pada sistem persamaan linier yang merupakan masukan untuk menyelesaikan sistem persamaan linier yang akan diselesaikan. Jadi, permasalahannya adalah bagaimana memberikan kemampuan pada komputer melalui sebuah program komputer agar komputer dapat mengenali koefisien, variabel, dan konstanta pada sistem persamaan linier. b. Setelah bagian-bagian sistem persamaan linier seperti koefisien, variabel, dan konstanta pada setiap persamaan diketahui, maka komputer harus dapat menggunakan bagian-bagian tersebut untuk mencari jawaban atau solusi dari sistem persamaan linier tersebut dengan cepat dan akurat. Pada skripsi ini pembahasan pembuatan bahasa SAMLIN Script dan perekayasaan interpreter SAMLIN untuk memecahkan permasalahan tetapi masih sangat sederhana. Program yang diuraikan dalam tulisan ini hanya merupakan sebuah prototipe program. Oleh sebab itu, masih sangat terbuka kemungkinan untuk mengembangkan, memperbaiki, dan menyempurnakannya.
I.3.
Tujuan Penulisan Tujuan perekayasaan interpreter SAMLIN adalah untuk menjawab persamaan
linier yang sangat sederhana, aplikasi ini di buat agar perhitungan persamaan linier sederhana bisa diselesaikan dengan komputer.
4
Sebenarnya, dengan program komputer yang menerapkan metode numerik tanpa kecerdasan tiruan, sistem persamaan linier sudah dapat diselesaikan. Tetapi pengguna tetap harus menentukan koefisien, variabel, dan konstanta dari sistem persamaan linier secara manual dan baru memasukkan koefisien, variabel, dan konstanta tersebut sebagai masukan bagi program komputer. Hal ini cukup merepotkan bagi pengguna. Tetapi, bila program komputer tersebut dilengkapi dengan kemampuan untuk mengenali sistem persamaan linier sehingga ia mampu menentukan koefisien, variabel, dan konstanta pada sistem persamaan linier, maka pengguna tidak perlu lagi melakukannya. Pengguna hanya perlu memasukkan sistem persamaan linier tersebut sebagai input dan selanjutnya komputer yang melakukan analisis dan memberikan solusi untuk sistem persamaan linier yang dimasukkan. Sebuah bahasa sederhana (script) diupayakan,dibuat dan direkayasa sebuah interpreter sederhana agar dapat mengekseskusi bahasa tersebut untuk menterjemahkan, menganalisis, dan menyelesaikan sistem persamaan linier. Bahasa tersebut diberi nama SAMLIN Script, sedangkan interpreter untuk mengeksekusi SAMLIN Script
diberi
nama SAMLIN.
I.4
Metodelogi Penelitian Metode penelitian yang digunakan untuk mendapatkan bahan-bahan yang
diperlukan dalam perekayasaan interpreter SAMLIN ini, yaitu : 1. Studi kepustakaan, dilakukan untuk mendapatkan metode-metode untuk menyelesaikan sistem persamaan linier, menyusun bahasa, dan merekayasa interpreter. 2. Eksperimen, dilakukan untuk menentukan metode terbaik dari beberapa metode yang didapat melalui studi kepustakaan untuk kemudian digunakan untuk mengimplementasikan program ini.
5
I.5.
Sistematika Penulisan Untuk mendapatkan gambaran yang jelas dan mempermudah penulisan ini, maka
penulis menyusunnya menjadi beberapa bab yaitu : Bab I :
PENDAHULUAN Bab ini berisi latar belakang penulisan, permasalahan yang akan dipecahkan, tujuan penulisan, batasan permasalahan, metode penelitian, dan sistematika penulisan.
Bab II :
LANDASAN TEORI Bab landasan teori ini terdiri dari pembahasan mengenai teori bahasa, predictive parser, dan tentu saja mengenai sistem persamaan linier.
Bab III :
SPESIFIKASI BAHASA SAMLIN SCRIPT DAN RANCANGAN INTERPRETER SAMLIN Bab Rancangan berisikan spesifikasi leksikal, spesifikasi sintaksis, dan spesifikasi semantik untuk bahasa SAMLIN Script. Pada bab ini juga dibahas tentang perancangan parser yang akan digunakan, rancangan input, rancangan output, dan antarmuka program.
Bab IV :
IMPLEMENTASI INTERPRETER SAMLIN DAN PENGUJIAN Bab Implementasi ini dibahas garis besar algoritma atau cara kerja interpreter SAMLIN, Bagian-bagian atau komponen-komponen kode sumber interpreter SAMLIN ini, juga contoh aplikasi dari program ini.
Bab V :
PENUTUP Bab ini berisi kesimpulan mengenai perekayasaan program ini dan saran-saran untuk lebih menyempurnakan program ini.
6
BAB II LANDASAN TEORI II.1
Teori Bahasa Sebuah bahasa merupakan himpunan kalimat. Kalimat adalah rangkaian lambang-
lambang dalam bahasa. Permasalahan yang berkaiatan dengan bahasa yang sering muncul
adalah
penentuan
kesesuaian
sebuah
kalimat
dengan
bahasa
yang
dispesifikasikan atau penyusunan sebuat kalimat berdasarkan tatabahasa yang dispesifikasikan. Persoalan tersebut dapat diselesaikan dengan cara menyajikan bahasa. Sebuah bahasa disajikan dengan menggunakan sebuah tata bahasa (grammar). Tata Bahasa G = (N, T, P, S) terdiri dari empat komponen, yaitu : a. Himpunan lambang non-terminal (N), adalah intermediate symbol yang digunakan untuk menyatakan struktur kalimat. b. Himpunan lambang terminal (T), adalah lambang-lambang yang digunakan untuk menyusun kalimat-kalimat dalam bahasa yang bersangkutan. c. Himpunan
produksi
(P),
merupakan
aturan-aturan
gramatikal
yang
menspesifikasikan bagaimana kalimat-kalimat dalam bahasa dapat disusun. Sebuah produksi berbentuk α → β, sedangkan α dan β adalah rangkaian lambang terminal dan/atau non-terminal. Produksi ini menyatakan bahwa α dapat ditransformasikan menjadi β. d. Starting symbol (S), adalah lambang non-terminal khusus yang memulai penyusunan atau penguraian kalimat dalam bahasa. Tata bahasa digolongkan ke dalam beberapa tingkatan tipe. Untuk memudahkan uraian berikut, A dan B digunakan untuk menyatakan suatu lambang non-terminal, a dan b untuk menyatakan suatu lambang terminal, sedangkan α dan β untuk menyatakan suatu rangkaian lambang terminal dan/atau non-terminal.
7
Sebuah tata bahasa disebut tata bahasa tipe-3 (regular grammar) jika semua produksi dalam tata bahasa berbentuk : A→a A → aB
atau
A→a A → Ba
Tabel 2.1 :Regular Grammar Ruas kiri dari setiap produksi selalu berupa sebuah lambang non-terminal dan ruas kanan berupa sebuah lambang terminal atau sebuah lambang terminal dan lambang non-terminal. Dalam tata bahasa tipe-2 (context free grammar) setiap produksi berbentuk : A→ β Ruas kiri dari setiap produksi selalu berupa sebuah lambang non-terminal. Dalam tata bahasa tipe-1 (context sensitive grammar) setiap produksi berbentuk : α→β dengan syarat panjang α lebih kecil atau sama dengan panjang β. Bila tidak memenuhi persyaratan ini maka tata bahasa termasuk tipe-0 (unrestricted grammar). Suatu tata bahasa pada suatu tipe juga termasuk pada tipe tata bahasa di bawahnya. Jadi, tata bahasa tipe-3 juga merupakan tata bahasa tipe-2, tipe-1, dan tipe-0. Begitu seterusnya. Bersesuaian dengan tipe-tipe tata bahasa yang berbeda, tipe-tipe bahasa juga berbeda. Suatu bahasa dikatakan sebagai bahasa tipe-i (i = 0, 1, 2, 3) jika bahasa tersebut dapat dispesifikasikan dengan menggunakan tata bahasa tipe-i, tetapi tidak dapat dispesifikasikan dengan menggunakan tata bahasa tipe-(i + 1). II.2
Predictive Parser Predictive parser merupakan salah satu metode yang efisien untuk menerapkan
parser. Parser jenis ini tidak mengijinkan pelacakan mundur karena pelacakan mundur dapat memperumit implementasi parser. Tata bahasa harus memenuhi aturan-aturan
8
berikut ini yang digunakan untuk menyatakan bahwa simbol terminal awal dari bagian kanan (aturan produksi) harus berbeda. ATURAN I Diketahui aturan produksi : A → ζ1 | ζ2 | ... | ζn himpunan simbol terminal awal semua kalimat yang dapat dibangkitkan dari ζi harus saling berlainan, yaitu : first(ζi) ∩ first(ζj) = ∅ untuk semua i ≠ j. Himpunan first(ζ) adalah himpunan semua simbol terminal yang dapat muncul dalam posisi pertama dari kalimat yang dapat diturunkan dari ζ. ATURAN II Untuk setiap simbol A ∈ N yang membangkitkan deret kosong (A → ε), himpunan simbol-simbol awalnya harus saling asing terhadap himpunan simbol yang dapat diikuti dengan sembarang deret yang dibangkitkan oleh A, yaitu : first(A) ∩ follow(A) = ∅.
II.3
Interpreter Interpreter adalah program yang mengeksekusi instruksi yang ditulis dalam
bahasa pemrograman tingkat tinggi. ada dua cara untuk menjalankan program yang ditulis dalam bahasa pemrograman tingkat tinggi. Cara yang paling umum adalah dengan mengkompilasinya, dan cara yang kedua adalah menggunakan interpreter. Interpreter menerjemahkan instruksi dalam bahasa tingkat tinggi ke dalam bentuk antara yang kemudian dieksekusi (dijalankan). Sebaliknya, compiler menerjemahkan instruksi dalam bahasa tingkat tinggi ke dalam bahasa mesin. Program yang dikompilasi secara umum lebih cepat daripada yang menggunakan interpreter. Keuntungan interpreter adalah program tidak perlu dikompilasi untuk dapat dijalankan. Proses kompilasi ini dapat memakan waktu, terutama jika program yang dikompilasi panjang. Baik interpreter maupun compiler tersedia pada
9
sebagian besar bahasa pemrograman tingkat tinggi. Meski demikian, BASIC dan LISP dirancang untuk dijalankan dengan interpreter. Interpreter juga dapat ditemukan pada page description language, seperti PostScript. Setiap printer PostScript printer mempunyai interpreter built-in yang menjalankan instruksi PostScript.
II.4
Sistem Persamaan Linier a. Bentuk Umum Sistem Persamaan Linier Suatu persamaan disebut persamaan linier jika pangkat tertinggi variabelnya adalah satu. Dalam bentuk umum sistem persamaam linier dapat ditulis sebagai berikut : a 11 x 1 + a 12 x 2 + a 13 x 3 + ... + a 1n x n = b1 a 21 x 1 + a 12 x 2 + a 23 x 3 + ... + a 2 n x n = b 2 a 13 x 1 + a 32 x 2 + a 33 x 3 + ... + a 3n x n = b 3 .... .... .... .... .... .... a m1 x 1 + a m 2 x 2 + a 13 x 3 + ... + a 1n x n = b m Setiap a adalah skalar yang disebut koefisien dan setiap b adalah skalar yang disebut konstanta, sedangkan setiap x disebut variabel. Sistem persamaan linier dapat disajikan dalam bentuk perkalian matriks yaitu sebagai berikut : ⎛ a 11 ⎜ ⎜ a 21 ⎜a ⎜ 31 ⎜ ... ⎜a ⎝ m1
a 12 a 22 a 32 ... a m2
a 13 a 23 a 33 ... a m3
... a 1n ⎞⎛ x 1 ⎞ ⎛ b1 ⎞ ⎟⎜ ⎟ ⎜ ⎟ ... a 2 n ⎟⎜ x 2 ⎟ ⎜ b 2 ⎟ ... a 3n ⎟⎜ x 3 ⎟ = ⎜ b 3 ⎟ ⎟⎜ ⎟ ⎜ ⎟ ... ... ⎟⎜ ... ⎟ ⎜ ... ⎟ ... a mn ⎟⎠⎜⎝ x n ⎟⎠ ⎜⎝ b m ⎟⎠
atau
AX = B
10
Matriks A yang berukuran (m x n) disebut matriks koefisien dan dapat berupa matriks bujur sangkar bila m = n. Sedangkan X dan B adalah vektorvektor kolom variabel dan konstanta. Misalnya ada sistem persamaan linier :
2x + y + z = 7 4 x + 4 y + 3z = 21 6 x + 7 y + 4z = 32 dapat ditulis dalam bentuk perkalian matiks : ⎛ 4 1 1 ⎞⎛ x ⎞ ⎛ 7 ⎞ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎜ 4 4 3 ⎟⎜ y ⎟ = ⎜ 21⎟ . ⎜ 6 7 4 ⎟⎜ z ⎟ ⎜ 32 ⎟ ⎠⎝ ⎠ ⎝ ⎠ ⎝
b. Klasifikasi Sistem Persamaan Linier Sistem persamaan linier dapat diklasifikasikan sebagai berikut. 1) Sistem persamaan linier homogen. Syaratnya AX = 0. Sistem persamaan linier homogen selalu mempunyai jawaban. a. Jika r = n maka jawaban selalu 0 (jawaban trival). b. Jika r < n maka ada jawaban selain jawaban trival. 2) Sistem persamaan linier non-homogen. Syaratnya AX = B dan B ≠ 0. a. Jika r(A) ≠ r(A,B) maka tidak ada jawaban. b. Jika r(A) = r(A,B) maka ada jawaban. •
Jika r = n maka jawaban unik (tunggal).
•
Jika r < n maka jawaban lebih dari satu (banyak jawaban).
c. Metode Eliminasi Gauss Menurut Dr. Eng. Supriyanto, M.Sc ada beberapa metode yang dapat digunakan untuk menyelesaikan sistem persamaan linier simultan, antara lain: metode grafik, metode Cramer, metode invers matriks, metode Gauss-Seidel, metode eliminasi Gauss, dan metode Gauss-Jordan.
11
Eliminasi Gauss adalah suatu cara mengoperasikan nilai-nilai di dalam matriks sehingga menjadi matriks yang lebih sederhana (ditemukan oleh Carl Friedrich Gauss). Caranya adalah dengan melakukan operasi baris sehingga matriks tersebut menjadi matriks yang Eselon-baris. Ini dapat digunakan sebagai salah satu metode penyelesaian persamaan linear dengan menggunakan matriks. Caranya dengan mengubah persamaan linear tersebut ke dalam matriks teraugmentasi dan mengoperasikannya. Setelah menjadi matriks Eselon-baris, lakukan substitusi balik untuk mendapatkan nilai dari variabel-variabel tersebut. Metode eliminasi Gauss merupakan salah satu metode yang cukup tua tetapi masih layak dipergunakan untuk menyelesaikan sistem persamaan linier yang kompleks dengan bantuan komputer. Bahkan dengan sedikit modifikasi dan tanbahan, tidak hanya dapat menyelesaikan sistem persamaan linier yang bebas linier, tetapi dapat juga digunakan untuk mencari jawaban umum untuk sistem persamaan yang bergantung linier. Inti dari metode eliminasi Gauss adalah mengeliminasi (menghilangkan) semua variabel di bawah elemen diagonal pada matriks koefisien dengan transformasi elementer baris pada augmented matrix (matriks hasil penggabungan matriks koefisien dan vektor kolom konstanta dengan cara menjadikan vektor kolom konstanta sebagai kolom terakhir matriks koefisien). Proses eliminasi Gauss terlihat seperti pada tahapan-tahapan yang dilakukan pada sistem persamaan linier berikut ini : 2x + y + z = 7 4 x + 4 y + 3 z = 21 6 x + 7 y + 4 z = 32 Kalikan persamaan pertama dengan –2 dan jumlahkan pada persamaan kedua. Kemudian kalikan persamaan pertama dengan –3 dan jumlahkan pada persamaan ketiga. Maka hasilnya sebagai berikut : 2x + y + z = 7 2y + z = 7 4 y + z = 11
12
Kalikan persamaan kedua dengan –2 dan jumlahkan pada persamaan ketiga. Dan hasilnya adalah seperti berikut : 2x + y + z = 7 2y + z = 7 − z = −3
Akhirnya, dengan substitusi dapat ditentukan nilai x, y, dan z, yaitu x = 1, y = 2, dan z = 3. Dengan menggunakan komputer maka pelaksanaannya dilakukan sebagai berikut. Mula-mula dibentuk augmented matriz dan melakukan transformasi elementer baris seperti tahap-tahap pada sistem persamaan linier di atas. ⎛2 ⎛2 1 1 7⎞ ⎟ H 21( −2 ) ⎜ ⎜ ⎜ 4 4 3 21⎟ ⎯⎯ ⎯→⎜ 0 ⎜6 ⎜ 6 7 4 32 ⎟ ⎝ ⎠ ⎝ ⎛2 ⎛2 1 1 7⎞ ⎟ H32( −2 ) ⎜ ⎜ ⎜ 0 2 1 7 ⎟ ⎯⎯ ⎯→⎜ 0 ⎜0 ⎜ 0 4 1 11⎟ ⎝ ⎠ ⎝
1 1 7⎞ ( −3 ) ⎟ 31 2 1 7 ⎟ ⎯H⎯ ⎯→ ⎟ 7 4 32 ⎠ 1 1 7⎞ ⎟ 2 1 7⎟ 0 − 1 − 3 ⎟⎠
Maka dari baris ketiga diperoleh z = (-3)/(-1) = 3. Kemudian z disubstitusikan pada baris kedua dan diperoleh y = (7 – 1(3))/2 = 2. Lalu y dan z disubstitusikan pada baris pertama dan diperoleh x = (7 – 1(2) – 1(3))/2 = 1. Dalam menerapkan metode eliminasi Gauss pada komputer ada beberapa masalah yang dapat muncul, yaitu sebagai berikut : 1) Pembagian dengan nol atau bilangan yang sangat kecil yang mendekati nol. Pembagian dengan nol (divide by zero) berakibat sangat fatal bagi program komputer karena jalannya program tidak terkendali lagi. Untuk mengatasi masalah ini dapat dilakukan beberapa cara, antara lain dengan pemeriksaan pembagi dan pertukaran baris (pivoting). 2) Kesalahan pembulatan. Masalah ini tidak dapat dihindari pada komputer, yang bisa dilakukan hanyalah meminimalkannya. Beberapa cara untuk mengurangi kesalahan pembulatan antara lain dengan menggunakan angka
13
significan lebih banyak, penskalaan, menghindari pembagian bilangan yang sangat besar dengan bilangan yang sangat kecil, dan koreksi kesalahan. 3) Sistem kondisi timpang (dur kondisi). Masalah ini muncul bila perubahan kecil pada koefisien menyebabkan perubahan besar pada solusi (jawaban). Masalah ini sangat berkaitan dengan ketiga masalah sebelumnya. Beberapa cara untuk mengatasi masalah ini antara lain dengan menggunakan angka signifikan lebih banyak, melakukan pemutaran (pivoting) parsial, melakukan penskalaan, dan dengan koreksi kesalahan.
14
BAB III SPESIFIKASI BAHASA SAMLIN SCRIPT DAN RANCANGAN INTERPRETER SAMLIN
III.1
Spesifikasi SAMLIN Script
III.1.1 Spesifikasi Leksikal
Spesifikasi leksikal adalah suatu bahasa pemrograman untuk menentukan macammacam token yang terdapat dalam bahasa tersebut. Dalam penulisan suatu penerjemah, spesifikasi leksikal biasanya disajikan dengan menggunakan RE (Regular Expression). Beberapa kelebihan RE antara lain : 1) penyajian aturan-aturan leksikal menjadi sederhana, 2) penyajian himpunan token menjadi mudah dipahami, dan 3) penyusunan penganalisis leksikal yang efisien menjadi lebih mudah. Berikut ini adalah Regular Expression yang digunakan untuk menspesifikasikan token-token yang terdapat dalam SAMLIN Script : 1) huruf → A|B|C|...|Z 2) angka → 0|1|2|...|9 3) koma_desimal → .|, 4) tanda_minus → 5) tanda_plus → + 6) tanda_asterik → * 7) tanda_sama_dengan → = 8) nama_variabel → huruf(angka|huruf)* 9) skalar_tanpa_tanda → angka+(koma_desimal angka+|ε)(E(+|-|ε)angka+|ε) 10) kata_samlin → SAMLIN 11) tanda_titik_koma → ; 12) kurung_kurawal_buka → { 13) kurung_kurawal_tutup → }
15
Catatan: 1) Huruf kecil dan huruf kapital dianggap sama (tidak case sensitive). 2) Nama variabel yang berarti hanya 15 karakter pertama. 3) Koma_desimal yang sah adalah yang sesuai dengan pengaturan (setting) pada Windows tempat program ini dijalankan. 4) Jangkauan skalar_tanpa_tanda adalah dari 3,4.10-4932 sampai 1,1.104932 dengan ketelitian 19 digit.
III.1.2 Spesifikasi Sintaksis
Spesifikasi sinstaksis sebuah scripts atau bahasa pemrograman menentukan aturan-aturan susunan token utnuk membuat kalimat atau program dalam bahasa yang bersangkutan untuk menyelesaikan suatu permasalahan. Berikut ini spesifikasi sintaksis SAMLIN Script dengan menggunakan CFG (context free gramaar) : G
=
(N, T, P, S)
N
=
{<SKRIP>, <SPL>,
, <Ekspresi>, , ,
,
,
,
, } T
=
{SAMLIN, {, }, ;, = , +, -, *, nama_variabel, skalar_tanpa_tanda}
S
=
<SKRIP>
P
=
himpunan produksi berikut. <SKRIP> → SAMLIN { <SPL> } <SPL> → ; <SPL> | ε → <Ekspresi> = <Ekspresi> → → nama_variabel
→
| ε → skalar_tanpa_tanda → skalar_tanpa_tanda * | ε
nama_variabel
16
→ - | ε → + | -
Semua produksi dalam himpunan P telah memenuhi persyaratan atau aturanaturan sebagai predictive parser yang nanti akan uraikan.
III.1.3 Spesifikasi Semantik
Berikut ini spesifikasi aturan-aturan semantik untuk SAMLIN Script yang meliputi pembahasan beberapa token, nama variabel, operator dan operan, dan ekspresi persamaan linier antara lain : a) Bila dalam satu persamaan muncul dua nama variabel yang sama, maka koefisien variabel tersebut akan dijumlahkan. Jadi, persamaan 2x + 3y –x = 5 sama artinya dengan x + 3y = 5. b) Nama variabel yang berarti hanya 15 karakter pertama. Bila nama variabel lebih panjang dari 15 karakter maka yang digunakan hanya 15 karakter pertama. Jadi, bila terdapat dua buah variabel yang berbeda tetapi 15 karakter pertama keduanya sama, maka kedua nama variabel tersebut dianggap sama. c) Jangkauan skalar (bilangan riil) tanpa tanda adalah dari 3,4.10-4932 sampai 1,1.104932 dengan ketelitian 19 digit. d) Maksimum jumlah variabel dan jumlah persamaan adalah 1024 buah.
III.2
Garis Besar Algoritma Interpreter SAMLIN
Input (masukan) yang berupa string yang mengikuti aturan tata bahasa SAMLIN Script diuraikan oleh penganalisis leksikal sehingga dapat dikenali token-token (simbolsimbol terminal) yang terdapat dalam string masukan tersebut satu per satu. Bila ada token yang tidak dikenali, maka program ini akan menghasilkan output berupa pesan kesalahan. Setiap sebuah token yang dapat dikenali, penganalisis sintaks melakukan pemeriksaan untuk memastikan bahwa tidak ada kesalahan sintaks pada string masukan. Bila
17
terdapat kesalahan sintaks, maka program ini akan menghasilkan keluaran berupa pesan kesalahan. Bila tidak terjadi kesalahan sintaks maka program mendaftarkan koefisienkoefisien, variabel-variabel, dan konstanta-konstanta pada setiap persamaan dalam sistem persamaan linier yang sedang dianalisis ke dalam daftar berkait (linked list). Agar lebih mudah dianalisis dan diselesaikan dengan metode eliminasi Gauss, daftar berkait tersebut dikonversi ke dalam bentuk matriks (array). Selanjutnya, dengan menggunakan metode eliminasi Gauss yang dimodifikasi, matriks sistem persamaan linier tersebut dianalisis. Pada tahap inilah ditentukan homogenitas, konsistensi dan sifat jawaban (umum atau tunggal) yang dimiliki oleh sistem persamaan linier yang dianalisis. Kemudian hasil analisis tersebut dikonversi ke dalam bentuk string sebagai keluaran.
III.3
Rancangan Interpreter SAMLIN
III.3.1 Bentuk Pengurai (Parser)
Parser dapat di implementasikan untuk menjadi sebuah tata bahasa, ada dua teknik berbeda yang dapat digunakan. Teknik yang pertama adalah dengan merancang program top-down parsing yang sesuai untuk semua kemungkinan tata bahasa (berlaku umum). Dalam hal ini, suatu tata bahasa akan dinyatakan dalam bentuk struktur data yang merupakan basis agar program dapat bekerja. Dalam beberapa hal program parser akan dikendalikan oleh struktur data yang digunakan, yang dikenal dengan table driven. Teknik yang kedua adalah dengan mengembangkan program top-down parsing yang khusus untuk suatu bahasa dan membangunnya secara sistematis sesuai dengan aturanaturan pemetaan sintaksis ke deretan statement, yaitu ke dalam sebuah program. Dalam hal ini dipilih pendekatan secara khusus karena implementasi menjadi lebih sederhana dan parser yang dihasilkan bekerja lebih efisien. Suatu sistaksis biasanya disajikan ke dalam suatu graf yang disebut dengan graf pengenalan atau grap sintaksis. Graf ini menunjukkan aliran kontrol selama suatu kalimat diuraikan. Berikut ini adalah graf sintaks yang sesuai dengan tata bahasa SAMLIN Script :
18
Gambar 3.1 : Graf Sintaks Parser
19
Agar lebih efisien dan mudah diimplementasikan, beberapa bagian disatukan dan dimodifikasi seperti bagian rekursif yang digantikan dengan iterasi. Graf sintaks hasil modifikasi adalah sebagai berikut :
Gambar 3.2 : Graf Sintaks Hasil Modifikasi Keterangan: a) Simbol elips mewakili simbol terminal. b) Simbol persegi panjang mewakili simbol non-terminal.
20
III.3.2 Rancangan Bentuk Masukan (Input), Keluaran (Output) dan Antarmuka (Interface)
Input untuk program ini adalah string yang berisi satu atau beberapa persamaan linier yang harus sesuai dengan aturan tata bahasa SAMLIN Script. Sedangkan outputnya adalah hasil analisis sistem persamaan linier dan solusi untuk sistem persamaan linier tersebut atau pesan kesalahan bila input tidak sesuai dengan tata bahasa SAMLIN Script atau terjadi kesalahan-kesalahan lainnya. Output dari rancangan program ini adalah string yang berisi jawaban atau solusi yang berbentuk jawaban khusus (solusi tunggal) atau jawaban umum (banyak solusi)). Hal ini tergantung pada persamaan-persamaan linier yang dianalisis. Gambar 3.3 berikut ini memperlihatkan rancangan bentuk antarmuka (interface) dengan contoh masukan (input) dan keluaran (output).
21
-
SAMLIN Input : Skrip Persamaan Linier x – 128 – x x – 128 - x x – 128 - x x – 128 - x x – 128 - x
X
Output : Analisis dan solusi x – 255 – x x – 255 – x x – 255 – x x – 255 – x x – 255 – x x – 255 – x x – 255 – x x – 255 – x x – 255 – x x – 255 – x Eksekusi
Clear
Keluar
Gambar 3.3 : Rancangan Interface SAMLIN
III.3.3 Algoritma Sumber SAMLIN dan Flowchart
Kode sumber SAMLIN terdiri dari beberapa file, yaitu SAMLIN.dpr, Muka.dfn, Muka.pas, DkGlobal.pas, ManajMem.pas, Gauss.pas, dan Parser.pas. File-file yang berekstensi .pas pada Delphi disebut unit. File SAMLIN.dpr adalah file utama dari proyek ini, sedangkan file Muka.dfn dan file Muka.pas adalah form yang menjadi antarmuka (interface) untuk menerima masukan dan menampilkan keluaran dari program ini.
22
File DkGlobal.pas berisi deklarasi semua konstanta, tipe data, dan variabel global yang digunakan oleh unit-unit yang lain antara lain. Muka.pas, ManajMem.pas, Gauss.pas, dan Parser.pas. Unit ManajMem berisi prosedur-prosedur dan fungsi-fungsi untuk manajemen memori. Adapun prosedur-prosedur dan fungsi-fungsi tersebut adalah sebagai berikut : 1) procedure HancurkanLinkedList; Sesuai dengan namanya, prosedur ini berguna untuk membebaskan memori yang digunakan oleh linked list setelah dikonversi ke dalam bentuk matriks. 2) function CariVar(Nama: PChar): PVari; Fungsi ini bertugas mencari alamat variabel. Fungsi ini mengembalikan alamat variabel bila ditemukan atau nil bila variabel tidak ditemukan di dalam daftar berkait. 3) function SisipVar(Nama: PChar): PVari; Fungsi SisipVar bertugas untuk membuat variabel baru pada daftar berkait. Fungsi ini mengembalikan alamat variabel yang dibuatnya. 4) procedure IsiKoefisien(Nilai: Riil; Nama: PChar; Baris: integer); Bertugas mendaftarkan koefisien variabel pada suatu baris pada daftar berkait. 5) procedure IsiKonstanta(Nilai: Riil); Mendaftarkan konstanta ruas kanan sust persamaan pada daftar berkait. 6) procedure
LinkedListKeArray(var
A,
X,
B:
PRiilArray;
var
N:
var
N:
PNamaVarArray); Bertugas melakukan konversi LinkedList de bentuk Array. 7) procedure
HancurkanArray(var
A,
X,
B:
PRiilArray;
PNamaVarArray); Prosedur ini bertugas untuk membebaskan memori yang digunakan oleh array seteleh digunakan dalam mencari jawaban sistem persamaan linier.
23
Unit Gauss berisi beberapa fungsi yang berguna untuk mencari solusi sistem persamaan linier. Fungsi-fungsi tersebut antara lain : 1) function CariJawab(var A: array of Riil; var X: array of Riil; var B: array of Riil; var V: array of TNamaVar; var SPLInfo: TSPLInfo): string; Fungsi ini bertugas mencari solusi dengan cara memanggil fungsi EliminasiGauss dan bila perlu ia juga memanggil fungsi JawabUmum. Fungsi ini mengembalikan string hasis analisis. 2) function JawabUmum(var A: array of Riil; var B: array of Riil; var V: array of TNamaVar; var SPLInfo: TSPLInfo): string; Fungsi ini mengembalikan string persamaan yang merupakan jawaban umum dari sistem persamaan linier yang dianalisis. 3) function EliminasiGauss(var A: array of Riil; var X: array of Riil; var B: array of Riil; var V: array of TNamaVar; var SPLInfo: TSPLInfo): integer; Fungsi EliminasiGauss bertugas melakukan proses eliminasi Gauss terhadap parameter masukan. Fungsi ini mengembalikan 0 bila sistem persamaan linier mempunyai solusi tunggal, 1 bila mempunyai banyak solusi, dan –1 bila persamaan tidak konsisten (tak ada solusi). Umit Parser berisi prosedur-prosedur dan fungsi-fungsi yang merupakan penganalisis leksikal dan sintaksis, penanganan kelasahan, dan bagian utama Parser. 1) Bagian utama parser function Parsing(StrSumber: PChar): string; procedure TentukanSolusiSPL; procedure Persiapan;
2) Penganalisis Sintaksis: Dibuat sesuai dengan graf sintaks. procedure Cocok(Simb: TSimbol); procedure Faktor; procedure Ekspresi; procedure Konstanta;
24
procedure Persamaan; procedure SistemPersamaanLinier; procedure Skrip;
3) Penganalisis Leksikal function Angka(C: char): boolean; begin function Huruf(C: char): boolean; begin function AngkaHuruf(C: char): boolean; begin procedure Resimbol;
4) Penanganan kesalahan procedure Kesalahan(S: string); Kode sumber selengkapnya dimasukkan pada halaman lampiran.
25
Untuk tampilan flowchart Seperti terlihat pada gambar 3.4
Start
Deklarasi Prosedur, Fungsi dan Variabel
Tampilkan layar Utama
Input Skrip Persamaan Linier
Input Pilih
Pilih= "Eksekusi"
Ya
Proses Inisialisasi Pengenalan Simbol Skrip Persamaan Linier
Tidak
Pilih= “Clear input”
Kesalahan = "True"
Ya
Tampilkan Pesan Kesalahan pada variabel
Tidak
Ya
Bersihkan textbox input persamaan linier
Proses Skrip Sistem Persamaan Linier
Tidak
Pilih="Keluar" Tidak Ya
End
Kesalahan = "True"
Ya
Tidak
Proses Penentuan Solusi Skrip Persamaan Linier
Tampilkan Hasil Skrip Persamaan Linier
Gambar 3.4 : Flowchart SAMLIN
Tampilkan Pesan Kesalahan pada bilangan skrip Persamaan Linier
26
Untuk Algoritma dari Flowchart tersebut dapat diilustrasikan sebagai berikut : 1. Fungsi EliminasiGaus 2. Input: 3. A : array koefisien 4. X: array variabel 5. B: array konstanta 6. V: array nama variabel 7. SPLInfo: m=jumlah persamaan, n=jumlah variabel, rA=rank A, rAB=rank A.B, 8. Homogen=persamaan homogen atau tidak. 9. Output: 10. Ret: 0 = jawaban tunggal, 1 = jawaban banyak, -1 = tidak ada jawaban. 11. 12. Proses: 13. JP:= SPLInfo.m; 14. JV:= SPLInfo.n; 15. LP:= JP - 1; 16. LV:= JV - 1; 17. 18. // Tentukan homogenitas persamaan 19. Periksa semua nilai di array B. 20.
Jika semuanya 0, SPLInfo.Homogen = true
21.
Selain itu, SPLInfo.Homogen = false
22. 23. // Proses Eliminasi Gaus 24. Untuk I dari 0 sampai LV 25. 26.
// Cari Pivot terbesar Cari Baris dan Kolom untuk Pivot terbesar (tidak peduli + atau -)
27.
dan masukkan dalam variabel Brs dan Klm
28.
SPLInfo.rA:= I;
27
29.
SPLInfo.rAB:= I;
30.
Jika Pivot terbesar = 0
31.
Untuk J dari I sampai LP
32.
Jika B[J] <> 0 maka SPLInfo.rAB = SPLInfo.rAB + 1
33.
Akhir untuk
34.
Jika SPLInfo.rA < SPLInfo.rAB maka
35. 36. 37.
Ret:= -1
// SPL tidak konsisten
Selain itu Ret:= 1
38.
Akhir jika
39.
Keluar fungsi
// SPL punya banyak jawaban
40. Akhir untuk 41. 42. Jika Klm <> I maka 43.
tukar nilai array A pada kolom Klm dan I
44.
tukar nilai array V pada index Klm dan I
45. akhir jika 46. Jika Brs <> I maka 47.
tukar nilai array A pada baris Brs dan I
48.
tukar nilai array B pada index Brs dan I
49.
akhir jika
50. 51. // Eliminasi koefisien di bawah pivot 52. Jika I bukan pivot terakhir maka
53.
Nolkan semua koefisien di bawah pivot
54. Akhir jika 55. 56. // Apakah SPL tidak konsisten
28
57. Jika LP > LV maka 58.
SPLInfo.rA:= JV
//(jumlah variabel)
59.
SPLInfo.rAB:= JP
//(jumlah persamaan)
60.
if SPLInfo.rA < SPLInfo.rAB then begin
61.
Ret:= -1
62.
Keluar fungsi
63.
// SPL tidak konsisten
akhir jika
64. akhir jika 65. 66. // Isi variabel X[j] 67. Hitung nilai elemen array X dari matrik A yang sudah dieliminasi. 68. 69. Ret:= 0; 70. Akhir fungsi
// SPL konsisten dan punya jawaban tetap
BAB IV IMPLEMENTASI INTERPRETER SAMLIN DAN PENGUJIAN Sistem persamaan linier ini dibuat untuk mempermudah dalam hal perhitungan linier baik itu berupa sebuah matrik atau sebuah persamaan dengan penyelesaian menggunakan teknik eliminasi Gauss.
IV.1
Tampilan Layar
Berikut ini akan dijelaskan tentang tampilan layar yang ada pada Aplikasi SAMLIN ini beserta potongan programnya.
IV.1.1 Tampilan Awal dan Tampilan Utama Program
Untuk menjalankan program, maka langkah pertama yang harus dilakukan adalah membuka file SAMLIN.dpr dan program akan terbuka melalui aplikasi delphi seperti gambar 4.1.
29
30
Gambar 4.1 : Tampilan Muka Aplikasi SAMLIN
Kemudian tekan F9 untuk menjalankan aplikasi ini.
1. unit Muka; 2. 3. interface 4. 5. uses 6. Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs, 7. StdCtrls, ExtCtrls, Buttons, DkGlobal, Parser; 8. 9. type 10. TfrmMuka = class(TForm)
31
11. Splitter1: TSplitter; 12. pnlButton: TPanel; 13. btnEksekusi: TButton; 14. btnKeluar: TButton; 15. pnlSoal: TPanel; 16. Label1: TLabel; 17. pnlSolusi: TPanel; 18. Label2: TLabel; 19. mmoSoal: TMemo; 20. mmoSolusi: TMemo; 21. Button1: TButton; 22. procedure btnEksekusiClick(Sender: TObject); 23. procedure btnKeluarClick(Sender: TObject); 25. procedure mmoSoalKeyPress(Sender: TObject; var Key: Char); 26. procedure Button1Click(Sender: TObject); 27. end; 28. 29. var 30. frmMuka: TfrmMuka; 31. 32. implementation 33. 34. {$R *.DFM} 35. procedure TfrmMuka.btnEksekusiClick(Sender: TObject); 36. var B: PChar; 37. begin 38. Screen.Cursor:= crHourGlass; 39. mmoSolusi.Clear; 40. B:= mmoSoal.Lines.GetText;
32
41. mmoSolusi.Lines.Text:= Parsing(B); 42. StrDispose(B); 43. Screen.Cursor:= crDefault; 44. end; 45. procedure TfrmMuka.btnKeluarClick(Sender: TObject); 46. begin 47. Close; 48. end; 49. 50. procedure TfrmMuka.mmoSoalKeyPress(Sender: TObject; var Key: Char); 51. begin 52. if Key = '.' then Key:= coDes; 53. end; 54. 55. procedure TfrmMuka.Button1Click(Sender: TObject); 56. begin 57. mmosoal.Lines.Clear; 58. mmosoal.Lines.Add('SAMLIN'); 59. mmosoal.Lines.Add('{'); 60. mmosoal.Lines.Add(''); 61. mmosoal.Lines.Add(''); 62. mmosoal.Lines.Add('}'); 63. end; 64. 65. end.
Atau dapat pula dijalankan file SAMLIN.exe, karena setiap kali kita exsekusi/run file SAMLIN.dpr file tersebut secara langsung akan membuat
executable file jadi bisa langsung dijalankan.
33
IV.1.2 Tampilan Input dan Output.
Pada tampilan input dan output ini terdapat tiga tombol yang akan di tampilkan, yaitu tombol eksekusi, tombol clear input dan tombol keluar adapun fungsi masing-masing tombol itu adalah sebagai berikut : 1) Tombol Eksekusi
Tombol ini berfungsi sebagai pengeksekusi / tombol penghasil output, dan
output itu sendiri didapat dari hasil parsing dari input, dan dapat dilihat seperti Gambar 4.2
Gambar 4.2 : Tampilan tombol Eksekusi
34
Kode Eksekusi sebagai berikut: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
procedure TfrmMuka.btnEksekusiClick(Sender: TObject); var B: PChar; begin Screen.Cursor:= crHourGlass; mmoSolusi.Clear; B:= mmoSoal.Lines.GetText; mmoSolusi.Lines.Text:= Parsing(B); StrDispose(B); {panggil procedure StrDispose} Screen.Cursor:= crDefault; end; 2) Tombol Clear Input
Tombol ini berfungsi untuk meng-Clearkan atau mengosongkan input yang ada di dalam kotak input, lihat gambar 4.3 dan gambar 4.4.
Gambar 4.3 : Gambar sebelum tombol clear input di tekan.
Potongan source Program 1. object mmoSoal: TMemo 2. Left = 1 {Atur posisi tampilan} 3. Top = 19 4. Width = 421 5. Height = 101 6. Align = alClient
35
7. Lines.Strings = ( 8. 'SAMLIN' 9.
'{'
10.
' 2*x + y + z = 7; '
11.
' 4*x + 4*y + 3*z = 21; '
12.
' 6*x + 7*y + 4*z = 32; '
13.
'}')
14. ScrollBars = ssVertical 15. TabOrder = 0 16. OnKeyPress = mmoSoalKeyPress 17. end
Gambar 4.4 : Sesudah tombol clear ditekan
Potongan Program Untuk tombol Clear Input 1. procedure TfrmMuka.Button1Click(Sender: TObject); 2. begin 3. mmosoal.Lines.Clear; 4. mmosoal.Lines.Add('SAMLIN'); 5. mmosoal.Lines.Add('{');
36
6. mmosoal.Lines.Add(''); 7. mmosoal.Lines.Add(''); 8. mmosoal.Lines.Add('}'); 9. end;
3) Tombol Keluar
Tombol ini sesuai namanya berfungsi untuk keluar (quit) dari dalam aplikasi SAMLIN.
Gambar 4.5 : Tampilan tombol Keluar
Potongan program untuk tombol keluar.
1. procedure TfrmMuka.btnKeluarClick(Sender: TObject); 2. begin 3. Close; 4. end;
37
IV.2.2 Spesifikasi Hardware dan Software untuk Uji Kasus
Dalam proses pembuatan Aplikasi ini dibutuhkan beberapa hal penting, diantaranya adalah spesifikasi hardware dan software yang menunjang pembuatan aplikasi Samlin ini adalah : 1) Spesifikasi Perangkat Keras dan Perangkat Lunak Untuk Pembuatan Aplikasi Samlin dan penulisan skripsi ini. Spesifikasi perangkat keras dan perangkat lunak yang digunakan dalam pembuatan aplikasi SAMLIN dan penulisan skripsi adalah sebagai berikut: Perangkat Keras
PC dengan processor Intel P4-2.8Ghz VGA card NVIDIA GeForce FX 5200 DDR SDRAM Vgen 1Gb Harddisk Seagate 120 GB Monitor LG – 17” Keyboard Acer Standart Mouse Relion PS2 Scroll Perangkat Lunak
Sistem Operasi Windows XP Professional Sp.2 Borland Delphi 7
2) Spesifikasi Perangkat Keras Dan Perangkat Lunak Menjalankan Aplikasi SAMLIN Berikut ini adalah kebutuhan minimal dari perangkat keras dan perangkat lunak untuk menjalankan Aplikasi SAMLIN ini : Perangkat Keras
PC dengan processor Pentium II atau setara RAM 32 MB atau lebih Hardisk / falshdisk
38
Keyboard dan mouse Perangkat Lunak
Sistem Operasi Microsoft Windows (semua Microsoft Windows OS ).
IV.2
Pengujian Aplikasi SAMLIN
Setelah dibahas tentang tampilan layar dan cara penggunaan dari aplikasi SAMLIN tersebut, maka untuk mengimplementasikan-nya dapat dicoba kedalam beberapa contoh kasus yang ada di bawah ini: 1)
Penyelesaian dengan jawaban unik/tunggal Nonhomogen
2)
Penyelesaian dengan jawaban Nonhomogen Banyak/tak terhingga.
3)
Penyelesaian dengan jawaban Nonhomogen tiada penyelesaian/tidak ada jawaban Syntax error
IV.3
Skenario Pengujian
Pengujian akan dilakukan menggunakan beberapa buah kasus dengan menggunakn metode manual dan dengan program SAMLIN.
IV.4
Penjelasan Skenario Pengujian.
IV.4.1 Penyelesaian dengan jawaban unik/tunggal Nonhomogen
Sistem persamaan linier nonhomogen ini hanya akan ditinjau sistem persamaan yang konsisten dengan banyaknya variabel sama dengan besar rank dari matriks koefisien dan untuk mencoba jalannya aplikasi SAMLIN inilah beberapa contoh kasus : contoh kasus-1 :
Sebuah toko komputer menjual tiga jenis barang, yaitu monitor, printer, dan scanner. Jumlah penerimaan pada penjualan 10 unit monitor dan 8 unit printer sebesar Rp 8.200.000. Jumlah penerimaan pada penjualan 5 unit monitor dan 3 unit scanner sebesar Rp 4.300.000. Sedangkan jumlah penerimaan pada penjualan 2 unit printer
39
dan 2 unit scanner sebesar Rp 2.000.000. Dari data-data tersebut ingin diketahui harga per unit masing-masing untuk monitor, printer, dan scanner. Persoalan ini dapat dirumuskan dengan sistem persamaan linier, berikut ini : 10 Monitor + 8 Printer = 8200000 5 Monitor + 3 Scanner = 4300000 2 Printer + 2 Scanner = 2000000
Untuk menyelesaikan sistem persamaan linier tersebut dengan interpreter SAMLIN, maka sistem persamaan linier tersebut harus ditulis sebagai berikut : SAMLIN { 10*Monitor + 8*Printer = 8200000; 5*Monitor + 3*Scanner = 4300000; 2*Printer + 2*Scanner = 2000000; } SAMLIN melakukan proses analisis leksikal dan sistaksis. Setelah melewati proses analisis leksikal dan sintaksis tersebut, maka terbentuk daftar berkait (linked
list) seperti Gambar 4.6 Tipe Variabel (Tvari)
Adik
Tipe Konstanta (Tkons) Nilai
Tipe Koefisien (Tkoef)
Gambar 4.6 : Daftar proses Linked list
40
Selanjutnya daftar berkait di atas dikonversi ke dalam bentuk matriks dan vektor kolom agar lebih mudah dianalisis dengan metode eliminasi Gauss. Matriks dan vektor kolom tersebut dalam Delphi dikenal sebagai variabel array. Variabel N menampung vektor kolom nama variabel, variabel A menampung matriks koefisien, variabel X menampung hasil perhitungan, dan variabel B menampung konstanta ruas kanan persamaan. Adapun isi masing-masing variabel tersebut untuk persoalan di atas adalah sebagai berikut :
N=
Monitor Printer Scanner
A=
10
8
0
5
0
3
x2
4300000
0
2
2
x3
2000000
X=
x1
B=
8200000
Tabel 4.1 : Tabel Proses Linked List Contoh Kasus-1
Setelah dianalisis dengan menggunakan metode eliminasi Gauss seperti yang telah diuraikan pada bab landasan teori, maka isi variabel-variabel array tersebut menjadi seperti berikut ini :
N=
Monitor Printer Scanner
A=
10
8
0
X = 500000
0
-4
3
400000
200000
0
0
3,5
600000
2100000
Tabel 4.2 : Tabel Array Contoh Kasus-1
B=
8200000
41
Penjelasan struktur data pada linket list adalah sebagai berikut: Pada baris kolom N disebut Tipe Variabel (TVari) yang memiliki adik dan anak, kearah sejajar disebut adik dan kearah kolom A disebut anak. Pada baris Kolom A disebut Tipe Koefisien (TKoef) yang memiliki nilai baris dan adik. Pada baris kolom B disebut Tipe konstanta (TKons) yang memiliki nilai dan adik, kolom sebelah kiri adalah nilai dan kolom sebelah kanan adalah adik. Penjelasan struktur data juga terdapat pada file program DkGlobal.pss seperti pada potongan program berikut:
type Riil = extended; TNamaVar = array[0..NameLen] of char; PNamaVarArray = ^TNamaVarArray; TNamaVarArray = array[0..MaxVar-1] of TNamaVar; PRiilArray = ^TRiilArray; TRiilArray = array[0..MaxVar*MaxVar-1] of Riil; TSPLInfo = record m, n, rA, rAB: integer; Homogen: boolean end; PKons = ^TKons; TKons = record Nilai: Riil; Adik: PKons; end; PKoef = ^TKoef; TKoef = record Nilai: Riil; Baris: integer;
42
Adik: PKoef; end; PVari = ^TVari; TVari = record Nama: TNamaVar; Adik: PVari; Anak: PKoef; end;
Seterusnya hasil-hasil tersebut direpresentasikan dalam bentuk string yang diperlakukan sebagai keluaran interpreter SAMLIN seperti berikut : Persamaan bersifat nonhomogen. Karena r(A) = r(A,B) = 3 dan r = n = 3 jadi, jawaban tuggal. Jawabannya adalah sebagai berikut : Monitor = 500000 Printer = 400000 Scanner = 600000 Keterangan: r(A): rank baris matriks koefisien r(A,B): rang baris augmented matrix r = r(A,B) n = jumlah variabel Dari keluaran interpreter SAMLIN tersebut dapat diketahui bahwa harga untuk satu unit monitor adalah Rp 500.000, harga satu unit printer adalah Rp.400.000, dan harga satu unit scanner adalah Rp 600.000. Jika kita lihat dari Layout aplikasi SAMLIN maka akan terlihat seperti Gambar 4.9
43
Gambar 4.7 : Layout hasil eksekusi Aplikasi SAMLIN
Contoh kasus-2 :
Diketahui sebuah balok yang masanya 4 kg didorong dengan gaya 50Newton. Didepan balok ini terdapat balok lain yang massanya 2 Kg. Setelah kedua balok saling menempel, hitunglah besar gaya kontak antara kedua balok dan percepatannya. Lantai dianggap licin. Seperti gambar 4.8 melukiskan keadaan kedua balok setelah saling menempel dengan gaya 50 Newton beraksi pada balok yang massanya 4 Kg. Dari gambar 4.9 melukiskan keadaan masing masing balok secara terpisah, dimana F adalah gaya dari luar dan T adalah gaya kontak. Dengan menggunakan hukum Newton II pada masing-masing balok maka diperoleh dua persamaan yaitu :
44
F – T = m1 a T = m2 a Kedua persamaan tersebut dapat ditulis dalam bentuk matriks menjadi : ⎛ m1 ⎜⎜ ⎝ m2
1⎞ ⎟ −1⎟⎠
⎛a⎞ ⎛F⎞ ⎜⎜ ⎟⎟ = ⎜⎜ ⎟⎟ ⎝T ⎠ ⎝0⎠
4 Kg 2 Kg 50 N
Gambar 4.8 : Gambar balok-balok saling menempel
F
T
T
Gambar 4.9 : Gambar Masing-masing balok terpisah
45
Dengan mensubstitusikan m1 = 4Kg dan m 2 = 2Kg maka diperoleh : ⎛ 4 1 ⎞⎛ a ⎞ ⎛ 50 ⎞ ⎜⎜ ⎟⎟⎜⎜ ⎟⎟ = ⎜⎜ ⎟⎟ ⎝ 2 − 1 ⎠⎝ T ⎠ ⎝ 0 ⎠ Untuk menyelesaikan sistem persamaan linier tersebut dengan interpreter SAMLIN, maka sistem persamaan linier tersebut harus ditulis sebagai berikut : SAMLIN { 4*a + T = 50; 2*a - T = 0; } Selanjutnya dilakukan proses analisis leksikal dan sintaksis. Setelah melewati proses analisis leksikal dan sintaksis tersebut, maka terbentuklah daftar berkait (linked list) pada gambar 4.10 berikut ini :
Gambar 4.10 : Daftar proses Linked List
Selanjutnya daftar berkait di atas dikonversi ke dalam bentuk matriks dan vektor kolom agar lebih mudah dianalisis dengan metode eliminasi Gauss. Matriks dan vektor kolom tersebut dalam Delphi dikenal sebagai variabel array. Variabel N menampung vektor kolom nama variabel, variabel A menampung matriks koefisien, variabel X menampung hasil perhitungan, dan variabel B menampung konstanta ruas kanan persamaan. Adapun isi masing-masing variabel tersebut untuk persoalan di atas adalah seperti tabel 4.3 berikut ini :
46
N=
A
T
A=
4
1
2
-1
X=
x1
B=
50 0
x2
Tabel 4.3 : Tabel Proses Linked List Contoh Kasus-2
Setelah dianalisis dengan menggunakan metode eliminasi Gauss seperti yang telah diuraikan pada bab landasan teori, maka isi variabel-variabel array tersebut menjadi seperti tabel 4.4 berikut ini :
N=
A
T
A=
4
1
0
3
X=
8,3
B=
16,7
50 50
Tabel 4.4 : Tabel Proses Linked List Contoh Kasus-2
Seterusnya hasil-hasil tersebut direpresentasikan dalam bentuk string yang diperlakukan sebagai keluaran interpreter SAMLIN seperti berikut: Persamaan bersifat nonhomogen. Karena r(A) = r(A,B) = 2 dan r = n = 2 jadi, jawaban tuggal. Jawabannya adalah sebagai berikut. a = 8.33333333333333 T = 16.6666666666667
47
Keterangan: r(A): rank baris matriks koefisien r(A,B): rang baris augmented matrix r = r(A,B) n = jumlah variabel
Dari keluaran interpreter SAMLIN tersebut dapat diketahui bahwa nilai percepatan (a) balok-balok adalah 8,3 m/s2 dan besar gaya kontak (T) adalah 16,7 N. Atau dapat dilihat dari gambar 4.11
Gambar 4.11 : Penyelesaian dengan Aplikasi SAMLIN Contoh kasus-3.
Untuk menyelesaikan persoalan yang muncul dalam kehidupan seharihari,sering kali persoalan itu dapat dapat dirumuskan dengan memakai model matematika yang berbentuk sistem persamaan, seperti contoh ini :
48
Tyas Seorang staff purchasing membuat PO (Purchasing Order) pesanan pembelian barang untuk masing-masing Suplier, di Reycom dia membeli 2 buah Hardisk, 3 Memory, 10 box CD-R dan 5 Box DVD-R dan membayar sebesar Rp. 4.300.000. di PCL komputer dia membeli 2 buah Hardisk, 4 Memory, 5 box CD-R dan 5 Box DVD-R dan membayar sebesar Rp. 3.750.000. Di Penguin Computer dia membeli 5 buah Hardisk, 1 Memory, 2 box CD-R dan 5 Box DVD-R dan membayar sebesar Rp. 4.500.000. Di Exits dia membeli 4 buah Hardisk, 2 Memory, 3 box CD-R dan 2 Box DVD-R dan membayar sebesar Rp. 3.600.000., Kemudian datang Reza dari Internal Audit mau menanyakan berapakah harga dari masing-masing barang dalam harga satuan, yaitu Hardisk,Memory,CD-R dan DVD-R. Untuk mengetahui harga sebuah Hardisk, Memory dan 1 box CD-R dan DVD-R maka persoalan ini terlebih dahulu diterjemahkan ke dalam bahasa matematika. Pekerjaan demikian disebut membuat model matematika, misalkan harga sebuah Hardisk ‘a’ rupiah,harga sebuah Memory ‘b’ rupiah, dan 1 box CD-R dan DVD-R ‘c’ dan ‘d’ Rupiah maka persoalan diatas dapat disajikan dalam bentuk tabel seperti dibawah tabel 4.5 dibawah ini :
Reycom PCL Penguin Exits Harga Perbuah
Hardisk
Memory
CD-R
2 2 5 4 A
3 4 1 2 b
10 5 2 3 c
Tabel 4.5 : Tabel Contoh Kasus-3
DVD-R Jumlah Pembayaran 5 4300000 5 3750000 5 4500000 2 3600000 d
49
Dari tabel tersebut akhirnya persoalan itu dapat dirumuskan dalam persamaan berikut : 2a + 3b + 10c + 5d = 4300000 2a + 4b + 5c + 5d = 3750000 5a + b + 2c + 5d = 4500000 4a + 2b + 3c + 2d = 3600000 Untuk menyelesaikan sistem persamaan linier tersebut dengan interpreter SAMLIN, maka sistem persamaan linier tersebut harus ditulis sebagai berikut. SAMLIN { 2*a + 3*b + 10*c + 5*d = 4300000; 2*a + 4*b + 5*c + 5*d = 3750000; 5*a + b + 2*c + 5*d = 4500000; 4*a + 2*b + 3*c + 2*d = 3600000; } Persamaan bersifat nonhomogen. Karena r(A) = r(A,B) = 4 dan r = n = 4 jadi, jawaban tuggal. Jawabannya adalah sebagai berikut. a = 586486.486486486 b = 188738.738738739 c = 147747.747747748 d = 216666.666666667
Keterangan: r(A): rank baris matriks koefisien r(A,B): rang baris augmented matrix r = r(A,B) n = jumlah variabel
50
Dari keluaran interpreter SAMLIN tersebut dapat diketahui bahwa Harga sebuah hardisk (a) adalah Rp. 586486 atau Rp.600.000,- , Memory (b) Rp. 188738 atau Rp. 200.000,- , 1 Box CD-R (c) adalah Rp. 147747 atau 150.000,- dan 1 Box DVD-R (d) Rp. 216666 atau Rp. 200.000,- . Atau dapat dilihat dari gambar 4.12
Gambar 4.12 : Penyelesaian dengan Aplikasi SAMLIN
IV.4.2 Penyelesaian dengan Jawaban Nonhomogen Banyak/Tak Terhingga.
Sistem Persamaan Linier yang homogen ialah Sistem Persamaan Linier yang boleh ditulis sebagai Ax = 0. Sistem Persamaan Linier yang homogen selalu konsisten karena x = O menjadi satu penyelesaian, yang dipanggil penyelesaian tak
terhingga/banyak . Penyelesaian Sistem persamaan Linier Homogen dapat disimpulkan sebagai berikut :
51
Nonhomogen/Unik (x=0) Tak terhingga(banyak) dan unik (x = O) NonHomogen (banyak)
Contoh Kasus-1.
Disebuah perusahaan terjadi sebuah pembelian toner printer dan Pita printer dari 2 suplier yaitu SOCA dan Reycom, di suplier pertama Soca dibeli toner printer sebanyak 4 buah dan pita printer 4 buah dan biaya yang dikeluarkan sebesar Rp. 4.00.000,- dan di suplier ke dua dibeli barang yang sama dengan permintaan 8 buah toner dan 8 buah pita dengan biaya yang dibayar Rp. 800.000,- jika dilihat dengan harga yang berbeda dapatkah di hitung berapakah harga satuan dari masing-masing barang tersebut ? untuk itu dibuatlah sebuah tabel seperti di bawah ini : Toner SOCA 4 REYCOM 8 Harga x perbuah
Pita 4 8 Y
Jumlah Yang dibayar 400000 800000
Tabel 4.6 : Tabel Contoh Kasus-1 NonHomogen dengan jawaban banyak
Dari tabel diatas dapat di rumuskan dalam persamaan berikut :
4x + 4y = 400000 8x + 8y = 800000 Untuk menyelesaikan sistem persamaan linier tersebut dengan interpreter SAMLIN, maka sistem persamaan linier tersebut harus ditulis sebagai berikut : SAMLIN { 4*x + 4*y = 400000; 8*x + 8*y = 800000; }
52
Maka setelah dieksekusi akan mendapatkan jawaban seperti ini : Persamaan bersifat nonhomogen. Karena r(A) = r(A,B) = 1 dan r = 1, n = 2, r < n jadi, ada banyak jawaban. Jawaban umumnya adalah sebagai berikut. x = 100000 - %1 y = %1 Jawaban tergantung parameter %1.
Keterangan: r(A): rank baris matriks koefisien r(A,B): rang baris augmented matrix r = r(A,B) n = jumlah variabel Maka diketahui bahwa ada kesalahan-kesalahan dari transaksi diatas, hal tersebut bisa di telusuri dengan manual cross cek, apakah ada diskon khusus sehingga terjadi perbedaan dari jumlah harga satuan. Jika kita telusuri menggunakan kaedah dari persamaan linier maka didapat diagram matrik seperti dibawah ini : ⎛ 4 4⎞ ⎟⎟, | A |= 0 , karena jika kita menggunakan eliminasi Gauss tidak A = ⎜⎜ ⎝8 8⎠ diperbolehkan
A = 0 atau r = 1, n = 2, r < n jadi, ada banyak jawaban. Jika kita menjalankan di Aplikasi SAMLIN akan terlihat seperti gambar 4.13
53
Gambar 4.13 : Penyelesaian dengan Aplikasi SAMLIN
Atau Seperti potongan Source untuk menampilkan string penyelesaian dengan jawaban banyak/tak terhingga (Gauss.pas) berikut ini:
1. begin 2. Str:= Str + 3. 'Karena r(A) = r(A,B) = ' + IntToStr(SPLInfo.rA) + 4. ' dan r = ' + IntToStr(SPLInfo.rA) + 5. ', n = ' + IntToStr(SPLInfo.n) + 6. ', r < n jadi, ada banyak jawaban.'#13#10 + 8. 'Jawaban umumnya adalah sebagai berikut.'; 9. Str:= Str + JawabUmum(A, B, V, SPLInfo); 10. end;
54
IV.4.3Penyelesaian dengan Jawaban Nonhomogen Tiada Penyelesaian/Tidak Ada Jawaban
Sebuah persamaan Linier dikatakan tiada penyelesaian / tidak ada jawaban jika memenuhi persyaratan seperti ini : Jika r(A) ≠ r(A,B) maka tidak ada jawaban. Contoh kasus-1
Diketahui 2 buah persamaan dengan dua variabel sebagai berikut :
x+y=1 x+y=2 Selesaikanlah system persamaan linier tersebut dengan menggunakan Eliminasi Gauss, maka akan terbentuk persamaan dalam bentuk matrik seperti dibawah ini : ⎛ 1 1⎞ ⎟⎟, | A |= 0 A = ⎜⎜ ⎝ 1 1⎠ Penyelesaian tidak Unik, dan bila kita eliminasikan akan menjadi seperti dibawah ini: ⎛1 1 | 1 ⎞ − B1 + B2 ⎛ 1 1 | 1 ⎞ ⎜⎜ ⎟⎟ ⎯⎯ ⎯→⎜⎜ ⎟⎟ ⎝1 1 | 2 ⎠ ⎝ 0 0 | 1⎠ x+y=1 0 = 1 (tidak benar) r (A) < r (A,B), karena r(A) = 1 dan r(A,B)=2 Jadi, eliminasi persamaan diatas tiada penyelesaian/tidak ada jawaban. Setelah kita coba persamaan diatas dengan metode manual, sekarang persamaan diatas dimasukan kedalam aplikasi SAMLIN SAMLIN {
x + y = 1; x + y = 2; }
55
Maka setelah di eksekusi akan muncul jawaban seperti ini : Persamaan bersifat nonhomogen. Karena r(A) = 1, r(A,B) = 2, r(A) < r(A,B) jadi, tidak ada jawaban. Keterangan: r(A): rank baris matriks koefisien r(A,B): rank baris augmented matrix r = r(A,B) n = jumlah variabel
atau seperti gambar 4.14 dibawah ini :
Gambar 4.14 : Penyelesaian dengan Aplikasi SAMLIN
Atau potongan dari source untuk menampilkan string penyelesaian dengan jawaban tidak ada jawaban (Gauss.pas) berikut :
56
1. else begin 2. Str:= Str + 3. 'Karena r(A) = ' + IntToStr(SPLInfo.rA) + 4. ', r(A,B) = ' + IntToStr(SPLInfo.rAB) + 5. ', r(A) < r(A,B) jadi, tidak ada jawaban.'; 6. end;
IV.4.4 Syntax Error
Aplikasi SAMLIN akan memunculkan pesan error jika menemukan beberapa kesalahan didalam format pemasukan data (input). Contoh kasus-1.
Lihat kesalahan pada Gambar 4.15
Gambar 4.15 : Penyelesaian dengan Aplikasi SAMLIN
57
Keterangan Kesalahan : Dari gambar 4.15 diatas di ketahui persamaan yang di input seharusnya :
1. SAMLIN 2. { 3. 2*x + y + z = 7; 4. 4*x + 4*y + 3*z = 21; 5. 6*x + 7*y + 4*z = 32; 6.
}
Tetapi ditulis seperti ini :
1. SAMLIN 2. { 3. 2x + y + z = 7; 4. 4*x + 4*y + 3*z = 21; 5. 6*x + 7*y + 4*z = 32; 6.
}
Lalu muncul pesan kesalahan di kotak Output, yang bertuliskan “3,5: "*" tidak ditemukan tetapi "VARIABEL" ditemukan “ maksud dari kesalahan itu
adalah : 3,5 = terjadi kesalahan di baris ke tiga kolom ke lima. * = tidak ada tanda * (asterik) Jadi pesan lengkapnya adalah : “baris ke 3 kolom 5 tidak ada tanda * tetapi ditemukan variabel “ karena jika ditemukan angka dan variabel maka diantaranya harus diberikan tanda * .
58
Contoh kasus-2
Lihat contoh kesalahan dari Gambar 4.16
Gambar 4.16 : Penyelesaian dengan Aplikasi SAMLIN Keterangan Kesalahan : Dari gambar 4.9b diatas di ketahui persamaan yang di input seharusnya :
1. SAMLIN 2. { 3. 2*x + y + z = 7; 4. 4*x + 4*y + 3*z = 21; 5. 6*x + 7*y + 4*z = 32; 6.
}
59
Tetapi ditulis seperti ini :
1. SAMLIN 2. { 3. 2x + y + z = 7; 4. 4*x + 4*y + 3*z = 21 5. 6*x + 7*y + 4*z = 32; 6.
}
Lalu muncul pesan kesalahan di kotak Output, yang bertuliskan “5,4: ";" tidak ditemukan tetapi "SKALAR" ditemukan “ maksud dari kesalahan itu adalah :
5,4 = terjadi kesalahan di baris kelima kolom keempat. ;
= tidak ada tanda ; (titik koma) Jadi pesan lengkapnya adalah : “baris ke 5 kolom 4 tidak ada tanda ; tetapi
ditemukan variabel “ karena jika tidak diketemukan tanda ; (titik koma) pada akhir persamaan maka dianggap error itu berada di baris berikutnya.
60
Contoh kasus-3
Lihat contoh kesalahan dari Gambar 4.17
Gambar 4.17 : Penyelesaian dengan Aplikasi SAMLIN
Keterangan Kesalahan : Dari gambar 4.17 diatas di ketahui persamaan yang di input seharusnya :
1. SAMLIN 2. { 3. 2*x + y + z = 7; 4. 4*x + 4*y + 3*z = 21; 5. 6*x + 7*y + 4*z = 32; 6.
}
61
Tetapi ditulis seperti ini :
1. SAMLIN 2. { 3. 2x + y + z = 7; 4. 4*x + 4*y + 3*z = 21; 5.
6*x + 7*y + 4*z =;
6.
}
Lalu muncul pesan kesalahan di kotak Output, yang bertuliskan “5,21: Konstanta tidak ditemukan “ maksud dari kesalahan itu adalah :
5,21 = terjadi kesalahan di baris kelima kolom ke dua puluh satu. Konstanta = bilangan setelah tanda = (sama dengan) Jadi pesan lengkapnya adalah : “baris ke 5 kolom 21 tidak ditemukan adanya konstanta“ karena jika tidak di ketemukan salah satu konstanta proses eliminasi tidak dapat dilanjutkan.
IV.5
Analisis Hasil Pengujian
Sistem persamaan linier ini dibuat untuk mempermudah dalam hal perhitungan linier baik itu berupa sebuah matrik atau sebuah persamaan dengan penyelesaian menggunakan teknik eliminasi Gauss. Interpreter SAMLIN terdiri dari dua bagian utama, bagian pertama bertugas menguraikan sistem persamaan linier yang harus diselesaikan menjadi array seperti manusia mengubah sistem persamaan linier ke dalam perkalian matriks, sedangkan bagian kedua bertugas menganalisis array yang dihasilkan oleh bagian pertama agar dapat ditemukan solusi sistem persamaan linier tersebut.
62
Input (masukan) yang berupa string yang mengikuti aturan tata bahasa SAMLIN Script diuraikan oleh penganalisis leksikal sehingga dapat dikenali tokentoken (simbol-simbol terminal) yang terdapat dalam string masukan tersebut satu per satu. Bila ada token yang tidak dikenali, maka program ini akan menghasilkan output berupa pesan kesalahan. Setiap token yang dapat dikenali, penganalisis sintaks melakukan pemeriksaan untuk memastikan bahwa tidak ada kesalahan sintaks pada string masukan. Bila terdapat kesalahan sintaks, maka program ini akan menghasilkan keluaran berupa pesan kesalahan. Bila tidak terjadi kesalahan sintaks maka program mendaftarkan koefisien-koefisien, variabel-variabel, dan konstanta-konstanta pada setiap persamaan dalam sistem persamaan linier yang sedang dianalisis ke dalam daftar berkait (linked list). Agar lebih mudah dianalisis dan diselesaikan dengan metode eliminasi Gauss, daftar berkait tersebut dikonversi ke dalam bentuk matriks (array). Selanjutnya, dengan menggunakan metode eliminasi Gauss yang dimodifikasi, matriks sistem persamaan linier tersebut dianalisis. Pada tahap inilah ditentukan homogenitas, konsistensi dan sifat jawaban (umum atau tunggal) yang dimiliki oleh sistem persamaan linier yang dianalisis. Kemudian hasil analisis tersebut dikonversi ke dalam bentuk string sebagai keluaran. Syntax error sering terjadi karena kesalahan penulisan bukan karena program tidak bisa menganalisa, lihat contoh kasus di bawah ini:
63
Gambar 4.18 Kesalahan Pada penulisan Keterangan Kesalahan : Dari gambar 4.21 diatas di ketahui persamaan yang di input seharusnya : 1. SAMLIN 2. { 3. 2*x + y + z = 7; 4.
4*x + 4*y + 3*z = 21;
5.
6*x + 7*y + 4*z = 32;
6.
}
64
Tetapi ditulis seperti ini : 1. SAMLIN 2. { 3. 2x + y + z = 7; 4.
4*x + 4*y + 3*z = 21;
5.
6*x + 7*y + 4*z = 32;
6.
}
Lalu muncul pesan kesalahan di kotak Output, yang bertuliskan “3,5: "*" tidak ditemukan tetapi "VARIABEL" ditemukan “ maksud dari kesalahan itu
adalah : 3,5 = terjadi kesalahan di baris ke tiga kolom ke lima. * = tidak ada tanda * (asterik) Jadi pesan lengkapnya adalah : “baris ke 3 kolom 5 tidak ada tanda * tetapi ditemukan variabel “ karena jika ditemukan angka dan variabel maka diantaranya harus diberikan tanda * .
65
BAB V PENUTUP V.1
Kesimpulan
Pada dasarnya komputer tidak dapat mengenali sistem persamaan linier, apa lagi menyelesaikannya. Tetapi, dengan menerapkan teknik kompilasi dan beberapa metode numerik melalui sebuah program komputer, dalam hal ini adalah interpreter SAMLIN, komputer dapat megenali, menganalisis, dan menyelesaikan sistem persamaan linier sederhana. Maka dapat ditarik kesimpulan sebagai berikut : 1) Interpreter SAMLIN terdiri dari dua bagian utama. Bagian pertama bertugas menguraikan sistem persamaan linier yang harus diselesaikan menjadi array seperti manusia mengubah sistem persamaan linier ke dalam perkalian matriks. Sedangkan bagian kedua bertugas menganalisis array yang dihasilkan oleh bagian pertama agar dapat ditemukan solusi sistem persamaan linier tersebut. 2) Interpreter SAMLIN seringkali tidak dapat menemukan hasil analisis dari input yang dimasukkan, hal ini disebabkan oleh kesalahan pada penulisan bukan oleh program tidak dapat menganalisis dengan baik, seperti kesalahan yang ditemukan pada kotak output (hasil pengujian) yang bertuliskan “3,5: "*" tidak ditemukan tetapi "VARIABEL" ditemukan “ hal itu disebabkan a. terjadi kesalahan di baris ke tiga kolom ke lima, yaitu tidak ada tanda * (asterik). b. Jadi pesan lengkapnya adalah : “baris ke 3 kolom 5 tidak ada tanda * tetapi ditemukan variabel “ karena jika ditemukan angka dan variabel maka diantaranya harus diberikan tanda * .
3) Sesuai dengan tujuan penulisan, bahwa sistem persamaan linier di buat untuk menyelesaikan persamaan linier sederhana dan aplikasi ini dibuat
66
agar perhitungan persamaan linier sederhana bisa diselesaikan dengan komputer. V.2
Saran-Saran
Karena berupa prototipe program, interpreter SAMLIN ini tentu masih memiliki banyak kekuarangan. Ada beberapa saran yang dapat diajukan untuk memperbaiki kekurangan-kekurangan tersebut :
a. Metode penanganan kesalahan pada program ini masih sangat sederhana sehingga kurang membantu pengguna. Penggunaan metode penanganan kesalahan yang lebih baik akan sangat membantu pengguna dalam menemukan dan memperbaiki kesalahan-kesalahan. b. Untuk meningkatkan akurasi solusi dapat digunakan mekanisme koreksi kesalahan, karena pada program ini belum diterapkan mekanisme tersebut. Kesalahan yang sering terjadi disebabkan oleh pembulatan dan bawaan. c. Dengan teknik-teknik dan metode-metode yang sama program ini dapat dikembangkan sedemikian rupa sehingga program ini tidak hanya dapat menyelesaikan sistem persamaan linier, tetapi juga dapat menyelesaikan pemrograman linier, penugasan, transportasi, teori permainan, dan lain sebagainya. d. Untuk mengurangi kesalahan pada penulisan sebaiknya program dikembangkan dengan tidak perlu lagi menggunakan tanda * (asterik) sehingga kesalahan pada penulisan dapat dikurangi.
DAFTAR PUSTAKA
1.
Slamet, Sumantri dan Suhartanto, Heru, Teknik Kompilasi, PT Elex Media Komputindo, Jakarta, 1993.
2.
Sukamdi, Tuntunan Praktis Pemrograman: Merekayasa Interpreter, PT Elex Media Komputindo, Jakarta, 1995.
3.
Wirth, Niklaus, Algoritma + Struktur Data = Program, ANDI, Yogyakarta, 1987.
4.
Capra, Steven C. Dan Canale, Raymond P., Metode Numerik untuk Teknik dengan Penerapan pada Komputer Pribadi, Penerbit UI (UI-Press), Jakarta, 1991.
5.
Soegeng, R., Komputasi Numerik dengan Turbo Pascal, Andi Offset, Yogyakarta, 1993.
6.
D. Suryadi H. S. & S. Harini Machmudi, Aljabar Linier, Ghalia Indonesia, Jakarta, 1985.
7.
Okianto, Dani, Panduan Belajar Borland Delphi 3.0, Elex Media Komputindo, Jakarta, 1998.
8.
Pramono Djoko, Seri Penuntun Praktis: Contoh Penggunaan Rutin-Rutin Borland Delphi, Elex Media Komputindo, Jakarta, 1996.
9.
Pramono Djoko, Belajar Sendiri: Pemrograman Delphi ’95, Elex Media Komputindo, Jakarta, 1996.
41
LAMPIRAN Berikut ini adalah Regular Expression yang digunakan untuk menspesifikasikan token-token yang terdapat dalam SAMLIN Script : 1) huruf → A|B|C|...|Z 2) angka → 0|1|2|...|9 3) koma_desimal → .|, 4) tanda_minus → 5) tanda_plus → + 6) tanda_asterik → * 7) tanda_sama_dengan → = 8) nama_variabel → huruf(angka|huruf)* 9) skalar_tanpa_tanda → angka+(koma_desimal angka+|ε)(E(+|-|ε)angka+|ε) 10) kata_samlin → SAMLIN 11) tanda_titik_koma → ; 12) kurung_kurawal_buka → { 13) kurung_kurawal_tutup → } Berikut ini spesifikasi sintaksis SAMLIN Script dengan menggunakan CFG (context free gramaar) : G = (N, T, P, S) N
=
{<SKRIP>, <SPL>, , <Ekspresi>, , , , , , , }
T
=
{SAMLIN,
{,
},
;,
=
,
+,
-,
*,
nama_variabel,
skalar_tanpa_tanda} S
=
<SKRIP>
P
=
himpunan produksi berikut. <SKRIP> → SAMLIN { <SPL> } <SPL> → ; <SPL> | ε → <Ekspresi> = <Ekspresi> → → nama_variabel
→
nama_variabel
| ε → skalar_tanpa_tanda → skalar_tanpa_tanda * | ε → - | ε → + | Tampilan Muka dari aplikasi Samlin 1. unit Muka; 2. 3. interface 4. 5. uses 6. Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs, 7. StdCtrls, ExtCtrls, Buttons, DkGlobal, Parser; 8. 9. type 10. TfrmMuka = class(TForm) 11. Splitter1: TSplitter; 12. pnlButton: TPanel; 13. btnEksekusi: TButton; 14. btnKeluar: TButton; 15. pnlSoal: TPanel; 16. Label1: TLabel; 17. pnlSolusi: TPanel; 18. Label2: TLabel; 19. mmoSoal: TMemo; 20. mmoSolusi: TMemo; 21. Button1: TButton; 22. procedure btnEksekusiClick(Sender: TObject); 23. procedure btnKeluarClick(Sender: TObject); 25. procedure mmoSoalKeyPress(Sender: TObject; var Key: Char); 26. procedure Button1Click(Sender: TObject); 27. end;
28. 29. var 30. frmMuka: TfrmMuka; 31. 32. implementation 33. 34. {$R *.DFM} 35. procedure TfrmMuka.btnEksekusiClick(Sender: TObject); 36. var B: PChar; 37. begin 38. Screen.Cursor:= crHourGlass; 39. mmoSolusi.Clear; 40. B:= mmoSoal.Lines.GetText; 41. mmoSolusi.Lines.Text:= Parsing(B); 42. StrDispose(B); 43. Screen.Cursor:= crDefault; 44. end; 45. procedure TfrmMuka.btnKeluarClick(Sender: TObject); 46. begin 47. Close; 48. end; 49. 50. procedure TfrmMuka.mmoSoalKeyPress(Sender: TObject; var Key: Char); 51. begin 52. if Key = '.' then Key:= coDes; 53. end; 54. 55. procedure TfrmMuka.Button1Click(Sender: TObject); 56. begin 57. mmosoal.Lines.Clear; 58. mmosoal.Lines.Add('SAMLIN'); 59. mmosoal.Lines.Add('{'); 60. mmosoal.Lines.Add(''); 61. mmosoal.Lines.Add('');
62. mmosoal.Lines.Add('}'); 63. end; 64. 65. end.
Kode Eksekusi sebagai berikut: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
procedure TfrmMuka.btnEksekusiClick(Sender: TObject); var B: PChar; begin Screen.Cursor:= crHourGlass; mmoSolusi.Clear; B:= mmoSoal.Lines.GetText; mmoSolusi.Lines.Text:= Parsing(B); StrDispose(B); {panggil procedure StrDispose} Screen.Cursor:= crDefault; end;
Program Untuk tombol Clear Input: 1. procedure TfrmMuka.Button1Click(Sender: TObject); 2. begin 3. mmosoal.Lines.Clear; 4. mmosoal.Lines.Add('SAMLIN'); 5. mmosoal.Lines.Add('{'); 6. mmosoal.Lines.Add(''); 7. mmosoal.Lines.Add(''); 8. mmosoal.Lines.Add('}'); 9. end
program untuk tombol keluar. 1. procedure TfrmMuka.btnKeluarClick(Sender: TObject); 2. begin 3. Close; 4. end;
Source untuk menampilkan string penyelesaian dengan jawaban banyak/tak terhingga (Gauss.pas) berikut ini: 1. begin 2. Str:= Str + 3. 'Karena r(A) = r(A,B) = ' + IntToStr(SPLInfo.rA) + 4. ' dan r = ' + IntToStr(SPLInfo.rA) + 5. ', n = ' + IntToStr(SPLInfo.n) + 6. ', r < n jadi, ada banyak jawaban.'#13#10 + 8. 'Jawaban umumnya adalah sebagai berikut.'; 9. Str:= Str + JawabUmum(A, B, V, SPLInfo); 10. end; source untuk menampilkan string penyelesaian dengan jawaban tidak ada jawaban (Gauss.pas) berikut : 1. else begin 2. Str:= Str + 3. 'Karena r(A) = ' + IntToStr(SPLInfo.rA) + 4. ', r(A,B) = ' + IntToStr(SPLInfo.rAB) + 5. ', r(A) < r(A,B) jadi, tidak ada jawaban.'; 6. end;
Untuk Algoritma dari Flowchart SAMLIN dapat diilustrasikan sebagai berikut : 1. Fungsi EliminasiGaus 2. Input: 3. A : array koefisien 4. X: array variabel 5. B: array konstanta 6. V: array nama variabel 7. SPLInfo: m=jumlah persamaan, n=jumlah variabel, rA=rank A, rAB=rank A.B, 8. Homogen=persamaan homogen atau tidak. 9. Output: 10. Ret: 0 = jawaban tunggal, 1 = jawaban banyak, -1 = tidak ada jawaban. 11. 12. Proses:
13. JP:= SPLInfo.m; 14. JV:= SPLInfo.n; 15. LP:= JP - 1; 16. LV:= JV - 1; 17. 18. // Tentukan homogenitas persamaan 19. Periksa semua nilai di array B. 20.
Jika semuanya 0, SPLInfo.Homogen = true
21.
Selain itu, SPLInfo.Homogen = false
22. 23. // Proses Eliminasi Gaus 24. Untuk I dari 0 sampai LV 25. 26.
// Cari Pivot terbesar Cari Baris dan Kolom untuk Pivot terbesar (tidak peduli + atau -)
27.
dan masukkan dalam variabel Brs dan Klm
28.
SPLInfo.rA:= I;
29.
SPLInfo.rAB:= I;
30.
Jika Pivot terbesar = 0
31.
Untuk J dari I sampai LP
32.
Jika B[J] <> 0 maka SPLInfo.rAB = SPLInfo.rAB + 1
33.
Akhir untuk
34.
Jika SPLInfo.rA < SPLInfo.rAB maka
35. 36. 37.
Ret:= -1
// SPL tidak konsisten
Selain itu Ret:= 1
38.
Akhir jika
39.
Keluar fungsi
// SPL punya banyak jawaban
40. Akhir untuk 41. 42. Jika Klm <> I maka 43.
tukar nilai array A pada kolom Klm dan I
44.
tukar nilai array V pada index Klm dan I
45. akhir jika 46. Jika Brs <> I maka
47.
tukar nilai array A pada baris Brs dan I
48.
tukar nilai array B pada index Brs dan I
49.
akhir jika
50. 51. // Eliminasi koefisien di bawah pivot 52. Jika I bukan pivot terakhir maka
53.
Nolkan semua koefisien di bawah pivot
54. Akhir jika 55. 56. // Apakah SPL tidak konsisten
57. Jika LP > LV maka 58.
SPLInfo.rA:= JV
//(jumlah variabel)
59.
SPLInfo.rAB:= JP
//(jumlah persamaan)
60.
if SPLInfo.rA < SPLInfo.rAB then begin
61.
Ret:= -1
62.
Keluar fungsi
63.
// SPL tidak konsisten
akhir jika
64. akhir jika 65. 66. // Isi variabel X[j] 67. Hitung nilai elemen array X dari matrik A yang sudah dieliminasi. 68. 69. Ret:= 0; 70. Akhir fungsi
// SPL konsisten dan punya jawaban tetap
unit DkGlobal; interface uses SysUtils; const NameLen = 15; MaxVar = 1024; coXTol= 1e-15; coDes: char = '.'; type Riil = extended; TNamaVar = array[0..NameLen] of char; PNamaVarArray = ^TNamaVarArray; TNamaVarArray = array[0..MaxVar-1] of TNamaVar; PRiilArray = ^TRiilArray; TRiilArray = array[0..MaxVar*MaxVar-1] of Riil; TSPLInfo = record m, n, rA, rAB: integer; Homogen: boolean end; PKons = ^TKons; TKons = record Nilai: Riil; Adik: PKons; end; PKoef = ^TKoef; TKoef = record Nilai: Riil; Baris: integer; Adik: PKoef; end; PVari = ^TVari; TVari = record Nama: TNamaVar; Adik: PVari; Anak: PKoef; end; TSimbol = (sbNil, sbSamlin, sbVariabel, sbSkalar, sbTitikKoma, sbBuka, sbTutup, sbMinus, sbPlus, sbAsterik, sbSamaDengan);
implementation begin coDes:= FloatToStr(0.1)[2]; end. unit Gauss; interface uses SysUtils, DkGlobal; function CariJawab( var A: array of Riil; { Matriks koefisien } var X: array of Riil; { Matriks Jawaban } var B: array of Riil; { Matriks Konstanta } var V: array of TNamaVar; { Matriks Nama Var } var SPLInfo: TSPLInfo): string; function JawabUmum( var A: array of Riil; { Matriks koefisien } var B: array of Riil; { Matriks Konstanta } var V: array of TNamaVar; { Matriks Nama Var } var SPLInfo: TSPLInfo): string; implementation procedure Kurangkan(var Oprn1: Riil; Oprn2: Riil); var Tmp: Riil; begin Tmp:= Oprn1 - Oprn2; if Abs(Tmp) < coXTol * Abs(Oprn1) then Oprn1:= 0 else Oprn1:= Tmp; end; function EliminasiGauss( var A: array of Riil; var X: array of Riil; var B: array of Riil; var V: array of TNamaVar; var SPLInfo: TSPLInfo): integer; var LV, LP, JV, JP: integer;
I, J, K, Brs, Klm: integer; T: Riil; TNV: TNamaVar; begin JP:= SPLInfo.m; JV:= SPLInfo.n; LP:= pred(JP); LV:= pred(JV); // Tentukan homogenitas persamaan SPLInfo.Homogen:= true; for I:= 0 to LP do if B[I] <> 0 then begin SPLInfo.Homogen:= false; break; end; // Proses Eliminasi Gauss for I:= 0 to LV do begin // Cari Pivot terbesar Brs:= I; Klm:= I; for J:= I to LV do begin // Kolom for K:= I to LP do // Baris if Abs(A[K*JV+J]) > Abs(A[Brs*JV+Klm]) then begin Brs:= K; Klm:= J; end; if A[Brs*JV+Klm] <> 0 then break; end; // Kalau tidak ada yang bukan nol if A[Brs*JV+Klm] = 0 then begin SPLInfo.rA:= I; SPLInfo.rAB:= I; for J:= I to LP do if B[J] <> 0 then inc(SPLInfo.rAB); if SPLInfo.rA < SPLInfo.rAB then Result:= -1 else Result:= 1; exit; end; // Tukar Kolom jika perlu if Klm <> I then begin for J:= 0 to LP do begin T:= A[J*JV+I]; A[J*JV+I]:= A[J*JV+Klm];
A[J*JV+Klm]:= T; end; TNV:= V[I]; V[I]:= V[Klm]; V[Klm]:= TNV; end; // Tukar Baris jika perlu if Brs <> I then begin for J:= I to LV do begin T:= A[I*JV+J]; A[I*JV+J]:= A[Brs*JV+J]; A[Brs*JV+J]:= T; end; T:= B[I]; B[I]:= B[Brs]; B[Brs]:= T; end; // Eliminasi koefisien di bawah pivot if I < LP then begin for J:= succ(I) to LP do begin T:= A[J*JV+I] / A[I*JV+I]; if T <> 0 then begin for K:= I to LV do Kurangkan(A[J*JV+K], A[I*JV+K] * T); Kurangkan(B[J], B[I] * T); end; end; end; end; // Apakah SPL tidak konsisten SPLInfo.rA:= JV; SPLInfo.rAB:= JV; if LP > LV then begin for I:= JV to LP do if B[I] <> 0 then inc(SPLInfo.rAB); if SPLInfo.rA < SPLInfo.rAB then begin Result:= -1; // SPL tidak konsisten exit; end; end;
// Isi variabel X[j] for I:= LV downto 0 do begin T:= B[I]; for J:= succ(I) to LV do Kurangkan(T, A[I*JV+J]*X[J]); X[I]:= T / A[I*JV+I]; end; Result:= 0; end; function CariJawab( var A: array of Riil; { Matriks koefisien } var X: array of Riil; { Matriks Jawaban } var B: array of Riil; { Matriks Konstanta } var V: array of TNamaVar; { Matriks Nama Var } var SPLInfo: TSPLInfo): string; var I, Ret: integer; Str: string; begin { Salin A, X, dan B } Ret:= EliminasiGauss(A, X, B, V, SPLInfo); if SPLInfo.Homogen then Str:= 'Persamaan bersifat homogen.'#13#10 else Str:= 'Persamaan bersifat nonhomogen.'#13#10; case Ret of 0: begin Str:= Str + 'Karena r(A) = r(A,B) = ' + IntToStr(SPLInfo.rA) + ' dan r = n = ' + IntToStr(SPLInfo.n) + ' jadi, jawaban tuggal.'#13#10 + 'Jawabannya adalah sebagai berikut.'; for I:= 0 to pred(SPLInfo.n) do Str:= Str + #13#10' ' + StrPas(V[I]) + ' = ' + FloatToStr(X[I]); end; 1: begin Str:= Str + 'Karena r(A) = r(A,B) = ' + IntToStr(SPLInfo.rA) + ' dan r = ' + IntToStr(SPLInfo.rA) + ', n = ' + IntToStr(SPLInfo.n) + ', r < n jadi, ada banyak jawaban.'#13#10 + 'Jawaban umumnya adalah sebagai berikut.';
Str:= Str + JawabUmum(A, B, V, SPLInfo); end; else begin Str:= Str + 'Karena r(A) = ' + IntToStr(SPLInfo.rA) + ', r(A,B) = ' + IntToStr(SPLInfo.rAB) + ', r(A) < r(A,B) jadi, tidak ada jawaban.'; end; end; Str:= Str + #13#10 + #13#10'Keterangan:' + #13#10' r(A): rank baris matriks koefisien' + #13#10' r(A,B): rang baris augmented matrix' + #13#10' r = r(A,B)' + #13#10' n = jumlah variabel'; Result:= Str; end; function JawabUmum( var A: array of Riil; { Matriks koefisien } var B: array of Riil; { Matriks Konstanta } var V: array of TNamaVar; { Matriks Nama Var } var SPLInfo: TSPLInfo): string; const coBR = #13#10; coBRSPC = coBR + ' '; var I, J, K, LR, JV: integer; Tmp: Riil; Str, STanda: string; begin LR:= pred(SPLInfo.rA); JV:= SPLInfo.n; for I:= 0 to LR do begin Tmp:= A[I*JV+I]; for J:= I to pred(JV) do A[I*JV+J]:= A[I*JV+J] / Tmp; B[I]:= B[I] / Tmp; end; for I:= LR downto 1 do begin for J:= pred(I) downto 0 do begin Tmp:= A[J*JV+I]; for K:= I to pred(JV) do Kurangkan(A[J*JV+K], A[I*JV+K] * Tmp); Kurangkan(B[J], B[I] * Tmp);
end; end; Str:= ''; for I:= 0 to LR do begin Str:= Str + coBRSPC + StrPas(V[I]) + ' = '; J:= succ(LR); if B[I] <> 0 then Str:= Str + FloatToStr(B[I]) else begin while A[I*JV+J] = 0 do inc(J); if J < JV then begin Tmp:= A[I*JV+J]; if Tmp < 0 then STanda:= '' else STanda:= '-'; Tmp:= Abs(Tmp); if Tmp <> 0 then begin Str:= Str + STanda; if Tmp <> 1 then Str:= Str + FloatToStr(Tmp) + '*'; Str:= Str + '%' + IntToStr(J-LR);; end; inc(J); end; end; while J < JV do begin Tmp:= A[I*JV+J]; if (J = succ(LR)) and (B[I] = 0) then STanda:= '' else if Tmp < 0 then STanda:= ' + ' else STanda:= ' - '; Tmp:= Abs(Tmp); if Tmp <> 0 then begin Str:= Str + STanda; if Tmp <> 1 then Str:= Str + FloatToStr(Tmp) + '*'; Str:= Str + '%' + IntToStr(J-LR);; end; inc(J); end; IF copy(Str, Length(Str), 1) = ' ' then Str:= Str + '0'; end; for I:= succ(LR) to pred(JV) do Str:= Str + coBRSPC + StrPas(V[I]) + ' = %' + IntToStr(I-LR); Str:= Str + coBR + 'Jawaban tergantung parameter '; I:= 1; Str:= Str + '%' + IntToStr(I); inc(I); while I < JV - LR do begin Str:= Str + ', %' + IntToStr(I); inc(I);
end; Result:= Str + '.'; end; end. {function GaussJordan( var A: array of Riil; var X: array of Riil; var B: array of Riil; var V: array of TNamaVar; var SPLInfo: TSPLInfo): integer; var LV, LP, JV, JP: integer; I, J, K, Brs, Klm: integer; T: Riil; TNV: TNamaVar; begin JP:= SPLInfo.m; JV:= SPLInfo.n; LP:= pred(JP); LV:= pred(JV); // Cek homogenitas persamaan SPLInfo.Homogen:= true; for I:= 0 to LP do if B[I] <> 0 then begin SPLInfo.Homogen:= false; break; end; // Proses Gaus Jordan for I:= 0 to LV do begin // Cek apakah pivot = 0 Brs:= I; Klm:= I; for J:= I to LV do begin //Kolom for K:= I to LP do begin //Baris if Abs(A[K*JV+J]) > Abs(A[Brs*JV+Klm]) then begin Brs:= K; Klm:= J; end; end;
if A[Brs*JV+Klm] <> 0 then break; end; // Kalau tidak ada yang selain nol if A[Brs*JV+Klm] = 0 then begin SPLInfo.rA:= I; SPLInfo.rAB:= I; // Cek r(A) < r(A,B) for J:= I to LP do if B[J] <> 0 then inc(SPLInfo.rAB); if SPLInfo.rA < SPLInfo.rAB then Result:= -1 else Result:= 1; exit; end; // Tukar Kolom jika perlu if Klm <> I then begin for J:= 0 to LP do begin T:= A[J*JV+I]; A[J*JV+I]:= A[J*JV+Klm]; A[J*JV+Klm]:= T; end; TNV:= V[I]; V[I]:= V[Klm]; V[Klm]:= TNV; end; // Tukar Baris jika perlu if Brs <> I then begin for J:= I to LV do begin T:= A[I*JV+J]; A[I*JV+J]:= A[Brs*JV+J]; A[Brs*JV+J]:= T; end; T:= B[I]; B[I]:= B[Brs]; B[Brs]:= T; end; // Usahakan pivot menjadi 1 T:= A[I*JV+I]; for J:= I to LV do A[I*JV+J]:= A[I*JV+J] / T; B[I]:= B[I] / T; // Usahakan komponen di bawah pivot menjadi 0 if I < LP then begin
for J:= succ(I) to LP do begin T:= A[J*JV+I] / A[I*JV+I]; if T <> 0 then begin for K:= I to LV do Kurangkan(A[J*JV+K], A[I*JV+K] * T); Kurangkan(B[J], B[I] * T); end; end; end; end; // Cek apakan r(A) <> r(A,B) SPLInfo.rA:= JV; SPLInfo.rAB:= JV; if LP > LV then begin for I:= JV to LP do if B[I] <> 0 then inc(SPLInfo.rAB); if SPLInfo.rA < SPLInfo.rAB then begin Result:= -1; exit; end; end; // Usahakan komponen di atas pivot menjadi 0 for I:= LV downto 1 do begin for J:= pred(I) downto 0 do begin Kurangkan(B[J], B[I] * A[J*JV+I]); A[J*JV+I]:= 0; end; end; // Isi variabel X[n] for I:= 0 to LV do X[I]:= B[I]; Result:= 0; end;} unit ManajMem; interface uses SysUtils, DkGlobal; var
JPersamaan, JVariabel: integer; // Jumlah persamaan dan variabel Kons: PKons; // Pointer Konstanta pertama NVar: PVari; // Pointer awal nama variabel procedure HancurkanLinkedList; function CariVar(Nama: PChar): PVari; function SisipVar(Nama: PChar): PVari; procedure IsiKoefisien(Nilai: Riil; Nama: PChar; Baris: integer); procedure IsiKonstanta(Nilai: Riil); procedure LinkedListKeArray(var A, X, B: PRiilArray; var N: PNamaVarArray); procedure HancurkanArray(var A, X, B: PRiilArray; var N: PNamaVarArray); implementation procedure HancurkanLinkedList; var P, A: PVari; Q, B: PKoef; R, S: PKons; begin P:= NVar; while P <> nil do begin Q:= P^.Anak; while Q <> nil do begin B:= Q; Q:= Q^.Adik; Dispose(B); end; A:= P; P:= P^.Adik; Dispose(A); end; R:= Kons; while R <> nil do begin S:= R; R:= R^.Adik; Dispose(S); end; end; function CariVar(Nama: PChar): PVari; var P: PVari; begin P:= NVar; while P <> nil do if StrIComp(Nama, P^.Nama) = 0 then
break else P:= P^.Adik; Result:= P; end; function SisipVar(Nama: PChar): PVari; var P, Q, V, VarZ: PVari; begin new(V); StrLCopy(V^.Nama, Nama, NameLen); V^.Anak:= nil; Result:= V; if NVar = nil then begin New(NVar); New(VarZ); StrCopy(NVar^.Nama, #0); StrCopy(VarZ^.Nama, #255); NVar^.Anak:= nil; VarZ^.Adik:= nil; NVar^.Adik:= V; VarZ^.Anak:= nil; V^.Adik:= VarZ; end else begin P:= NVar; Q:= NVar^.Adik; while StrIComp(V^.Nama, Q^.Nama) > 0 do begin P:= Q; Q:= Q^.Adik; end; P^.Adik:= V; V^.Adik:= Q; end; inc(JVariabel); end; procedure IsiKoefisien(Nilai: Riil; Nama: PChar; Baris: integer); var V: PVari; K, L: PKoef; begin V:= CariVar(Nama); if V = nil then V:= SisipVar(Nama); New(K); K^.Nilai:= Nilai; K^.Baris:= Pred(Baris); K^.Adik:= nil; if V^.Anak = nil then V^.Anak:= K else begin L:= V^.Anak;
while L^.Adik <> nil do L:= L^.Adik; L^.Adik:= K; end; end; procedure IsiKonstanta(Nilai: Riil); var P, K: PKons; begin New(K); K^.Nilai:= Nilai; K^.Adik:= nil; if Kons = nil then Kons:= K else begin P:= Kons; while P^.Adik <> nil do P:= P^.Adik; P^.Adik:= K; end; end; procedure LinkedListKeArray(var A, X, B: PRiilArray; var N: PNamaVarArray); var I : integer; V: PVari; K: PKoef; P: PKons; begin // vb dim A() as Double // redim A(JPersamaan*JVariabel) as Double GetMem(A, JPersamaan*JVariabel*SizeOf(Riil)); GetMem(B, JPersamaan*SizeOf(Riil)); GetMem(X, JVariabel*SizeOf(Riil)); GetMem(N, JVariabel*SizeOf(TNamaVar)); FillChar(A^, JPersamaan*JVariabel*SizeOf(Riil), 0); FillChar(B^, JPersamaan*SizeOf(Riil), 0); FillChar(X^, JVariabel*SizeOf(Riil), 0); FillChar(N^, JVariabel*SizeOf(TNamaVar), 0); I:= 0; V:= NVar^.Adik; while V^.Adik <> nil do begin StrCopy(N^[I], V^.Nama); K:= V^.Anak; while K <> nil do begin A^[K^.Baris * JVariabel + I]:= K^.Nilai + A^[K^.Baris * JVariabel + I]; K:= K^.Adik;
end; V:= V^.Adik; inc(I); end; I:= 0; P:= Kons; while P <> nil do begin B^[I]:= P^.Nilai; P:= P^.Adik; inc(I); end; HancurkanLinkedList; end; procedure HancurkanArray(var A, X, B: PRiilArray; var N: PNamaVarArray); begin FreeMem(A, JPersamaan*JVariabel*SizeOf(Riil)); FreeMem(B, JPersamaan*SizeOf(Riil)); FreeMem(X, JVariabel*SizeOf(Riil)); FreeMem(N, JVariabel*SizeOf(TNamaVar)); end; end. unit Muka; interface uses Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, ExtCtrls, Buttons, DkGlobal, Parser; type TfrmMuka = class(TForm) Splitter1: TSplitter; pnlButton: TPanel; btnEksekusi: TButton; btnKeluar: TButton; pnlSoal: TPanel; Label1: TLabel; pnlSolusi: TPanel;
Label2: TLabel; mmoSoal: TMemo; mmoSolusi: TMemo; procedure btnEksekusiClick(Sender: TObject); procedure btnKeluarClick(Sender: TObject); procedure mmoSoalKeyPress(Sender: TObject; var Key: Char); end; var frmMuka: TfrmMuka; implementation {$R *.DFM} procedure TfrmMuka.btnEksekusiClick(Sender: TObject); var B: PChar; begin Screen.Cursor:= crHourGlass; mmoSolusi.Clear; B:= mmoSoal.Lines.GetText; mmoSolusi.Lines.Text:= Parsing(B); StrDispose(B); Screen.Cursor:= crDefault; end; procedure TfrmMuka.btnKeluarClick(Sender: TObject); begin Close; end; procedure TfrmMuka.mmoSoalKeyPress(Sender: TObject; var Key: Char); begin if Key = '.' then Key:= coDes; end; end. unit Parser; interface
uses SysUtils, DkGlobal, ManajMem, Gauss; function Parsing(StrSumber: PChar): string; implementation const arSimbol: array[TSimbol] of PChar = ('NIL', 'SAMLIN', 'VARIABEL', 'SKALAR', ';', '{', '}', '-', '+', '*', '='); var Sumber: PChar; // Pointer string skrip Simbol: TSimbol; // Simbol terminal terakhir NamaVar: TNamaVar; // Nama Variabel terakhir Skalar: extended; // Skalar tanpa tanda terakhir Tanda: Riil; // Tanda koefisien dan konstanta Baris, Kolom, // Posisi Baris dan kolom terakhir TmpKolom: integer; // Kolom terakhir sementara AdaKesalahan: boolean; // Status keberadaan kesalahan strHasil: string; // Menampung hasil akhir {==========================================} { } { Rutin untuk menangani kesalahan } { } {==========================================} procedure Kesalahan(S: string); begin Adakesalahan:= true; StrHasil:= format('%d,%d: %s', [Baris, Kolom - 1, S]); HancurkanLinkedList; end;
{===========================================} { } { Bagin Analisis Leksikal } { } {===========================================} function Angka(C: char): boolean; begin Angka:= (C >= '0') and (C <= '9'); end;
function Huruf(C: char): boolean; begin Huruf:= ((C>='A') and (C<='Z')) or ((C>='a') and (C<='z')); end; function AngkaHuruf(C: char): boolean; begin AngkaHuruf:= Angka(C) or Huruf(C); end; procedure Resimbol; var Str: array[0..256] of char; I: integer; procedure Maju; begin inc(Sumber); inc(TmpKolom); end; procedure Mundur; begin dec(Sumber); dec(TmpKolom); end; procedure UrusSpasi; begin while true do case Sumber^ of #9, #10, #32: Maju; #13: begin inc(Baris); TmpKolom:= 1; inc(Sumber); end; else break; end; end; procedure IsiStr; begin Str[I]:= Sumber^; Maju; inc(I); end; begin if AdaKesalahan then exit; UrusSpasi; Kolom:= TmpKolom; case Upcase(Sumber^) of #0: begin Simbol:= sbNil; Mundur; end; '{': Simbol:= sbBuka; '}': Simbol:= sbTutup; ';': Simbol:= sbTitikKoma; '*': Simbol:= sbAsterik; '+': Simbol:= sbPlus;
'-': Simbol:= sbMinus; '=': Simbol:= sbSamaDengan; 'A'..'Z': begin I:= 0; repeat IsiStr until not AngkaHuruf(Sumber^); Str[I]:= #0; StrLCopy(NamaVar, Str, NameLen); if StrIComp(NamaVar, arSimbol[sbSamlin])=0 then Simbol:= sbSamlin else Simbol:= sbVariabel; Mundur; end; '0'..'9': begin I:= 0; repeat IsiStr until not Angka(Sumber^); if Sumber^ = coDes then begin IsiStr; if Angka(Sumber^) then repeat IsiStr until not Angka(Sumber^) else begin Kesalahan('Bagian desimal bilangan tidak lengkap'); exit; end; end; if Upcase(Sumber^) = 'E' then begin IsiStr; if (Sumber^='+') or (Sumber^='-') then IsiStr; if Angka(Sumber^) then repeat IsiStr until not Angka(Sumber^) else begin Kesalahan('Bagian eksponen bilangan tidak lengkap'); exit; end; end; Str[I]:= #0; if TextToFloat(Str, Skalar, fvExtended) = false then begin Kesalahan('Konversi bilangan gagal'); exit; end; Simbol:= sbSkalar; Mundur; end;
else begin Kesalahan('Simbol tidak dikenal ' + Sumber^); exit; end; end; Maju; end;
{===========================================} { } { Bagin Analisis Sintaksis } { } {===========================================} procedure Cocok(Simb: TSimbol); begin if AdaKesalahan then exit; if Simbol = Simb then Resimbol else begin Kesalahan('"' + StrPas(arSimbol[Simb]) + '" tidak ditemukan tetapi "' + StrPas(arSimbol[Simbol]) + '" ditemukan'); exit; end; end; procedure Faktor; begin if AdaKesalahan then exit; if Simbol = sbSkalar then begin Skalar:= Tanda*Skalar; Resimbol; Cocok(sbAsterik); end else Skalar:= Tanda; if Simbol = sbVariabel then begin IsiKoefisien(SKalar, NamaVar, JPersamaan); Resimbol; end else begin Kesalahan('Variabel tidak ditemukan'); exit; end; end;
procedure Ekspresi; begin if AdaKesalahan then exit; if Simbol = sbMinus then begin Tanda:= -1; Resimbol; end else Tanda:= 1; Faktor; while (Simbol = sbPlus) or (Simbol = sbMinus) do begin if Simbol = sbMinus then Tanda:= -1 else Tanda:= 1; Resimbol; Faktor; end; end; procedure Konstanta; begin if AdaKesalahan then exit; if Simbol = sbMinus then begin Tanda:= -1; Resimbol; end else Tanda:= 1; if Simbol = sbSkalar then begin Skalar:= Tanda*Skalar; IsiKonstanta(Skalar); Resimbol; end else begin Kesalahan('Konstanta tidak ditemukan'); exit; end; end; procedure Persamaan; begin if AdaKesalahan then exit; inc(JPersamaan); Ekspresi; Cocok(sbSamaDengan); Konstanta; end; procedure SistemPersamaanLinier; begin while (Simbol = sbMinus) or (Simbol = sbSkalar)
or (Simbol = sbVariabel) do begin if AdaKesalahan then exit; Persamaan; Cocok(sbTitikKoma); end; end; procedure Skrip; begin Cocok(sbSamlin); Cocok(sbBuka); SistemPersamaanLinier; Cocok(sbTutup); end;
{===========================================} { Bagin Persiapan/Inisialisasi } {===========================================} procedure Persiapan; begin NVar:= nil; Kons:= nil; JPersamaan:= 0; JVariabel:= 0; Baris:= 1; Kolom:= 1; TmpKolom:= 1; AdaKesalahan:= false; StrHasil:= ''; Resimbol; end; {===========================================} { Bagin Penentuan Solusi SPL } {===========================================} procedure TentukanSolusiSPL; var SPLInfo: TSPLInfo; A, X, B: PRiilArray; N: PNamaVarArray; begin if AdaKesalahan then exit; if JPersamaan = 0 then exit; if JPersamaan < JVariabel then JPersamaan:= JVariabel; LinkedListKeArray(A, X, B, N); SPLInfo.m:= JPersamaan; SPLInfo.n:= JVariabel;
StrHasil:= CariJawab(A^, X^, B^, N^, SPLInfo); HancurkanArray(A, X, B, N); end; {===========================================} { } { Bagin Utama Parser } { } {===========================================} function Parsing(StrSumber: PChar): string; begin Sumber:= StrSumber; Persiapan; Skrip; TentukanSolusiSPL; Result:= StrHasil; end; end.
