Teori komputasi adalah cabang ilmu komputer dan matematika yang digabungkan yang berkaitan dengan seberapa efisien masalah dapat diselesaikan pada model komputasi, menggunakan algoritma.
Teori komputasi mempelajari sifat umum komputasi yang pada gilirannya, membantu kami meningkatkan efisiensi di mana komputer memecahkan masalah. Ini dilakukan ketika kami memperkirakan validitas solusi yang diberikan oleh komputer melalui teori komputasi dan kemudian mengganti algoritma sehingga kami dapat memperoleh solusi yang lebih handal. Teori komputasi mempunyai cabang yang berkembang pesat dan telah membantu menyelesaikan masalah di banyak bidang selain ilmu komputer seperti Fisika, Ekonomi, Biologi dan banyak lainnya.
Sebelum kita masuk pada dasar-dasar teori komputasi, mari kita belajar tentang mesin Turing, karena mesin Turing berperan baik dalam menjelaskan teori ini:
Mesin turing adalah mesin abstrak teoritis yang digunakan sebagai model komputasi. Ini menggunakan pita memori tak terbatas di mana informasi yang diperoleh disimpan, dan menganalisis informasi ini untuk menentukan apakah operasi itu layak atau tidak. Mesin ini adalah ciptaan Alan Turing pada tahun 1963 oleh, dia menggunakannya untuk membuktikan properti komputasi secara umum dan menjawab pertanyaan berikut:
- "Apakah ada mesin yang dapat menentukan apakah mesin sembarang pada pita rekamannya" melingkar "
- "Apakah ada mesin yang dapat menentukan apakah mesin sewenang-wenang pada kasetnya pernah mencetak simbol tertentu"
 |
| Analogi Mesin Turing |
Kembali ke teori komputasi, Teori ini terbagi menjadi tiga cabang pengetahuan:
1. Teori Automata
2. Teori Komputasi
3. Teori Kompleksitas
Ketiga cabang ini pada dasarnya menggunakan algoritma untuk memanfaatkan kekuatan komputer dalam memecahkan masalah. Berikut ilustrasi dari bidang-bidang tersebut:
Teori Automata:
 |
| Teori Automata |
Cabang ini didirikan pada abad ke-20 oleh ahli matematika. Tujuan utama dari cabang ini adalah untuk menganalisis perilaku mesin dan bagaimana mereka memecahkan masalah Model automata yang paling kuat adalah mesin Turing.
Teori Komputabilitas:
 |
| Teori Komputabilitas |
Teori komputabilitas adalah saat kita dapat merumuskan masalah dengan menggunakan mesin Turing dengan mudah, tetapi kita tidak pernah dapat menyelesaikannya ... Dengan kata lain, komputer dapat mengatasi masalah tetapi tidak dapat menemukan solusinya
Teori Kompleksitas:
 |
| Teori Kompleksitas |
Teori kompleksitas membahas efisiensi di mana suatu masalah dapat diselesaikan. Hal ini dilakukan dengan mempertimbangkan dua aspek utama: kompleksitas waktu dan kompleksitas ruang, yang merupakan ukuran jumlah langkah yang diperlukan untuk menganalisis dan memecahkan masalah dan dengan demikian menentukan ruang memori yang dibutuhkan untuk menyelesaikan masalah.Untuk menentukan sebelumnya ruang dan waktu yang akan dibutuhkan, ilmuwan komputer menghubungkan kedua faktor ini dengan jumlah masukan yang diterima, karena waktu dan ruang yang dibutuhkan meningkat secara linier seiring dengan jumlah masukan meningkat.
Komentar
Posting Komentar