Animasi Sederhana: Kehidupan di Pekarangan

I. Abstrak
Project ini adalah pembuatan animasi sederhana yang bertema Kehidupan di Pekarangan. Tujuan khusus pada pembuatan animasi sederhana ini adalah untuk menjelaskan cara membuat animasi sederhana menggunakan aplikasi yang ada pada Microsoft Office, yaitu Micosoft Power Point. Pada pembuatan aplikasi ini mencoba untuk menjelaskan kehidupan hewan yang ada disekitar pekarangan, misalnya ada sapi-sapi yang sedang berkumpul, ada ayam yang sedang berkumpul bersama induknya, ada kambing yang sedang asik makan rumput, dan ada pengembala yang sedang bersantai dibawah pohon rindang. Pada pembuatan animasi ini harus memperhatikan ketelitian, kecermatan, serta keserasian dalam pemilihan latar dan audio.

II. Pendahuluan
Animasi berasal dari kata Animation, dalam bahasa inggris 'to animate' yang artinya menggerakkan. Contohnya sebuah benda yang mati lalu digerakkan melalui perubahan sedikit demi sedikit dan teratur, sehingga memberikan kesan hidup. Animasi adala proses penciptaan efek gerak atau efek perubahan bentuk yang terjadi selama beberapa waktu. Animasi juga merupakan suatu teknik menampilkan gambar berurut sedemikian rupa sehingga penonton merasakan adanya ilustrasi gerakan pada gambar yang ditampilkan.
Animasi dapat diintegrasikan ke media lain seperti video, sehingga cocok untuk menjelaskan sebuah cerita pada animasi tersebut. Salah satu perangkat lunak pembuatan animasi sederhana adalah microsoft office yang berguna untuk membuat presentasi dalam bentuk slide dan juga dapat dibuat untuk membuat animasi sederhana dengan menggunakan menu-menu yang telah tersedia.

III. Isi
Pada pembuatan animasi ini yang menggunakan aplikasi Microsoft Power Point tentang Kehidupan di Pekarangan ada proses yang dijalankan, sehingga dapat menjadi sebuah animasi sederhana. Pertama-tama, membuka microsoft word, lalu pada lembar kerja masukkan foto yang ingin dijadikan background sesuai tema yang dipilih. Disini penulis memakai background halaman luas di area pekarangan. Setelah ini masukkan objek-objek yang ingin dimasukkan. Disini penulis menggunakan 7 objek, diantaranya ada sapi, kambing, kerbau, ayam, matahari, burung, dan pengembala. Dan ada 2 gambar yang berformat .gif yang artinya gambar bisa bergerak. Untuk membuat gambar bergerak dan berjalan maka pilih gambar yang ingin digerakkan lalu pada menu bar pilih Animation, lalu Add Animation, selanjutnya pilih More Motion Path, dan silahkan pilih model gerakan mana yang diinginkan. Untuk mengedit objek, pilih Animation Pane lalu muncul kotak Animation Pane, akan ada beberapa picture yang digunakan pilih list yang ada pada picture effect option, maka akan muncul kotak down, ada submenu effect dan timing. Pada effect dapat diatur kecepatan jalannya atau geraknya, dan dapat memilih sound yang sesuai dengan gambar tersebut. Sedangkan pada timing, dapat mengatur start ada pilihan on click yang berarti dapat dijalankan apabila di click dengan mouse, with previous yang artinya jalan bersamaan dengan gambar sebelumnya, after previous artinya berjalan setelah gambar yang sebelumnya. Dapat iatur pula durasi yang diinginkan untuk menampilkan gambar tersebut.

IV. Penutup
Pada pembuatan animasi sederhana ini dapat menggunakan aplikasi apasaja, misalnya dapat menggunakan Flash, Movie Maker, dan lain-lain. Pada kali ini saya menggunakan Microsoft Power Point. Pada Microsoft Power Point ini untuk membuat animasi harus sediakan terlebih dahulu tema yang ingin dibuat, lalu mendownload foto background dan objek yang ingin digunakan, setelah itu pilih sound yang selaras dengan tema yang dibuat. Objek yang digunakan juga harus sesuai dengan gerakan aslinya. Pada pembuatan animasi ini harus memperhatikan ketelitian, kecermatan, keselarasan anatar objek, latar, dan sound.

V. Referensi
http://www.gambaranimasi.org/data/media/234/animasi-bergerak-kambing-0020.gif
http://cd1.dibujos.net/dibujos/pintados/201407/vaca-2-animales-la-granja-pintado-por-ketita-9880957.jpg
Jurnal tentang pembuatan animasi, Pembuatan Film Pendek Action Format 3D Jurnal Media Informatika voll.11 no.1 Februari 2015
http://bestanimations.com/Animals/Birds/Eagles/animated-eagle-gif-9.gif
http://iesjosealcantara.es/tic/paginas/KOMPOZER/ganaderia/gallina2.png
http://clipart-library.com/imager/8iAEnqpbT.png
http://clker.com/cliparts/z/H/B/O/E/L/sun-large-md.png

Studi Kasus : Prolog

Contoh Program Prolog

write(“Program Sederhana Prolog”),nl,nl,

write(“Masukkan nama : “), read(Nama),

write(Nama),nl,

write(“Masukkan kelas : “), read(_kelas),

write(_kelas),nl,nl,

write(“Menghitung Luas Persegi Panjang!”),nl,

write(“Masukkan panjang : “), read(P),

write(P),nl,

write(“Masukkan lebar : “), read(L),

write(L),nl,

LUAS is P*L,

write(“Luas Persegi Panjang = “),

write(LUAS).

Pada saat program di-run , untuk menginput nilai variabel Nama & _kelas  dengan 2 kata atau lebih, pake tanda (“); seperti pada contoh output di bawah, saat menginput nilai untuk variabel Nama yaitu “Aresa Riskiana” , contoh untuk variabel _kelas yaitu “3 IA03”

Bahasa Pemrograman untuk Intelegensi Buatan : Prolog

A. Dasar-Dasar Prolog

Fakta dan Relasi

      Fakta Adalah suatu unit yang selalu bernilai benar,fakta ini merupakan kumpulan data-data objek. Suatu fakta dibedakan dalam 2 jenis, yaitu fakta yang menunjukan relasi dan fakta yang menunjukan milik/sifat, penulisan suatu fakta selalu di akhir dengan (.)

Contoh :

Fakta	Prolog
Slamet adalah ayah Amin	ayah (slamet, amin).
Anita adalah seorang wanita	wanita (anita).
Angga suka renang dan tenis	suka(angga,renang).dan suka(angga,tenis).
Jeruk berwarna jingga	jngga(jeruk).

Aturan (“Rules”)

      Aturan adalah suatu pernyataan yang menunjukan bagaimana fakta-fakta berinteraksi satu dengan yang lain untuk membentuk suatu kesimpulan. Sebuah aturan dinyatakan sebagai suatu kalimat bersyarat. Kata “if” adalah kata yang dikenal Prolog untuk menyatakan kalimat bersyarat atau disimbolkan dengan “:-“.

Contoh :

Fakta dan Aturan	Prolog
F : Tino suka apel A : Yuli suka sesuatu yang disukai Tino	suka(tino, apel). suka(yuli,Sesuatu) :-  suka(tino,Sesuatu).

Pertanyaan (“Query”)

Setelah memberikan data-data berupa fakta dan aturan, selanjutnya kita dapat mengajukan pertanyaan berdasarkan fakta dan aturan yang ada. Penulisannya diawali simbol “?-“ dan diakhiri tanda “.”.

Contoh :

Pertanyaan	Prolog dan Jawaban Program
Apakah Tini suka boneka ?	?- suka(tini,boneka). Yes ……. (jika faktanya Tini suka boneka) No……..…(jika tidak sesuai fakta).
Apakah yang disukai Tini ?	?- suka(tini,Apa). Apa=boneka
Siapakah yang suka boneka ?	?- suka(Siapa,boneka). Siapa=tini
Dari contoh silsilah keluarga di atas : Siapakah kakek Budi ? Siapakah cucu Slamet ?	?- kakek(Siapa,budi). Siapa=slamet ?- kakek(slamet,Cucu). Cucu=budi ; Cucu=badu (jika kemungkinan ada lebih dari satu jawaban gunakan tanda “;” pada akhir setiap jawaban).

B. Struktur Program Prolog

Dalam struktur program prolog terdapat 4 macam di antara nya adalah Domain,Predicate,Variable, dan goal.

Domain

Domain berfungsi untuk menyatakan jenis suatu variabel seperti hal nya tipe data dalam bahasa prosedural (Pascal,C) . beberapa domain standar dalam prolog diantara nya char,integer,real,string,symbol. Contoh :

namaBunga = symbol

mataKuliah = string

nilai = integer

Domains char dipakai pada predikat yang argumennya memiliki nilai berupa karakter tunggal,  yaitu abjad,  angka,  pungtuasi (?.!,<,...), dan operasi (+,‐,...). Penulisan argumen bertipe char dalam prolog diapit tanda ’...’. contoh : nilai (dita, ’A’).

Domains string dipakai pada predikat yang argumennya memiliki nilai berupa karakter jamak yang dapat berupa kata maupun suatu tulisan (kumpulan kata‐kata termasuk di dalamnya pungtuasi dan tanda operasi yang dapat dipisahkan spasi). Penulisan argumen bertipe string dalam prolog diapit tanda ”...”. contoh: hobi(rina,”Memasak”).

Domains integer dipakai pada predikat yang argumennya memiliki nilai berupa bilangan bulat.

Contoh : nilai(tini,”Kalkulus”,75).

Domains real dipakai pada predikat yang argumennya memiliki nilai berupa bilangan pecahan. Penulisan argumen bertipe real dalam prolog untuk nilai pecahan ditulis di belakang tanda titik (.). contoh: nilai(ivan, 8.75).

Domains symbol dipakai pada predikat yang argumennya memiliki nilai berupa kumpulan karakter yang hanya terdiri dari huruf atau kata tanpa dipisahkan oleh spasi. Suatu kata  dapat disambungkan dengan kata lain dengan  tanda _ (underscore). contoh : lelaki(toni_setiawan).

Predicate

Dalam bahasa prolog kita perlu mendeklarasikan predikat yang ada pada bagian Predicates dan mendefinisikannya dalam bagian Clauses. Jika tidak, Prolog tidak akan mengenalnya. Namun untuk predikat standar seperti cursor, makewindow, readln, readchar dsb tidak perlu dideklarasikan.

Misalkan untuk domains seperti di atas dapat dibuat predicates

            Predicates

            menu(integer)

            data(NamaOrang, Alamat, Umur)

Deklarasi predicates dalam bagian predicates, harus disertai argumen jika memang berargumen. Nama predikat harus diawali dengan huruf, boleh besar atau kecil, selebihnya bisa huruf, angka, garis bawah, namun dianjurkan untuk dimulai dengan huruf kecil. Nama predikat tidak boleh mengandung spasi, tanda minus, asteris atau garis miring.

Variable

Variabel merupakan sebuah interpretasi yang digunakan untuk menemukan

nilai dari sebuah klausa. Variabel harus diawali dengan huruf besar.

Contoh : 

  - suka(andi,X) .

            X = eskrim

  - anakperempuan(lila, X).

            X = agus

Variabel yang memiliki beberapa value kamu dapat memunculkan nilai lain dengan

menekan tombol (;)

Deskripsi Rekrusif dari Sebuah Hubungan

Nah ini yang gak kalah penting, Rekursif ini digunakan untuk mencari seluruh dari

child dari sebuah tree. Intinya, misalkan terdapat sebuah keluarga terdapat kakek,

ayah, dan anak. Maka untuk mendapatkan seluruh keturunan dari kakek, yaitu kakek,

ayah, anak, anaknya anak dan seterusnya kita membutuhkan rekursif.

Representasinya seperti berkut

turunan(X,Y) :- antiturunan(Y,X).

turunan(X,Y) :- antiturunan(Y,Z), turunan(X,Z).

Goal

Goal dalam turbo Prolog ada 2 macam yakni :

a. Goal eksternal

b. Goal internal

            Goal eksternal diketikkan langsung pada bagian ‘goal’ : di jendela dialog pada kompiler terpadu Turbo Prolog. dengan cara ini kita hanya bisa menjalankan program dari lingkungan kompiler Turbo Prolog. Untuk dapat dijalankan di lingkungan DOS kita harus menggunakan goal internal yang di simpan pada bagian Goal. Sebenarnya goal inilah yang dicari dan dipanggil pada saat program dijalankan. Jika goal tercapai, program berhenti dengan berhasil, tapi jika sebaliknya, program berhenti dalam keadaan gagal.

Contoh :

            Predicates

                        tulis(string)

            Goal

                        tulis(X),

                        write(X).

            Clauses

                        tulis(“Bandung”).

                        tulis(“Yogya”).

                        tulis(“Jakarta”).

Program ini pertama akan memanggil goalnya, yang terdiri dari sub goal tulis dan write. Ini artinya, goal akan memanggil klausa tulis. Di bagian clauses, terdapat tulis yang berupa fakta. Prolog akan mencarinya dari paling atas, diperoleh tulis(“Bandung”). Ini berarti sub-goal tulis(X) berhasil dengan X terikat dengan nilai “Bandung”. Selanjutnya Prolog membuktikan sub-goal kedua yakni write(X). Ini pasti berhasil dan program berhenti. Jika goal diajukan dari luar (dari jendela Goal, goal internalnya dibuang), kemudian kita tuliskan : tulis(X) [enter], akan tertulis pada layar :

            X = Bandung

            X = Yogya

            X = Jakarta

Penalaran

A. Ketidakpastian

Ketidakpastian dapat dianggap sebagai suatu kekurangan informasi yang memadai untuk membuat suatu keputusan.  Ketidakpastian merupakan suatu permasalahan karena mungkin menghalangi kita membuat suatu keputusan yang terbaik.

Teori-teori yang berhubungan dengan ketidakpastian :

- Probabilitas Klasik

- Probabilitas Bayes

- Teori Hartley yang berdasarkan pada himpunan klasik

- Teori Shanon yang didasarkan pada peluang

- Teori Dempster-Shafer

- Teori Fuzzy Zadeh

Contoh aplikasi yang klasik sistem pakar yang sukses sehubungan dengan ketidakpastian:

- MYCIN untuk diagnosa medis

- PROPECTOR untuk ekplorasi mineral

B. Probabilitas dan Teorema Bayes

Teorema Bayes ditemukan oleh Thomas Bayes. Teorema Bayes kebalikan dari probabilitas kondisional P(A|B) atau disebut posteriori probability, dimana dalam teorema Bayes: state probabilitas dari kejadian awal diberikan untuk melihat kejadian yang mungkin akan terjadi kemudian.

Dari contoh kerusakan disket merk X dan bukan merk X :

·        (6) 75% kemungkinan disket merk X akan rusak dlm 1 tahun adalah.

·        (7) probabilitas disket merk bukan X rusak dalam 1 tahun 50%.

·     Pertanyaannya adalah : kita punya disket dan tidak tahu merk apa, bagaimana probabilitas kerusakannya jika merk X ? Atau merk bukan X ?

·      Diketahui kita diberikan disket rusak, probabilitas merk X dapat diperoleh dari probabilitas kondisional dan hasil (1), (5).

P(X | C) = P(C Ç X) = 0.6   = 6

                             P(C)      0.7       7

·        Alternatif lain, menggunakan Hukum Multiplicative (1), (3), (6).

P(X | C) = P(C|X) P(X) = (0.75) (0.8) = 0.6  = 6
                     P(C)                0.7            0.7    7 

C. Faktor Kepastian (Certainty Factor)

Faktor kepastian merupakan cara dari penggabungan kepercayaan (belief) dan ketidapercayaan (unbelief) dalam bilangan yang tunggal. Dalam certainty theory, data-data kualitatif direpresentasikan sebagai derajat keyakinan (degree of belief).

Tahapan Representasi Data Kualitatif :

1.     Kemampuan untuk mengekspresikan derajat keyakinan sesuai dengan metode yang sudah dibahas sebelumnya.

2.     Kemampuan untuk menempatkan dan mengkombinasikan derajat keyakinan tersebut dalam sistem pakar

Dalam mengekspresikan derajat keyakinan digunakan suatu nilai yang disebut certainy factor (CF) untuk mengasumsikan derajat keyakinan seorang pakar terhadap suatu data.

D. Teori Dempster-Shafer

Teori Dempster-Shafer adalah suatu teori matematika untuk pembuktian berdasarkan belief functions and plausible reasoning (fungsi kepercayaan dan pemikiran yang masuk akal), yang digunakan untuk mengkombinasikan potongan informasi yang terpisah (bukti) untuk mengkalkulasi kemungkinan dari suatu peristiwa. Teori ini dikembangkan oleh Arthur P. Dempster dan Glenn Shafer.

Secara umum Teori Dempster-Shafer ditulis dalam suatu interval:

[Belief,Plausibility]

Belief

Belief (Bel) adalah ukuran kekuatan evidence (gejala) dalam mendukung suatu himpunan bagian. Jika bernilai 0 maka mengindikasikan bahwa tidak ada evidence, dan jika bernilai 1 menunjukan adanya kepastian.

Plausibility

Plausibility (Pl) dinotasikan sebagai:

Pl(s)= 1 – Bel(¬­­­­­­­­­s)­­­­­­­

Plausibility juga bernilai 0 sampai 1. Jika kita yakin akan –s, maka dapat dikatakan bahwa Bel(¬s)=1, dan Pl(¬s)=0. Plausability akan mengurangi tingkat kepercayaan dari evidence. Pada teori Dempster-Shafer kita mengenal adanya frame of discernment yang dinotasikan dengan θ dan mass function yang dinotasikan dengan m. Frame ini merupakan semesta pembicaraan dari sekumpulan hipotesis sehingga disebut dengan environtment.

Misalkan: θ = {A, B, C, D, E, F, G, H, I, J}
Dengan :
A   = Gagal Ginjal Kronik
B   = Kanker Ginjal
C   = Pielonefritis
D   = Sindroma Nefrotik
E    = Hidronefrosis
F    = Kanker Kandung Kemih
G   = Ginjal Polikista
H   = Nefritis Tubulointerstisialis
I     = Sistitis
J     = Infeksi Saluran Kemih

Mass Function

Sedangkan mass function (m) dalam teori Dempster-Shafer adalah tingkat kepercayaan dari suatu evidence measure sehingga dinotasikan dengan (m). Untuk mengatasi sejumlah evidence pada teori Dempster-Shafer menggunakan aturan yang lebih dikenal dengan Dempster’s Rule of Combination.

Inferensi dalam Logika Order Pertama

A. Mengubah Inferensi Order Pertama menjadi Inferensi Proposisi
------------------------------------------
Representasi 4 kategori silogisme menggunakan logika predikat

Kaidah universal Instation merupakan state dasar, dimana suatu individual dapat digantikan kedalam sifat universal.

• Contoh :

Misal, φ merupakan fungsi proposisi :

(∀ x) φ(x)

∴ φ(a)

merupakan bentuk yang valid, dimana a menunjukkan spesifik individual, sedangkan x adalah suatu variabel yang berada dalam jangkauan semua individu (universal)

• Contoh lain : (∀ x) H(x)

∴ H(Socrates)

• Berikut ini adalah contoh pembuktian formal silogisme

All men are mortal

Socrates is a man

Therefore, Socrates is mortal

Misal : H = man, M = mortal, s = Socrates

1. (∀ x) (H (x) -> M(x))

2. H(s) / ∴ M(s)

3. H(s) -> M(s) 1 Universal Instatiation

4. M(s) 2,3 Modus Ponens

B. Unifikasi

--------------------

Unifikasi adalah usaha untuk mencoba membuat dua ekspresi menjadi identik (mempersatukan keduanya) dengan mencari substitusi-substitusi tertentu untuk mengikuti peubah-peubah dalam ekspresi mereka tersebut. Unifikasi merupakan suatu prosedur sistematik untuk memperoleh peubah-peubah instan dalam wffs. Ketika nilai kebenaran predikat adalah sebuah fungsi dari nilai-nilai yang diasumsikan dengan argumen mereka, keinstanan terkontrol dari nilai-nilai selanjutnya yang menyediakan cara memvalidasi nilai-nilai kebenaran pernyataan yang berisi predikat. Unifikasi merupakan dasar atas kebanyakan strategi inferensi dalam Kecerdasan Buatan. Sedangkan dasar dari unifikasi adalah substitusi.

      Suatu substitusi (substitution) adalah suatu himpunan penetapan istilah-istilah kepada peubah, tanpa ada peubah yang ditetapkan lebih dari satu istilah. Sebagai pengetahuan jantung dari eksekusi Prolog, adalah mekanisme unifikasi.

Aturan-aturan unifikasi :

1.      Dua atom (konstanta atau peubah) adalah identik.

2.      Dua daftar identik, atau ekspresi dikonversi ke dalam satu buah daftar.

3.      Sebuah konstanta dan satu peubah terikat dipersatukan, sehingga peubah menjadi terikat kepada konstanta.

4.      Sebuah peubah tak terikat dipersatukan dengan sebuah peubah terikat.

5.      Sebuah peubah terikat dipersatukan dengan sebuah konstanta jika pengikatan pada peubah terikat dengan konstanta tidak ada konflik.

6.      Dua peubah tidak terikat disatukan. Jika peubah yang satu lainnya menjadi terikat dalam upa-urutan langkah unifikasi, yang lainnya juga menjadi terikat ke atom yang sama (peubah atau konstanta).

7.      Dua peubah terikat disatukan jika keduanya terikat (mungkin melalui pengikatan tengah) ke atom yang sama (peubah atau konstanta).

C. Generalized Modus Ponens (GMP)

----------------------------------------------------------

Dalam logika Boolean, dengan aturan `` JIKA X adalah A THEN Y adalah B '', proposisi X adalah A harus diamati untuk mempertimbangkan proposisi Yadalah B. Dalam logika fuzzy, proposisi `` X adalah A' '', Dekat dengan premis `` X adalah A '' dapat diamati untuk memberikan kesimpulan `` Y adalah B' '' Dekat dengan kesimpulan `` Y adalah B '' . Sebuah inferensi fuzzy sederhana dapat direpresentasikan sebagai :

Aturan	: JIKA	X adalah A THEN	Y adalah B
Fakta	:	X adalah A'
Kesimpulan	:		Y adalah B'

Untuk menyimpulkan seperti inferensi fuzzy kita menggunakan mekanisme yang disebut umum modus ponens. Di sini, kita menggunakan salah satu berdasarkan implikasi fuzzy Brouwer-Gödel diungkapkan oleh:

Catatan:
Asumsikan --> operator implikasi Brouwer-Godel dan operator kombinasi, rumus dapat dinyatakan dengan B' = Ao(A-->B) yang kita gunakan sekarang untuk menyederhanakan notasi

D. Rangkaian Forward and Backward Chaining

-------------------------------------------------------------
Forward Chaining :
Suatu rantai yang dicari atau dilewati/dilintasi dari suatu permasalahn untuk memperoleh solusi. Penalaran dari fakta menuju konklusi yang terdapat dari fakta
Backward Chaining :
Suatu rantai yang dilintasi dari suatu hipotesa kembali ke fakta yang mendukung hipotesa tersebut.

·         Tujuan yang dapat dipenuhi dengan pemenuhan sub tujuannya.

 Karakteristik Forward dan Backward chaining :

Forward chaining	Backward chaining
Perencanaan, monitoring, kontrol	Diagnosis
Disajkan untuk masa depan	Disajikan untuk masa lalu
Antecedent ke konsekuen	Konsekuen ke antecedent
Data memandu, penalaran dari bawah ke atas	Tujuan memandu, penalaran dari atas ke bawah
Bekerja ke depan untuk mendapatkan solusi apa yang mengikuti fakta	Bekerja ke belakang untuk mendapatkan fakta yang mendukung hipotesis
Breadth first search dimudahkan	Depth first search dimudahkan
Antecedent menentukan pencarian	Konsekuen menentukan pencarian
Penjelasan tidak difasilitasi	Penjelasan difasilitasi

Contoh Metode Pencarian dan Pelacakan

Contoh Generate & Test

Di sini akan dibahas mengenail solusi TSP dengan algoritma Generate & Test (GT). Pada prinsipnya, algoritma ini meng-generate sebuah kandidat solusi, lalu dites apakah kandidat tersebut solusi yang dicari. Iterasi berhenti jika solusi sudah ditemukan.

Tetapi untuk menyelesaikan kasus TSP ini, algoritma tersebut mengalami sedikit modifikasi, di mana iterasinya akan berhenti setelah semua kandidat solusi telah dites untuk menghasilkan solusi yang optimal.

Rute dikatakan valid jika jalur yang dilalui tidak berjarak 0. Jika rute valid, maka jarak dihitung lalu dibandingkan untuk mendapatkan jarak yang paling optimal.

Setiap rute yang valid akan dibandingkan dengan rute valid lainnya guna mendapatkan rute terpendek yang merupakan solusi dari kasus TSP-nya. Yang dalam hal ini dipecahkan menggunakan algoritma Generate & Test.

Kelebihan dari algoritma ini adalah pencariannya yang lengkap dan selalu menghasilkan solusi yang optimal. Sedangkan kekurangannya adalah tidak cocok untuk data yang besar/banyak dan waktu pencariannya yang lama sesuai dengan banyak datanya.

Sistem Cerdas

Metode Pencarian dan Pelacakan 2 (Heuristik)
PENCARIAN TERBAIK PERTAMA (Best-First Search)
Metode ini merupakan kombinasi dari metode depth-first search dan breadth-first search. Pada metode best-first search, pencarian diperbolehkan mengunjungi node yang ada dilevel yang lebih rendah, jika ternyata node pada level yang lebih tinggi ternyata memiliki nilai heuristic yang lebih buruk.

Fungsi Heuristikcyang digunakan merupakan prakiraan (estimasi) cost dari initial stateke goal state, yang dinyatakan dengan :
                f’(n) = g(n) + h’(n)
dimana f’= Fungsi evaluasi
    g = cost dari initial stateke current state
    h’= prakiraan cost dari current state ke goal state

Contoh.
Misalkan kita memiliki ruang pencarian seperti pada gambar berikut.
Node M merupakan keadaan awal dan node T merupakan tujuannya. Biaya edge yang menghubungkan node M dengan node A adalah biaya yang dikeluarkan untuk bergerak dari kota M ke kota A. Nilai g diperoleh berdasarkan biaya edge minimal. Sedangkan nilai h’ dinode A merupakan hasil perkiraan terhadap biaya yang diperlukan dari node A untuk sampai ke tujuan. h’(n) bernilai ~ jika sudah jelas tidak ada hubungan antara node n dengan node tujuan (jalan buntu). Kita bisa merunut nilai untuk setiap node.

REDUKSI MASALAH

• Kebanyakan solusi menggunakan pohon OR, dimana lintasan dari awal sampai tujuan tidak terletak pada satu cabang.
• Bila lintasan dari keadaan awal sampai tujuan dapat terletak pada satu cabang, maka kita akan dapat menemukan tujuan lebih cepat.
• Graf AND-OR
• Graf AO*

CONSTRAINT SATISFICATION
Problem search standard :
  - state adalah"black box“ – setiap struktur data yang mendukung fungsi successor, fungsi heuristik dan tes goal.
CSP :
  - state didefinisikan sebagai variabel Xi dengan nilai dari domain Di
  - Tesgoal adalah sekumpulan constraint yang menspesifikasikan kombinasi dari nilai subset variabel.
Contoh sederhana adalah bahasa representasi formal.
CSP ini merupakan algoritma general-purpose dengan kekuatan lebih daripada algoritma pencarian standar.

Constraint Graf

• Binary CSP biner: setiap constraint merelasikan dua variabel
• Graf Constraint : node adalah variabel, arc adalah constraint

MEA (Means-Ends Analysis)

• MEA adalah strategi penyelesaian masalah yang diperkenalkan pertama kali dalam GPS (General Problem Solver) [Newell & Simon, 1963].
• Proses pencarian berdasarkan ruang masalah yang menggabungkan aspek penalaran forward dan back ward.
• Perbedaan antara state current dan goal digunakan untuk mengusulkan operator yang mengurangi perbedaan itu.
• Keterhubungan antara operator dan perbedaan tsb disajikan sebagai pengetahuan dalam sistem (pada GPS dikenal dengan Table of Connections) atau mungkin ditentukan sampai beberapa pemeriksaan operator jika tindakan operator dapat dipenetrasi.
• Contoh OPERATOR first-order predicate calculus dan operator 2 tertentu mengijinkan perbedaan korelasitask-independent terhadap operator yang menguranginya.
• Kapan pengetahuan ada tersedia mengenai pentingnya perbedaan, perbedaan yang paling utama terpilih pertama lebih lanjut meningkatkan rata-rata capaian dari MEA diatas strategi pencarian Brute-Force.
• Bagaimanapun, bahkan tanpa pemesanan dari perbedaan menurut arti penting, MEA meningkatkan metode pencarian heuristik lain (dirata-rata kasus) dengan pemusatan pemecahan masalah pada perbedaan yang nyata antara current state dengan goal-nya.

REPRESENTASI PENGETAHUAN
Pengetahuan (Knowledge) :
   - Definisi umum : fakta atau kondisi sesuatu atau keadaan yang timbul karena suatu pengalaman.
   - Cabang ilmu filsafat, yaitu Epistemology, berkenaan dengan sifat, struktur dan keaslian dari knowledge.

Priori Knowledge :

• Berarti yang mendahului (pengetahuan datang sebelumnya dan bebas dari arti)
• Kebenaran yang universal dan tidak dapat disangkal tanpa kontradiksi
• Contoh : pernyataan logika, hukum matematika

Posteriori Knowledge :

• Knowledge yang diturunkan dari akal pikiran yang sehat.
• Kebenaran atau kesalahan dapat dibuktikan dengan menggunakan pengalaman akal sehat.
• Contoh : bola mata seseorang berwarna biru, tetapi ketika orang tersebut mengganti contact lens-nya, bisa jadi bola matanya menjadi berwarna hijau.

Kategori Knowledge :

• Procedural Knowledge : Bagaimana melakukan sesuatu
• Declarative Knowledge : Mengetahui sesuatu itu benar atau salah
• Tacit Knowledge : Tidak dapat diungkapkan dengan bahasa

Knowledge pada ES :

• Analogi dengan ekpresi klasik Wirth : ALGORITMA + STRUKTUR DATA = PROGRAM
• Knowledge pada ES : KNOWLEDGE + INFERENSI = ES

Teknik Representasi Pengetahuan :
  1) Aturan Produksi
  2) Jaringan Semantik
  3) Frame dan Scemata
  4) Logic

ATURAN PRODUKSI
Sering digunakan untuk merepresentasikan pengetahuan pada ES.
Bentuk formalnya Backus-Naus Form (BNF) :
  - metalanguange untuk mendefinisikan sintaks bahasa
  - suatu grammar haruslah lengkap dan unambiguous set dari aturan produksi untuk bahasa yang spesifik
  - arse tree adalah representasi grafis dari kalimat pada suatu bahasa
  - deskripsi sintaks tersedia dalam bahasa
  - tidak semua kalimat adalah benar

Contoh :
 <sentence> ::= <subject> <verb> <end-mark> dimana,
    < .. > dan ::= adalah symbol metalanguange.
    ::= artinya “ditentukan sebagai” yang dalam BNF ekuivalen dengan -->
 Term di dalam kurung disebut symbol Nonterminal, yang masih bisa direpresentasikan ke dalam bentuk lebih sederhana lagi.
  Nonterminal yang tidak dapat disederhanakan lagi disebut Terminal.

   <sentence> à <subject> <verb> <end-mark>
   <subject> à I | You | We
   <verb> à left | came
   <end-mark>à . | ? | !

Produksinya :
    I left.
   You came?
   We left ! dst…..
Contoh :
   <sentence>à<subject phrase><verb><object phrase>
   <subject phrase>à<determiner><noun>
   <object phrase>à<determiner><adjective><noun>
   <determiner>à a | an | the | this | these | those
   <noun> à man | eater
   <verb> à is | was
   <adjective> dessert | heavy

JARINGAN SEMANTIK
Dibangun oleh M.R.Quillian, sebagai model memori manusia.
  - Representasi grafis dari informasi Propositional.
  - Proposisi adalah pernyataan yang dapat bernilai benar atau salah.
  - Disajikan dalam bentuk graf berarah
  - Node merepresentasikan konsep, objek atau situasi :
      a. Label ditunjukkan melalui penamaan
      b. Node dapat berupa objek tunggal atau kelas
- Links merepresentasikan suatu hubungan :
     a. Links adalah struktur dasar untuk pengorganisasian pengetahuan
     b. Contoh jaringan semantic.

SCHEMATA  :  FRAME & SCRIPT
A. FRAME
Frame (Minsky, 1975) dipandang sebagai struktur data static yang digunakan untuk merepsentasi-kan situasi-situasi yang telah dipahami dan stereotype. Frame digunakan untuk merepresentasikan pengetahuan stereotype atau pengetahuan yang didasarkan kepada karakteristik yang sudah dikenal yang merupakan pengalaman masa lalu. Frame berupa kumpulan slot-slot (representasi entitas sebagai struktru objek) yang merupakan atribut untuk mendeskripsikan pengetahuan berupa kejadian, lokasi, situasi ataupun elemen-elemen lain. Frame digunakan untuk representasi pengetahuan deklaratif.

Contoh 1 :
Frame Pohon
  - Spesialisasi dari : Tumbuhan
  - Jumlah batang : integer (default 1)
  - Jenis kulit : halus
 - Model daun : jenis pohon jarum, berganti daun
  - Bentuk daun : sederhana, berlekuk, campuran

Frame Pohon Perdu
  - Spesialisasi dari : Pohon
  - Jumlah batang : 3
  - Jenis kulit : halus
  - Model daun : berganti daun
  - Bentuk daun : sederhana, berlekuk

Contoh 2 : Deskripsi frame untuk kamar hotel.

Setiap frame individual dapat dipandang sebagai struktur data yang mirip record, berisi informasi yang relevan dengan entitas-entitas stereotype.
Slot-slot dalam frame dapat berisi :
  - Informasi identifikasi frame
  - Hubungan frame dengan frame lain
  - Penggambaran persyaratan yang dibutuhkan frame
  - Informasi procedural untuk menggunakan struktur yang digambarkan
  - Informasi default frame
  - Informasi terbaru.

B. SCRIPT
Script (Schank & Abelson, Yale univ) merupakan representasi terstruktur yang menggambarkan urutan stereotip dari kejadian-kejadian dalam sebuah konteks khusus. Script mirip dengan frame, perbedaannya : Frame menggambarkan objek, sedangkan Script menggambarkan urutan peristiwa. Dalam menggambarkan urutan peristiwa, script menggunakan serangkaian slot yang berisi informasi tentang orang, objek dan tindakan-tindakan yang terjadi dalam suatu peristiwa.
Elemen script yang tipikal :
  - Kondisi masukan : menggambarkan situasi yang harus dipenuhi sebelum terjadi suatu peristiwa yang ada dalam script.
  - Prop : mengacu kepada objek yang digunakan dalam urutan peristiwa yang terjadi.
  - Role : mengacu kepada orang-orang yang terlibat dalam script.
  - Hasil : kondisi yang ada sesudah peristiwa dalam script berlangsung.
  - Track : mengacu kepada variasi yang mungkin terjadi dalam script tertentu.
  - Scene : menggambarkan urutan peristiwa aktural yang terjadi.

Contoh : Script pergi ke restoran
SCRIPT Restoran
  - Jalur (track) : fast food restoran
  - Peran (roles) : tamu, pelayan
  - Pendukung (prop): conter, baki, makanan, uang, serbet, garam, merica, kecap, sedotan, dll
  - Kondisi masukan : tamu lapar – tamu punya uang

Adegan (scene) 1 : Masuk
  - Tamu parkir mobil
  - Tamu masuk restoran
  - Tamu antri
  - Tamu baca menu di list menu dan mengambil keputusan tentang apa yang akan diminta.

Adegan (scene) 2 : Pesanan
  - Tamu memberikan pesanan pada pelayan
  - Pelayan mengambil pesanan dan meletakkan makanan di atas baki
  - Tamu membayar

Adegan (scene) 3 : Makan
  - Tamu mengambil serbet, sedotan, garam, dll
  - Tamu makan dengan cepat

Adegan (scene) 4 : Pulang
  - Tamu membersihkan meja
  - Tamu membuang sampah
  - Tamu meninggalkan restoran
  - Tamu naik mobil dan pulang

Hasil
  - Tamu merasa kenyang
  - Tamu senang
  - Tamu kecewa
  - Tamu sakit perut

Keistimewaan Script :
1. Script menyediakan beberapa cara yang sangat alami untuk merepresentasikan “suatu inforamsi” yang lazim” dengan masalah yang bersumber dari sistem AI dari mula.
2. Script menyediakan struktur hirarki untuk merepresentasikan inforamsi melalui inklusi subscript dengan sript.

Representasi Pengetahuan : Logika Proposisi
A. Logika dan Set

Representasi pengetahuan dengan symbol logika merupakan bagian dari penalaran eksak. Bagian yang paling penting dalam penalaran adalah mengambil kesimpulan dari premis. Logika dikembangkan oleh filusuf Yunani, Aristoteles (abad ke 4 SM) didasarkan pada silogisme, dengan dua premis dan satu konklusi.

Contoh :            

– Premis : Semua wanita adalah makhluk hidup

– Premis : Dewi adalah Wanita

– Konklusi : Dewi adalah makhluk hidup

Cara lain merepresentasikan pengetahuan adalah dengan Diagram Venn.

Diagram Venn merepresentasikan sebuah himpunan yang merupakan kumpulan objek. Objek dalam himpunan disebut elemen.

A ={1,3,5,7} ,  B = {….,-4,-2,0,2,4,…..} ,  C = {pesawat, balon}

Symbol epsilon ε menunjukkan bahwa suatu elemen merupakan anggota dari suatu himpunan, contoh : 1 ε A . Jika suatu elemen bukan anggota dari suatu himpunan maka symbol yang digunakan ∉, contoh : 2 ∉ A. Jika suatu himpunan sembarang, misal X dan Y didefinisikan bahwa setiap elemen X merupakan elemen Y, maka X adalah subset dari Y, dituliskan : X ⊂ Y atau Y ⊃ X.

Operasi-operasi Dasar dalam Diagram Venn:

   – Interseksi (Irisan)

         C = A ∩ B C = {x ∈ U | (x ∈ A) ∧ (x ∈ B)}

         Dimana : ∩ menyatakan irisan himpunan | dibaca “sedemikian hingga” ∧ operator logika AND

   – Union (Gabungan)

         C = A ∪ B C = {x ∈ U | (x ∈ A) ∨ (x ∈ B)}

         Dimana : ∪ menyatakan gabungan himpunan ∨ operator logika OR

   – Komplemen

         A’ = {x ∈ U | ~(x ∈ A) }

         Dimana : ’ menyatakan komplemen himpunan ~ operator logika NOT

B. Operator Logika 

Operator Boolean atau Operator Logika adalah operator yang digunakan untuk melakukan operasi logika yaitu operator yang menghasilkan nilai TRUE (benar) atau FALSE (salah).
Bebarapa macam operator logika antara lain:

1. and : menghasilkan nilai TRUE jika kedua operand bernilai TRUE
2. or : menghasilkan nilai TRUE jika salah satu operand bernilai TRUE
3. xor : menghasilkan nilai TRUE jika salah satu operand bernilai TRUE tetapi bukan keduaduanya bernilai TRUE
4. ! : mengasilkan nilai tidak TRUE
5. && : menghasilkan nilai TRUE jika kedua operand bernilai TRUE
6. || : menghasilkan nilai TRUE jika salah satu operand bernailai TRUE

C. Tautologi, Kontradiksi dan Contingent

Tautologi

Tautologi adalahsuatu ekspresi logika yang selalu bernilai benar di dalam tabel kebenarannya, tanpa memperdulikan nilai kebenaran dari proposisi-proposisi yang berada didalamnya.

Contoh :

a. ((p => q) ʌ (r => q)) => ((p v r) =>q
b. (p ʌ  ~q) => p

Kontradiksi

Adalah Suatu ekspresi logika yang selalu bernilai salah di dalam tabel kebenarannya, tanpa memperdulikan nilai kebenarannya dari proposisi-proposisi yang berada di dalamnya.

Contoh : (p ʌ ~p)

Contigent

Adalah Suatu ekspresi logika yang mempunyai nilai benar dan salah di dalam tabel kebenarannya, tanpa mempedulikan nilai kebenaran dari proposisi-proposisi yang berada di dalamnya.

D. Resolusi Logika Proporsi

Logika Proposisi disebut juga kalkulus proposisi yang merupakan logika simbolik untuk memanipulasi proposisi. Proposisi merupakan pernytaan yang dapat bernilai benar atau salah.

Operator logika yang digunakan :

Representasi Pengetahuan : Logika Predikat
A. Logika Predikat Set Order Pertama
Disebut juga kalkulus predikat, merupakan logika yang digunakan untuk merepresentasikan masalah yang tidak dapat direpresentasikan dengan menggunakan proposisi. Logika predikat dapat memberikan representasi fakat-fakta sebagai suatu pernyataan yang mapan (well form).

Syarat-syarat symbol dalam logika predikat :
  - Himpunan huruf, baik huruf kecil maupun huruf besar dalam abjad.
  - Himpunan digit (angka) 0,1,2,…9
  - Garis bawah “_”
  - Symbol-simbol dalam logika predikat dimulai dengan sebuah huruf dan diikuti oleh sembarang rangkaian karakter-karakter yang diijinkan.
  - Symbol-simbol logika predikat dapat merepresentasikan variable, konstanta, fungsi atau predikat

1. Konstanta: objek atau sifat dari semesta pembicaraan. Penulisannya diawali dengan huruf kecil, seperti pohon, tinggi. Konstanta true(benar) dan false(salah) adalah symbol kebenaran (truth symbol).
2. Variable : digunakan untuk merancang kelas objek atau sifat-sifat secara umum dalam semesta pembicaraan. Penulisannya diawali dengan huruf besar, seperti : Bill, Kate.
3. Fungsi : pemetaan (mapping) dari satu atau lebih elemen dalam suatu himpunan yang disebut domainfungsi ke dalam sebuah elemen unik pada himpunan lain yang disebut rangefungsi. Penulisannya dimulai dengan huruf kecil. Suatu ekspresi fungsi merupakan symbol fungsi yang diikuti argument.
4. Argument adalah elemen-elemen dari fungsi, ditulis diapit tanda kurung dan dipisahkan dengan tanda koma.
5. Predikat: menamai hubungan antara nol atau lebih objek dalam semesta pembicaraan. Penulisannya dimulai dengan huruf kecil, seperti : equals, sama dengan, likes, near.

Contoh kalimat dasar :
  teman(george,allen)
  teman(ayah_dari(david),ayah_dari(andrew))
    dimana :
    argument : ayah_dari(david) adalah george
    argument : ayah_dari(andrew) adalah allen
    predikat : teman

B. Universal Quantifier 
• Menunjukkan semua kalimat adalah benar untuk semua nilai variabelnya.
• Direpresentasikan dengan symbol ∀ diikuti satu atau lebih argument untuk suatu domain variable.
• Symbol ∀ diinterpretasikan “untuk setiap ”atau “ untuk semua”.

Contoh 1 :
(∀x) (x + x = 2x)
“untuk setiap x (dimana x adalah suatu bilangan),
kalimat x + x = 2x adalah benar.”

Contoh 2 :
(∀x) (p) (Jika x adalah seekor kucing 􀃆x adalah binatang)
Kebalikan kalimat “bukan kucing adalah binantang” ditulis : (∀x) (p) (Jika x adalah seekor kucing 􀃆~x adalah binatang)
dan dibaca : -“setiap kucing adalah bukan binantang”
-“semua kucing adalah bukan binantang”

C. Existensial Quantifier
• Menunjukkan semua kalimat adalah benar untuk suatu nilai tertentu dalam sebuah domain.
• Direpresentasikan dengan symbol ∃diikuti satu atau lebih argument.
• Symbol ∃diinterpretasikan “terdapat”atau “ada”, “paling sedikit satu”,“terdapat satu”, “beberapa”.

Contoh 1 :
(∃x) (x . x = 1)
Dibaca : “terdapat x yang bila dikalikan dengan dirinya sendiri hasilnya sama dengan 1.”

Contoh 2 :
(∃x) (gajah(x) ∧nama(Clyde))
Dibaca : “beberapa gajah bernama Clyde”.

Contoh 3 :
(∀x) (gajah(x) 􀃆berkaki empat(x))
Dibaca : “semua gajah berkaki empat”.
Universal quantifier dapat diekspresikan sebagai konjungsi.
(∃x) (gajah(x) ∧berkaki tiga(x))
Dibaca : “ada gajah yang berkaki tiga”

• Existensial quantifier dapat diekspresikan sebagai disjungsi dari urutan ai. P(a1) ∨P(a2) ∨P(a3) …∨P(aN)

D. Resolusi Logika Predikat

Resolusi pada logika predikat pada dasarnya sama dengan resolusi pada logika proposisi, hanya saja ditambah dengan unufikasi. Pada logika predikat, prosedur untuk membuktikan pernyataan P dengan beberapa pernyataan F yang telah diketahui, dengan menggunakan resolusi, dapat dilakukan melalui algoritma sebagai berikut:

1. Konversikan semua proposisi F ke bentuk klausa.
2. Negasikan P, dan konversikan hasil negasi tersebut ke bentuk klausa. Tambahkan ke himpunan klausa yang telah ada pada langkah 1.
3. Kerjakan hingga terjadi kontradiksi atau proses tidak mengalami kemajuan :
    a. Seleksi 2 klausa sebagai klausa parent.
    b. Bandingkan (resolve) secara bersama-sama. Klausa hasil resolve tersebut dinamakan resolvent. Jika ada pasangan literal T1 dan T2 sedemikian hingga keduanya dapat dilakukan unifikasi, maka salah satu T1 atau T2 tidak muncul lagi dalam resolvent. T1 dan T2 disebut sebagai complementary literal. Jika ada lebih dari 1 complementary literal, maka hanya sepasang yang dapat meninggalkan resolvent.
   c. Jika resolvent berupa klausa kosong, maka ditemukan kontradiksi. Jika tidak, tambahkan ke himpunan klausa yang telah ada.

Contoh :
Misalkan terdapat pernyataan-pernyataan sebagai berikut :
1. Andi adalah seorang mahasiswa.
2. Andi masuk Jurusan Elektro.
3. Setiap mahasiswa elektro pasti mahasiswa teknik.
4. Kalkulus adalah matakuliah yang sulit.
5. Setiap mahasiswa teknik pasti akan suka kalkulus atau akan membencinya.
6. Setiap mahasiswa pasti akan suka terhadap suatu matakuliah.
7. Mahasiswa yang tidak pernah hadir pada kuliah matakuliah sulit, maka mereka pasti tidak suka terhadap matakuliah tersebut.
8. Andi tidak pernah hadir kuliah matakuliah kalkulus.
Kedelapan pernyataan di atas dapat dibawa ke bentuk logika predikat, dengan menggunakan operator-operator logika predikat, sebagai berikut :
9. mahasiswa(Andi).
10. Elektro(Andi).
11. ∀x:Elektro(x)→Teknik(x).
12. sulit(Kalkulus).
13. ∀x:Teknik(x) → suka(x,Kalkulus) ∨ benci(x,Kalkulus).
14. ∀x:∃y:suka(x,y).
15. ∀x:∀y:mahasiswa(x)∧sulit(y) ∧ ￢hadir(x,y)→ ￢suka(x,y).
16. ￢hadir(Andi,Kalkulus).

Kita dapat membawa pernyataan-pernyataan yang ada menjadi bentuk klausa (CNF) sebagai berikut:
1. mahasiswa(Andi).
2. Elektro(Andi).
3. ￢Elektro(x1) ∨ Teknik(x1).
4. sulit(Kalkulus).
5. ￢Teknik(x2) ∨ suka(x2,Kalkulus) ∨ benci(x2,Kalkulus).
6. suka(x3,fl(x3)).
7. ￢mahasiswa(x4) ∨ ￢sulit(y1) ∨ hadir(x4,y1) ∨ ￢suka(x4,y1).
8. ￢hadir(Andi,Kalkulus).
Apabila ingin dibuktikan apakah Andi benci kalkulus, maka kita bisa lakukan dengan membuktikan : (dibuktikan dalam gambar paling atas)