Puspa Riri: Juni 2018

Kamis, 07 Juni 2018

KONVERSI INFLIX KE POSTFIX

Ada tiga bentuk penulisan notasi matematis di komputer, satu bentuk adalah yang umum digunakan manusia (sebagai input di komputer) yaitu infix, dan dua yang digunakan oleh komputer (sebagai proses), yaitu postfix dan infix. Berikut contoh-contohnya:

No.	*Infix*	*Postfix*	*Prefix*
1.	A + B	A B +	+ A B
2.	(A + B) * C	A B + C *	* + A B C
3.	A * ( B + C)	A B C + *	* A + B C

1. Konversi Infix ke Postfix

Untuk mengetahui bentuk postfix dari notasi infix, ada tiga cara yang dapat dilakukan, yaitu

(1) manual dan (2) stack. Berikut contoh notasi infixnya: A * ( B + C ) / D ^ E –F

1.a. Cara Manual

Caranya adalah dengan menyederhanakan notasi menjadi dua operand (variabel) dan satu operator, seperti A + B.

Langkah 1: tentukan (berdasarkan derajat operasi) mana yang akan diproses terlebih dulu. Diperoleh ( B + C ). Jika ( B + C ) dianggap G, maka notasi infix tadi menjadi: A * G / D ^ E – F

Langkah 2: dari hasil langkah 1, disederhanakan lagi, kali ini ((berdasarkan derajat operasi) akan disederhanakan D ^ E. Bila D ^ E dianggap H, maka notasi infix tadi menjadi: A * G / H – F

Langkah 3: dari hasil langkah 2, disederhanakan lagi, kali ini ((berdasarkan derajat operasi) akan disederhanakan A * G. Bila A* G dianggap I, maka notasi infix tadi menjadi: I / H – F

Langkah 4: dari hasil langkah 3, disederhanakan lagi, kali ini ((berdasarkan derajat operasi) akan disederhanakan I / H. Bila I / H dianggap J, maka notasi infix tadi menjadi: J – F

Setelah diperoleh bentuk seperti itu, maka satu per satu kita kembalikan ke notasi semula sambil mengubahnya menjadi notasi postfix.

Langkah 5: hasil akhir J – F, dibentuk postfixnya, menjadi J F –

Langkah 6: J sebenarnya adalah I / H yang jika ditulis dalam bentuk postfix menjadi I H /,

lalu kita gabung dengan hasil di langkah 5 tadi, diperoleh: I H / F -

Langkah 7: H sebenarnya adalah D ^ E yang jika ditulis dalam bentuk postfix menjadi D E ^,

lalu kita gabung dengan hasil di langkah 6 tadi, diperoleh: I D E ^ / F –

Langkah 8: I sebenarnya adalah A * G yang jika ditulis dalam bentuk postfix menjadi A G *,

lalu kita gabung dengan hasil di langkah 7 tadi, diperoleh: A G * D E ^ / F –

Langkah 9: G sebenarnya adalah B + C yang jika ditulis dalam bentuk postfix menjadi B C +,

lalu kita gabung dengan hasil di langkah 8 tadi, diperoleh: A B C + * D E ^ / F –

Dengan demikian, untuk notasi infix: A * ( B + C ) / D ^ E – F maka notasi postfixnya

menjadi: A B C + * D E ^ / F –

Postfix tidak memerlukan tanda kurung, prosesnya berjalan sebagai berikut:

2 3 5 + * 4 2 ^ / 3 –

2 8 * 4 2 ^ / 3 –

16 4 2 ^ / 3 -

16 16 / 3 -

1 3 –

-2

Sama hasilnya pada infix: 2 * ( 3 + 5 ) / 4 ^ 2 – 3 = -2

1.b. Cara Stack

Stack adalah tumpukan (jadi, memori diibaratkan dengan tumpukan) yang memiliki cara kerja, “yang pertama masuk ke kotak, maka akan terakhir kali diambil kembali” atau “first in last out”, atau sebaliknya, “yang terakhir masuk ke kotak, akan diambil yang pertama kali,” atau “last in first out.”

Untuk mengubah notasi infix menjadi postfix digunakan stack untuk menyimpan operator dengan beberapa aturan sebagai berikut

Sediakan stack untuk menyimpan operator (tipe : char)

Algoritma mengubah notasi infix menjadi postfix

[1]. Baca setiap karakter notasi infix dari awal

[2]. Bila operand maka langsung dicetak

[3]. Bila tanda ‘(‘ masukkan stack

[4]. Bila tanda ‘)’ pop dan cetak semua isi stack sampai TOS = ‘(‘. Pop juga tanda ‘(‘ ini, tetapi tidak usah dicetak

[5]. Bila operator : jika stack kosong atau derajad operator lebih tinggi dibanding derajad TOS, push operator ke dalam stack. Jika tidak, pop dan cetak; kemudian ulangi pembandingan dengan TOS. Kemudian di-push

[6]. Jika akhir notasi infix telah tercapai, dan stack masih belum kosong, pop semua isi stack dan cetak hasilnya Contoh notasi infix : ( A + B ) / (( C – D ) * E ^ F) Ilustrasi pengubahan notasi infix di atas menjadi notasi postfix secara lengkap tersaji dalam tabel sebagai berikut:

Karakter dibaca	Isi Tumpukan	Karakter tercetak	Hasil Notasi Postfix Yang Terbentuk
(	(
A	( +	A	A
+	( +
B		B	A B
)		+	A B +
/	/
(	/ (
(	/ ( (
C	/ ( (	C	A B + C
–	/ ( ( –
D	/ ( ( –	D	A B + C D
)	/ (	–	A B + C D –
*	/ ( *
E	/ ( *	E	A B + C D – E
^	/ ( * ^
F	/ ( * ^	F	A B + C D – E F
)	/ ( *	^	A B + C D – E F ^
	/ (	*	A B + C D – E F ^ *
	/
		/	A B + C D – E F ^ */

Dari ilustrasi di atas, bisa kita lihat bahwa notasi postfix dari ungkapan: ( A + B ) / (( C – D ) * E ^ F) adalah A B + C D – E F ^ */

Sabtu, 02 Juni 2018

POHON (TREE) MATEMATIKA DISKRET

POHON (TREE)

Pohon (tree) telah digunakan sejak tahun 1857 oleh matematikawan Inggris yang bernama Arthur Cayley untuk menghitung jumlah senyawa kimia.Silsilah keluarga biasanya juga digambarkan pasa bentuk pohon.
Pohon (tree) adalah merupakan graf yang tak berarah terhubung yang tidak memuat sirkuit sederhana. Diagram pohon dapat digunakan sebagai alat untuk memecahkan masalah dengan menggambarkan semua alternative pemecahan.

Jadi, dapat disimpulkan bahwa pohon adalah suatu graph yang banyak vertexnya sama dengan n (n>1), jika :

~ Graph tersebut tidak mempunyai lingkar (cycle free) dan banyaknya rusuk (n-1).

~ Graph tersebut terhubung .

Contoh :

Hutan ( forest ) merupakan kumpulan pohon yang saling lepas. Dengan kata lain, hutan merupakan graf tidak terhubung yang tidak mengandung sirkuit.

Ciri – ciri hutan :

banyaknya titik = n

banyaknya pohon = k

banyaknya rusuk = n-k

Sifat-sifat Pohon

Misalkan G = (V,E) adalah graf tak-berarah sederhana dan jumlah simpulnya n, maka :

1. G adalah pohon

2. Setiap pasang simpul di dalam G terhubung dengan lintasan tunggal

3. G terhubung dan memiliki m = n -1 buah sisi

4. G tidak mengandung sirkuit dan memiliki m = n – 1 buah sisi

5. G tidak mengandung sirkuit dan penambahan satu sisi pada graf akan membuat hanya satu sirkuit

6. G terhubung dan semua sisinya adalah jembatan (jembatan adalah sisi yang bila dihapus

menyebabkan graf terpecah menjadi dua komponen)

Jika hutan F dengan k komponen mempunyai

m = n – 1 buah sisi

Spanning Tree

Spanning Tree adalah subgraph G merupakan pohon dan mencakup semua titik dari G.Pohon merentang di peroleh dengan cara menghilangkan sirkuit didalam graf tersebut.

Contoh :

T₁, T₂, T₃, T₄ ® merupakan spanning tree dari G

Minimal spanning tree dari labeled graph Adalah spanning tree dari graph yang mempunyai jumlah panjang edge minimum.

Contoh :

Rooted Tree ( Pohon Berakar )

Rooted tree adalah suatu tree yang mempunyai akar . Istilah-istilah / unsur - unsur yang ada pada pohon berakar :

1. Akar :dinyatakan dengan lingkar-aN

2. Daun

3. Cabang

4. Tinggi / level / dept / dalamnya suatu vertex

Contoh :

CONTOH:

Gunakan Algoritma Prim untuk mendapatkan pohon rentang minimal dari graf $G$ berikut.

—-INISIASI: ALGORITMA PRIM—–
Step 1: Pilih salah satu titik, misalnya titik a.
Step 2: Misalkan $T = \{a\}$ dan $F = \{b, c, d, e, f, g, h, i\}$ . Dengan meninjau keterhubungan langsung titik pada himpunan $F$ dengan titik pada himpunan $T$ , diperoleh
$a(-, -); b(a, 4)~\boxed{c(a, 3)}$
$d(a, 5)~e(-, -)~f(-, -)~g(-, -)~h(-, -)~i(-. -)$
Pilih titik $c(a, 3)$ (bobot c ke a adalah 3).
Tulis $T = \{a, c\}$
Step 3: Tidak semua titik berada pada himpunan $T$ , berarti kembali ke step 2.
—-ITERASI—-
Step 2: Misalkan $T = \{a, c\}$ dan $F = \{b, d, e, f, g, h, i\}$ . Gunakan prinsip yang sama.
Untuk selanjutnya, titik yang tidak terhubung langsung dengan titik-titik di $T$ tidak ditulis.
$c(a, 3); \boxed{b(a, 4)}~b(c,6)~d(a,5)~\boxed{d(c,4)}$
Ada 2 pilihan. Pilih salah satu, misalkan dipilih $b(a, 4)$ (bobot b ke a adalah 4).
Tulis $T = \{a, c, b\}$
Step 3: Tidak semua titik berada pada himpunan $T$ , berarti kembali ke step 2.
—-ITERASI—-
Step 2: Misalkan $T = \{a, c, b\}$ dan $F = \{d, e, f, g, h, i\}$
$b(a, 4); d(a,5)~\boxed{d(c,4)}$
Pilih $d(c, 4)$ (bobot d ke c adalah 4).
Tulis $T = \{a, c, b, d\}$
Step 3: Tidak semua titik berada pada himpunan $T$ , berarti kembali ke step 2.
—-ITERASI—-
Step 2: Misalkan $T = \{a, c, b, d\}$ dan $F = \{e, f, g, h, i\}$
$d(c, 4); ~\boxed{e(d, 2)}$
Pilih $e(d, 2)$ (bobot e ke d adalah 2).
Tulis $T = \{a, c, b, d, e\}$
Step 3: Tidak semua titik berada pada himpunan $T$ , berarti kembali ke step 2.
—-ITERASI—-
Step 2: Misalkan $T = \{a, c, b, d, e\}$ dan $F = \{f, g, h, i\}$
$e(d, 2); h(e,2)~\boxed{g(e, 1)}~f(e, 4)$
Pilih $g(e, 1)$ (bobot g ke e adalah 1).
Tulis $T = \{a, c, b, d, e, g\}$
Step 3: Tidak semua titik berada pada himpunan $T$ , berarti kembali ke step 2.
—-ITERASI—
Step 2: Misalkan $T = \{a, c, b, d, e, g\}$ dan $F = \{f, h, i\}$
$g(e, 1); \boxed{h(e, 2)}~f(e, 4)~h(g, 4)~\boxed{i(g, 2)}$
Ambil salah satu. Misal dipilih $h(e, 2)$ (bobot h ke e adalah 2).
Tulis $T = \{a, c, b, d, e, g, h\}$
Step 3: Tidak semua titik berada pada himpunan $T$ , berarti kembali ke step 2.
—-ITERASI—-
Step 2: Misalkan $T = \{a, c, b, d, e, g, h\}$ dan $F = \{f, i\}$
$h(e, 2); i(h,3)~\boxed{i(g, 2)}~f(e, 4)$
Pilih $i(g, 2)$ (bobot i ke g adalah 2).
Tulis $T = \{a, c, b, d, e, g, h, i\}$
Step 3: Tidak semua titik berada pada himpunan $T$ , berarti kembali ke step 2.
—-ITERASI—-
Step 2: Misalkan $T = \{a, c, b, d, e, g, h, i\}$ dan $F = \{f\}$
$i(g, 2); \boxed{f(i,3)}~f(e, 4)$
Pilih $f(i, 3)$ (bobot f ke i adalah 3).
Tulis $T = \{a, c, b, d, e, g, h, i, f\}$
Step 3: Semua titik berada pada himpunan $T$ . Beri pesan: $T = \{a, c, b, d, e, g, h, i, f\}$ adalah pohon rentang minimal dengan bobot $3 + 4 + 4 + 2 + 1 + 2 + 2 + 3 + 3 = 24$
—ALGORITMA SELESAI—–