A11.2008.04511: 2010

Kamis, 17 Juni 2010

Manajemen Memori 1

Manajemen Memori
(1)Manajemen Memori Manajemen Memori Manajemen Memori
Memori utama harus diatur sebaik mungkin agar :
 meningkatkan utilitas CPU yang sebesar-besarnya
 data dan instruksi dapat diakses dengan cepat oleh
CPU
 memori utama memiliki kapasitas yang sangat

Baca selengkapnya >>

Manajemen Input/OutputFungsi

Manajemen
Input/OutputFungsi
 mengirim perintah ke perangkat
masukan/keluaran agar menyediakan layanan.
 menangani interupsi perangkat
masukan/keluaran
 menangani kesalahan pada perangkat
masukan/keluaran
 menyediakan interface ke pemakai Klasifikasi Perangkat I/O
 Berdasarkan sifat aliran datanya :
 perangkat berorientasi blok (blok oriented
device)
 menyimpan dan menukarkan
(menerima/mengirim) informasi sebagai blok-
blok berukuran tetap, contoh : disk, tape,
CDROM, optical disk, dll
 perangkat berorientasi aliran karakter
 perangkat yang mengantarkan atau menerima
aliran karakter tanpa peduli membentuk suatu
struktur blok, contoh : terminal, line printer,
pita kertas, mouse, kartu berlubang Klasifikasi Perangkat I/O
 Berdasarkan sasaran komunikasi:
 perangkat yang terbaca manusia (human
readable devices)
 perangkat yang cocok untuk komunikasi
dengan manusia, contoh : monitor, keyboard,
mouse
 perangkat yang terbaca mesin (machine
readable devices)
 perangkat yang cocok untuk komunikasi
dengan perangkat elektronik, contoh : disk
dan tape, sensor, controller.
 untuk komunikasi
 perangkat yang cocok untuk komunikasi
dengan perangkat jarak jauh, contoh : modemPrinsip Manajemen I/O
Dua sasaran perancangan manajemen I/O :
 Efisiensi (eficiency)
 Merupakan aspek penting karena operasi I/O
sering merupakan operasi yang
menimbulkan bottleneck pada sistem
operasi.
 Generalitas (generality)
 Manajemen perangkat i/o selain berkaitan
dengan simplisitas dan bebas kesalahan,
juga menangani perangkat secara seragam
baik dari cara proses memandang maupun
cara sistem operasi mengelola perangkat
dan operasi i/o. Masalah yang Harus Diselesaikan
Masalah-masalah yang terdapat dan harus
diselesaikan pada perancangan manajemen
i/o :
 Penamaan yang seragam (uniform naming)
 nama berkas atau perangkat adalah string
atau integer
 Penanganan kesalahan (error handling) Masalah yang Harus Diselesaikan
 Transfer sinkron vs asinkron
 Kebanyakan i/o adalah asinkron. Prosesor
melakukan proses transfer data dan mengijinkan
proses lain untuk berlanjut meskipun proses
transfer blm selesai.
 Sharable vs dedicated
 beberapa perangkat dapat dipakai bersama seperti
disk, tapi ada juga perangkat yang hanya satu
pemakai yang dibolehkan memakai pada satu saat,
contoh perangkat dedicated : printer. Hirarki Manajemen I/O
 INTERRUPT HANDLER
 Pengendali interupsi (interrupt handler) harus
disembunyikan di sistem yang paling dalam
agar tidak terlihat ke rutin-rutin berikutnya.
 DEVICE DRIVER
 Semua kode bergantung peralatan yang
ditempatkan pada device driver. Tiap device
driver menangani satu tipe peralatan atau satu
kelas peralatan yang berhubungan. device
driver bertugas menerima permintaan abstrak
perangkat lunak device-independent diatasnya
dan melakukan layanan sesuai permintaan. Hirarki Manajemen I/O
 Mekanisme device driver :
 Menerjemahkan perintah-perintah abstrak
menjadi perintah-perintah kongkret
 Setelah mendapat perintah, device driver mulai
menulis ke register-register pengendali peralatan
 Setelah operasi selesai dilakukan, device driver
memeriksa kesalahan-kesalahan yang terjadi
 Jika semua berjalan baik, device driver
melewatkan data ke perangkat lunak device-
independent
 Device driver melaporkan status operasinya ke
pemanggil Hirarki Manajemen I/O
PERANGKAT LUNAK DEVICE INDEPENDENT
 Fungsi utama perangkat lunak ini :
 membentuk fungsi-fungsi i/o yang berlaku untuk
semua perangkat
 memberi interface/antarmuka seragam ke
perangkat lunak tingkat pemakai Hirarki Manajemen I/O
 Fungsi yang dilakukan antara lain:
 interface seragam untuk seluruh device driver
 penamaan peralatan
 proteksi peralatan
 memberi ukuran blok peralatan
 melakukan buffering
 alokasi penyimpanan pada block-devices
 alokasi dan pelepasan dedicated-devices
 pelaporan kesalahan Hirarki Manajemen I/O
PERANGKAT LUNAK LEVEL PEMAKAI
 Kebanyakan perangkat lunak i/o terdapat pada
sistem operasi.
 Tidak semua perangkat lunak i/o level
pemakai berisi prosedur-prosedur pemakai.
 Kategori penting adalah sistem spooling.
 Spooling merupakan cara khusus berurusan
dengan peralatan i/o yang harus didedikasikan
pada sistem multiprogramming.Mekanisme Perangkat Lunak I/O
DISK
 Disk diorganisasikan menjadi silinder-silinder dengan track-track terdapat
head yang ditumpuk secara vertikal. Tiap track terbagi menjadi sektor-
sektor. Waktu yang dibutuhkan untuk membaca dan menulis disk
dipengaruhi oleh :
 Waktu seek
 Waktu yang diperlukan untuk sampai ke posisi track yang dituju.
Waktu seek merupakan faktor yang paling dominan.
 Waktu tunda rotasi
 Waktu yang diperlukan mekanisme akses mencapai blok yang
diinginkan.
 Waktu transfer data
 waktu tranfer data bergantung pada kecepatan rotasi dan
kepadatan rekaman. Transfer rate (t) adalah kecepatan transfer
data sesaat, data ini diberikan oleh pembuat perangkat kerasBeberapa tipe kesalahan dapat muncul ketika operasi disk.
Kesalahan-kesalahan pada disk dapat dikategorikan sebagai
berikut :
 Programming error
 Kesalahan yang disebabkan pemrograman, misalnya
driver memerintahkan mencari track yang tak ada,
membaca sector yang tak ada, dll
 Transient checksum error
 Kesalahan disebabkan adanya debu diantara head
dengan permukaan disk. Untuk mengeliminasi
kesalahan ini maka dilakukan pengulangan operasi
pada disk.
 Permanent checksum error
 Kesalahan disebabkan kerusakan disk maka harus
dibuat daftar blok-blok buruk agar data tidak ditulis di
blok buruk.  Seek error
 Kesalahan ini ditanggulangi dengan
mengkalibrasi disk supaya berfungsi
kembali.
 Controller error
 Kesalahan ini ditanggulangi dengan
menukar pengendali yang salah dengan
pengendali yang baru. Mekanisme Perangkat Lunak I/O
CLOCK
 Perangkat keras clock mempunyai 2 tipe
clock, yaitu :
 Clock yang ditimbulkan impulse tegangan
listrik
 Programmable interval timer (PIT) Mekanisme Perangkat Lunak I/O
 Sedangkan perangkat lunak clock pada sistem
operasi mempunyai beberapa fungsi, antara
lain :
 mengelola waktu dan tanggal (waktu nyata)
 mencegah proses berjalan lebih dari waktu
yang ditetapkan
 menghitung penggunaan pemroses
 mengerjakan monitoring dan pengumpulan
statistik Alokasi Piranti
 Dedicated device
 merupakan cara mengalokasikan piranti
untuk sebuah pekerjaan selama pekerjaan
berada dalam sistem. Kelemahannya adalah
tidak efisien karena bila suatu pekerjaan
menggunakan sekali-kali, tetapi piranti harus
tetap melayani pekerjaan tersebut.
 Shared device
 merupakan cara mengalokasikan piranti
supaya dapat digunakan secara bergantian
untuk beberapa pekerjaan. Beberapa piranti
seperti cakram magnetis, drum dapat
digunakan secara bergantian. Alokasi Piranti
 Virtual device
 Piranti yang digunakan dengan cara dedicated,
misal printer, dapat diubah menjadi piranti shared
melalui cara-cara seperti spooling.
 Spooling adalah proses transfer data dengan
menempatkannya pada temporary area dimana
program lain dapat mengaksesnya nanti.
• Contoh : mencetak dokumen, prosesor akan
menempatkan data yang akan dicetak ke temporary
area, kemudian akan dibaca oleh printer untuk
kemudian dicetak

deadlock

DEADLOCKDeadlock
 Terjadi jika proses menunggu suatu kejadian
tertentu yang tidak pernah terjadi
 Sekumpulan proses berkondisi deadlock bila
setiap proses yang ada di kumpulan
menunggu suatu kejadian yang hanya dapat
dilakukan proses lain yang juga berada di
kumpulan itu. Pengoperasian I/O
 meminta (request) : meminta pelayanan
perangkat masukan/keluaran
 memakai (use) : memakai perangkat
masukan / keluaran
 melepaskan (release) : melepaskan
pemakaian perangkat masukan/keluaran
Syarat Deadlock
 mutual exclusion (mutual exclusion conditional)
 tiap sumber daya saat itu diberikan pada tepat 1 proses.
 kondisi genggam dan tunggu (hold and wait)
 proses-proses yang sedang menggenggam sumber daya,
menunggu sumber daya-sumber daya baru.
 kondisi non-preemption (non-preemption condition)
 sumber daya-sumber daya yang sebelumnya diberikan
tidak dapat diambil paksa dari proses itu.Sumber daya
harus secara explisit dilepaskan dari proses yang
menggenggamnya.
 kondisi menunggu secara sirkuler (circular wait condition)
 harus terdapat rantai sirkuler dari dua proses atau lebih,
masing-masing menunggu sumber daya yang digenggam
oleh anggota berikutnya pada rantai itu. Syarat Deadlock
 Terjadi deadlock bila terdapat ketiga kondisi
itu, tetapi adanya ketiga kondisi itu belum
berarti terjadi deadlock.
 Deadlock benar-benar terjadi bila syarat
keempat terpenuhi. Kondisi keempat
merupakan keharusan bagi terjadinya
deadlock.
 Deadlock bisa terjadi pada saat proses akan
mengakses objek seperti file,device, dll secara
tidak semestinya. Objek tersebut dinamakan
resource. Jenis Resource
 preemtable resource
 resource yang dapat diambil dan dilepas dari
proses yang sedang memakainya tanpa
memberikan efek apapun pada proses tersebut.
 Non-preemtable resource
 resource tidak dapat diambil dari proses yang
sedang membawanya, karena akan
mengakibatkan kegagalan komputasi, contoh :
printer, bila suatu proses sedang menggunakan
printer untuk mencetak, maka proses lain tidak
dapat menggunakan printer tersebut. Metode Mengatasi Deadlock
 Pencegahan deadlock
 Tiap proses harus meminta semua sumber daya
yang diperlukan secara sekaligus dan tidak
berlanjut sampai semuanya diberikan.
 Jika proses sedang memegang sumberdaya
tertentu, untuk permintaan berikutnya proses
harus melepas dulu sumberdaya yang
dipegangnya.
 Beri pengurutan linier terhadap tipe-tipe sumber
daya pada semua proses, yaitu jika proses telah
dialokasikan suatu tipe sumber daya, proses
hanya boleh meminta tipe sumber daya pada
urutan berikutnya. Metode Mengatasi Deadlock
 Penghindaran deadlock
 Menghindari deadlock dengan cara hanya
memberi akses ke permintaan sumber daya
yang tidak mungkin menimbulkan deadlock.
 jika pemberian akses sumber daya tidak mungkin
menuju deadlock, sumber daya diberikan ke
peminta.
 Jika tidak aman (memungkinkan timbulnya
deadlock), proses yang meminta di suspend
sampai suatu waktu permintaannya aman
diberikan. Kondisi ini biasanya terjadi setelah 1
sumber daya / lebih yang semula dipegang oleh
proses-proses aktif lain dilepaskan. Metode Mengatasi Deadlock
 Agar dapat mengevaluasi safe-nya state
sistem, penghindaran deadlock mengharuskan
semua proses menyatakan jumlah kebutuhan
sumber daya maksimum sebelum eksekusi.
 Begitu eksekusi dimulai, tiap proses meminta
sumber daya saat diperlukan sampai batas
maksimum yang dinyatakan di awal. Proses-
proses yang menyatakan kebutuhan sumber
daya melebihi kapasitas total sistem tidak
dapat dieksekusi.Safe State
• State selamat (safe state) : jika tidak
deadlock dan terdapat cara untuk memenuhi
semua permintaan yang ditunda tanpa
menghasilkan deadlock dengan menjalankan
proses secara hati-hati mengikuti suatu
urutan tertentu. Safe State
• Contoh :
• Sistem dengan 10 sumber daya setipe,
proses A memerlukan sumber daya
maksimum sebanyak 10, sedang saat ini
menggenggam 2 sumber daya. proses B
memerlukan sumber daya maksimum
sebanyak 3, sedang saat ini menggenggam
1 sumber daya. Proses C memerlukan
sumber dayamaksimum sebanyak 7, sedang
saat ini menggenggam 3 sumber daya.
Masih tersedia 4 sumber daya. Safe State
• Contoh :Safe State
• Contoh :
• State dinyatakan selamat (safe) karena
terdapat barisan pengalokasian yang dapat
memungkinkan semua proses selesai.
Dengan penjadwalan secara hati-hati, sistem
dapat terhindarkan dari deadlock. Barisan
tersebut adalah : Unsafe State
• State tak selamat (unsafe state) : jika tidak
terdapat cara untuk memenuhi semua
permintaan yang saat ini ditunda dengan
menjalankan proses-proses dengan suatu
urutan.
• Contoh :
• State dibawah ini sama dengan state
selamat sebelumnya, tapi dapat berubah
menjadi state tak selamat bila alokasi
sumber daya tak terkendali. Deteksi dan Pemulihan Deadlock
• Deteksi deadlock adalah teknik untuk
menentukan apakah deadlock terjadi serta
mengidentifikasi proses-proses dan sumberdaya-
sumberdaya yang terlibat deadlock.
• Periode yang biasa dilakukan adalah memonitor
permintaan dan pelepasan sumber daya.
• Bila sistem terdapat deadlock maka deadlock
harus diputuskan. Biasanya beberapa proses
akan kehilangan sebagian atau semua kerja
yang telah dilakukan. Hal ini lebih baik daripada
terjadinya deadlock yang berarti semua proses
tidak menghasilkan apapunDeteksi dan Pemulihan Deadlock
• Teknik pemulihan yang biasa digunakan
adalah menghilangkan (suspend / kill)
proses-proses dari sistem dan pengklaiman
kembali sumberdaya yang dipegang proses-
proses tersebut.
• Proses yang dihilangkan biasanya cacat
tetapi proses lain dapat menyelesaikan
prosesnyaPemulihan Deadlock
• singkirkan semua proses yang terlibat deadlock
• backup semua proses yang terlibat deadlock ke
suatu check point yang didefinisikan sebelumnya
dan jalankan kembali proses itu.
• secara berurutan abaikan proses-proses sampai
deadlock tidak terjadi lagi. Urutan proses yang
dipilih untuk disingkirkan berdasar kriteria ongkos
minimum.
• secara berurutan preempt sumberdaya-
sumberdaya sampai tidak ada deadlock lagi.
Proses yang kehilangan sumber daya karena
preemption harus dikembalikan (roll-back) ke titik
sebelum memperoleh sumber daya.Kriteria Pemilihan Proses Yang
Akan Disingkirkan
• waktu pemrosesan yang dijalankan paling
kecil
• jumlah baris keluaran yang diproduksi paling
kecil
• mempunyai estimasi sisa waktu eksekusi
terbesar
• jumlah total sumber daya terkecil yang telah
dialokasikan
• prioritas terkecil. Kriteria Pemilihan Proses Yang
Akan Disingkirkan
• Dalam penyingkiran proses, sistem harus
mengembalikan berkas-berkas yang telah
dimodifikasi oleh proses-proses yang
disingkirkan ke keadaan asli karena
berpengaruh terhadap konsistensi data
sistem itu.

Jumat, 11 Juni 2010

kisi SO

Kisi-Kisi UAS Sistem Operasi

Bahan yang harus dipelajari untuk UAS Sistem Operasi adalah sebagai berikut :

konsep deadlock

safe state dan unsafe state

algoritma penggantian page

komponen manajemen I/O

strategi alokasi memori

klasifikasi perangkat I/O

konsep manajemen I/O

mesin turing

MESIN TURING

• Stack (tumpukan) yang terdapat pada PDA memiliki keterbatasan kemampuan akses, yaitu hanya mengakses data yang terdapat pada top / puncak dari stack.

• Untuk melakukan akses pada bagian yang lebih rendah dari puncak stack, harus memindahkan bagian di atasnya (pop), yang mana akan menyebabkan bagian tersebut hilang.

• Pada mesin Turing, memori berupa suatu pita yang pada dasarnya berupa array (deretan) sel-sel penyimpanan. Setiap sel mampu menyimpan sebuah simbol tunggal.

• Pita tersebut tidak mempunyai sel pertama dan sel terakhir. Pita dapat memuat informasi dalam jumlah tak terbatas, dan dapat diakses bagian manapun dari pita dengan urutan bagaimanapun.

• Terdapat sebuah head yang menunjukkan posisi yang diakses pada pita. Head dapat bergerak ke kanan atau ke kiri untuk membaca input dari pita dan sekaligus juga bisa melakukan penulisan pada pita/mengubah isi pita.

• Mesin Turing bisa dianalogikan seperti komputer sederhana, dengan sejumlah state sebagai memori, pita sebagai secondary storage, fungsi transisi sebagai program.

• Sebuah mesin Turing secara formal dinyatakan dalam 7 tupel, yaitu M = (Q, Σ, Γ, δ, S, F, b) dimana :

Q = himpunan state

Σ = himpunan simbol input

Γ = simbol pada pita (meliputi pula blank)

δ = fungsi transisi

S = state awal, S ∈ Q

F = himpunan state akhir, F⊆ Q

b = simbol kosong (blank) 􀃆 bukan bagian dari Σ, b ∉Σ

Bagian dari pita yang belum ditulisi dianggap berisi simbol b (blank)

• Contoh :

Misal terdapat mesin Turing :

Q = {q1,q2}

Σ = {a,b}

Γ = {a,b, b)

F = {q2}

S = {q1}

Fungsi transisinya : Pergerakan mesin Turing : R = right(kanan), L = left (kiri)

δ (q1,a) = (q1,a,R) 􀃎 pada state q1, head menunjuk karakter ‘a’ pada pita, menjadi state q1, head

bergerak ke kanan

δ (q1,b) = (q1,a,R) 􀃎 pada state q1, head menunjuk karakter ‘b’ pada pita, menjadi state q1, head

menulis karakter ‘a’ lalu bergerak ke kanan

δ (q1, b ) = (q2, b ,L) 􀃎 pada state q1, head menunjuk karakter ‘ b ’ pada pita menjadi state q2,

head bergerak ke kiri

Perhatian : pada mesin Turing

δ (q,x) = (q,y,G)

bila x <> y, maka head akan menulis simbol y (menimpa x) sebelum bergerak sesuai G

(kiri / kanan)

Jadi berdasarkan fungsi transisi diatas, maka mesin Turing beroperasi seperti berikut :

Head ditunjukkan dengan

1. Misal pita yang akan dibaca : ‘abbaa’

state q1

Fungsi transisi δ (q1,a) = (q1,a,R) menyebabkan head bergerak ke kanan

state q1

Fungsi transisi δ (q1,b) = (q1,a,R) menyebabkan head menulis ‘a’ lalu bergerak ke kanan

state q1

Fungsi transisi δ (q1,b) = (q1,a,R) menyebabkan head menulis ‘a’ lalu bergerak ke kanan

state q1

Fungsi transisi δ (q1,a) = (q1,a,R) menyebabkan head bergerak ke kanan

state q1

Fungsi transisi δ (q1,a) = (q1,a,R) menyebabkan head bergerak ke kanan

state q1

Head menunjuk b, karena bagian pita yang belum ditulisi dianggap berisi b

Fungsi transisi δ (q1, b ) = (q2, b ,L) menyebabkan head bergerak ke kiri

state q2

Tidak ada transisi lagi dari state q2, mesin Turing akan berhenti (halt state)

Karena state q2 termasuk state akhir berarti input tersebut diterima

• Contoh :

Misal konfigurasi mesin Turing :

Q = {q0,q1,q2,q3,q4}

Σ = {0,1}

Γ = {0,1,X,Y, b)

F = {q4}

S = {q0}

Fungsi transisinya dalam bentuk tabel sebagai berikut :

(q1,X,R)

(q3,Y,R)

(q1,0,R)

(q2,Y,L)

(q1,Y,R)

(q2,0,L)

(q0,X,R)

(q2,Y,L)

(q3,Y,R)

(q4, b ,L)

1. Misal pita yang akan dibaca : ‘0011’

state q0

state q1

state q2

state q0

state q1

state q2

10.

state q2

11.

state q0

12.

state q3

13.

state q3

14.

state q4

Tidak ada transisi lagi dari state q4, mesin Turing berhenti dan karena state q4 termasuk state akhir, maka input tersebut diterima.

DESKRIPSI SEKETIKA PADA MESIN TURING

• Tahapan transisi nomor (1) sampai (14) pada contoh diatas dapat dinyatakan dalam notasi yang disebut deskripsi seketika (instantaneous description).

• Deskripsi seketika diperlukan untuk menyatakan secara formal konfigurasi mesin Turing pada suatu saat.

• Perubahan dari suatu kondisi ke berikutnya dipisahkan dengan tanda ‘ | ‘

Untuk simbol head ditulis dengan garis bawah ‘_’

• Jadi tahapan no. 1 sampai 14 dapat dinyatakan sebagai berikut :

(q0,0011) | (q1,X011) (q1,X011) (q2,X0Y1) (q2,X0Y1) (q0,X0Y1) (q1,XXY1) (q1,XXY1) (q2,XXYY) (q2,XXYY) (q0,XXYY) (q3,XXYY) (q3,XXYY b) (q4,XXYY b)

• Misal bila mendapat input 011 :

(q0,011) (q1,X11) (q2,XY1) (q0,XY1) (q3,XY1)

Tidak ada transisi (q3,1) maka mesin berhenti dan karena q3 tidak termasuk state akhir berarti input tersebut ditolak.

pushdown automata

PUSHDOWN AUTOMATA (PDA)

• PDA merupakan mesin otomata dan CFG. Bila sebuah FSA mempunyai kemampuan “memori” yang terbatas, pada PDA didefinisikan sebuah tempat penyimpanan yang tidak terbatas berupa stack / tumpukan

• Stack = kumpulan dari elemen-elemen sejenis dengan sifat penambahan elemen dan pengambilan elemen melalui suatu tempat yang disebut top of stack (puncak stack).

• Pengambilan elemen dan stack dinyatakan dengan operasi pop, sedangkan memasukkan elemen ke dalam stack dengan operasi push.

• Setiap elemen stack bisa memuat 1 simbol, yang disebut simbol stack.

• Contoh sebuah stack :

Bila dilakukan operasi pop, maka kondisi stack menjadi :

Bila dilakukan operasi push B, maka kondisi stack menjadi :

• Sebuah PDA dinyatakan dalam 7 tupel, M = (Q, Σ, Γ, Δ, S, F, Z) dimana :

Q = himpunan state

Σ = himpunan simbol input

Γ = simbol-simbol tumpukan/stack

Δ = fungsi transisi

S = state awal, S∈ Q

F = himpunan final state F∈Q

Z = simbol awal tumpukan / top stack, Z ∈ Γ

Dari komponen diatas dapat dilihat :

- Definisi untuk Q, Σ, Δ, S, F sama dengan yang ada pada FSA

- Tupel yang baru adalah Γ, Z yang berhubungan dengan stack

- Δ memiliki kemiripan dengan δ pada FSA dengan beberapa perbedaan

• Pada PDA terdapat 2 jenis transisi (Δ) yaitu :

- Memakai suatu simbol input

Bergantung pada simbol input, simbol pada top stack dan state terdapat sejumlah pilihan yang mungkin. Setiap pilihan terdiri dari state berikutnya dan simbol-simbol untuk mengganti simbol pada top stack. Penggantian simbol pada top stack bisa berupa push untuk satu atau beberapa simbol, bisa berupa pop untuk simbol kosong.

- Dengan transisi ε

Mirip yang pertama tetapi dilakukan tanpa membaca simbol. Transisi ini memungkinkan PDA memanipulasi isi stack atau berpindah state tanpa membaca simbol.

• Contoh PDA :

Q = {q1, q2}

Σ = {a, b}

Γ = {A, B, Z}

S = q1

F = {q2}

Z = Z

Memiliki fungsi transisi sebagai berikut :

Δ(q1,ε, Z) = {(q2,Z)}

Δ(q1,a, Z) = {(q1,AZ)}

Δ(q1,b, Z) = {(q1,BZ)}

Δ(q1,a, A) = {(q1,AA)}

Δ(q1,b, A) = {(q1,ε)}

Δ(q1,a, B) = {(q1,ε)}

Δ(q1,b, B) = {(q1,BB)}

Apakah string ‘abba’ diterima PDA ini :

1. Konfigurasi awal mesin : state q1, top stack Z, membaca input ‘a’, fungsi transisinya

Δ(q1,a, Z) = {(q1,AZ)}

Konfigurasi mesin menjadi state q1, A di push

2. Membaca input ‘b’

Fungsi transisinya Δ(q1,b,A) = {(q1,ε)}

Konfigurasi mesin menjadi state q1, top stack dipop

3. Membaca input ‘b’

Fungsi transisinya Δ(q1,b, Z) = {(q1,BZ)}

Konfigurasi mesin menjadi state q1, B dipush

4. Membaca input ‘a’

Fungsi transisinya Δ(q1,a, B) = {(q1, ε)}

Konfigurasi mesin menjadi state q1, top stack dipop

5. Semua input telah selesai dibaca

Fungsi transisinya Δ(q1, ε, Z) = {(q2, Z)}

Konfigurasi mesin menjadi state q2

State q2 berada dalam F (final state) maka ‘abba’ diterima oleh PDA tersebut.

• Contoh PDA :

Q = {q1,q2}

Σ = {0,1,2}

Γ = {Z, B, G}

S = q1

F = ∅

Z = Z

Memiliki fungsi transisi sebagai berikut :

Δ(q1,0, Z) = {(q1,BZ)}

Δ(q1,0, B) = {(q1,BB)}

Δ(q1,0, G) = {(q1,BG)}

Δ(q1,0, Z) = {(q1,GZ)}

Δ(q1,0, B) = {(q1,GB)}

Δ(q1,2, Z) = {(q2,Z)}

Δ(q1,2, B) = {(q2,B)}

Δ(q1,2, G) = {(q2,G)}

Δ(q2,0, B) = {(q2,ε)}

Δ(q2,ε, Z) = {(q2,ε)}

Δ(q2,1, G) = {(q2,ε)}

Apakah string ‘020’ diterima PDA ini :

1. Konfigurasi awal mesin : state q1, top stack Z, membaca input ‘0’, fungsi transisinya

Δ(q1,0, Z) = {(q1,BZ)}

Konfigurasi mesin menjadi state q1, B dipush

2. Membaca input ‘2’

Fungsi transisinya Δ(q1,2,B) = {(q2,B)}

Konfigurasi mesin menjadi state q2, stack tetap

3. Membaca input ‘0’

Fungsi transisinya Δ(q2,0,B) = {(q2,ε)}

Konfigurasi mesin menjadi state q2, B dipop

4. Tanpa membaca input ‘ε’

Fungsi transisinya Δ(q2,ε, Z) = {(q2, ε)}

Konfigurasi mesin menjadi state q2, Z dipop

Stack kosong.

Semua input telah selesai dibaca, stack kosong berada dalam F (final state) maka ‘020’ diterima oleh PDA tersebut.

BENTUK NORMAL CHOMSKY

BENTUK NORMAL CHOMSKY

(CHOMSKY NORMAL FORM / CNF)

• Merupakan salah satu bentuk normal yang sangat berguna untuk CFG

• Bentuk normal Chomsky dibuat dari CFG yang telah mengalami penyederhanaan yaitu penghilangan produksi useless, unit, dan ε.

• Aturan produksi dalam bentuk normal Chomsky adalah ruas kanannya tepat berupa sebuah terminal atau 2 variabel, misal :

A 􀃆 BC

A 􀃆 b

B 􀃆 a

C 􀃆 BA | d

• Langkah-langkah pembentukan bentuk normal Chomsky :

Biarkan yang sudah CNF

• Contoh : Berikut ini CFG yang sudah mengalami penyederhanaan

S 􀃆 Ba | Ab

A 􀃆 Baa | As | a

B 􀃆 Abb | Bs | b

Aturan produksi yang sudah dalam bentuk normal Chomsky (CNF) :

A 􀃆 a

B 􀃆 b

Dilakukan penggantian aturan produksi yang belum bentuk normal Chomsky :

S 􀃆 Ba menjadi S 􀃆 P1A

S 􀃆 Ab menjadi S 􀃆 P2B

A 􀃆 Baa menjadi A 􀃆 P1AA menjadi A 􀃆 P1P3

A 􀃆 As menjadi A 􀃆 P2S

B 􀃆 Abb menjadi B 􀃆 P2BB menjadi B 􀃆 P2P4

B 􀃆 Bs menjadi B 􀃆 P1S

Sehingga terbentuk aturan produksi dan simbol variabel baru :

P1 􀃆 b

P2 􀃆 a

P3 􀃆 AA

P4 􀃆 BB

Hasil akhir aturan produksi dalam bentuk normal Chomsky :

A 􀃆 a

B 􀃆 b

S 􀃆 P1A

S 􀃆 P2B

A 􀃆 P1P3

A 􀃆 P2S

B 􀃆 P2 P4

B 􀃆 P1S

CFG yang sudah disederhanakan

Penggantian simbol terminal pada aturan produksi yang ruas kanan > 1

Buat variabel dan aturan produksi baru bila perlu

CNF

Penggantian aturan produksi yang simbol variabel > 2

P1 􀃆 b

P2 􀃆 a

P3 􀃆 AA

P4 􀃆 BB

• Contoh : Berikut ini CFG yang sudah mengalami penyederhanaan

S 􀃆 Ab | CA

A 􀃆 a | bc

B 􀃆 BC | Ab

C 􀃆 Ab | b

Aturan produksi yang sudah dalam bentuk normal Chomsky :

S 􀃆 CA

A 􀃆 a

B 􀃆 BC

C 􀃆 b

Penggantian aturan produksi yang belum dalam bentuk normal Chomsky :

S 􀃆 Ab menjadi S 􀃆 P1B

A 􀃆 bc menjadi S 􀃆 P2P3

B 􀃆 Ab menjadi B 􀃆 AP2

C 􀃆 Ab menjadi C 􀃆 P1B

Terbentuk aturan produksi dan simbol variabel baru :

P1 􀃆 a

P2 􀃆 b

P3 􀃆 c

Hasil akhir aturan produksi dalam bentuk normal Chomsky :

S 􀃆 CA

A 􀃆 a

B 􀃆 BC

C 􀃆 b

S 􀃆 P1B

S 􀃆 P2P3

B 􀃆 AP2

C 􀃆 P1B

P1 􀃆 a

P2 􀃆 b

P3 􀃆 c

• Contoh CFG :

S 􀃆 Aab | ch | CD

A 􀃆 dbE | Eec

B 􀃆 ff | DD

C 􀃆 ADB | As

D 􀃆 i

E 􀃆 jd

Aturan produksi yang sudah dalam bentuk normal Chomsky :

S 􀃆 CD

B 􀃆 DD

D 􀃆 i

Penggantian aturan produksi :

S 􀃆 Aab menjadi S 􀃆 P1P2

S 􀃆 ch menjadi S 􀃆 P3P4

A 􀃆 dbE menjadi A 􀃆 P5P6

A 􀃆 Eec menjadi A 􀃆 P8P9

B 􀃆 ff menjadi B 􀃆 P10P10

C 􀃆 ADB menjadi C 􀃆 AP11

C 􀃆 As menjadi C 􀃆 P1S

E 􀃆 Jd menjadi E 􀃆 P12D

Terbentuk aturan produksi baru :

P1 􀃆 a

P2 􀃆 AB

P3 􀃆 c

P4 􀃆 h

P5 􀃆 d

P6 􀃆 P7E

P7 􀃆 b

P8 􀃆 e

P9 􀃆 EC

P10 􀃆 f

P11 􀃆 DB

P12 􀃆 j

Hasil akhir dalam bentuk normal Chomsky :

S 􀃆 CD

B 􀃆 DD

D 􀃆 i

S 􀃆 P1P2

S 􀃆 P3P4

A 􀃆 P5P6

A 􀃆 P8P9

B 􀃆 P10P10

C 􀃆 AP11

C 􀃆 P1S

E 􀃆 P12D

P1 􀃆 a

P2 􀃆 AB

P3 􀃆 c

P4 􀃆 h

P5 􀃆 d

P6 􀃆 P7E

P7 􀃆 b

P8 􀃆 e

P9 􀃆 EC

P10 􀃆 f

P11 􀃆 DB

P12 􀃆 j

BENTUK NORMAL CHOMSKY

(CHOMSKY NORMAL FORM / CNF)

• Merupakan salah satu bentuk normal yang sangat berguna untuk CFG

• Bentuk normal Chomsky dibuat dari CFG yang telah mengalami penyederhanaan yaitu penghilangan produksi useless, unit, dan ε.

• Aturan produksi dalam bentuk normal Chomsky adalah ruas kanannya tepat berupa sebuah terminal atau 2 variabel, misal :

A 􀃆 BC

A 􀃆 b

B 􀃆 a

C 􀃆 BA | d

• Langkah-langkah pembentukan bentuk normal Chomsky :

Biarkan yang sudah CNF

• Contoh : Berikut ini CFG yang sudah mengalami penyederhanaan

S 􀃆 Ba | Ab

A 􀃆 Baa | As | a

B 􀃆 Abb | Bs | b

Aturan produksi yang sudah dalam bentuk normal Chomsky (CNF) :

A 􀃆 a

B 􀃆 b

Dilakukan penggantian aturan produksi yang belum bentuk normal Chomsky :

S 􀃆 Ba menjadi S 􀃆 P1A

S 􀃆 Ab menjadi S 􀃆 P2B

A 􀃆 Baa menjadi A 􀃆 P1AA menjadi A 􀃆 P1P3

A 􀃆 As menjadi A 􀃆 P2S

B 􀃆 Abb menjadi B 􀃆 P2BB menjadi B 􀃆 P2P4

B 􀃆 Bs menjadi B 􀃆 P1S

Sehingga terbentuk aturan produksi dan simbol variabel baru :

P1 􀃆 b

P2 􀃆 a

P3 􀃆 AA

P4 􀃆 BB

Hasil akhir aturan produksi dalam bentuk normal Chomsky :

A 􀃆 a

B 􀃆 b

S 􀃆 P1A

S 􀃆 P2B

A 􀃆 P1P3

A 􀃆 P2S

B 􀃆 P2 P4

B 􀃆 P1S

CFG yang sudah disederhanakan

Penggantian simbol terminal pada aturan produksi yang ruas kanan > 1

Buat variabel dan aturan produksi baru bila perlu

CNF

Penggantian aturan produksi yang simbol variabel > 2

P1 􀃆 b

P2 􀃆 a

P3 􀃆 AA

P4 􀃆 BB

• Contoh : Berikut ini CFG yang sudah mengalami penyederhanaan

S 􀃆 Ab | CA

A 􀃆 a | bc

B 􀃆 BC | Ab

C 􀃆 Ab | b

Aturan produksi yang sudah dalam bentuk normal Chomsky :

S 􀃆 CA

A 􀃆 a

B 􀃆 BC

C 􀃆 b

Penggantian aturan produksi yang belum dalam bentuk normal Chomsky :

S 􀃆 Ab menjadi S 􀃆 P1B

A 􀃆 bc menjadi S 􀃆 P2P3

B 􀃆 Ab menjadi B 􀃆 AP2

C 􀃆 Ab menjadi C 􀃆 P1B

Terbentuk aturan produksi dan simbol variabel baru :

P1 􀃆 a

P2 􀃆 b

P3 􀃆 c

Hasil akhir aturan produksi dalam bentuk normal Chomsky :

S 􀃆 CA

A 􀃆 a

B 􀃆 BC

C 􀃆 b

S 􀃆 P1B

S 􀃆 P2P3

B 􀃆 AP2

C 􀃆 P1B

P1 􀃆 a

P2 􀃆 b

P3 􀃆 c

• Contoh CFG :

S 􀃆 Aab | ch | CD

A 􀃆 dbE | Eec

B 􀃆 ff | DD

C 􀃆 ADB | As

D 􀃆 i

E 􀃆 jd

Aturan produksi yang sudah dalam bentuk normal Chomsky :

S 􀃆 CD

B 􀃆 DD

D 􀃆 i

Penggantian aturan produksi :

S 􀃆 Aab menjadi S 􀃆 P1P2

S 􀃆 ch menjadi S 􀃆 P3P4

A 􀃆 dbE menjadi A 􀃆 P5P6

A 􀃆 Eec menjadi A 􀃆 P8P9

B 􀃆 ff menjadi B 􀃆 P10P10

C 􀃆 ADB menjadi C 􀃆 AP11

C 􀃆 As menjadi C 􀃆 P1S

E 􀃆 Jd menjadi E 􀃆 P12D

Terbentuk aturan produksi baru :

P1 􀃆 a

P2 􀃆 AB

P3 􀃆 c

P4 􀃆 h

P5 􀃆 d

P6 􀃆 P7E

P7 􀃆 b

P8 􀃆 e

P9 􀃆 EC

P10 􀃆 f

P11 􀃆 DB

P12 􀃆 j

Hasil akhir dalam bentuk normal Chomsky :

S 􀃆 CD

B 􀃆 DD

D 􀃆 i

S 􀃆 P1P2

S 􀃆 P3P4

A 􀃆 P5P6

A 􀃆 P8P9

B 􀃆 P10P10

C 􀃆 AP11

C 􀃆 P1S

E 􀃆 P12D

P1 􀃆 a

P2 􀃆 AB

P3 􀃆 c

P4 􀃆 h

P5 􀃆 d

P6 􀃆 P7E

P7 􀃆 b

P8 􀃆 e

P9 􀃆 EC

P10 􀃆 f

P11 􀃆 DB

P12 􀃆 j

penyederhanaan CFG

PENYEDERHANAAN CFG

1. TUJUAN PENYEDERHANAAN

• Melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tidak perlu atau aturan produksi yang tidak berarti.

• Contoh :

S 􀃆 AB | a

A 􀃆 a

Kelemahan CFG diatas, aturan produksi S 􀃆 AB tidak berarti karena B tidak memiliki penurunan.

Untuk CFG berikut :

S 􀃆 A

A 􀃆 B

B 􀃆 C

C 􀃆 D

D 􀃆 a | A

Memiliki kelemahan terlalu panjang jalannya padahal berujung pada S 􀃆 a, produksi D 􀃆 A juga menyebabkan kerumitan.

• Suatu CFG dapat disederhanakan dengan melakukan :

1. Penghilangan produksi useless (tidak berguna)

2. Penghilangan produksi unit

3. Penghilangan produksi ε

2. PENGHILANGAN PRODUKSI USELESS

• Produksi useless didefinisikan sebagai :

- Produksi yang memuat simbol variabel yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya (disebut ‘menuju terminal’). Produksi ini tidak berguna karena bila diturunkan tidak akan pernah selesai masih ada simbol variabel yang tersisa.

- Produksi yang tidak akan pernah dicapai dengan penurunan apapun dari simbol awal sehingga produksi itu redundance (berlebih)

• Contoh terdapat CFG :

S 􀃆 aSa | Abd | Bde

A 􀃆 Ada

B 􀃆 BBB | a

Maka :

1. Simbol variabel A tidak memiliki penurunan yang menuju terminal, sehingga bisa dihilangkan

2. Konsekuensi no. (1), aturan produksi S 􀃆 Abd tidak memiliki penurunan maka CFG setelah disederhanakan menjadi :

S 􀃆 aSa | Bde

B 􀃆 BBB | a

• Contoh terdapat CFG :

S 􀃆 Aa | B

A 􀃆 ab | D

B 􀃆 b | E

C 􀃆 bb

E 􀃆 aEa

Maka :

1. Pada aturan produksi A 􀃆 D, simbol variabel D tidak memiliki penurunan

2. Pada aturan produksi C 􀃆 bb, bila dicoba melakukan penurunan dari simbol awal S tidak akan pernah mencapai C.

3. Simbol variabel E tidak memiliki aturan produksi yang menuju terminal

4. Konsekuensi no (3) aturan produksi B 􀃆 E, simbol variabel E tidak memiliki penurunan

Sehingga dari CFG diatas, produksi yang useless :

A 􀃆 D

C 􀃆 bb

E 􀃆 aEa

B 􀃆 E

Maka CFG setelah disederhanakan menjadi :

S 􀃆 Aa | B

A 􀃆 ab

B 􀃆 b

• Contoh CFG :

S 􀃆 aAb | Ceb

A 􀃆 Dbe | eeC

B 􀃆 ff

C 􀃆 ae

D 􀃆 h

Maka :

1. Pada aturan produksi S 􀃆 Ceb, A 􀃆 Dbe (E tidak memiliki penurunan)

2. Aturan produksi D 􀃆 h redundan

Sehingga :

S 􀃆 aAb

A 􀃆 eeC

B 􀃆 ff

C 􀃆 ae

Dari sisa CFG diatas B 􀃆 ff juga redundan, sehingga hasil penyederhanaan menjadi :

S 􀃆 aAb

A 􀃆 eeC

C 􀃆 ae

• Contoh CFG :

S 􀃆 Ab

A 􀃆 bcD | Dac

B 􀃆 e | Ab

C 􀃆 bCb | adF | ab

F 􀃆 Cfb

Maka :

1. Pada aturan produksi A 􀃆 bcD, variabel D tidak memiliki penurunan

2. Konsekuensi no (1), simbol variabel A tidak memiliki penurunan yang menuju terminal sehingga tersisa hanya A 􀃆 Dac

3. Konsekuensi no (2), B 􀃆 Ab tidak memiliki penurunan

4. Simbol variabel F tidak memiliki penurunan yang menuju terminal

5. Konsekuensi no (4), C 􀃆 adF tidak memiliki penurunan

Setelah disederhanakan menjadi :

S 􀃆 Ab

B 􀃆 e

• Contoh CFG :

S 􀃆 Abd

B 􀃆 Cd | Ab

D 􀃆 ef

A 􀃆 Ed

F 􀃆 dc

Maka :

1. Pada aturan produksi A 􀃆 Ed, E tidak memiliki penurunan

2. Pada aturan produksi F 􀃆 dc, redundan

Sehingga :

S 􀃆 Abd

B 􀃆 Cd | Ab

D 􀃆 ef

Dari sisa CFG diatas maka pada aturan produksi B 􀃆 Ab, A tidak mempunyai penurunan, sehingga aturan produksi setelah disederhanakan :

S 􀃆 Abd

B 􀃆 Cd

D 􀃆 ef

• Contoh CFG :

S 􀃆 Abc | ab

A􀃆 AAA | ε

Maka :

S 􀃆 Abc | ab

A􀃆 AAA | ε

Hasil tetap karena A 􀃆 ε diperhitungkan.

• Prinsipnya setiap kali melakukan penyederhanaan, periksa lagi aturan produksi yang tersisa, apakah semua produksi yang useless sudah dihilangkan.

2. PENGHILANGAN PRODUKSI UNIT

• Produksi unit adalah produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu simbol variabel, misalkan A 􀃆 B, C 􀃆 D

• Keberadaan produksi unit membuat tata bahasa memiliki kerumitan yang tidak perlu atau menambah panjang penurunan.

• Penyederhanaan ini dilakukan dengan melakukan penggantian aturan produksi unit

• Contoh CFG :

S 􀃆 Sb

S 􀃆 C

C 􀃆 D

C 􀃆 ef

D 􀃆 dd

Lakukan penggantian berturutan mulai dari aturan produksi yang oaling dekat menuju ke penurunan terminal.

C 􀃆 D menjadi C 􀃆 dd

S 􀃆 C menjadi S 􀃆 dd | ef

Sehingga aturan produksi setelah penyederhanaan :

S 􀃆 Sb

S 􀃆 dd | ef

C 􀃆 dd

C 􀃆 ef

D 􀃆 dd

• Contoh CFG

S 􀃆 A

S 􀃆 Aa

A 􀃆 B

B 􀃆 C

B 􀃆 b

C 􀃆 D

C 􀃆 ab

D 􀃆 b

Penggantian yang dilakukan :

C 􀃆 D menjadi C 􀃆 b

B 􀃆 C menjadi B 􀃆 b | ab karena B 􀃆 b sudah ada maka cukup tulis B 􀃆 ab

A 􀃆 B menjadi A 􀃆 ab | b

S 􀃆 A menjadi S 􀃆 ab | b

Sehingga aturan produksi setelah penyederhanaan :

S 􀃆 ab | b

S 􀃆 Aa

A 􀃆 ab | b

B 􀃆 ab

B 􀃆 b

C 􀃆 b

C 􀃆 ab

D 􀃆 b

• Contoh CFG

S 􀃆 Cba | D

A 􀃆 bbC

B 􀃆 Sc | ddd

C 􀃆 Ea | f | C

D 􀃆 E | SABC

E 􀃆 gh

Penggantian yang dilakukan :

D 􀃆 E menjadi D 􀃆 gh

C 􀃆 C dihapus

S 􀃆 D menjadi S 􀃆 gh | SABC

Sehingga aturan produksi setelah penyederhanaan :

S 􀃆 Cba | gh | SABC

A 􀃆 bbC

B 􀃆 Sc | ddd

C 􀃆 Ea | f

D 􀃆 gh | SABC

E 􀃆 gh

3. PENGHILANGAN PRODUKSI ε

• Produksi ε adalah produksi dalam bentuk α 􀃆 ε atau bisa dianggap sebagai produksi kosong (empty).

• Penghilangan ε dilakukan dengan penggantian produksi yang memuat variabel yang bisa menuju produksi ε atau disebut nullable.

• Contoh :

S 􀃆 bcAd

A 􀃆 ε

Pada kasus diatas A nullable, serta A 􀃆 ε satu-satunya produksi dari A, maka variabel A bisa ditiadakan . Hasil penyederhanaan CFG menjadi :

S 􀃆 bcd

Tetapi bila kasusnya :

S 􀃆 bcAd

A 􀃆 bd | ε

Pada kasus diatas A nullable tapi A 􀃆 ε bukan satu-satunya produksi dari A, maka hasil penyederhanaan :

S 􀃆 bcAd | bcd

A 􀃆 bd

• Contoh CFG :

S 􀃆 Ab | Cd

A 􀃆 d

C 􀃆 ε

Variabel yang nullable adalah variabel C. Karena penurunan C 􀃆 ε merupakan penurunan satu-satunya dari C, maka produksi C 􀃆 ε dihapus dan S 􀃆 Cd menjadi S 􀃆 d.

Hasil penyederhanaan CFG :

S 􀃆 Ab | d

A 􀃆 d

• Contoh CFG :

S 􀃆 Da | Bd

A 􀃆 bc

A 􀃆 ε

B 􀃆 C

Variabel yang nullable adalah variabel A.

A 􀃆 ε bukan penurunan satu-satunya dari A (terdapat A 􀃆 bc), maka

S 􀃆 Da menjadi S 􀃆 Da | d dan A 􀃆 ε dihapus.

Setelah penyederhanaan :

S 􀃆 Da | d | Bd

A 􀃆 bc

B 􀃆 c

• Contoh CFG :

S 􀃆 AaCD

A 􀃆 CD | AB

B 􀃆 b | ε

C 􀃆 d | ε

D 􀃆 ε

Variabel yang nullable adalah variabel B,C,D.

Dari A 􀃆 CD, D hanya memiliki penurunan D 􀃆 ε,maka D 􀃆 ε dihapus sehingga

S 􀃆 AaCD menjadi S 􀃆 AaC

A 􀃆 CD menjadi A 􀃆 C

Variabel B dan C memiliki penurunan ε meskipun bukan satu-satunya penurunan maka dilakukan penggantian :

A 􀃆 AB menjadi A 􀃆 AB | A | B

S 􀃆 AaC menjadi S 􀃆 AaC | Ac | Aa | a

B 􀃆 ε dan C 􀃆 ε dihapus

Setelah penyederhanaan :

S 􀃆 AaC | Ac | Aa | a

A 􀃆 C | AB | A | B

B 􀃆 b

C 􀃆 d

• Contoh CFG :

S 􀃆 AB

A 􀃆 abB | aCa | ε

B 􀃆 Ba | BB | ε

C 􀃆 ε

Variabel yang nullable adalah A,B,C.

Dari S 􀃆 AB, maka S juga nullable. Lakukan penggantian :

A 􀃆 aCa menjadi A 􀃆 aa

B 􀃆 Ba menjadi B 􀃆 Ba | b

B 􀃆 BB menjadi B 􀃆 BB | B

A 􀃆 abB menjadi A 􀃆 abB | ab

S 􀃆 AB menjadi S 􀃆 AB | A | B | ε

C 􀃆 ε, B 􀃆 ε, A 􀃆 ε dihapus

Perhatikan :

Untuk penggantian S 􀃆 AB, S 􀃆 ε tetap dipertahankan karena S merupakan simbol awal. Ini merupakan satu-satunya perkecualian produksi ε yang tidak dihapus yaitu produksi ε yang dihasilkan oleh simbol awal.

Hasil akhir penyedernaan :

S 􀃆 AB | A | B | ε

A 􀃆 abB | ab | aa

B 􀃆 Ba | b | BB | B

• Contoh CFG :

S 􀃆 aAb

A 􀃆 aAb | ε

Hasil penyederhanaan :

S 􀃆 aAb | ab

A 􀃆 aAb | ab

• Contoh CFG :

S 􀃆 ABaC

A 􀃆 BC

B 􀃆 b | ε

C 􀃆 D | ε

D 􀃆 d

Hasil penyederhanaan :

S 􀃆 ABaC | BaC | AaC | ABa | aC | Aa | Ba | a

A 􀃆 B | C | BC

B 􀃆 b

C 􀃆 D

D 􀃆 d

• Pada prakteknya ketiga penyederhanaan tersebut (penghilangan useless, unit, ε) dilakukan bersama pada suatu CFG yang nantinya menyiapkan CFG tersebut untuk diubah ke dalam bentuk normal Chomsky (dibahas bab selanjutnya).

• Hal yang memerlukan perhatian adalah penghilangan suatu tipe produksi bisa menghasilkan produksi yang lain, hal ini didasari kenyataan bahwa penghilangan suatu tipe produksi bisa menghasilkan produksi tipe yang lain, hal ini didasari kenyataan bahwa penghilangan produksi ε bisa menghasilkan produksi unit.

• Tapi perhatikan juga bahwa penghilangan produksi unit tidak menghasilkan produksi ε dan penghilangan produksi useless tidak menghasilkan produksi unit maupun produksi ε.

• Maka untuk menghapus semua produksi yang tidak diinginkan tersebut dengan melakukan urutan sebagai berikut :

1. Hilangkan produksi ε

2. Hilangkan produksi unit

3. Hilangkan produksi useless

CFG yang sudah disederhanakan

Penghilangan

produksi useless

Penghilangan

produksi unit

Penghilangan

produksi ε

CFG

• Hasil yang diperoleh adalah tata bahasa yang sudah bebas dari ketiga jenis produksi tersebut.

Contoh :

S 􀃆 AA | C | bd

A 􀃆 Bb | ε

B 􀃆 AB | d

C 􀃆 de

Lakukan penghilangan produksi ε, sehingga aturan produksi menjadi :

S 􀃆 A | AA | C | bd

A 􀃆 Bb

B 􀃆 B | AB | d

C 􀃆 de

Penghilangan produksi ε berpotensi untuk menghasilkan produksi unit baru yang sebelumnya tidak ada. Selanjutnya lakukan penghilangan produksi unit menjadi :

S 􀃆 Bb | AA | de | bd

A 􀃆 Bb

B 􀃆 AB | d

C 􀃆 de

Penghilangan produksi unit bisa menghasilkan produksi useless sehingga lakukan penghilangan produksi useless :

S 􀃆 Bb | AA | de | bd

A 􀃆 Bb

B 􀃆 AB | d

Hasil akhir aturan produksi diatas tidak lagi memiliki produksi ε, produksi unit, produksi useless.

PENYEDERHANAAN CFG

1. TUJUAN PENYEDERHANAAN

• Melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tidak perlu atau aturan produksi yang tidak berarti.

• Contoh :

S 􀃆 AB | a

A 􀃆 a

Kelemahan CFG diatas, aturan produksi S 􀃆 AB tidak berarti karena B tidak memiliki penurunan.

Untuk CFG berikut :

S 􀃆 A

A 􀃆 B

B 􀃆 C

C 􀃆 D

D 􀃆 a | A

Memiliki kelemahan terlalu panjang jalannya padahal berujung pada S 􀃆 a, produksi D 􀃆 A juga menyebabkan kerumitan.

• Suatu CFG dapat disederhanakan dengan melakukan :

1. Penghilangan produksi useless (tidak berguna)

2. Penghilangan produksi unit

3. Penghilangan produksi ε

2. PENGHILANGAN PRODUKSI USELESS

• Produksi useless didefinisikan sebagai :

- Produksi yang tidak akan pernah dicapai dengan penurunan apapun dari simbol awal sehingga produksi itu redundance (berlebih)

• Contoh terdapat CFG :

S 􀃆 aSa | Abd | Bde

A 􀃆 Ada

B 􀃆 BBB | a

Maka :

1. Simbol variabel A tidak memiliki penurunan yang menuju terminal, sehingga bisa dihilangkan

2. Konsekuensi no. (1), aturan produksi S 􀃆 Abd tidak memiliki penurunan maka CFG setelah disederhanakan menjadi :

S 􀃆 aSa | Bde

B 􀃆 BBB | a

• Contoh terdapat CFG :

S 􀃆 Aa | B

A 􀃆 ab | D

B 􀃆 b | E

C 􀃆 bb

E 􀃆 aEa

Maka :

1. Pada aturan produksi A 􀃆 D, simbol variabel D tidak memiliki penurunan

2. Pada aturan produksi C 􀃆 bb, bila dicoba melakukan penurunan dari simbol awal S tidak akan pernah mencapai C.

3. Simbol variabel E tidak memiliki aturan produksi yang menuju terminal

4. Konsekuensi no (3) aturan produksi B 􀃆 E, simbol variabel E tidak memiliki penurunan

Sehingga dari CFG diatas, produksi yang useless :

A 􀃆 D

C 􀃆 bb

E 􀃆 aEa

B 􀃆 E

Maka CFG setelah disederhanakan menjadi :

S 􀃆 Aa | B

A 􀃆 ab

B 􀃆 b

• Contoh CFG :

S 􀃆 aAb | Ceb

A 􀃆 Dbe | eeC

B 􀃆 ff

C 􀃆 ae

D 􀃆 h

Maka :

1. Pada aturan produksi S 􀃆 Ceb, A 􀃆 Dbe (E tidak memiliki penurunan)

2. Aturan produksi D 􀃆 h redundan

Sehingga :

S 􀃆 aAb

A 􀃆 eeC

B 􀃆 ff

C 􀃆 ae

Dari sisa CFG diatas B 􀃆 ff juga redundan, sehingga hasil penyederhanaan menjadi :

S 􀃆 aAb

A 􀃆 eeC

C 􀃆 ae

• Contoh CFG :

S 􀃆 Ab

A 􀃆 bcD | Dac

B 􀃆 e | Ab

C 􀃆 bCb | adF | ab

F 􀃆 Cfb

Maka :

1. Pada aturan produksi A 􀃆 bcD, variabel D tidak memiliki penurunan

2. Konsekuensi no (1), simbol variabel A tidak memiliki penurunan yang menuju terminal sehingga tersisa hanya A 􀃆 Dac

3. Konsekuensi no (2), B 􀃆 Ab tidak memiliki penurunan

4. Simbol variabel F tidak memiliki penurunan yang menuju terminal

5. Konsekuensi no (4), C 􀃆 adF tidak memiliki penurunan

Setelah disederhanakan menjadi :

S 􀃆 Ab

B 􀃆 e

• Contoh CFG :

S 􀃆 Abd

B 􀃆 Cd | Ab

D 􀃆 ef

A 􀃆 Ed

F 􀃆 dc

Maka :

1. Pada aturan produksi A 􀃆 Ed, E tidak memiliki penurunan

2. Pada aturan produksi F 􀃆 dc, redundan

Sehingga :

S 􀃆 Abd

B 􀃆 Cd | Ab

D 􀃆 ef

Dari sisa CFG diatas maka pada aturan produksi B 􀃆 Ab, A tidak mempunyai penurunan, sehingga aturan produksi setelah disederhanakan :

S 􀃆 Abd

B 􀃆 Cd

D 􀃆 ef

• Contoh CFG :

S 􀃆 Abc | ab

A􀃆 AAA | ε

Maka :

S 􀃆 Abc | ab

A􀃆 AAA | ε

Hasil tetap karena A 􀃆 ε diperhitungkan.

• Prinsipnya setiap kali melakukan penyederhanaan, periksa lagi aturan produksi yang tersisa, apakah semua produksi yang useless sudah dihilangkan.

2. PENGHILANGAN PRODUKSI UNIT

• Produksi unit adalah produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu simbol variabel, misalkan A 􀃆 B, C 􀃆 D

• Keberadaan produksi unit membuat tata bahasa memiliki kerumitan yang tidak perlu atau menambah panjang penurunan.

• Penyederhanaan ini dilakukan dengan melakukan penggantian aturan produksi unit

• Contoh CFG :

S 􀃆 Sb

S 􀃆 C

C 􀃆 D

C 􀃆 ef

D 􀃆 dd

Lakukan penggantian berturutan mulai dari aturan produksi yang oaling dekat menuju ke penurunan terminal.

C 􀃆 D menjadi C 􀃆 dd

S 􀃆 C menjadi S 􀃆 dd | ef

Sehingga aturan produksi setelah penyederhanaan :

S 􀃆 Sb

S 􀃆 dd | ef

C 􀃆 dd

C 􀃆 ef

D 􀃆 dd

• Contoh CFG

S 􀃆 A

S 􀃆 Aa

A 􀃆 B

B 􀃆 C

B 􀃆 b

C 􀃆 D

C 􀃆 ab

D 􀃆 b

Penggantian yang dilakukan :

C 􀃆 D menjadi C 􀃆 b

B 􀃆 C menjadi B 􀃆 b | ab karena B 􀃆 b sudah ada maka cukup tulis B 􀃆 ab

A 􀃆 B menjadi A 􀃆 ab | b

S 􀃆 A menjadi S 􀃆 ab | b

Sehingga aturan produksi setelah penyederhanaan :

S 􀃆 ab | b

S 􀃆 Aa

A 􀃆 ab | b

B 􀃆 ab

B 􀃆 b

C 􀃆 b

C 􀃆 ab

D 􀃆 b

• Contoh CFG

S 􀃆 Cba | D

A 􀃆 bbC

B 􀃆 Sc | ddd

C 􀃆 Ea | f | C

D 􀃆 E | SABC

E 􀃆 gh

Penggantian yang dilakukan :

D 􀃆 E menjadi D 􀃆 gh

C 􀃆 C dihapus

S 􀃆 D menjadi S 􀃆 gh | SABC

Sehingga aturan produksi setelah penyederhanaan :

S 􀃆 Cba | gh | SABC

A 􀃆 bbC

B 􀃆 Sc | ddd

C 􀃆 Ea | f

D 􀃆 gh | SABC

E 􀃆 gh

3. PENGHILANGAN PRODUKSI ε

• Produksi ε adalah produksi dalam bentuk α 􀃆 ε atau bisa dianggap sebagai produksi kosong (empty).

• Penghilangan ε dilakukan dengan penggantian produksi yang memuat variabel yang bisa menuju produksi ε atau disebut nullable.

• Contoh :

S 􀃆 bcAd

A 􀃆 ε

Pada kasus diatas A nullable, serta A 􀃆 ε satu-satunya produksi dari A, maka variabel A bisa ditiadakan . Hasil penyederhanaan CFG menjadi :

S 􀃆 bcd

Tetapi bila kasusnya :

S 􀃆 bcAd

A 􀃆 bd | ε

Pada kasus diatas A nullable tapi A 􀃆 ε bukan satu-satunya produksi dari A, maka hasil penyederhanaan :

S 􀃆 bcAd | bcd

A 􀃆 bd

• Contoh CFG :

S 􀃆 Ab | Cd

A 􀃆 d

C 􀃆 ε

Variabel yang nullable adalah variabel C. Karena penurunan C 􀃆 ε merupakan penurunan satu-satunya dari C, maka produksi C 􀃆 ε dihapus dan S 􀃆 Cd menjadi S 􀃆 d.

Hasil penyederhanaan CFG :

S 􀃆 Ab | d

A 􀃆 d

• Contoh CFG :

S 􀃆 Da | Bd

A 􀃆 bc

A 􀃆 ε

B 􀃆 C

Variabel yang nullable adalah variabel A.

A 􀃆 ε bukan penurunan satu-satunya dari A (terdapat A 􀃆 bc), maka

S 􀃆 Da menjadi S 􀃆 Da | d dan A 􀃆 ε dihapus.

Setelah penyederhanaan :

S 􀃆 Da | d | Bd

A 􀃆 bc

B 􀃆 c

• Contoh CFG :

S 􀃆 AaCD

A 􀃆 CD | AB

B 􀃆 b | ε

C 􀃆 d | ε

D 􀃆 ε

Variabel yang nullable adalah variabel B,C,D.

Dari A 􀃆 CD, D hanya memiliki penurunan D 􀃆 ε,maka D 􀃆 ε dihapus sehingga

S 􀃆 AaCD menjadi S 􀃆 AaC

A 􀃆 CD menjadi A 􀃆 C

Variabel B dan C memiliki penurunan ε meskipun bukan satu-satunya penurunan maka dilakukan penggantian :

A 􀃆 AB menjadi A 􀃆 AB | A | B

S 􀃆 AaC menjadi S 􀃆 AaC | Ac | Aa | a

B 􀃆 ε dan C 􀃆 ε dihapus

Setelah penyederhanaan :

S 􀃆 AaC | Ac | Aa | a

A 􀃆 C | AB | A | B

B 􀃆 b

C 􀃆 d

• Contoh CFG :

S 􀃆 AB

A 􀃆 abB | aCa | ε

B 􀃆 Ba | BB | ε

C 􀃆 ε

Variabel yang nullable adalah A,B,C.

Dari S 􀃆 AB, maka S juga nullable. Lakukan penggantian :

A 􀃆 aCa menjadi A 􀃆 aa

B 􀃆 Ba menjadi B 􀃆 Ba | b

B 􀃆 BB menjadi B 􀃆 BB | B

A 􀃆 abB menjadi A 􀃆 abB | ab

S 􀃆 AB menjadi S 􀃆 AB | A | B | ε

C 􀃆 ε, B 􀃆 ε, A 􀃆 ε dihapus

Perhatikan :

Hasil akhir penyedernaan :

S 􀃆 AB | A | B | ε

A 􀃆 abB | ab | aa

B 􀃆 Ba | b | BB | B

• Contoh CFG :

S 􀃆 aAb

A 􀃆 aAb | ε

Hasil penyederhanaan :

S 􀃆 aAb | ab

A 􀃆 aAb | ab

• Contoh CFG :

S 􀃆 ABaC

A 􀃆 BC

B 􀃆 b | ε

C 􀃆 D | ε

D 􀃆 d

Hasil penyederhanaan :

S 􀃆 ABaC | BaC | AaC | ABa | aC | Aa | Ba | a

A 􀃆 B | C | BC

B 􀃆 b

C 􀃆 D

D 􀃆 d

• Tapi perhatikan juga bahwa penghilangan produksi unit tidak menghasilkan produksi ε dan penghilangan produksi useless tidak menghasilkan produksi unit maupun produksi ε.

• Maka untuk menghapus semua produksi yang tidak diinginkan tersebut dengan melakukan urutan sebagai berikut :

1. Hilangkan produksi ε

2. Hilangkan produksi unit

3. Hilangkan produksi useless

CFG yang sudah disederhanakan

Penghilangan

produksi useless

Penghilangan

produksi unit

Penghilangan

produksi ε

CFG

• Hasil yang diperoleh adalah tata bahasa yang sudah bebas dari ketiga jenis produksi tersebut.

Contoh :

S 􀃆 AA | C | bd

A 􀃆 Bb | ε

B 􀃆 AB | d

C 􀃆 de

Lakukan penghilangan produksi ε, sehingga aturan produksi menjadi :

S 􀃆 A | AA | C | bd

A 􀃆 Bb

B 􀃆 B | AB | d

C 􀃆 de

Penghilangan produksi ε berpotensi untuk menghasilkan produksi unit baru yang sebelumnya tidak ada. Selanjutnya lakukan penghilangan produksi unit menjadi :

S 􀃆 Bb | AA | de | bd

A 􀃆 Bb

B 􀃆 AB | d

C 􀃆 de

Penghilangan produksi unit bisa menghasilkan produksi useless sehingga lakukan penghilangan produksi useless :

S 􀃆 Bb | AA | de | bd

A 􀃆 Bb

B 􀃆 AB | d

Hasil akhir aturan produksi diatas tidak lagi memiliki produksi ε, produksi unit, produksi useless.

pohon pnurunan

POHON PENURUNAN

1. CONTEXT FREE GRAMMAR (CFG)

• Pada tata bahasa bebas konteks / Context Free Grammar (CFG) tidak terdapat pembatasan hasil produksinya. Beda halnya dengan tata bahasa reguler yang ada pembatasan pada ruas kanan atau hasil produksinya.

• Contoh aturan produksi yang termasuk tata bahasa reguler :

S 􀃆 abA | baB

A 􀃆 Bs

B 􀃆 As

Bagian yang belum terturunkan selalu terjadi pada ujung.

• Contoh aturan produksi yang termasuk CFG :

B 􀃆 CdeFg

C 􀃆 BcDe

Bagian yang belum terturunkan bisa terjadi dimana saja.

• CFG merupakan suatu cara yang menunjukkan bagaimana menghasilkan untai-untai dalam sebuah bahasa

• CFG menjadi dasar dalam pembentukan suatu parser (proses analisis sintaksis) dimana bagian sintaks dalam suatu kompilator kebanyakan didefinisikan dalam CFG

2. PARSING

• Pohon penurunan (derivation tree / parse tree) berguna untuk menggambarkan bagaimana memperoleh suatu string (untai) dengan cara menurunkan simbol-simbol variabel menjadi simbol-simbol terminal

• Setiap simbol variabel akan diturunkan menjadi terminal, sampai tidak ada yang belum tergantikan.

• Misal terdapat CFG dengan aturan produksi (dengan simbol awal S) :

S 􀃆 AB

A 􀃆 Aa | a

B 􀃆 Bb | b

Akan digambarkan pohon penurunan untuk memperoleh untai ‘aabbb’.

Pada pohon tersebut simbol awal S akan menjadi akar (root).

Setiap kali penurunan dipilih aturan produksi yang menuju ke solusi.

Simbol-simbol variabel akan menjadi simpul-simpul yang mempunyai anak.

Simpul-simpul yang tidak mempunyai anak akan menjadi simbol terminal, seperti gambar berikut :

• Proses penurunan / parsing dapat dilakukan dengan 2 cara :

- Penurunan terkiri (leftmost derivation)

Simbol variabel terkiri yang diperluas terlebih dulu

- Penurunan terkanan (rightmost derivation)

Simbol variabel terkanan yang diperluas terlebih dulu

• Contoh :

Diberikan CFG : (‘􀃆’ dibaca ‘menurunkan’)

S 􀃆 Aas | a

A 􀃆 SbA | ba

Untuk memperoleh untai ‘aabbaa’ dari CFG :

- Penurunan terkiri (leftmost derivation)

S 􀃆 Aas 􀃆 aSbAS 􀃆 aabAS 􀃆 aabbaS 􀃆 aabbaa

- Penurunan terkanan (rightmost derivation)

Simbol variabel terkanan yang diperluas terlebih dulu

S 􀃆 Aas 􀃆 aAa 􀃆 aSbAa 􀃆 aSbbaa 􀃆 aabbaa

Proses penurunannya berbeda tetapi akan diperoleh pohon yang sama :

• Biasanya persoalan yang berkaitan dengan pohon penurunan adalah mencari penurunan yang hasilnya menuju kepada suatu untai yang ditentukan yang dalam hal ini perlu dilakukan percobaan pemilihan aturan produksi yang bisa menuju ke solusi

• Contoh : CFG

S 􀃆 Ab | Ba

A 􀃆 a | As | Baa

B 􀃆 b | Bs | Abb

Berikut pohon penurunan untuk memperoleh string ‘aaabbabbba’

3. AMBIGUITAS (Kedwiartian)

• Ambiguitas terjadi bila terdapat lebih dari satu pohon penurunan yang berbeda untuk memperoleh suatu untai

• Misal terdapat CFG :

S 􀃆 A | B

A 􀃆 a

B 􀃆 a

Untuk memperoleh untai ‘a’ bisa dengan 2 penurunan, yaitu :

- S 􀃆 A 􀃆 a

- S 􀃆 B 􀃆 a

• Misal : CFG

S 􀃆 SbS | ScS |a

Untuk memperoleh untai ‘abaca’ bisa dengan 2 cara, yaitu :

- S 􀃆 SbS 􀃆 SbScS 􀃆 SbSca 􀃆 Sbaca 􀃆 abaca

- S 􀃆 ScS 􀃆 SbScS 􀃆 abScS 􀃆 abacS 􀃆 abaca

Senin, 07 Juni 2010

fuzzzy

LOGIKA FUZZY 7
7.1 PENDAHULUAN
Orang yang belum pernah mengenal logika fuzzy pasti akan mengira bahwa logika fuzzy adalah sesuatu yang amat rumit dan tidak menyenangkan. Namun, sekali seseorang mulai mengenalnya, ia pasti akan sangat tertarik dan akan menjadi pendatang baru untuk ikut serta mempelajari logika fuzzy. Logika fuzzy dikatakan sebagai logika baru yang lama, sebab ilmu tentang logika fuzzy modern dan metodis baru ditemukan beberapa tahun yang lalu, padahal sebenarnya konsep tentang logika fuzzy itu sendiri sudah ada pada diri kita sejak lama.
Logika fuzzy adalah suatu cara yang tepat untuk memetakan suatu ruang input ke dalam suatu ruang output. Sebagai contoh:
1. Manajer pergudangan mengatakan pada manajer produksi seberapa banyak persediaan barang pada akhir minggu ini, kemudian manajer produksi akan menetapkan jumlah barang yang harus diproduksi esok hari.
2. Pelayan restoran memberikan pelayanan terhadap tamu, kemudian tamu akan memberikan tip yang sesuai atas baik tidaknya pelayan yang diberikan;
3. Anda mengatakan pada saya seberapa sejuk ruangan yang anda inginkan, saya akan mengatur putaran kipas yang ada pada ruangan ini.
4. Penumpang taksi berkata pada sopir taksi seberapa cepat laju kendaraan yang diinginkan, sopir taksi akan mengatur pijakan gas taksinya.
Salah satu contoh pemetaan suatu input-output dalam bentuk grafis seperti terlihat pada Gambar 7.1. KOTAK HITAM persediaan barang akhir minggu produksi barang esok hari Ruang Input (semua total persediaan barang yang mungkin) Ruang Output (semua jumlah produksi barang yang mungkin) Pemetaan input-output pada masalah produksi “Diberikan data persediaan barang, berapa jumlah barang yang harus diproduksi?
Gambar 7.1 Contoh pemetaan input-output.
Antara input dan output terdapat satu kotak hitam yang harus memetakan input ke output yang sesuai.
109
7.2 ALASAN DIGUNAKANNYA LOGIKA FUZZY
Ada beberapa alasan mengapa orang menggunakan logika fuzzy, antara lain:
1. Konsep logika fuzzy mudah dimengerti. Konsep matematis yang mendasari penalaran fuzzy sangat sederhana dan mudah dimengerti.
2. Logika fuzzy sangat fleksibel.
3. Logika fuzzy memiliki toleransi terhadap data-data yang tidak tepat.
4. Logika fuzzy mampu memodelkan fungsi-fungsi nonlinear yang sangat kompleks.
5. Logika fuzzy dapat membangun dan mengaplikasikan pengalaman-pengalaman para pakar secara langsung tanpa harus melalui proses pelatihan.
6. Logika fuzzy dapat bekerjasama dengan teknik-teknik kendali secara konvensional.
7. Logika fuzzy didasarkan pada bahasa alami.
7.3 APLIKASI
Beberapa aplikasi logika fuzzy, antara lain:
1. Pada tahun 1990 pertama kali dibuat mesin cuci dengan logika fuzzy di Jepang (Matsushita Electric Industrial Company). Sistem fuzzy digunakan untuk menentukan putaran yang tepat secara otomatis berdasarkan jenis dan banyaknya kotoran serta jumlah yang akan dicuci. Input yang digunakan adalah: seberapa kotor, jenis kotoran, dan banyaknya yang dicuci. Mesin ini menggunakan sensor optik , mengeluarkan cahaya ke air dan mengukur bagaimana cahaya tersebut sampai ke ujung lainnya. Makin kotor, maka sinar yang sampai makin redup. Disamping itu, sistem juga dapat menentukan jenis kotoran (daki atau minyak).
2. Transmisi otomatis pada mobil. Mobil Nissan telah menggunakan sistem fuzzy pada transmisi otomatis, dan mampu menghemat bensin 12 – 17%.
3. Kereta bawah tanah Sendai mengontrol pemberhentian otomatis pada area tertentu.
4. Ilmu kedokteran dan biologi, seperti sistem diagnosis yang didasarkan pada logika fuzzy, penelitian kanker, manipulasi peralatan prostetik yang didasarkan pada logika fuzzy, dll.
5. Manajemen dan pengambilan keputusan, seperti manajemen basisdata yang didasarkan pada logika fuzzy, tata letak pabrik yang didasarkan pada logika fuzzy, sistem pembuat keputusan di militer yang didasarkan pada logika fuzzy, pembuatan games yang didasarkan pada logika fuzzy, dll.
6. Ekonomi, seperti pemodelan fuzzy pada sistem pemasaran yang kompleks, dll.
7. Klasifikasi dan pencocokan pola.
8. Psikologi, seperti logika fuzzy untuk menganalisis kelakuan masyarakat, pencegahan dan investigasi kriminal, dll.
9. Ilmu-ilmu sosial, terutam untuk pemodelan informasi yang tidak pasti.
10. Ilmu lingkungan, seperti kendali kualitas air, prediksi cuaca, dll. 110
11. Teknik, seperti perancangan jaringan komputer, prediksi adanya gempa bumi, dll.
12. Riset operasi, seperti penjadwalan dan pemodelan, pengalokasian, dll.
13. Peningkatan kepercayaan, seperti kegagalan diagnosis, inspeksi dan monitoring produksi.
7.4 HIMPUNAN FUZZY
Pada himpunan tegas (crisp), nilai keanggotaan suatu item x dalam suatu himpunan A, yang sering ditulis dengan μA[x], memiliki 2 kemungkinan, yaitu:
􀁄 satu (1), yang berarti bahwa suatu item menjadi anggota dalam suatu himpunan, atau
􀁄 nol (0), yang berarti bahwa suatu item tidak menjadi anggota dalam suatu himpunan.
Contoh 7.1:
Jika diketahui:
S = {1, 2, 3, 4, 5, 6} adalah semesta pembicaraan.
A = {1, 2, 3}
B = {3, 4, 5}
bisa dikatakan bahwa:
􀀡 Nilai keanggotaan 2 pada himpunan A, μA[2]=1, karena 2∈A.
􀀡 Nilai keanggotaan 3 pada himpunan A, μA[3]=1, karena 3∈A.
􀀡 Nilai keanggotaan 4 pada himpunan A, μA[4]=0, karena 4∉A.
􀀡 Nilai keanggotaan 2 pada himpunan B, μB[2]=0, karena 2∉B.
􀀡 Nilai keanggotaan 3 pada himpunan B, μB[3]=1, karena 3∈B.
Contoh 7.2:
Misalkan variabel umur dibagi menjadi 3 kategori, yaitu:
MUDA umur < 35 tahun
PAROBAYA 35 ≤ umur ≤ 55 tahun
TUA umur > 55 tahun
Nilai keanggotaan secara grafis, himpunan MUDA, PAROBAYA dan TUA ini dapat dilihat pada Gambar 7.2. 55 35 0 1 μ[x] umur (th) PAROBAYA 35 0 0 1 μ[x] umur (th) MUDA (a) 55 01 μ[x]umur (th) TUA (b) (c)
Gambar 7.2 Himpunan: MUDA, PAROBAYA, dan TUA.
Pada Gambar 7.2, dapat dilihat bahwa:
􀂙 apabila seseorang berusia 34 tahun, maka ia dikatakan MUDA (μMUDA[34] =1);
􀂙 apabila seseorang berusia 35 tahun, maka ia dikatakan TIDAK MUDA (μMUDA[35]=0);
111
􀂙 apabila seseorang berusia 35 tahun kurang 1 hari, maka ia dikatakan TIDAK MUDA (μMUDA[35 th -1hr]=0);
􀂙 apabila seseorang berusia 35 tahun, maka ia dikatakan PAROBAYA (μPAROBAYA[35]=1);
􀂙 apabila seseorang berusia 34 tahun, maka ia dikatakan TIDAK PAROBAYA (μPAROBAYA[34]=0);
􀂙 apabila seseorang berusia 35 tahun, maka ia dikatakan PAROBAYA (μPAROBAYA[35]=1);
􀂙 apabila seseorang berusia 35 tahun kurang 1 hari, maka ia dikatakan TIDAK PAROBAYA (μPAROBAYA[35 th - 1 hr]=0);
Dari sini bisa dikatakan bahwa pemakaian himpunan crisp untuk menyatakan umur sangat tidak adil, adanya perubahan kecil saja pada suatu nilai mengakibatkan perbedaan kategori yang cukup signifikan.
Himpunan fuzzy digunakan untuk mengantisipasi hal tersebut. Seseorang dapat masuk dalam 2 himpunan yang berbeda, MUDA dan PAROBAYA, PAROBAYA dan TUA, dsb. Seberapa besar eksistensinya dalam himpunan tersebut dapat dilihat pada nilai keanggotaannya. Gambar 7.3 menunjukkan himpunan fuzzy untuk variabel umur. 10 25 45 65 55 35 Umur (th) μ[x] MUDA PAROBAYA TUA 40 50 0,5
0,25
Gambar 7.3 Himpunan fuzzy untuk variabel Umur.
Pada Gambar 7.3, dapat dilihat bahwa:
􀂙 Seseorang yang berumur 40 tahun, termasuk dalam himpunan MUDA dengan μMUDA[40]=0,25; namun dia juga termasuk dalam himpunan PAROBAYA dengan μPABOBAYA[40]=0,5.
􀂙 Seseorang yang berumur 50 tahun, termasuk dalam himpunan MUDA dengan μTUA[50]=0,25; namun dia juga termasuk dalam himpunan PAROBAYA dengan μPABOBAYA[50]=0,5.
Kalau pada himpunan crisp, nilai keanggotaan hanya ada 2 kemungkinan, yaitu 0 atau 1, pada himpunan fuzzy nilai keanggotaan terletak pada rentang 0 sampai 1. Apabila x memiliki nilai keanggotaan fuzzy μA[x]=0 berarti x tidak menjadi anggota himpunan A, demikian pula apabila x memiliki nilai keanggotaan fuzzy μA[x]=1 berarti x menjadi anggota penuh pada himpunan A.
Terkadang kemiripan antara keanggotaan fuzzy dengan probabilitas menimbulkan kerancuan. Keduanya memiliki nilai pada interval [0,1], namun interpretasi nilainya sangat berbeda antara kedua kasus tersebut. Keanggotaan fuzzy memberikan suatu ukuran terhadap pendapat atau keputusan, sedangkan probabilitas mengindikasikan proporsi terhadap keseringan suatu hasil bernilai benar dalam jangka panjang. Misalnya, jika nilai keanggotaan suatu himpunan fuzzy MUDA adalah 0,9; maka tidak perlu dipermasalahkan berapa seringnya nilai itu diulang secara individual untuk mengharapkan suatu hasil yang hampir pasti 112
muda. Di lain pihak, nilai probabilitas 0,9 muda berarti 10% dari himpunan tersebut diharapkan tidak muda.
Himpunan fuzzy memiliki 2 atribut, yaitu:
a. Linguistik, yaitu penamaan suatu grup yang mewakili suatu keadaan atau kondisi tertentu dengan menggunakan bahasa alami, seperti: MUDA, PAROBAYA, TUA.
b. Numeris, yaitu suatu nilai (angka) yang menunjukkan ukuran dari suatu variabel seperti: 40, 25, 50, dsb.
Ada beberapa hal yang perlu diketahui dalam memahami sistem fuzzy, yaitu:
a. Variabel fuzzy
Variabel fuzzy merupakan variabel yang hendak dibahas dalam suatu sistem fuzzy. Contoh: umur, temperatur, permintaan, dsb.
b. Himpunan fuzzy
Himpunan fuzzy merupakan suatu grup yang mewakili suatu kondisi atau keadaan tertentu dalam suatu variabel fuzzy.
Contoh:
􀂃 Variabel umur, terbagi menjadi 3 himpunan fuzzy, yaitu: MUDA, PAROBAYA, dan TUA. (Gambar 7.3)
􀂃 Variabel temperatur, terbagi menjadi 5 himpunan fuzzy, yaitu: DINGIN, SEJUK, NORMAL, HANGAT, dan PANAS. (Gambar 7.4) 1 0 15 25 35 30 20 Temperatur (oC)) μ[x] DINGIN SEJUK NORMAL HANGAT PANAS 0 40
Gambar 7.4 Himpunan fuzzy pada variabel temperatur.
c. Semesta Pembicaraan
Semesta pembicaraan adalah keseluruhan nilai yang diperbolehkan untuk dioperasikan dalam suatu variabel fuzzy. Semesta pembicaraan merupakan himpunan bilangan real yang senantiasa naik (bertambah) secara monoton dari kiri ke kanan. Nilai semesta pembicaraan dapat berupa bilangan positif maupun negatif. Adakalanya nilai semesta pembicaraan ini tidak dibatasi batas atasnya.
Contoh:
􀂃 Semesta pembicaraan untuk variabel umur: [0 +∞)
􀂃 Semesta pembicaraan untuk variabel temperatur: [0 40]
113
d. Domain
Domain himpunan fuzzy adalah keseluruhan nilai yang diijinkan dalam semesta pembicaraan dan boleh dioperasikan dalam suatu himpunan fuzzy. Seperti halnya semesta pembicaraan, domain merupakan himpunan bilangan real yang senantiasa naik (bertambah) secara monoton dari kiri ke kanan. Nilai domain dapat berupa bilangan positif maupun negatif.
Contoh domain himpunan fuzzy:
􀂃 MUDA = [0 45]
􀂃 PABOBAYA = [35 55]
􀂃 TUA = [45 +∞)
􀂃 DINGIN = [0 20]
􀂃 SEJUK = [15 25]
􀂃 NORMAL = [20 30]
􀂃 HANGAT = [25 35]
􀂃 PANAS = [30 40]
7.5 FUNGSI KEANGGOTAAN
Fungsi Keanggotaan (membership function) adalah suatu kurva yang menunjukkan pemetaan titik-titik input data ke dalam nilai keanggotaannya (sering juga disebut dengan derajat keanggotaan) yang memiliki interval antara 0 sampai 1. Salah satu cara yang dapat digunakan untuk mendapatkan nilai keanggotaan adalah dengan melalui pendekatan fungsi. Ada beberapa fungsi yang bisa digunakan.
a. Representasi Linear
Pada representasi linear, pemetaan input ke derajat keanggotannya digambarkan sebagai suatu garis lurus. Bentuk ini paling sederhana dan menjadi pilihan yang baik untuk mendekati suatu konsep yang kurang jelas.
Ada 2 keadaan himpunan fuzzy yang linear. Pertama, kenaikan himpunan dimulai pada nilai domain yang memiliki derajat keanggotaan nol [0] bergerak ke kanan menuju ke nilai domain yang memiliki derajat keanggotaan lebih tinggi (Gambar 7.5)
Gambar 7.5 Representasi Linear Naik. derajat keanggotaan μ[x] 1 0 domaina b
Fungsi Keanggotaan:
⎪⎩⎪⎨⎧≥≤≤−−≤=bxbxaabaxaxx;1);/()(;0][μ (7.1)
114
Contoh 7.3:
Fungsi keanggotaan untuk himpunan PANAS pada variabel temperatur ruangan seperti terlihat pada Gambar 7.6.
μPANAS[32] = (32-25)/(35-25)
= 7/10 = 0,7
Gambar 7.6 Himpunan fuzzy: PANAS. derajat keanggotaan μ[x] 1 0 Temperatur(oC)25 35 PANAS 32 0,7
Kedua, merupakan kebalikan yang pertama. Garis lurus dimulai dari nilai domain dengan derajat keanggotaan tertinggi pada sisi kiri, kemudian bergerak menurun ke nilai domain yang memiliki derajat keanggotaan lebih rendah (Gambar 7.7). derajat keanggotaan μ[x] 10domaina b
Gambar 7.7 Representasi Linear Turun.
Fungsi Keanggotaan:
⎩⎨⎧≥≤≤−−=bxbxaabxbx;0);/()(][μ (7.2)
Contoh 7.4:
Fungsi keanggotaan untuk himpunan DINGIN pada variabel temperatur ruangan seperti terlihat pada Gambar 7.8.
μDINGIN[20] = (30-20)/(30-15)
= 10/15 = 0,667
115
derajat keanggotaan μ[x] 1 0 Temperatur (oC) 15 30 DINGIN20 0,667
Gambar 7.8 Himpunan fuzzy: DINGIN.
b. Representasi Kurva Segitiga
Kurva Segitiga pada dasarnya merupakan gabungan antara 2 garis (linear) seperti terlihat pada Gambar 7.9.
Gambar 7.9 Kurva Segitiga. derajat keanggotaan μ[x] 1 0 domaina b c
Fungsi Keanggotaan:
⎪⎩⎪⎨⎧≤≤≤≤≥≤=cxbb);-x)/(c-(bbxaa);-a)/(b-(xcx atau ;0][axxμ (7.3)
Contoh 7.5:
Fungsi keanggotaan untuk himpunan NORMAL pada variabel temperatur ruangan seperti terlihat pada Gambar 7.10.
μNORMAL[23] = (23-15)/(25-15)
= 8/10 = 0,8 116
derajat keanggotaan μ[x] 10NORMAL 15 25 35 23 0,8 Temperatur (oC)
Gambar 7.10 Himpunan fuzzy: NORMAL (kurva segitiga).
c. Representasi Kurva Trapesium
Kurva Segitiga pada dasarnya seperti bentuk segitiga, hanya saja ada beberapa titik yang memiliki nilai keanggotaan 1 (Gambar 2.26). derajat keanggotaan μ[x] 1 0 domaina b d c
Gambar 7.11 Kurva Trapesium.
Fungsi Keanggotaan:
⎪⎪⎩⎪⎪⎨⎧≥≤≤≤≤≥≤=dxaxxc);-x)/(d-(dcxb1;bxaa);-a)/(b-(xdx atau ;0][μ (7.4)
Contoh 7.6:
Fungsi keanggotaan untuk himpunan NORMAL pada variabel temperatur ruangan seperti terlihat pada Gambar 7.12.
μNORMAL[23] = (35-32)/(35-27)
= 3/8 = 0,375
117
μ[x]1 0 NORMAL 15 27 35 24 0,375 Temperatur (oC) 32
Gambar 7.12 Himpunan fuzzy: NORMAL (kurva trapesium).
d. Representasi Kurva Bentuk Bahu
Daerah yang terletak di tengah-tengah suatu variabel yang direpresentasikan dalam bentuk segitiga, pada sisi kanan dan kirinya akan naik dan turun (misalkan: DINGIN bergerak ke SEJUK bergerak ke HANGAT dan bergerak ke PANAS). Tetapi terkadang salah satu sisi dari variabel tersebut tidak mengalami perubahan. Sebagai contoh, apabila telah mencapai kondisi PANAS, kenaikan temperatur akan tetap berada pada kondisi PANAS. Himpunan fuzzy ‘bahu’, bukan segitiga, digunakan untuk mengakhiri variabel suatu daerah fuzzy. Bahu kiri bergerak dari benar ke salah, demikian juga bahu kanan bergerak dari salah ke benar. Gambar 7.13 menunjukkan variabel TEMPERATUR dengan daerah bahunya. 0 28 40 0 1 derajat keanggotaan μ[x] TEMPERATUR SEJUK DINGIN HANGAT PANAStemperatur (oC)NORMAL Bahu Kiri Bahu Kanan
Gambar 7.13 Daerah ‘bahu’ pada variabel TEMPERATUR.
e. Representasi Kurva-S
Kurva PERTUMBUHAN dan PENYUSUTAN merupakan kurva-S atau sigmoid yang berhubungan dengan kenaikan dan penurunan permukaan secara tak linear.
Kurva-S untuk PERTUMBUHAN akan bergerak dari sisi paling kiri (nilai keanggotaan = 0) ke sisi paling kanan (nilai keanggotaan = 1). Fungsi
118
keanggotaannya akan tertumpu pada 50% nilai keanggotaannya yang sering disebut dengan titik infleksi (Gambar 7.14). 1 0 ℜ1domainderajat keanggotaan μ[x] ℜn
Gambar 7.14 Himpunan fuzzy dengan kurva-S: PERTUMBUHAN.
Kurva-S untuk PENYUSUTAN akan bergerak dari sisi paling kanan (nilai keanggotaan = 1) ke sisi paling kiri (nilai keanggotaan = 0) seperti telihat pada Gambar 7.15.
Gambar 7.15 Himpunan fuzzy dengan kurva-S: PENYUSUTAN. 1 0 ℜidomainderajat keanggotaan μ[x] ℜj
Kurva-S didefinisikan dengan menggunakan 3 parameter, yaitu: nilai keanggotaan nol (α), nilai keanggotaan lengkap (γ), dan titik infleksi atau crossover (β) yaitu titik yang memiliki domain 50% benar. Gambar 7.16 menunjukkan karakteristik kurva-S dalam bentuk skema. 1 0 ℜ1domainderajat keanggotaan μ[x] ℜnμ[x]=0 α μ[x]=0,5 β μ[x]=1 γ 0,5
Gambar 7.16 Karakteristik fungsi kurva-S. 119
Fungsi keangotaanpada kurva PERTUMBUHAN adalah:
⎪⎪⎩⎪⎪⎨⎧≥→≤≤→−−−≤≤→−−≤→=γγβαγγβααγααγβαxxxxxxxS1))/()((21))/()((20),,;(22 (7.5)
Contoh 7.7:
Fungsi keanggotaan untuk himpunan TUA pada variabel umur seperti terlihat pada Gambar 7.17.
μTUA[50] = 1 – 2((60-50)/(60-35))2
= 1 – 2(10/25)2
= 0,68 1 0 35 μ[x] 60 50 0,68 TUA
u
umr (tahun)
Gambar 7.17 Himpunan Fuzzy: TUA.
Sedangkan fungsi keanggotaan pada kurva PENYUSUTAN adalah:
⎪⎪⎩⎪⎪⎨⎧≥→≤≤→−−≤≤→−−−≤→=γγβαγγβααγααγβαxxxxxxxS0))/()((2))/()((211),,;(22 (7.6)
Contoh 7.8:
Fungsi keanggotaan untuk himpunan MUDA pada variabel umur seperti terlihat pada Gambar 7.18.
μMUDA[50] = 2((50-37)/(50-20))2
= 2(13/30)2
= 0,376
Gambar 7.18 Himpunan Fuzzy: MUDA. 1 0 20 umur (tahun) μ[x] 50 37 0,376 MUDA
120
f. Representasi Kurva Bentuk Lonceng (Bell Curve)
Untuk merepresentasikan bilangan fuzzy, biasanya digunakan kurva berbentuk lonceng. Kurva berbentuk lonceng ini terbagi atas 3 kelas, yaitu: himpunan fuzzy PI, beta, dan Gauss. Perbedaan ketiga kurva ini terletak pada gradiennya.
(i) Kurva PI
Kurva PI berbentuk lonceng dengan derajat keanggotaan 1 terletak pada pusat dengan domain (γ), dan lebar kurva (β) seperti terlihat pada Gambar 7.19. Nilai kurva untuk suatu nilai domain x diberikan sebagai:
Gambar 7.19 Karakteristik fungsional kurva PI. 1 0 ℜiderajat keanggotaan 0,5 ℜjTitik Infleksi Pusat γ Lebar β Domain
Fungsi Keanggotaan: ⎪⎪⎩⎪⎪⎨⎧>→⎟⎟⎠⎞⎜⎜⎝⎛++−≤→⎟⎟⎠⎞⎜⎜⎝⎛−−=ΠγβγβγγγγβγβγγβxxSxxSx,2,;1,2,;),,( (7.7)
Contoh 7.9:
Fungsi keanggotaan untuk himpunan PAROBAYA pada variabel umur seperti terlihat pada Gambar 7.20.
μ1/2BAYA[42] = 1 - 2((45-42)/(45-35))2
= 1 - 2(3/10)2
= 0,82
μ1/2BAYA[51] = 2((55-51)/(55-45))2
= 2(4/10)2
= 0,32
121
1 μ[x] PAROBAYA 0 35 55 45 42 51 0,82
0,32
Gambar 7.20 Himpunan Fuzzy: PAROBAYA dengan kurva phi.
(ii) Kurva BETA
Seperti halnya kurva PI, kurva BETA juga berbentuk lonceng namun lebih rapat. Kurva ini juga didefinisikan dengan 2 parameter, yaitu nilai pada domain yang menunjukkan pusat kurva (γ), dan setengah lebar kurva (β) seperti terlihat pada Gambar 7.21. Nilai kurva untuk suatu nilai domain x diberikan sebagai: 1 0 ℜ1derajat keanggotaan μ[x] ℜnTitik Infleksi γ−β Pusat γ Domain Titik Infleksi γ+β 0,5
Gambar 7.21 Karakteristik fungsional kurva BETA.
Fungsi Keanggotaan: 211),;(⎟⎟⎠⎞⎜⎜⎝⎛−+=βγβγxxB (7.8)
122
Salah satu perbedaan mencolok kurva BETA dari kurva PI adalah, fungsi keanggotaannya akan mendekati nol hanya jika nilai (β) sangat besar.
Contoh 7.10:
Fungsi keanggotaan untuk himpunan SETENGAH BAYA pada variabel umur seperti terlihat pada Gambar 7.22.
μ1/2BAYA[42] = 1/(1+((42-45)/5)2)
= 0,7353
μ1/2BAYA[51] = 1/(1+((51-45)/5)2)
= 0,4098 1 μ[x] PAROBAYA 0 35 55 45 42 51 0,7353
0,4098
Gambar 7.23 Himpunan Fuzzy: SETENGAH BAYA dengan kurva Beta.
(iii) Kurva GAUSS
Jika kurva PI dan kurva BETA menggunakan 2 parameter yaitu (γ) dan (β), kurva GAUSS juga menggunakan (γ) untuk menunjukkan nilai domain pada pusat kurva, dan (k) yang menunjukkan lebar kurva (Gambar 7.25). Nilai kurva untuk suatu nilai domain x diberikan sebagai: 1 0 ℜiderajat keanggotaan μ[x] ℜjPusat γ Lebar k Domain 0,5
Gambar 7.25 Karakteristik fungsional kurva GAUSS. 123
Fungsi Keanggotaan:
2)(),;(xkekxG−−=γγ (7.9)
g. Koordinat Keanggotaan
Himpunan fuzzy berisi urutan pasangan berurutan yang berisi nilai domain dan kebenaran nilai keanggotaannya dalam bentuk:
Skalar(i) / Derajat(i)
‘Skalar’ adalah suatu nilai yang digambar dari domain himpunan fuzzy, sedangkan ‘Derajat’ skalar merupakan derajat keanggotaan himpunan fuzzynya. 10 20 30 40 50 60 70 80 90 100 umur (th) 0,5 μ[x] PENGENDARA BERESIKO TINGGI (dalam umur)0 1
Gambar 7.26 Titik-titik koordinat yang menunjukkan PENGENDARA BERESIKO TINGGI
Gambar 7.26 merupakan contoh himpunan fuzzy yang diterapkan pada sistem asuransi yang akan menanggung resiko seorang pengendara kendaraan bermotor berdasarkan usianya, akan berbentuk ‘U’. Koordinatnya dapat digambarkan dengan 7 pasangan berurutan sebagai berikut:
16/1 21/.6 28/.3 68/.3 76/.5 80/.7 96/1
Gambar 2.43 memperlihatkan koordinat yang menspesifikasikan titik-titik sepanjang domain himpunan fuzzy. Semua titik harus ada di domain, dan paling sedikit harus ada satu titik yang memiliki nilai kebenaran sama dengan 1. Apabila titik-titik tersebut telah digambarkan, maka digunakan interpolasi linear untuk mendapatkan permukaan fuzzy-nya seperti terlihat pada Gambar 7.27.
124
10 20 30 40 50 60 70 80 90 100 umur 0,5 μ[x] PENGENDARA BERESIKO TINGGI (dalam umur) 0 1
Gambar 7.27 Kurva yang berhubungan dengan PENGENDARA BERESIKO TINGGI
7.6 OPERATOR DASAR ZADEH UNTUK OPERASI HIMPUNAN FUZZY
Seperti halnya himpunan konvensional, ada beberapa operasi yang didefinisikan secara khusus untuk mengkombinasi dan memodifikasi himpunan fuzzy. Nilai keanggotaan sebagai hasil dari operasi 2 himpunan sering dikenal dengan nama fire strength atau α–predikat. Ada 3 operator dasar yang diciptakan oleh Zadeh, yaitu:
7.6.1 Operator AND
Operator ini berhubungan dengan operasi interseksi pada himpunan. α–predikat sebagai hasil operasi dengan operator AND diperoleh dengan mengambil nilai keanggotaan terkecil antar elemen pada himpunan-himpunan yang bersangkutan.
μA∩B = min(μA[x], μB[y])
Contoh 7.11:
Misalkan nilai keanggotaan 27 tahun pada himpunan MUDA adalah 0,6 (μMUDA[27]=0,6); dan nilai keanggotaan Rp 2.000.000,- pada himpunan penghasilan TINGGI adalah 0,8 (μGAJITINGGI[2x106]=0,8); maka α–predikat untuk usia MUDA dan berpenghasilan TINGGI adalah:
μMUDA∩GAJITINGGI = min(μMUDA[27], μGAJITINGGI[2x106)
= min(0,6; 0,8)
= 0,6
7.6.2 Operator OR
Operator ini berhubungan dengan operasi union pada himpunan. α–predikat sebagai hasil operasi dengan operator OR diperoleh dengan mengambil nilai keanggotaan terbesar antar elemen pada himpunan-himpunan yang bersangkutan.
μA∪B = max(μA[x], μB[y])
125
Contoh 7.12:
Pada contoh 7.11, dapat dihitung nilai α–predikat untuk usia MUDA atau berpenghasilan TINGGI adalah:
μMUDA∪GAJITINGGI = max(μMUDA[27], μGAJITINGGI[2x106)
= max(0,6; 0,8)
= 0,8
7.6.3 Operator NOT
Operator ini berhubungan dengan operasi komplemen pada himpunan. α–predikat sebagai hasil operasi dengan operator NOT diperoleh dengan mengurangkan nilai keanggotaan elemen pada himpunan yang bersangkutan dari 1.
μA’ = 1-μA[x]
Contoh 7.13:
Pada contoh 7.11, dapat dihitung nilai α–predikat untuk usia TIDAK MUDA adalah:
μMUDA’ [27] = 1 - μMUDA[27]
= 1 - 0,6
= 0,4
7.7 PENALARAN MONOTON
Metode penalaran secara monoton digunakan sebagai dasar untuk teknik implikasi fuzzy. Meskipun penalaran ini sudah jarang sekali digunakan, namun terkadang masih digunakan untuk penskalaan fuzzy. Jika 2 daerah fuzzy direlasikan dengan implikasi sederhana sebagai berikut:
IF x is A THEN y is B
transfer fungsi:
y = f((x,A),B)
maka sistem fuzzy dapat berjalan tanpa harus melalui komposisi dan dekomposisi fuzzy. Nilai output dapat diestimasi secara langsung dari nilai keanggotaan yang berhubungan dengan antesedennya.
Contoh 7.14:
Misalkan ada 2 himpunan fuzzy: TINGGI (menunjukkan tinggi badan orang Indonesia) dan BERAT (menunjukkan berat badan orang Indonesia) seperti terlihat pada Gambar 7.28.
126
μ[x] 1 0 150 170 Tinggi badan (cm) TINGGI μ[y] 1040 70 Berat badan (Kg) BERAT
Gambar 7.28 Himpunan fuzzy: TINGGI dan BERAT.
Relasi antara kedua himpunan diekspresikan dengan aturan tunggal sebagai berikut:
IF TinggiBadan is TINGGI THEN BeratBadan is BERAT
Implikasi secara monoton akan menyeleksi daerah fuzzy A dan B dengan algoritma sebagai berikut:
• Untuk suatu elemen x pada domain A, tentukan nilai keanggotannya dalam daerah fuzzy A, yaitu: μA[x];
• Pada daerah fuzzy B, nilai keanggotaan yang berhubungan dengan tentukan permukaan fuzzy-nya. Tarik garis lurus ke arah domain. Nilai pada sumbu domain, y, merupakan solusi dari fungsi implikasi tersebut. Dapat dituliskan:
yB = f(μA[x],DB)
Gambar 7.29 menunjukkan kerja algoritma tersebut. Seseorang yang memiliki tinggi badan 165 cm, memiliki derajat keanggotaan 0,75 pada daerah fuzzy TINGGI; diperoleh dari:
μTINGGI[165] = (165 – 150)/(170 – 150)
= 15/20
= 0,75
Nilai ini dipetakan ke daerah fuzzy BERAT yang akan memberikan solusi berat badan orang tersebut yaitu 59,4 kg; diperoleh dari:
μBERAT[y] = S(y; 40,55,70) = 0,75
Karena 0,75 > 0,5 maka letak y adalah antara 52,5 sampai 70, sehingga:
⇔ 1-2[(70-y)/(70-40)]2 = 0,75
⇔ 1-2(70-y)2/900 = 0,75
⇔ 2(70-y)2/900 = 0,25
⇔ (70-y)2 = 112,5
⇔ (70-y) = ±√(112,5)
127
⇔ y = 70 ± 10,6 ---> ambil (-) nya, karena
nilainya harus < 70
⇔ y = 59,4 μ[x] 1 0 150 165 170 Tinggi badan (cm) TINGGI μ[x] 1 0 40 59,4 70 Berat badan (Kg) BERAT [0,75] [0,75]
Gambar 7.29 Implikasi monoton: TINGGI ke BERAT.
7.8 FUNGSI IMPLIKASI
Tiap-tiap aturan (proposisi) pada basis pengetahuan fuzzy akan berhubungan dengan suatu relasi fuzzy. Bentuk umum dari aturan yang digunakan dalam fungsi implikasi adalah:
IF x is A THEN y is B
dengan x dan y adalah skalar, dan A dan B adalah himpunan fuzzy. Proposisi yang mengikuti IF disebut sebagi anteseden, sedangkan proposisi yang mengikuti THEN disebut sebagai konsekuen. Proposisi ini dapat diperluas dengan menggunakan operator fuzzy, seperti:
IF (x1 is A1) • (x2 is A2) • (x3 is A3) • ...... • (xN is AN) THEN y is B
dengan • adalah operator (misal: OR atau AND).
Secara umum, ada 2 fungsi implikasi yang dapat digunakan, yaitu:
a. Min (minimum). Fungsi ini akan memotong output himpunan fuzzy. Gambar 7.30 menunjukkan salah satu contoh penggunaan fungsi min.
128
TINGGI IF Permintaan TINGGI AND BiayaProduksi SEDANG THEN ProduksiBarang NORMAL SEDANG NORMAL Aplikasi Operator AND Aplikasi fungsi implikasi Min
Gambar 7.30 Fungsi implikasi: MIN.
b. Dot (product). Fungsi ini akan menskala output himpunan fuzzy. Gambar 7.31 menunjukkan salah satu contoh penggunaan fungsi dot. TINGGI IF Permintaan TINGGI AND BiayaProduksi SEDANG THEN ProduksiBarang NORMAL SEDANG NORMAL Aplikasi Operator AND Aplikasi fungsi implikasi Dot (Product)
Gambar 7.31 Fungsi implikasi: DOT.
7.8 SISTEM INFERENSI FUZZY
7.8.1 Metode Tsukamoto
Pada Metode Tsukamoto, setiap konsekuen pada aturan yang berbentuk IF-Then harus direpresentasikan dengan suatu himpunan fuzzy dengan fungsi keanggotaan yang monoton (Gambar 7.32). Sebagai hasilnya, output hasil inferensi dari tiap-tiap aturan diberikan secara tegas (crisp) berdasarkan α-predikat (fire strength). Hasil akhirnya diperoleh dengan menggunakan rata-rata terbobot.
129
Gambar 7.32 Inferensi dengan menggunakan Metode Tsukamoto.
Contoh 7.15:
Suatu perusahaan makanan kaleng akan memproduksi makanan jenis ABC. Dari data 1 bulan terakhir, permintaan terbesar hingga mencapai 5000 kemasan/hari, dan permintaan terkecil sampai 1000 kemasan/hari. Persediaan barang digudang terbanyak sampai 600 kemasan/hari, dan terkecil pernah sampai 100 kemasan/hari. Dengan segala keterbatasannya, sampai saat ini, perusahaan baru mampu memproduksi barang maksimum 7000 kemasan/hari, serta demi efisiensi mesin dan SDM tiap hari diharapkan perusahaan memproduksi paling tidak 2000 kemasan. Apabila proses produksi perusahaan tersebut menggunakan 4 aturan fuzzy sbb:
[R1] IF Permintaan TURUN And Persediaan BANYAK
THEN Produksi Barang BERKURANG;
{R2] IF Permintaan TURUN And Persediaan SEDIKIT
THEN Produksi Barang BERKURANG;
[R3] IF Permintaan NAIK And Persediaan BANYAK
THEN Produksi Barang BERTAMBAH;
[R4] IF Permintaan NAIK And Persediaan SEDIKIT
THEN Produksi Barang BERTAMBAH;
Berapa kemasan makanan jenis ABC yang harus diproduksi, jika jumlah permintaan sebanyak 4000 kemasan, dan persediaan di gudang masih 300 kemasan? Var-1 Var-2 Var-3 0 0 0 1 1 1 μμ
130
Solusi:
Ada 3 variabel fuzzy yang akan dimodelkan, yaitu:
• Permintaan; terdiri-atas 2 himpunan fuzzy, yaitu: NAIK dan TURUN (Gambar 7.33). 0 1 μ[x] 1000 5000 TURUN NAIK Permintaan (kemasan/hari) 4000 0,25
0,75
Gambar 7.33 Fungsi keanggotaan variabel Permintaan pada Contoh 7.15. ⎪⎪⎩⎪⎪⎨⎧≥≤≤−≤=5000x,05000x1000,4000x50001000x,1]x[PmtTURUNμ ⎪⎪⎩⎪⎪⎨⎧≥≤≤−≤=5000x,15000x1000,40001000x1000x,0]x[PmtNAIKμ
Kita bisa mencari nilai keanggotaan:
μPmtTURUN[4000] = (5000-4000)/4000
= 0,25
μPmtNAIK[4000] = (4000-1000)/4000
= 0,75
• Persediaan; terdiri-atas 2 himpunan fuzzy, yaitu: SEDIKIT dan BANYAK (Gambar 7.34). 0,6
Gambar 7.34 Fungsi keanggotaan variabel Persediaan pada Contoh 7.15.
131
⎪⎪⎩⎪⎪⎨⎧≥≤≤−≤=600y,0600y100,500y600100y,1]y[PsdSEDIKITμ ⎪⎪⎩⎪⎪⎨⎧≥≤≤−≤=600y,1600y100,500100y100y,0]y[PsdBANYAKμ
Kita bisa mencari nilai keanggotaan:
μPsdSEDIKIT[300] = (600-300)/500
= 0,6
μPsdBANYAK[300] = (300-100)/500
= 0,4
• Produksi barang; terdiri-atas 2 himpunan fuzzy, yaitu: BERKURANG dan BERTAMBAH (Gambar 7.35).
Gambar 7.35 Fungsi keanggotaan variabel Produksi Barang pada Contoh 7.15. ⎪⎪⎩⎪⎪⎨⎧≥≤≤−≤=7000z,07000z2000,5000z70002000z,1]z[NGBrgBERKURAPrμ ⎪⎪⎩⎪⎪⎨⎧≥≤≤−≤=7000z,17000z2000,50002000z2000z,0]z[AHBrgBERTAMBPrμ
Sekarang kita cari nilai z untuk setiap aturan dengan menggunakan fungsi MIN pada aplikasi fungsi implikasinya:
[R1] IF Permintaan TURUN And Persediaan BANYAK
132
THEN Produksi Barang BERKURANG;
α-predikat1 = μPmtTURUN ∩ PsdBANYAK
= min(μPmtTURUN [4000],μPsdBANYAK[300])
= min(0,25; 0,4)
= 0,25
Lihat himpunan Produksi Barang BERKURANG,
(7000-z)/5000 = 0,25 ---> z1 = 5750
{R2] IF Permintaan TURUN And Persediaan SEDIKIT
THEN Produksi Barang BERKURANG;
α-predikat2 = μPmtTURUN ∩ PsdSEDIKIT
= min(μPmtTURUN [4000],μPsdSEDIKIT[300])
= min(0,25; 0,6)
= 0,25
Lihat himpunan Produksi Barang BERKURANG,
(7000-z)/5000 = 0,25 ---> z2 = 5750
[R3] IF Permintaan NAIK And Persediaan BANYAK
THEN Produksi Barang BERTAMBAH;
α-predikat3 = μPmtNAIK ∩ PsdBANYAK
= min(μPmtNAIK [4000],μPsdBANYAK[300])
= min(0,75; 0,4)
= 0,4
Lihat himpunan Produksi Barang BERTAMBAH,
(z-2000)/5000 = 0,4 ---> z3 = 4000
[R4] IF Permintaan NAIK And Persediaan SEDIKIT
THEN Produksi Barang BERTAMBAH;
α-predikat4 = μPmtNAIK ∩ PsdBANYAK
= min(μPmtNAIK [4000],μPsdSEDIKIT[300])
= min(0,75; 0,6)
= 0,6
Lihat himpunan Produksi Barang BERTAMBAH,
(z-2000)/5000 = 0,6 ---> z4 = 5000
Dari sini kita dapat mencari berapakah nilai z, yaitu: 432144332211predpredpredpredz*predz*predz*predz*predzαααααααα++++++=
133
49835,174756,04,025,025,05000*6,04000*4,05750*25,05750*25,0z==++++++=
Jadi jumlah makanan kaleng jenis ABC yang harus diproduksi sebanyak 4983 kemasan.
7.8.2 Metode Mamdani
Metode Mamdani sering juga dikenal dengan nama Metode Max-Min. Metode ini diperkenalkan oleh Ebrahim Mamdani pada tahun 1975. Untuk mendapatkan output, diperlukan 4 tahapan:
1. Pembentukan himpunan fuzzy
2. Aplikasi fungsi implikasi (aturan)
3. Komposisi aturan
4. Penegasan (deffuzy)
1. Pembentukan himpunan fuzzy
Pada Metode Mamdani, baik variabel input maupun variabel output dibagi menjadi satu atau lebih himpunan fuzzy.
2. Aplikasi fungsi implikasi
Pada Metode Mamdani, fungsi implikasi yang digunakan adalah Min.
3. Komposisi Aturan
Tidak seperti penalaran monoton, apabila sistem terdiri-dari beberapa aturan, maka inferensi diperoleh dari kumpulan dan korelasi antar aturan. Ada 3 metode yang digunakan dalam melakukan inferensi sistem fuzzy, yaitu: max, additive dan probabilistik OR (probor).
a. Metode Max (Maximum)
Pada metode ini, solusi himpunan fuzzy diperoleh dengan cara mengambil nilai maksimum aturan, kemudian menggunakannya untuk memodifikasi daerah fuzzy, dan mengaplikasikannya ke output dengan menggunakan operator OR (union). Jika semua proposisi telah dievaluasi, maka output akan berisi suatu himpunan fuzzy yang merefleksikan konstribusi dari tiap-tiap proposisi. Secara umum dapat dituliskan:
μsf[xi] ← max(μsf[xi], μkf[xi])
dengan:
μsf[xi] = nilai keanggotaan solusi fuzzy sampai aturan ke-i;
μkf[xi] = nilai keanggotaan konsekuen fuzzy aturan ke-i;
Misalkan ada 3 aturan (proposisi) sebagai berikut:
[R1] IF Biaya Produksi RENDAH And Permintaan NAIK
THEN Produksi Barang BERTAMBAH;
{R2] IF Biaya Produksi STANDAR
THEN Produksi Barang NORMAL;
[R3] IF Biaya Produksi TINGGI And Permintaan TURUN
THEN Produksi Barang BERKURANG;
Proses inferensi dengan menggunakan metode Max dalam melakukan komposisi aturan seperti terlihat pada Gambar 7.36.
134
Apabila digunakan fungsi implikasi MIN, maka metode komposisi ini sering disebut dengan nama MAX-MIN atau MIN-MAX atau MAMDANI.
Gambar 7.36 Komposisi aturan Fuzzy: Metode MAX. TINGGI BERKURANG TURUN STANDAR NORMAL Tak ada input RENDAH NAIK BERTAMBAH 1. Input fuzzy 2. Aplikasi operasi fuzzy (And = Min)3. Aplikasi metode implikasi (min) IF Biaya Produksi RENDAH And Permintaan NAIK THEN Produksi Barang BERTAMBAH IF Biaya Produksi STANDAR THEN Produksi Barang NORMAL IF Biaya Produksi TINGGI And Permintaan TURUN THEN Produksi Barang BERKURANG 4. Aplikasi metode komposisi (max)
b. Metode Additive (Sum)
Pada metode ini, solusi himpunan fuzzy diperoleh dengan cara melakukan bounded-sum terhadap semua output daerah fuzzy. Secara umum dituliskan:
μsf[xi] ← min(1,μsf[xi]+ μkf[xi])
dengan:
μsf[xi] = nilai keanggotaan solusi fuzzy sampai aturan ke-i;
μkf[xi] = nilai keanggotaan konsekuen fuzzy aturan ke-i;
c. Metode Probabilistik OR (probor)
Pada metode ini, solusi himpunan fuzzy diperoleh dengan cara melakukan product terhadap semua output daerah fuzzy. Secara umum dituliskan:
135
μsf[xi] ← (μsf[xi]+ μkf[xi]) - (μsf[xi] * μkf[xi])
dengan:
μsf[xi] = nilai keanggotaan solusi fuzzy sampai aturan ke-i;
μkf[xi] = nilai keanggotaan konsekuen fuzzy aturan ke-i;
4. Penegasan (defuzzy)
Input dari proses defuzzifikasi adalah suatu himpunan fuzzy yang diperoleh dari komposisi aturan-aturan fuzzy, sedangkan output yang dihasilkan merupakan suatu bilangan pada domain himpunan fuzzy tersebut. Sehingga jika diberikan suatu himpunan fuzzy dalam range tertentu, maka harus dapat diambil suatu nilai crsip tertentu sebagai output seperti terlihat pada Gambar 7.37. Daerah fuzzy ‘B’ Daerah fuzzy ‘A’ Daerah fuzzy ‘C’ Output: Daerah fuzzyNilai yang diharapkan
Gambar 7.37 Proses defuzzifikasi.
Ada beberapa metode defuzzifikasi pada komposisi aturan MAMDANI, antara lain:
a. Metode Centroid (Composite Moment)
Pada metode ini, solusi crisp diperoleh dengan cara mengambil titik pusat (z*) daerah fuzzy. Secara umum dirumuskan: ∫∫=zZdz)z(dz)z(z*zμμ ΣΣ===n1jjn1jjj)z()z(z*zμμ
136
b. Metode Bisektor
Pada metode ini, solusi crisp diperoleh dengan cara mengambil nilai pada domain fuzzy yang memiliki nilai keanggotaan separo dari jumlah total nilai keanggotaan pada daerah fuzzy. Secara umum dituliskan: ∫∫ℜℜ=npp1dz(z)dz(z) hingga sedemikian μμpz
c. Metode Mean of Maximum (MOM)
Pada metode ini, solusi crisp diperoleh dengan cara mengambil nilai rata-rata domain yang memiliki nilai keanggotaan maksimum.
d. Metode Largest of Maximum (LOM)
Pada metode ini, solusi crisp diperoleh dengan cara mengambil nilai terbesar dari domain yang memiliki nilai keanggotaan maksimum.
e. Metode Smallest of Maximum (SOM)
Pada metode ini, solusi crisp diperoleh dengan cara mengambil nilai terkecil dari domain yang memiliki nilai keanggotaan maksimum.
Contoh 7.16:
Kita kembali pada contoh yang sama seperti pada contoh 7.15. Himpunan fuzzy pada setiap variabel juga sama seperti penyelesaian pada contoh tersebut. Sekarang kita awali dengan mengaplikasikan fungsi implikasi untuk setiap aturan. Karena kita menggunakan Metode MAMDANI, maka fungsi implikasi yang kita gunakan adalah fungsi MIN.
􀃒 Aplikasi fungsi implikasi:
[R1] IF Permintaan TURUN And Persediaan BANYAK
THEN Produksi Barang BERKURANG;
Lihat Gambar 7.38:
α-predikat1 = μPmtTURUN ∩ PsdBANYAK
= min(μPmtTURUN [4000],μPsdBANYAK[300])
= min(0,25; 0,4)
= 0,25
Gambar 7.38 Aplikasi fungsi implikasi untuk R1.
{R2] IF Permintaan TURUN And Persediaan SEDIKIT
THEN Produksi Barang BERKURANG; Permintaan Persediaan Prod. Brg. 0 0 0 0 1 1 1 1 μ[x] μ[y] μ[z] μ[z] TURUN
300 0,4
137
Lihat Gambar 7.39:
α-predikat2 = μPmtTURUN ∩ PsdSEDIKIT
= min(μPmtTURUN [4000],μPsdSEDIKIT[300])
= min(0,25; 0,6)
= 0,25
Gambar 7.39 Aplikasi fungsi implikasi untuk R2.
[R3] IF Permintaan NAIK And Persediaan BANYAK
THEN Produksi Barang BERTAMBAH;
Lihat Gambar 7.40:
α-predikat3 = μPmtNAIK ∩ PsdBANYAK
= min(μPmtNAIK [4000],μPsdBANYAK[300])
= min(0,75; 0,4)
= 0,4
Gambar 7.40 Aplikasi fungsi implikasi untuk R3.
[R4] IF Permintaan NAIK And Persediaan SEDIKIT
THEN Produksi Barang BERTAMBAH;
Lihat Gambar 7.41:
α-predikat4 = μPmtNAIK ∩ PsdBANYAK
= min(μPmtNAIK [4000],μPsdSEDIKIT[300])
= min(0,75; 0,6)
= 0,6 Permintaan Persediaan Prod. Brg. 0 0 0 0 1 1 1 1 μ[x] μ[y] μ[z] μ[z] TURUN
300 0,6 Permintaan Persediaan Prod. Brg. 0 0 0 0 1 1 1 1 μ[x] μ[y] μ[z] μ[z] NAIK BANYAK BERTAMBAH 4000 300 0,4 0,4
138
Gambar 7.41 Aplikasi fungsi implikasi untuk R4.
􀃒 Komposisi antar aturan
Dari hasil aplikasi fungsi implikasi dari tiap aturan, digunakan metode MAX untuk melakukan komposisi antar semua aturan. Hasilnya seperti pada Gambar 7.42.
Gambar 7.42 Daerah hasil komposisi.
Pada Gambar 7.42 tersebut, daerah hasil kita bagi menjadi 3 bagian, yaitu A1, A2, dan A3. Sekarang kita cari nilai a1 dan a2.
(a1 – 2000)/5000 = 0,25 ---> a1 = 3250
(a2 – 2000)/5000 = 0,60 ---> a2 = 5000
Dengan demikian, fungsi keanggotaan untuk hasil komposisi ini adalah:
⎪⎩⎪⎨⎧≥≤≤−≤=5000z;6,05000z3250;5000/)2000z(3250z;25,0]z[μ
􀃒 Penegasan (defuzzy)
Metode penegasan yang akan kita gunakan adalah metode centroid. Untuk itu, pertama-tama kita hitung dulu momen untuk setiap daerah. 5,1320312z125,0dzz)25,0(1M32500232500===∫ 625,3187515z2,0z000067,0dz)z4,0z0002,0(dzz5000)2000z(2M500032502350003250250003250=−=−=−=∫∫Permintaan Persediaan Prod. Brg. 0 0 0 0 1 1 1 1 μ
300 0,6 0,6 0 1 0,6 0,25 A1 A2 A3 a1a2μ[z] Prod. Brg.
139
7200000z3,0dzz)6,0(3M70005000270005000===∫
Kemudian kita hitung luas setiap daerah:
A1 = 3250*0,25 = 812,5
A2 = (0,25+0,6)*(5000-3250)/2 = 743,75
A3 = (7000-5000)*0,6 = 1200
Titik pusat dapat diperoleh dari: 74,4247120075,7435,8127200000625,31875155,1320312z=++++=
Jadi jumlah makanan kaleng jenis ABC yang harus diproduksi sebanyak 4248 kemasan.
7.8.3 Metode Sugeno
Penalaran dengan metode SUGENO hampir sama dengan penalaran MAMDANI, hanya saja output (konsekuen) sistem tidak berupa himpunan fuzzy, melainkan berupa konstanta atau persamaan linear. Metode ini diperkenalkan oleh Takagi-Sugeno Kang pada tahun 1985.
a. Model Fuzzy Sugeno Orde-Nol
Secara umum bentuk model fuzzy SUGENO Orde-Nol adalah:
IF (x1 is A1) • (x2 is A2) • (x3 is A3) • ...... • (xN is AN) THEN z=k
dengan Ai adalah himpunan fuzzy ke-i sebagai anteseden, dan k adalah suatu konstanta (tegas) sebagai konsekuen.
b. Model Fuzzy Sugeno Orde-Satu
Secara umum bentuk model fuzzy SUGENO Orde-Satu adalah:
IF (x1 is A1) • ...... • (xN is AN) THEN z = p1*x1 + … + pN*xN + q
dengan Ai adalah himpunan fuzzy ke-i sebagai anteseden, dan pi adalah suatu konstanta (tegas) ke-i dan q juga merupakan konstanta dalam konsekuen.
Apabila komposisi aturan menggunakan metode SUGENO, maka deffuzifikasi dilakukan dengan cara mencari nilai rata-ratanya.
Contoh 7.17.
Kita kembali pada contoh yang sama seperti pada contoh 7.15. Himpunan fuzzy pada variabel permintaan dan persediaan juga sama seperti penyelesaian pada contoh tersebut. Hanya saja aturan yang digunakan sedikit dimodifikasi, sebagai
140
berikut (dengan asumsi bahwa jumlah permintaan selalu lebih tinggi dibanding dengan jumlah persediaan):
[R1] IF Permintaan TURUN And Persediaan BANYAK
THEN Produksi Barang = Permintaan - Persediaan;
{R2] IF Permintaan TURUN And Persediaan SEDIKIT
THEN Produksi Barang = Permintaan;
[R3] IF Permintaan NAIK And Persediaan BANYAK
THEN Produksi Barang = Permintaan;
[R4] IF Permintaan NAIK And Persediaan SEDIKIT
THEN Produksi Barang = 1,25*Permintaan - Persediaan;
Sekarang kita cari α-predikat dan nilai z untuk setiap aturan:
[R1] IF Permintaan TURUN And Persediaan BANYAK
THEN Produksi Barang = Permintaan - Persediaan;
α-predikat1 = μPmtTURUN ∩ PsdBANYAK
= min(μPmtTURUN [4000],μPsdBANYAK[300])
= min(0,25; 0,4)
= 0,25
Nilai z1: z1 = 4000 – 300 = 3700
{R2] IF Permintaan TURUN And Persediaan SEDIKIT
THEN Produksi Barang = Permintaan;
α-predikat2 = μPmtTURUN ∩ PsdSEDIKIT
= min(μPmtTURUN [4000],μPsdSEDIKIT[300])
= min(0,25; 0,6)
= 0,25
Nilai z2: z2 = 4000
[R3] IF Permintaan NAIK And Persediaan BANYAK
THEN Produksi Barang = Permintaan;
α-predikat3 = μPmtNAIK ∩ PsdBANYAK
= min(μPmtNAIK [4000],μPsdBANYAK[300])
= min(0,75; 0,4)
= 0,4
Nilai z3: z3 = 4000
[R4] IF Permintaan NAIK And Persediaan SEDIKIT
THEN Produksi Barang = 1,25*Permintaan - Persediaan;
α-predikat4 = μPmtNAIK ∩ PsdBANYAK
141
= min(μPmtNAIK [4000],μPsdSEDIKIT[300])
= min(0,75; 0,6)
= 0,6
Nilai z4: z4 = 1,25*4000 – 300 = 4700
Dari sini kita dapat mencari berapakah nilai z, yaitu: 432144332211predpredpredpredz*predz*predz*predz*predzαααααααα++++++= 42305,163456,04,025,025,04700*6,04000*4,04000*25,03700*25,0z==++++++=
Jadi jumlah makanan kaleng jenis ABC yang harus diproduksi sebanyak 4230 kemasan.
7.9 BASISDATA FUZZY
Sebagian besar basis data standar diklasifikasikan berdasarkan bagaimana data tersebut dipandang oleh user. Misalkan kita memiliki data karyawan yang tersimpan pada tabel DT_KARYAWAN dengan field NIP, nama, tgl lahir, th masuk, dan gaji per bulan seperti pada Tabel 7.1.
Tabel 7.1 Data mentah karyawan.
NIP
Nama
Tgl Lahir
Th. Masuk
Gaji/bl (Rp)
01
Lia
03-06-1972
1996
750.000
02
Iwan
23-09-1954
1985
1.500.000
03
Sari
12-12-1966
1988
1.255.000
04
Andi
06-03-1965
1998
1.040.000
05
Budi
04-12-1960
1990
950.000
06
Amir
18-11-1963
1989
1.600.000
07
Rian
28-05-1965
1997
1.250.000
08
Kiki
09-07-1971
2001
550.000
09
Alda
14-08-1967
1999
735.000
10
Yoga
17-09-1977
2000
860.000
Kemudian dari tabel DT_KARYAWAN, kita oleh menjadi suatu tabel temporer untuk menghitung umur karyawan dan masa kerjanya. Tabel tersebut kita beri nama dengan tabel KARYAWAN (Tabel 7.2)
Tabel 7.2 Data karywan setelah diolah.
NIP
Nama
Umur (th)
Masa Kerja (th)*
Gaji/bl
01
Lia
30
6
750.000
02
Iwan
48
17
1.500.000
03
Sari
36
14
1.255.000
04
Andi
37
4
1.040.000
05
Budi
42
12
950.000
06
Amir
39
13
1.600.000
142
07
Rian
37
5
1.250.000
08
Kiki
32
1
550.000
09
Alda
35
3
735.000
10
Yoga
25
2
860.000
*Misal sekarang tahun 2002
Dengan menggunakan basisdata standar, kita dapat mencari data-data karyawan dengan spesifikasi tertentu dengan menggunakan query. Misal kita ingin mendapatkan informasi tentang nama-nama karyawan yang usianya kurang dari 35 tahun, maka kita bisa ciptakan suatu query:
SELECT NAMA
FROM KARYAWAN
WHERE (Umur < 35)
sehingga muncul nama-nama Lia, Kiki, dan Yoga. Apabila kita ingin mendapatkan informasi tentang nama-nama karyawan yang gajinya lebih dari 1 juta rupiah, maka kita bisa ciptakan suatu query:
SELECT NAMA
FROM KARYAWAN
WHERE (Gaji > 1000000)
sehingga muncul nama-nama Iwan, Sari, Andi, Amir, dan Rian. Apabila kita ingin mendapatkan unformasi tentang nama-nama karyawan yang yang masa kerjanya kurang dari atau sama dengan 5 tahun tetapi gajinya sudah lebih dari 1 juta rupiah, maka kita bisa ciptakan suatu query:
SELECT NAMA
FROM KARYAWAN
WHERE (MasaKerja <= 5) and (Gaji > 1000000)
sehingga muncul nama-nama Andi dan Rian.
Pada kenyataannya, seseorang kadang membutuhkan informasi dari data-data yang bersifat ambiguous. Apabila hal ini terjadi, maka kita menggunakan basisdata fuzzy. Selama ini, sudah ada beberapa penelitian tentang basisdata fuzzy. Salah satu diantaranya adalah model Tahani. Basisdata fuzzy model Tahani masih tetap menggunakan relasi standar, hanya saja model ini menggunakan teori himpunan fuzzy untuk mendapatkan informasi pada query-nya.
Misalkan kita mengkategorikan usia karyawan diatas ke dalam himpunan: MUDA, PAROBAYA, dan TUA (Gambar 7.43)
Gambar 7.43 Fungsi keanggotaan untuk variabel Usia.
143
Fungsi keanggotaan: ⎪⎩⎪⎨⎧≥≤≤−≤=40;04030;104030;1][xxxxxMUDAμ ⎪⎪⎪⎩⎪⎪⎪⎨⎧≤≤−≤≤−≥≤=5045;5504535;10355035;0][xxxxxatauxxPAROBAYAμ ⎪⎩⎪⎨⎧≥≤≤−≤=50;15040;104040;0][xxxxxTUAμ
Tabel 7.3 menunjukkan tabel karyawan berdasarkan umur dengan derajat keanggotannya pada setiap himpunan.
Tabel 7.3 KARYAWAN berdasarkan umur:
Derajat Keanggotaan (μ[x])
NIP
Nama
Umur
MUDA
PAROBAYA
TUA
01
Lia
30
1
0
0
02
Iwan
48
0
0,4
0,8
03
Sari
36
0,4
0,1
0
04
Andi
37
0,3
0,2
0
05
Budi
42
0
0,7
0,2
06
Amir
39
0,1
0,4
0
07
Rian
37
0,3
0,2
0
08
Kiki
32
0,8
0
0
09
Alda
35
0,5
0
0
10
Yoga
25
1
0
0
Variabel Masa Kerja bisa dikategorikan dalam himpunan: BARU dan LAMA (Gambar 7.44)
Gambar 7.44 Fungsi keanggotaan untuk variabel Masa Kerja.
144
Fungsi keanggotaan: ⎪⎩⎪⎨⎧≥≤≤−≤=15;0155;10155;1][yyyyyBARUμ ⎪⎩⎪⎨⎧≥≤≤−≤=25;12510;151010;0][yyyyyLAMAμ
Tabel 7.4 menunjukkan tabel karyawan berdasarkan umur dengan derajat keanggotannya pada setiap himpunan.
Tabel 7.4 KARYAWAN berdasarkan Masa Kerja.
Derajat Keanggotaan (μ[y])
NIP
Nama
Masa Kerja
BARU
LAMA
01
Lia
6
0,9
0
02
Iwan
17
0
0,467
03
Sari
14
0,1
0,267
04
Andi
4
1
0
05
Budi
12
0,3
0,133
06
Amir
13
0,2
0,200
07
Rian
5
1
0
08
Kiki
1
1
0
09
Alda
3
1
0
10
Yoga
2
1
0
Variabel Gaji bisa dikategorikan dalam himpunan: RENDAH, SEDANG, dan TINGGI (Gambar 7.45). 800 300 0 1 502000 150μ[z] RENDAH SEDANG TINGGI Gaji (x1000 Rp/bl) 100
Gambar 7.45 Fungsi keanggotaan untuk variabel Gaji.
Fungsi keanggotaan: ⎪⎩⎪⎨⎧≥≤≤−≤=800;0800300;500800300;1][zzzzzRENDAHμ
145
⎪⎪⎪⎩⎪⎪⎪⎨⎧≤≤−≤≤−≥≤=15001000;50015001000500;5005001500500;0][zzzzzatauzzSEDANGμ ⎪⎩⎪⎨⎧≥≤≤−≤=2000;120001000;100010001000;0][zzzzzTINGGIμ
Tabel 7.5 menunjukkan tabel karyawan berdasarkan umur dengan derajat keanggotannya pada setiap himpunan.
Tabel 7.5 Karyawan berdasar gaji.
Derajat Keanggotaan (μ[z])
NIP
Nama
Gaji / bl
RENDAH
SEDANG
TINGGI
01
Lia
750.000
0,1
0,50
0
02
Iwan
1.255.000
0
0,49
0,255
03
Sari
1.500.000
0
0
0,500
04
Andi
1.040.000
0
0,92
0,040
05
Budi
950.000
0
0,90
0
06
Amir
1.600.000
0
0
0,600
07
Rian
1.250.000
0
0,50
0,250
08
Kiki
550.000
0,5
0
0
09
Alda
735.000
0,13
0
0
10
Yoga
860.000
0
0
0
Ada beberapa query yang bisa diberikan, misalkan:
Query1:
Siapa saja-kah karyawan yang masih muda tapi memiliki gaji tinggi?
SELECT NAMA
FROM KARYAWAN
WHERE (Umur = “MUDA”) and (Gaji = “TINGGI”)
Tabel 7.6 menunjukkan hasil query1, yaitu nama-nama karyawan yang masih muda tapi memiliki gaji yang tinggi.
Tabel 7.6 Hasil query1.
Derajat Keanggotaan
NIP
NAMA
UMUR
GAJI
MUDA
TINGGI
MUDA & TINGGI
03
Sari
36
1.500.000
0,4
0,5
0,4
07
Rian
37
1.250.000
0,3
0,25
0,25
06
Amir
39
1.600.000
0,1
0,6
0,1
04
Andi
37
1.040.000
0,3
0,04
0,04
01
Lia
30
750.000
1
0
0
146
02
Iwan
48
1.255.000
0
0,255
0
05
Budi
42
950.000
0
0
0
08
Kiki
32
550.000
0,8
0
0
09
Alda
35
735.000
0,5
0
0
10
Yoga
25
860.000
1
0
0
Query2:
Siapa saja-kah karyawan yang masih muda atau karyawan yang memiliki gaji tinggi?
SELECT NAMA
FROM KARYAWAN
WHERE (Umur = “MUDA”) or (Gaji = “TINGGI”)
Tabel 7.7 menunjukkan hasil query2, yaitu nama-nama karyawan yang masih muda atau yang memiliki gaji yang tinggi.
Tabel 7.7 Hasil query2.
Derajat Keanggotaan
NIP
NAMA
UMUR
GAJI
MUDA
TINGGI
MUDA atau TINGGI
01
Lia
30
750.000
1
0
1
10
Yoga
25
860.000
1
0
1
08
Kiki
32
550.000
0,8
0
0,8
06
Amir
39
1.600.000
0,1
0,6
0,6
03
Sari
36
1.500.000
0,4
0,5
0,5
09
Alda
35
735.000
0,5
0
0,5
04
Andi
37
1.040.000
0,3
0,04
0,3
07
Rian
37
1.250.000
0,3
0,25
0,3
02
Iwan
48
1.255.000
0
0,255
0,255
05
Budi
42
950.000
0
0
0
Query3:
Siapa saja-kah karyawan yang masih muda tapi masa kerjanya sudah lama?
SELECT NAMA
FROM KARYAWAN
WHERE (Umur = “MUDA”) and (MasaKerja = “LAMA”)
Tabel 7.8 menunjukkan hasil query3, yaitu nama-nama karyawan yang masih muda tapi masakerjanya sudah lama.
Tabel 7.8 Hasil query3.
Derajat Keanggotaan
NIP
NAMA
UMUR
Masa Kerja
MUDA
LAMA
MUDA & LAMA
03
Sari
36
14
0,4
0,267
0,267
06
Amir
39
13
0,1
0,2
0,1
01
Lia
30
6
1
0
0
02
Iwan
48
17
0
0,467
0
147
04
Andi
37
4
0,3
0
0
05
Budi
42
12
0
0,133
0
07
Rian
37
5
0,3
0
0
08
Kiki
32
1
0,8
0
0
09
Alda
35
3
0,5
0
0
10
Yoga
25
2
1
0
0
Query4:
Siapa saja-kah karyawan yang parobaya dan gajinya sedang, atau karyawan yang parobaya tapi masa kerjanya sudah lama?
SELECT NAMA
FROM KARYAWAN
WHERE (Umur = “PAROBAYA”) and
[(Gaji = “SEDANG”) atau (MasaKerja = “LAMA”)]
Tabel 7.9 menunjukkan hasil query4, yaitu nama-nama karyawan yang parobaya dan gajinya sedang, atau karyawan yang parobaya tapi masakerjanya sudah lama.
Tabel 7.9 Hasil query4.
Derajat Keanggotaan
NIP
NAMA
SEDANG
LAMA
SEDANG atau LAMA
PAROBAYA
PAROBAYA & (SEDANG atau LAMA)
05
Budi
0,9
0,133
0,9
0,7
0,7
02
Iwan
0,49
0,467
0,49
0,4
0,4
04
Andi
0,92
0
0,92
0,2
0,2
06
Amir
0
0,2
0,2
0,4
0,2
07
Rian
0,5
0
0,5
0,2
0,2
03
Sari
0
0,267
0,267
0,1
0,1
01
Lia
0,5
0
0,5
0
0
08
Kiki
0
0
0
0
0
09
Alda
0
0
0
0
0
10
Yoga
0
0
0
0
0

148