Pendahuluan. CSG3D3 Teori Komputasi

CSG3D3 | Teori Komputasi

Pendahuluan

Agung Toto Wibowo Ahmad Suryan Yanti Rusmawati Mahmud Dwi Sulistiyo Kurniawan Nur Ramadhani Said Al Faraby Dede Rohidin

KK Intelligence, Computing, and Multimedia

Pertemuan 1

Perkenalan

Teori Komputasi | CSG3D3

Dosen Pengampu dan Kelas Nama Kode NIP Ruangan E-mail Kelas Wakil Kelas Kontak

: Mahmud Dwi Sulistiyo : MDS : 13881141-1 : Lecture Room (E105) : [email protected], [email protected] : IF-37-GAB : Geriska : [email protected]


Identitas Mata Kuliah Nama Mata Kuliah

: Teori Komputasi

Kode Mata Kuliah

: CSG3D3

SKS

: 3

Jenis

: MK Wajib

Jam pelaksanaan

: Tatap muka di kelas

= 3 jam per minggu

Tutorial / responsi

= 1 jam per minggu

Semester / Tingkat

: 5 (lima) / 3 (tiga)

Pre-requisite

: Teori Himpunan, Matematika Diskrit

Co-requisite

: -

Bidang Kajian

: Algorithm


Buku Referensi Brookshear, Glen J., “Theory of Computation : Formal Language, Automata and Complexity”, The Benjamin/Cummings Publishing Company, 1989 Revesz, Gyorgy E., “Introduction to Formal Languages”, McGraw Hill Book Company, 1985 Hopcroft, Jhon E., and Jeffery D. Ullman, “Introduction to Automata Theory, Language, and Computation” Linz Peter, “An Introduction to Formal Languages and Automata 5th Edition, Jones & Bartlett Publishers”, ISBN: 144961552X, 9781449615529, 2011 Utdirartatmo, Firrar, “Teknik Kompilasi”, J&J Learning Yogyakarta, ISBN: 979-939811-8, 2001 Hariyanto, Bambang, “Teori Bahasa, Otomata dan Komputasi serta Terapannya” Sipser, M, “Introduction to the Theory of Computation”, Cengage Learning, 2012


Bahan Kajian [1] Sebelum UTS (minggu 1 s.d. 7) –Pendahuluan; Teori Himpunan –Grammar dan Tingkat Bahasa; Regular Grammar –Finite Automata (FA); Diagram dan Tabel Transisi –Deterministic Finite Automata (DFA) –Non-Deterministic Finite Automata (NDFA) –NDFA dengan ε-Move –Minimum DFA –Operasi FA dan Regular Expression; FA vs. RG –Mesin Mealy dan Moore [pengayaan] Teori Komputasi | CSG3D3

Bahan Kajian [2] Setelah UTS (minggu 8 s.d. 14) –Pushdown Automata (PDA) –Context Free Grammar (CFG) –PDA vs CFG –Chomsky Normal Form (CNF) –Deterministic PDA dan LL Parser –Pumping Lemma [pengayaan] –Turing Machine –Combining Turing Machines –Basic Building Block Teori Komputasi | CSG3D3

Komponen Penilaian Tugas Harian dan Kuis Tugas Besar Ujian Tengah Semester Ujian Akhir Semester

: 15% : 20% : 35% : 30%


Penentuan Indeks Nilai [1] Penilaian Acuan Kriteria (PAK) –A –AB –B –BC –C –D –E

: Nilai Akhir > 80 : 70 < Nilai Akhir <= 80 : 65 < Nilai Akhir <= 70 : 60 < Nilai Akhir <= 65 : 50 < Nilai Akhir <= 60 : 40 < Nilai Akhir <= 50 : Nilai Akhir <= 40


Penentuan Indeks Nilai [2] Penilaian Acuan Normal (PAN) –A –AB –B –BC –C –D –E

: Nilai Akhir > µ + 1.2 σ : µ + σ <= Nilai Akhir < µ + 1.5 σ : µ <= Nilai Akhir < µ + σ : µ - σ <= Nilai Akhir < µ : µ - 1.5 σ <= Nilai Akhir < µ - σ : µ - 2 σ <= Nilai Akhir < µ - 1.5 σ : Nilai Akhir < µ - 2 σ

µ : rataan nilai-nilai mahasiswa kelas dengan Nilai Akhir > 40 σ : simpangan baku nilai-nilai kelas dengan Nilai Akhir > 40 Teori Komputasi | CSG3D3

Tugas Besar Tugas besar dibagi menjadi 2 tahap: –Tahap 1:  Membuat Lexical Analyzer untuk studi kasus tertentu  Menyangkut materi Regular Grammar dan Finite Automata  Deskripsi dan detail tugas besar tahap 1 menyusul  Ditargetkan selesai sebelum UTS

–Tahap 2:  Membuat Parser, merupakan kelanjutan dari tahap 1  Menyangkut materi Context Free Grammar dan Pushdown Automata  Deskripsi dan detail tugas besar tahap 2 menyusul  Ditargetkan selesai sebelum UAS Teori Komputasi | CSG3D3

Saran Baca text book atau buku-buku referensi sebelum dan/atau setelah perkuliahan Hadir di setiap perkuliahan dan aktif berdiskusi Kerjakan setiap tugas yang diberikan secepatnya Jika ada pertanyaan, diskusikanlah dengan dosen ataupun teman (di kelas, di ruangan, atau melalui email) Communication & Feedback –Kirim feedback via email di akhir UTS dan UAS –Feedback berguna memperbaiki perkuliahan –The success of this course is not how much I teach, but how much you learn


Aturan Tambahan MDS Segala bentuk komunikasi formal kita dilakukan melalui email. Segala bentuk tindakan plagiarisme, seperti mencontek dan menggunakan karya orang lain, mendapatkan sanksi maksimal nilai E untuk semua MK yang diambil di semester ini. Masuk perkuliahan di kelas harus mengenakan seragam/pakaian yang sesuai aturan institusi, jika tidak dilaksanakan akan mendapatkan sanksi (misal tidak boleh ikut kuliah). Aturan keterlambatan: – Dosen: maksimal 30 menit dari jadwal semula JIKA tidak ada kabar – Mahasiswa: bebas, tidak ada batasan keterlambatan

Hal-hal yang membuat pengurangan pada penilaian mahasiswa: – Terpergok merokok di lingkungan kampus – Terlibat kegiatan-kegiatan yang dapat merusak moral pelajar, seperti ikut dugem, tawuran, dan kegiatan sejenisnya Teori Komputasi | CSG3D3

Pertemuan 1

Motivation


Motivation Theory of computation teaches you about the elementary ways in which a computer can be made to think.

“What is a computer?” “What can a computer do?”


What can a computer do?


What’s the benefit? Dalam bidang Natural Language Processing: pembuatan Finite State machines (Finite State Automata) State machines juga digunakan dalam bidang matematika seperti Number theory Regular expressions dapat digambarkan menggunakan Nondeterministic Finite Automata Beragam algorithma dapat dinyatakan dalam bentuk finite state machine. Contoh: topological sort. Setiap tahapan topological sort mewakili satu state automata.


People are so overwhelmed by the wonders of the technology but they fail to wonder about the theory underlying it.


Stil Unsure…? Sipser (2012) Theory is good for you because studying it expands your mind. Computer technology changes quickly. Specific technical knowledge, though useful today, becomes outdated in just a few years. Consider, instead, the abilities: – to think, – to express yourself clearly and precisely, – to solve problems, and – to know when you have not solved a problem.

These abilities have lasting values. Theory trains you in these areas.


Pertemuan 1

Pengantar Teori Komputasi


Tiga Area Teori Komputasi Referensi: Sipser, M. (2012). Introduction to the Theory of Computation. Cengage Learning.

Apa kemampuan dasar dan keterbatasan komputer? Teori Komputasi | CSG3D3

Complexity Apa yang membedakan suatu masalah sulit sedangkan yang lainnya mudah dalam hal komputasi? Riset tentang complexity > 40 tahun. Achievement? Klasifikasi masalah berdasarkan kesulitan komputasinya. Mudah → sorting problem Sulit → scheduling problem Salah satu penerapan : cryptography


Computability Sampai pertengahan abad ke-20, ahli matematika seperti Kurt Godel, Alan Turing, dan Alonzo Church menemukan fakta bahwa beberapa masalah dasar tertentu tidak dapat dipecahkan oleh komputer. Contoh: bagaimana komputer dapat menentukan apakah suatu pernyataan matematika adalah true atau false. Salah satu konsekuensinya, pengembangan ide tentang model teoritis komputer yang membantu konstruksi komputer seperti yang kita gunakan sekarang. Dalam complexity theory, tujuannya adalah mengklasifikasikan permasalahan sebagai masalah yang mudah (easy) atau sulit (hard). Dalam computability theory, klasifikasi permasalahan berdasarkan pada dapat dipecahkan (solvable) atau tidaknya suatu permasalahan tersebut. Beberapa konsep dalam computability digunakan dalam complexity theory.


Automata Automata theory berkaitan dengan definisi dan properti dari model-model matematika komputasi. Model pertama disebut finite automaton, yang dapat digunakan dalam text processing, compilers, dan hardware design. Adapun model lainnya disebut context-free grammar, yang digunakan dalam bahasa pemrograman dan artificial intelligence. Teori computability dan complexity memerlukan definisi yang tepat mengenai komputer.


Pertemuan 1

Teori Himpunan


Set/Himpunan [1] Set/Himpunan: sekumpulan objek/elemen/member Contoh: A = {0,1}; B = {a, b, c} Infinite set: himpunan dengan jumlah anggota yang tak terbatas Contoh: –N = natural numbers = {1,2,3,…} –Z = integers = {…,-2,-1,0,1,2,…}

Empty set (himpunan kosong) dinotasikan dengan  atau {} Teori Komputasi | CSG3D3

Set/Himpunan [2] Union dari himpunan A dan B dinotasikan dengan A  B adalah kumpulan dari semua elemen yang ada di A atau di B Intersection dari himpunan A dan B dinotasikan dengan A  B adalah kumpulan elemen yang menjadi anggota A dan juga B sekaligus Complement A dinotasikan Ā adalah semua objek yang berada di dalam pembicaraan yang bukan menjadi anggota himpunan A


Set/Himpunan [3] Kita menggunakan tanda minus (–) untuk menyatakan subtraction Sebagai contoh, {a, b, c} – {a, c} = {b} {a, b} – {d, e} = {a, b}

A – B juga bisa kita sebut sebagai komplemen B relatif terhadap A Lihat bahwa A - Ā adalah A Teori Komputasi | CSG3D3

Set/Himpunan [4] A adalah subset dari B dinotasikan dengan A  B, terjadi jika semua elemen A menjadi anggota himpunan B A adalah proper subset dari B jika A  B dan B – A ≠ {} Semua proper subset adalah subset, tetapi tidak semua subset adalah proper subset Empty set (himpunan kosong) merupakan subset dari himpunan manapun A adalah equal B jika dan hanya jika berlaku hubungan A  B dan B  A Teori Komputasi | CSG3D3

Set/Himpunan [5] Power set dari A adalah himpunan semua subsets dari A – Notasi power set dari A  p(A) – Misal, A = {0,1} – Power set dari A = p(A) = {, {0}, {1}, {0,1}}

Kardinalitas dari sebuah himpunan adalah jumlah elemen/anggota dari sebuah himpunan tersebut. – Notasi kardinalitas dari himpunan A  |A|

Kardinalitas dari power set himpunan A – Dihitung dengan cara: |p(A)| = 2|A| – Contoh: jika A = {0,1}  |p(A)| = 22 = 4 Teori Komputasi | CSG3D3

Sequence dan Tuple [1] Suatu sequence dari objek adalah daftar dari objek dalam urutan tertentu. Contoh: (7, 21, 57); (4, 1) Tuple adalah sequence dengan jumlah anggota terbatas Contoh: k-tuple 3-tuple (7, 21, 57) 2-tuple (7, 21)  pair


Sequence dan Tuple [2] Cartesian product atau cross product dari A dan B, dinotasikan dengan A x B, adalah semua pair terurut dalam (a, b), di mana a Є A dan b Є B Contoh: A = {1,2} and B = {a,b,c} A x B = {(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)} BxA=? Apakah A x B = B x A ??? Teori Komputasi | CSG3D3

Fungsi dan Relasi [1] Sebuah fungsi akan menerima input dan selalu menghasilkan sebuah nilai output. Komponen fungsi: – Domain: daerah asal  himpunan input yang diperbolehkan untuk suatu fungsi – Kodomain: daerah kawan  himpunan yang merupakan kemungkinan output sebuah fungsi – Range: daerah hasil  himpunan output hasil dari suatu fungsi

Fungsi disebut juga dengan pemetaan/mapping, di mana sebuah fungsi akan memetakan domain ke kodomain, dengan hasilnya adalah range. f : A  B artinya f adalah fungsi dengan domain A, kodomain B, sehingga f(A) merupakan range dari fungsi f. Contohnya, abs : Z  Z Teori Komputasi | CSG3D3

Fungsi dan Relasi [2] Diberikan fungsi f : A  B Fungsi f disebut fungsi pada atau surjektif atau onto jika dan hanya jika untuk sembarang b ∈ B terdapat paling tidak satu a dalam domain A sehingga berlaku f(a) = b. Dengan kata lain, pada suatu fungsi surjektif, kodomain sama dengan range-nya (f(A) = B). Setiap anggota himpunan A mempunyai 1 kawan di B.


Fungsi dan Relasi [3] Diberikan fungsi f : A  B Fungsi f disebut fungsi satu-satu atau injektif atau into jika dan hanya jika untuk sembarang a1 dan a2 ∈ A dengan a1 ≠ a2 berlaku f(a1) ≠ f(a2). Dengan kata lain, bila a1 = a2 maka f(a1) = f(a2). Setiap anggota himpunan A memiliki 1 kawan di B yang tunggal (hanya punya 1 pasangan dari A).


Fungsi dan Relasi [4] Diberikan fungsi f : A  B Fungsi f disebut fungsi bijektif atau korespondensi 1-1 jika dan hanya jika untuk sembarang b ∈ B terdapat tepat satu a ∈ A sehingga f(a) = b, dan tidak ada anggota A yang tidak terpetakan dalam B. Dengan kata lain, fungsi bijektif adalah fungsi injektif dan sekaligus merupakan surjektif. Setiap anggota himpunan B mempunyai tepat satu kawan di A.


Graph [1] Sebuah graph adalah sekumpulan point/node dengan garisgaris yang menghubungkan antar node tersebut. 1 4

2 3

Definisi G = (V,E), V: kumpulan node, E: kumpulan garis G = ({1,2,3,4}, {(1,2),(1,4),(1,3),(2,4),(3,4)}) Teori Komputasi | CSG3D3

Graph [2]

1

2

G dan G’

4

3

Derajat dari node: derajat dari suatu node dihitung dari jumlah busur yang terhubung dengan node itu. Contohnya, derajat node 1 adalah 3. Subgraph: G’ = ({1,2,4}, {(1,2), (1,4), (2,4)}) Jalur/Path: rangkaian node yang terhubung oleh busur. Contohnya, (2,4,3) Sirkuit/Circle: jalur dengan start dan end node sama. Contohnya, (1,2,4,1)


Graph [3]

1 2

3

4 Tree: graph terhubung dengan tidak ada circle/sirkuit Tree terdiri dari Root (akar), dan leave (daun)


Graph [4]

1 4

2 3

Graph Berarah: graph yang dihubungkan dengan busur berarah (bukan sekedar garis)


Pertemuan 1

Latihan


Latihan 1 Jika kita memiliki himpunan A = {1, 2, z}, maka powerset dari A adalah ... Sedangkan powerset dari B = {} adalah ... Berapa kardinalitas dari kedua powerset itu?


Latihan 2 Jika kita memiliki himpunan X = {x : x Є N (natural) dan x adalah bilangan ganjil}, Y = {y : y Є N (natural) dan y adalah bilangan prima}, serta Z = {z : z Є N (natural), dan z adalah bilangan kelipatan 3}, maka notasikan/deskripsikan hasil himpunan dari operasi berikut.

a. b. c. d.

XY YZ (Y  Z) – X XY

adalah : adalah : adalah : adalah :


Latihan 3 Jika A dan B adalah himpunan dari semesta S, maka manakah pernyataan berikut yang selalu benar? a. A union B akan menghasilkan S b. B intersection A akan menghasilkan suatu himpunan dengan kardinalitas selalu lebih besar dari 1 c. A complement adalah semua anggota S yang tidak menjadi anggota A d. S – A adalah B e. Tidak ada jawaban yang benar


Latihan 4 Termasuk fungsi apakah di bawah ini?


Tugas Membaca Reverensi : Buku 1 Theory of Computation Chapter 0 : Introduction (review & next lecture) Chapter 1.1 : Finite Automata (next lecture)


Pendahuluan. CSG3D3 Teori Komputasi

Recommend Documents