Pengenalan Teori Komputasi dan Implementasinya

Teori komputasi adalah sebuah teori pada ilmu komputer yang menjelaskan tingkat efisiensi suatu model matematis dalam menyelesaikan suatu masalah. Teori ini dibagi menjadi tiga cabang utama, yaitu:

1. Teori bahasa dan otomata
2. Teori komputabilitas
3. Teori kompleksitas

Teori bahasa dan otomata membahas beberapa mesin abstrak dan masalah yang dapat diselesaikan oleh mesin tersebut. Mesin ini akan menerima sebuah input dan secara otomatis memproses input tersebut. Mesin inilah yang disebut otomata. Otomata sangat dekat dengan teori bahasa formal, karena dengan otomata, sebuah bahasa dapat dibangun.

Lalu, teori komputabilitas membahas sejauh mana sebuah masalah dapat diselesaikan dengan komputer dan teori kompleksitas membahas seberapa efisien suatu masalah diselesaikan.

Dalam implementasinya, ketiga teori ini saling berkaitan. Pertama, seorang ilmuan komputer akan menggunakan model abstrak matematis untuk menyelesaikan masalah yang ada. Umumnya model yang digunakan adalah Turing machine, karena Turing machine mudah untuk dibentuk, dapat dianalisa dan digunakan untuk membuktikan hasil yang didapat, serta dianggap sebagai model yang hebat.

Selanjutnya, ilmuan komputer mulai melakukan proses pemecahan masalah menggunakan model abstrak tersebut berdasarkan teori komputabilitas. Salah satu contoh kasusnya adalah masalah halting. Halting merupakan kondisi di mana sebuah program dengan suatu input harus berhenti atau berjalan selamanya. Masalah ini mudah untuk dianalisa dan tidak dapat dipecahkan dengan Turing machine.

Terakhir, ilmuan komputer akan menghitung seberapa efisien masalah tersebut diselesaikan. Aspek yang diperhatikan adalah, waktu dan ruang. Aspek waktu menunjukan berapa lama masalah tersebut diselesaikan. Aspek ruang menunjukan berapa besar tempat yang digunakan untuk memecahkan masalah tersebut.

Untuk menghitung kedua aspek tersebut, ilmuan komputer menuliskan solusi yang didapat menjadi sebuah fungsi dengan besar input dari suatu masalah. Sebagai contoh, pencarian suatu nilai di dalam larik membutuhkan waktu yang besar jika larik tersebut besar juga. Untuk memudahkan masalah tersebut, notasi Big O digunakan.

Kemudian, masalah seperti apa yang dapat diselesaikan? Pada bidang matematika, teori komputasi umum digunakan untuk permasalahan analisis numerik. Beberapa masalahnya adalah,

1. Pencarian akar suatu fungsi, seperti metode bisection, metode Newton, serta metode Secant
2. Interpolasi yaitu untuk mendapatkan data point baru dari beberapa data point yang sudah diketahui
3. Operasi pada matriks, seperti dot product, cross product
4. Aljabar linier.

Pada masalah pencarian akar suatu fungsi, metode yang digunakan dapat berupa metode iteratif menggunakan iterasi khusus. Iterasi tidak dilakukan pada fungsi yang diberikan, tetapi dilakukan pada fungsi tambahan dan mengaproksimasi nilai akar menggunakan fungsi tersebut. Sehingga proses iterasi tidak memakan waktu yang lama. Metode yang menggunakan iterasi adalah metode Newton dan metode Secant.

Tak hanya menggunakan iterasi, pencarian akar pun dapat dilakukan dengan membagi fungsi menjadi beberapa bagian. Ini dilakukan agar ruang yang digunakan tidak besar. Metode yang menggunakan proses ini adalah bisection dan regula falsi.