TEORI KOMPUTASI

Teori Komputasi atau Theory of Computation merupakan sebuah ilmu komputer dan matematika yang digabungkang berdasarkan beberaoa efisien masalah yang dapat diselesaikan pada model komputesi yang menggunakan algoritma

Pada sifat umumnya komputasi jelas membatu meningkat efisiensi pada komputer untuk memecahkan masalah .  ini dapat dilakukan ketika memperkirakan validaliti solusi yang diberikan oleh komputer melalui teori komputer dan mengganti algoritma nya. 

Teori Komputasi memiliki beberapa bidang yaitu:

1. Teori Automata
2. Teori Komputasi
3. Teori Kompleksitas Komputasi

Teori Automata :

Tujuan pada Teori Automati adalah untuk menganalisis perilaku mesin dan bagaimana mereka memecahkan masalah model automata yang paling kuat pada pada mesin turing

Teori Komputasi :

Tujuan Teori komputasi bermula pada mesin turing dikarenakan masalah pada tidak pernah diselesaikan sekali pun. Pada saat itulah teori ini dapat mengatasi masalah tetapi tidak dapat m,enemukan solusinya.

Teori Kompleksitas Komputasi :

Tujuan Teori komplesitas ini untuk menambah efisiensi dimana suatu masalah dapat diselesaikan. Dengan cara mempertibangkan dua aspek utama pada kompleksitas waktu dan kompleksitas ruang, yang merupakan ukuran jumlah langkah yang diperlukan untuk menganalisis dan memecahkan masalah, sehingga menentuka ruang memori yang diperlukan untuk menyelesaikan masalah.

Terminologi dasar yang penting dan sering digunakan dalam Teori Komputasi :

Symbol : Simbol ( sering disebut karakter) adalah blok bangunan terkecil yang dapat berupa alfabet, huruf, atau gambar apa pun.

a,b,c,0,1 ………

Alphabet (Σ) : Alphabet atau abjad adalah kumpulan simbol, yang selalu terbatas.

Σ = {0,1} merupakan alpabet dari digit biner
Σ = {0,1, ….. , 9 } merupakan alpabet dari digit desimal
Σ = {a,b,c}
Σ = {A,B,C, ……, Z}

String : String adalah urutan simbol yang terbatas dari beberapa alfabet. String umumnya dilambangkan sebagai w dan panjanga string dilambangkan sebagai /w/.

Language : Language atau bahasa adalah sekumpulan string, dipilih dari beberapa Σ * atau bisa dikatakan ‘Bahasa adalah bagian dari Σ *’ yang dapat menjadi Finite atau Infinite.

Teori komputasi sudah berkembang pesat yang telah  membantu menyelesaikan masalah di banyak bidang selain ilmu komputer seperti Fisika, Biologi, Geografi dan banyak lainnya.

Sumber :

http://www.contrib.andrew.cmu.edu/~hebah/Theory%20of%20computation.html

https://www.geeksforgeeks.org/introduction-of-theory-of-computation/