teori matematika terkait dengan tbo · himpunan adalah koleksi dari beberapa elemen ... untuk...

Teori Matematika Terkait dengan TBO

1

Sri Handayaningsih, S.T., M.T.Email : [email protected]

Teknik Informatika

Pertemuan Ke-1

TIU dan TIK

1. Mengingatkan kembali teori matematikayang terkait dengan TBO

2. Memahami teori matematika terkait denganhimpunan, fungsi, relasi, graf dan teknikpembuktiannya.

TEORI BAHASA OTOMATA2

pembuktiannya.

Penggunaan Secara Matematik

• Himpunan

• Fungsi

• Relasi


• Relasi

• Graf

• Teknik Pembuktian

}3,2,1{AHimpunan adalah koleksi dari beberapa elemen

Himpunan

},,,{ airplanebicyclebustrainB


Bisa ditulis

A1

Bship

1 anggota bagian dari A

Ship bukan anggota bagian dari B

Representasi dari Himpunan

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

C = { a, b, …, k }

S = { 2, 4, 6, … }

S = { j : j > 0, dan j = 2k untuk semua k>0 }

Set yang mempunyai akhir

Set yang tidakmempunyai akhir


S = { j : j > 0, dan j = 2k untuk semua k>0 }

S = { j : j bukan bilangan negatif dan ada }

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

1 2 34 5

A

U

6

78


Himpunan Universal :seluruh elemen yang mungkin ada

U = { 1 , … , 10 }

4 57

910

Operasi HimpunanA = { 1, 2, 3 } B = { 2, 3, 4, 5}

• Union

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

• Intersection

A B23

14

5


• Intersection

A B = { 2, 3 }

• Difference

A - B = { 1 }

B - A = { 4, 5 }

U

23

1

Venn diagrams

A

• Complement

Himpunan Universal = {1, …, 7}

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

46A


A1

23

5

6

7

A

A = A

{ even integers } = { odd integers }

Baca :Negasi dari even integer adalah odd integer

Integers


024

6

1

3

5

7

even

odd

Hukum DeMorgan’s

A U B = A B

U

A B = A U BU


A B = A U BU

Himpunan Kosong:= { }

S U = S

S =U

= Universal Set


S - = S

- S =

= Universal Set

Himpunan BagianA = { 1, 2, 3} B = { 1, 2, 3, 4, 5 }

A B

U

Himpunan Bagian yang Sesuai: A BU


Himpunan Bagian yang Sesuai: A B

A

B

Himpunan DisjointA = { 1, 2, 3 } B = { 5, 6}

A B =

U


A B

Cardinalitas Himpunan

• Untuk set yang mempunyai nilai akhir

A = { 2, 5, 7 }

|A| = 3


|A| = 3

(ukuran set)

PowersetsPowerset adalah Himpunan dalam himpunan

Powerset dari S = himpunan dari seluruh subsets S

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

Produk CartesiusA = { 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|


|A X B| = |A| |B|

Secara Umum untuk dua himpunan atau lebih

A X B X … X Z

FUNGSIdomain

123

a

bc

range

A Bf(1) = a

4

5


3 c

f : A -> BJika A = domain

maka f adalah funsi total

Jika tidak f adalah function parsial (bagian)

5

RELASIR = {(x1, y1), (x2, y2), (x3, y3), …}

xi R yi


e. g. if R = ‘>’: 2 > 1, 3 > 2, 3 > 1

Equivalensi Relasi• Refleksi: x R x

• Simetrik: x R y y R x

• Transitif: x R y dan y R z x R z


Contoh: R = ‘=‘

• x = x

• x = y y = x

• x = y dan y = z x = z

Equivalensi Pada ClasUntuk equivalensi relasi R

equivalensi class adalah x = {y : x R y}

Contoh:

R = { (1, 1), (2, 2), (1, 2), (2, 1),


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}

GRAFGraf adalah ……

nodea

b

c

d

e


• 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) }

c

Pemberian Nama Graf

a

b

c

d

e

1 3

5 6

26

2


c5

Lintasan

a

b

c

d

e


c

Lintasan adalah urutan dari edges yang berdekatan

(e, d), (d, c), (c, a)

Path

a

b

c

d

e


c

Path adalah lintasan dimana tidak ada edge yang diulang

Path sederhana : tidak ada node yang berulang

Cycle

a

b

c

d

e

12

3

base


c2

Cycle adalah lintasan dari node awal kembali ke node awal lagi

Cycle sederhana : hanya node awal aja yang berulang

Lintasan Euler

a

b

c

d

e1

23

45 6

7

8 base


c3

Sebuah cycle yang melintasi edge satu kali

Hamiltonian Cycle

a

b

c

d

e1

23

4

5 base


c3

Lintasan sederhana yang melintasi seluruh node

Contoh Soal :

Temukan seluruh path sederhana

a

b

c

d

e


corigin

Langkah 1

a

b

c

d

e


(c, a)

(c, e)

cbase

(c, a)

Langkah 2

a

b

c

d

e


(c, a)

(c, a), (a, b)

(c, e)

(c, e), (e, b)

(c, e), (e, d)

cbase

Langkah 3

a

b

c

d

e


cbase

(c, a)

(c, a), (a, b)

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

(c, e)

(c, e), (e, b)

(c, e), (e, d)

Langkah 4

a

b

c

d

e

base(c, a)


cbase(c, a)

(c, a), (a, b)

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

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

(c, e)

(c, e), (e, b)

(c, e), (e, d)

TreesAkar

Daun

Orang tua


Daun

anak

Tree tidak memiliki cycle

akar

daun

Level 0

Level 1

Height 3


daun

Level 2

Level 3

Height 3

Binary Trees


TEKNIK PEMBUKTIAN

• Pembuktian dengan induksi

• Pembuktian dengan kontradiksi


Induksi

Diketahui beberapa statemen P1, P2, P3, …

Tentukan :

• untuk batas akhir b di mana P1, P2, …, Pb


1 2 b

Adalah benar

• untuk k >= b maka

P1, P2, …, Pk termasuk Pk+1

maka

setiap Pi adalah benar

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

Contoh

Teori: Sebuah binary tree mempunyai tinggi n

maka mempunyai 2n daun.

Pembuktian dengan Induksi:

lihat L(i) menjadi jumlah daun maksimum


lihat L(i) menjadi jumlah daun maksimum

dari setiap subtree dengan tinggi i

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

Buktikan L(k + 1) <= 2k+1

Langkah Induksi

Tinggi

k


Dari Hipotesis Induksi : L(k) <= 2k

k+1

L(k) <= 2k

Langkah Induksi

tinggi

k


L(k+1) <= 2 * L(k) <= 2 * 2k = 2k+1

k+1

(tambahkan 2 node untuk setiap daun pada level k)

Pembuktian dengan Kontradiksi

Berharap untuk pembuktian pada a statemen Padalah benar

• assumekan P adalah salah

• kemudian dihasilkan kesimpulan yangtidak benar


• kemudian dihasilkan kesimpulan yangtidak benar

• sehingga statemen P harus benar

Pustaka1. Tedy Setiadi, Diktat Teori Bahasa dan Otomata,

Teknik Informatika UAD, 20052. Hopcroft John E., Rajeev Motwani, Jeffrey D. Ullman,

Introduction to Automata Theory, Languages, andComputation, 2rd, Addison-Wesley,2000

3. Martin C. John, Introduction to Languages and Theory ofComputation, McGraw-Hill Internatioanal edition,1991


3. Martin C. John, Introduction to Languages and Theory ofComputation, McGraw-Hill Internatioanal edition,1991

4. Linz Peter,Introduction to Formal Languages & Automata,DC Heath and Company, 1990

5. Dulimarta Hans, Sudiana, Catatan Kuliah MatematikaInformatika, Magister Teknik Informatika ITB, 1998

6. Hinrich Schütze, IMS, Uni Stuttgart, WS 2006/07,Slides based on RPI CSCI 2400

teori matematika terkait dengan tbo · himpunan adalah koleksi dari beberapa elemen ... untuk...

Documents