Teori Matematika Terkait dengan TBO

Teori Matematika Terkait dengan TBO

Pertemuan Ke-1 Sri Handayaningsih, S.T., M.T. Email : [email protected] Teknik Informatika

1

TIU dan TIK 1. Mengingatkan kembali teori matematika yang terkait dengan TBO 2. Memahami teori matematika terkait dengan himpunan, fungsi, relasi, graf dan teknik pembuktiannya.

TEORI BAHASA OTOMATA

2

Penggunaan Secara Matematik • Himpunan • Fungsi • Relasi • Graf • Teknik Pembuktian


3

Himpunan Himpunan adalah koleksi dari beberapa elemen

A {1, 2, 3} B {train, bus, bicycle, airplane} Bisa ditulis

1A ship B TEORI BAHASA OTOMATA

1 anggota bagian dari A Ship bukan anggota bagian dari B 4

Representasi dari Himpunan C = { a, b, c, d, e, f, g, h, i, j, k } C = { a, b, …, k }

Set yang mempunyai akhir

S = { 2, 4, 6, … }

Set yang tidak mempunyai akhir

S = { j : j > 0, dan j = 2k untuk semua k>0 } S = { j : j bukan bilangan negatif dan ada }


5

A = { 1, 2, 3, 4, 5 }

U A

6 1

7

2 4

8

3 5

10

9

Himpunan Universal :seluruh elemen yang mungkin ada U = { 1 , … , 10 } TEORI BAHASA OTOMATA

6

Operasi Himpunan A = { 1, 2, 3 }

B = { 2, 3, 4, 5} B

A

• Union A U B = { 1, 2, 3, 4, 5 }

2

1

3

4 5

• Intersection U

A

B = { 2, 3 }

2 3

• Difference A-B={1} B - A = { 4, 5 } TEORI BAHASA OTOMATA

1

Venn diagrams

7

• Complement Himpunan Universal = {1, …, 7} A = { 1, 2, 3 } 4

A = { 4, 5, 6, 7}

A 1 5

A 2

6

3 7

A=A TEORI BAHASA OTOMATA

8

{ even integers } = { odd integers }

Baca :

Negasi dari even integer adalah odd integer

Integers 1

odd

2 3


even

0

4

5

6 7

9

Hukum DeMorgan’s


U

A

U

AUB=A

B

B=AUB

10

Himpunan Kosong: ={} SU

=S

S

=

U

S-

= Universal Set

=S -S=


11

Himpunan Bagian A = { 1, 2, 3}

B = { 1, 2, 3, 4, 5 } U

A

B

U

Himpunan Bagian yang Sesuai: A

B

B A


12

Himpunan Disjoint A = { 1, 2, 3 }

A


U

A

B = { 5, 6} B=

B

13

Cardinalitas Himpunan • Untuk set yang mempunyai nilai akhir A = { 2, 5, 7 } |A| = 3

(ukuran set)


14

Powersets Powerset adalah Himpunan dalam himpunan S = { a, b, c } Powerset dari S = himpunan dari seluruh subsets S 2S = {

, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} }

Observasi: | 2S | = 2|S| = 23= 8 TEORI BAHASA OTOMATA

15

Produk Cartesius A = { 2, 4 }

B = { 2, 3, 5 }

A X B = { (2, 2), (2, 3), (2, 5), ( 4, 2), (4, 3), (4, 5) } |A X B| = |A| |B| Secara Umum untuk dua himpunan atau lebih AXBX…XZ TEORI BAHASA OTOMATA

16

FUNGSI domain 4

A 1 2

5

range f(1) = a

a b

3

Jika A = domain

B

c

f : A -> B

maka f adalah funsi total Jika tidak f adalah function parsial (bagian) TEORI BAHASA OTOMATA

17

RELASI R = {(x1, y1), (x2, y2), (x3, y3), …} xi R yi e. g. if R = ‘>’: 2 > 1, 3 > 2, 3 > 1


18

Equivalensi Relasi • Refleksi: • Simetrik:

xRx xRy

• Transitif:

yRx

x R y dan y R z

xRz

Contoh: R = ‘=‘ •x=x •x=y • x = y dan y = z TEORI BAHASA OTOMATA

y=x x=z 19

Equivalensi Pada Clas Untuk equivalensi relasi R equivalensi class adalah x = {y : x R y} Contoh: R = { (1, 1), (2, 2), (1, 2), (2, 1), (3, 3), (4, 4), (3, 4), (4, 3) } Equivalensi class dari 1 = {1, 2} Equivalensi class dari 3 = {3, 4} TEORI BAHASA OTOMATA

20

GRAF Graf adalah …… e node

b d

a

c • Nodes (Vertices) V = { a, b, c, d, e } • Edges E = { (a,b), (b,c), (b,e),(c,a), (c,e), (d,c), (e,b), (e,d) } 21


Pemberian Nama Graf 2 6 a


b

1 5

3

e 6

2 d

c

22

Lintasan e b d

a c

Lintasan adalah urutan dari edges yang berdekatan (e, d), (d, c), (c, a) TEORI BAHASA OTOMATA

23

Path e b d

a c

Path adalah lintasan dimana tidak ada edge yang diulang Path sederhana : tidak ada node yang berulang


24

Cycle base a

3 2

e b 1

d c

Cycle adalah lintasan dari node awal kembali ke node awal lagi Cycle sederhana : hanya node awal aja yang berulang


25

Lintasan Euler 8 b

4 a

7

3

6

5

base e 1 2

d

c

Sebuah cycle yang melintasi edge satu kali


26

Hamiltonian Cycle 5 b

4 a

3

base e 1 2

d

c

Lintasan sederhana yang melintasi seluruh node


27

Contoh Soal : Temukan seluruh path sederhana e b d

a c


origin

28

Langkah 1 e b d

a c (c, a)

base

(c, e)


29

Langkah 2 e b d

a (c, a) (c, a), (a, b)

c

base

(c, e) (c, e), (e, b) (c, e), (e, d)


30

Langkah 3 e b d

a (c, a) (c, a), (a, b)

c

base

(c, a), (a, b), (b, e) (c, e) (c, e), (e, b) (c,TEORI e), BAHASA (e, d) OTOMATA

31

Langkah 4 e b d

a (c, a) (c, a), (a, b)

c

base

(c, a), (a, b), (b, e) (c, a), (a, b), (b, e), (e,d) (c, e) (c, e), (e, b) (c, e), (e, d) TEORI BAHASA OTOMATA

32

Akar

Trees

Orang tua Daun anak Tree tidak memiliki cycle


33

akar

Level 0

Level 1 Height 3

daun Level 2

Level 3 TEORI BAHASA OTOMATA

34

Binary Trees


35

TEKNIK PEMBUKTIAN • Pembuktian dengan induksi • Pembuktian dengan kontradiksi


36

Induksi Diketahui beberapa statemen P1, P2, P3, … Tentukan : • untuk batas akhir b di mana P1, P2, …, Pb Adalah benar • untuk k >= b maka P1, P2, …, Pk termasuk Pk+1 maka setiap P adalah benar

TEORI BAHASA OTOMATAi

37

Pembuktian dengan Induksi • Dasar Induksi Temukan P1, P2, …, Pb yang bernilai benar • Hipotesis Induksi Asumsikan P1, P2, …, Pk adalah benar, Untuk setiap k >= b • Langkah induksi Lihat Pk+1 adalah benar


38

Contoh Teori: Sebuah binary tree mempunyai tinggi n maka mempunyai 2n daun. Pembuktian dengan Induksi: lihat L(i) menjadi jumlah daun maksimum dari setiap subtree dengan tinggi i


39

Terlihat: L(i) <= 2i • Dasar Induksi L(0) = 1

(node pada akar)

• Hipotesis induksi Asumsikan L(i) <= 2i untuk seluruh i = 0, 1, …, k • Langkah Induksi k+1 Buktikan L(k + 1) <= 2 TEORI BAHASA OTOMATA

40

Langkah Induksi

Tinggi k k+1

Dari Hipotesis Induksi : L(k) <= 2k TEORI BAHASA OTOMATA

41

Langkah Induksi

tinggi k

L(k) <= 2k

k+1 L(k+1) <= 2 * L(k) <= 2 * 2k = 2k+1 (tambahkan 2 node untuk setiap daun pada level k) TEORI BAHASA OTOMATA

42

Pembuktian dengan Kontradiksi Berharap untuk pembuktian pada a statemen P adalah benar • assumekan P adalah salah • kemudian dihasilkan kesimpulan yang tidak benar • sehingga statemen P harus benar


43

Pustaka 1. 2. 3. 4. 5. 6.

Tedy Setiadi, Diktat Teori Bahasa dan Otomata, Teknik Informatika UAD, 2005 Hopcroft John E., Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 2rd, Addison-Wesley,2000 Martin C. John, Introduction to Languages and Theory of Computation, McGraw-Hill Internatioanal edition,1991 Linz Peter,Introduction to Formal Languages & Automata, DC Heath and Company, 1990 Dulimarta Hans, Sudiana, Catatan Kuliah Matematika Informatika, Magister Teknik Informatika ITB, 1998 Hinrich Schütze, IMS, Uni Stuttgart, WS 2006/07, Slides based on RPI CSCI 2400


44

Teori Matematika Terkait dengan TBO

Recommend Documents