Teori Komputasi dan Implementasinya Pada Bidang Matematika

 Teori Komputasi

    Teori komputasi adalah salah satu cabang dari ilmu komputer dan matematika yang membahas masalah mana saja yang dapat diselesaikan dalam model komputasi menggunakan algoritma dan bagaimana menyelesaikan masalah tersebut secara efektif.

Teori komputasi terbagi menjadi 3 cabang utama:

1. Automata theory and formal languages (teori automata dan bahasa formal). Teori ini terdiri atas 3 model, yakni finite automata, context-free grammars, dan turing machines.
2. Computability theory (teori komputabilitas). Teori ini digunakan untuk memahami masalah mana yang bisa dipecahkan (solvable) dan mana yang tidak bisa dipecahkan (unsolvable).
3. Computational complexity theory (teori kompleksitas komputasi). Teori ini mengklasifikasikan masalah berdasarkan tingkat kesulitannya. Memberikan bukti yang kuat jika masalah yang sulit memang benar-benar sulit. 

    Salah satu implementasi pada bidang matematikanya adalah Finite Automata. Finite automata adalah model yang baik untuk komputer yang memiliki jumlah atau kapasitas memori terbatas.

    Salah satu contoh yang dapat dilakukan dari model finite automata adalah pintu otomatis yang dapat buka tutup tanpa menggunakan bantuan dari manusia.

 

Pengertian Finite Automata

    Finite-state machine (FSM) atau finite-state automaton (FSA, automata) atau finite automata adalah model komputasi matematika.

    Mesin ini dapat berubah dari kondisi yang satu ke kondisi yang lain, bergantung dari input yang didapatkan.

Terdapat jua denis finite state:

1. Deterministic Finite Automata (DFA) / Deterministic Finite-State Machine (DFSM) / Deterministic Finite-State Automata (DFSA)
2. Non-Deterministic Finite Automata (NFA) / Non-Deterministic Finite-State Machine (NFSM) / Non-Deterministic Finite-State Automata (NFSA)

Contoh Finite Automata

Contoh finite automata kali ini pada pintu otomatis.

    Pintu otomatis tersebut mempunyai bantalan, untuk mendeteksi mengenai keberadaan seseorang yang akan melewati pintu. Konfigurasi tersebut dapat dilihat pada gambar berikut, jika dilihat dari sisi atas:

 

    Kontroler berada di salah 1 dari 2 kondisi yang ada, “open” atau “closed“, yang merepresentasikan kondisi pintu itu sendiri.

Artinya, dengan hal tersebut, akan ada 4 kemungkinan:

1. Front, artinya seseorang berdiri di bantalan pintu bagian depan
2. Rear, artinya seseorang berdiri di bantalan pintu bagian belakang
3. Both, artinya terdapat orang yang berdiri di kedua bantalan
4. Neither, artinya tidak ada orang yang berdiri di kedua bantalan

 

State diagram kontroler pintu otomatis

State transisi tabel kontroler pintu otomatis

Kontroler pintu otomatis tersebut bergerak dari state yang satu ke state yang lain, tergantung dari masukan (input) yang diterima.

Misal, jika kontroler tersebut dimulai dengan status closed dan menerima rangkaian sinyal input front, rear, neither, front, both, neither, rear, dan neither, maka status tersebut menjadi closed (mulai), open, open, closed, open, open, closed, closed, dan closed.

 

Finite automata M1 dengan 3 state

Finite Automata dalam Perspektif Matematika

Gambar di atas dinamakan dengan state diagram M₁. Pada diagram tersebut, terdiri atas 3 state, yakni q₁, q₂, dan q₃.

Saat automata tersebut menerima string masukan (input), contohnya 1101, maka string tersebut akan diproses dan menghasilkan keluaran (output). Keluaran yang dihasilkan bisa diterima atau ditolak.

Sebagai contohnya, jika string input 1101 dimasukkan ke dalam mesin M₁, maka proses yang dijalankan sebagai berikut:

1. Start in state q₁
2. Read 1, follow transition from q₁ to q₂
3. Read 1, follow transition from q₂ to q₂
4. Read 0, follow transition from q₂ to q₃
5. Read 1, follow transition from q₃ to q₂
6. Accept

 

Definisi formal finite automata

 

  asd

Teori tersebut mengkategorikan masalah menurut kesulitannya. Jika pertanyaan sulit benar-benar sulit, harap berikan bukti konklusif. Teori tersebut mengkategorikan masalah menurut kesulitannya. Jika pertanyaan sulit benar-benar sulit, harap berikan bukti konklusif