Month Maret 2019

Teori Komputasi

anbiyasr Tinggalkan komentar

Teori Komputasi

 

#AnbiyaShafardhiawanRizqullah

#4IA19

#TeoriKomputasi

#PengantarKomputasiModern

Komputasi sebetulnya bisa diartikan sebagai cara untuk menemukan pemecahan masalah dari data input dengan menggunakan suatu algoritma. Hal ini ialah apa yang disebut dengan teori komputasi, suatu sub-bidang dari ilmu komputer dan matematika. Selama ribuan tahun, 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.

Teori komputasi berkaitan dengan studi bagaimana persoalan (problem) dapat diselesaikan pada sebuah model dengan menggunakan algoritma. Model tersebut dinamakan model komputasi. Ada beberapa model yang digunakan, namun yang paling umum dipelajari adalah mesin Turing. Sebuah mesin Turing dapat dipikirkan sebagai komputer pribadi meja dengan kapasitas memori yang tak terhingga, namun hanya dapat diakses dalam bagian-bagian terpisah dan diskret. Ilmuwan komputer mempelajari mesin Turing karena mudah dirumuskan, dianalisis dan digunakan untuk pembuktian, dan karena mesin ini mewakili model komputasi yang dianggap sebagai model paling masuk akal yang paling ampuh yang dimungkinkan. Kapasitas memori tidak terbatas mungkin terlihat sebagai sifat yang tidak mungkin terwujudkan, namun setiap permasalahan yang “terputuskan” (decidable) yang dipecahkan oleh mesin Turing selalu hanya akan memerlukan jumlah memori terhingga. Jadi pada dasarnya setiap masalah yang dapat dipecahkan (diputuskan) oleh mesin Turing dapat dipecahkan oleh komputer yang memiliki jumlah memori terbatas.

Teori komputasi dibagi lagi menjadi 3 ranting :

  1. Teori Otomata (automata theory)

Teori Otomata adalah teori mengenai mesin-mesin abstrak, dan berkaitan erat dengan teori bahasa formal. ada beberapa hal yang berkaitan dengan Otomata, yaitu Grammar. Grammar adalah bentuk abstrak yang dapat diterima (accept) untuk membangkitkan suatu kalimat otomata berdasarkan suatu aturan tertentu.

  1. Teori Komputabilitas (computability 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.

  1. Teori Kompleksitas (computational complexity theory)

Teori kompleksitas mengklasifikasikan persoalan sebagai persoalan mudah (easy) atau persoalan sukar (hard).

 

Ketiganya(otomata, komputabilitas, dan kompleksitas) dikaitkan dengan pertanyaan:
“Apa yang dapat dilakukan oleh komputer danapa keterbatasannya?” (What are the fundamental capabilities and limitation of computers?)
• Pertanyaan senada dikemukakan oleh Peter J. Denning di dalam tulisannya(“Computer Science: The Discipline” in Encyclopedia of Computer Science) menyatakan bahwa pertanyaan fundamental yang mendasari ilmu komputer adalah: “What can be (efficiently) automated?” dengan kata lain: apa yang dapat dikomputasi?

•Studi teori komputasi di fokuskan untuk menjawab dua pertanyaan diatas:

1. Apa yang dapat dikomputasi?

2. Berapa banyak sumber daya(waktu/time dan ruang/space memori) yang dibutuhkan untuk melakukan komputasi tersebut?
• Untuk menjawab pertanyaan pertama dan kedua, teori komputabilitas dan teori kompleksitas sangat berhubungan erat.

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

• Untuk menjawab pertanyaan kedua, teori kompleksitas bertujuan untuk mengkaji kebutuhan waktu dan ruang untuk memecahkan persoalan yang diselesaikan dengan pendekatan yang berbeda-beda.

• Dengan kata lain, teori kompleksitas mengklasifikasikan persoalan sebagai persoalan mudah (easy) atau persoalan sukar (hard).
•Teori komputabilitas memperkenalkan beberapa konsep yang digunakan didalam teori kompleksitas.

• Teori otomata mengacu pada definisi dan sifat-sifat model komputasi.

• Beberapa model komputasi:

1. Finite State Automata (FSA)/Finite State Machine (FSM) (bentuk tunggal: automaton, plural: automata)

2. Push Down Automata (PDA)

3. MesinTuring(Turing Machine) atauTM
Di dalam teori komputasi, model komputasi yang sering dipakai adalah Mesin Turing.

 

 

sumber