Penjelasan teori komputasi

Komputasi dapat diartikan sebagai cara untuk menemukan pemecahan masalah dari data input dengan menggunakan suatu algoritma. Perhitungan dan komputasi umumnya dilakukan dengan menggunakan pena dan kertas, atau kapur dan batu tulis, atau dikerjakan secara mental, kadang-kadang dengan bantuan suatu tabel. Namun sekarang, kebanyakan komputasi telah dilakukan dengan menggunakan komputer.

Sehingga dapat diambil kesimpulan bahwa teori komputasi adalah suatu cabang ilmu komputer dan matematika yang membahas apakah dan bagaimanakah suatu masalah dapat dipecahkan pada model komputasi, menggunakan algoritma.

  • Teori komputasi terbagi menjadi 3 teori :
  1. Teori Otomata (automata theory)
  2. Teori Komputabilitas (computability theory)
  3. Teori Kompleksitas (computational complexity theory)

Teori komputabilitas bertujuan untuk memeriksa apakah persoalan komputasi dapat dipecahkan pada suatu model komputasi teoritis. Dengan kata lain, teori komputabilitas mengklasifikasikan persoalan sebagai dapat dipecahkan (solvable) atau persoalan yang tidak dapat dipecahkan (unsolvable). Teori kompleksitas bertujuan untuk mengkaji kebutuhan waktu dan ruang untuk memecahkan persoalan yang diselesaikan dengan pendekatan yang berbeda-beda dan mengklasifikasikan persoalan sebagai persoalan mudah (easy) atau persoalan sukar (hard). Teori komputabilitas memperkenalkan beberapa konsep yang digunakan di dalam teori kompleksitas. Teori otomata mengacu pada definisi dan sifat-sifat model komputasi. Di dalam teori komputasi, model komputasi yang sering dipakai adalah Mesin Turing.

  • Beberapa model komputasi :
  1. Finite State Automata (FSA)/Finite State Machine (FSM)
  2. Push Down Automata (PDA)
  3. Mesin Turing (Turing Machine) atau TM

sumber :

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s