Ilmu komputer teoretis

**Ilmu komputer <span lang="Krystal" dir="ltr">teoretis</span>** (en: *Theoretical computer science,* TCS) merupakan irisan dari ilmu komputer umum dan ilmu matematika yang fokus pada teori matematis dari ilmu komputer yang mencakup teori komputasi, teori bahasa formal, kalkulus lambda, dan teori tipe .

Kompleksitas dari istilah "teori/teoretis" membuat penentuan definisi ilmu komputer teoretis sulit. Kelompok Minat Khusus Algoritma dan Teori Komputasi (*Special Interest Group on Algorithms and Computation Theory,* SIGACT) dari ACM menjelaskan bahwa ilmu komputer teoretik mencakup ragam topik seperti algoritma, struktur data, kompleksitas komputasi, komputasi paralel dan terdistribusi, komputasi probabilistik, komputasi kuantum, teori automata, teori informasi, kriptografi, semantik dan verifikasi pemrograman, pembelajaran mesin, biologi komputasi, ekonomi komputasi, geometri komputasi, dan teori bilangan komputasi dan teori aljabar komputasi. Ilmu komputer teoretik dicirikan dengan penggunaan teknik matematika dan kekakuan/ketepatan pembuktian matematis (*mathematical rigour*) 

## Sejarah
Pada tahun 1931, Kurt Gödel memublikasikan teorema ketidaklengkapan yang membuktikan bahwa terdapat batasan mendasar dalam inferensi logika dan pembuktian matematika, atau dalam kata lain, terdapat keterbatasan logika dan matematika dalam melakukan penyangkalan atau pembuktian matematika.

Kajian mengenai teori informasi dimulai kemudian dengan publikasi teori matematika pada proses komunikasi digital pada tahun 1948 oleh Claude Shannon. Pada dekade yang sama, Donald Hebb memperkenalkan model matematis yang menggambarkan proses biologis aktivitas pembelajaran di otak manusia. Hipotesis Hebb tersebut didukung oleh banyaknya data biologis dari penelitian-penelitian mengenai jaringan syaraf. Dari penelitian-penelitian tersebut, mulai dikenal kajian jaringan saraf tiruan dan pemrosesan terdistribusi paralel. Pada tahun 1971, Stephen Cook dan Leonid Levin secara independen membuktikan bahwa terdapat permasalahan matematika yang bersifat NP-complete – sebuah hasil penting dalam kajian teori kompleksitas komputasi.

Pada awal abad ke-20, perkembangan pesat kajian mekanika kuantum memberikan sudut pandang baru dalam pemaknaan kata "komputasi". Kajian teori informasi pada dekade sebelumnya fokus melakukan abstraksi terhadap kondisi realitas untuk mendapatkan informasi secara akurat, dengan mengabaikan bentuk fisik (aliran sinyal listrik pada prosesor, misalnya) dari mesin dan realitas itu sendiri. Kegiatan abstraksi ini bersandar pada prinsip-prinsip mekanika klasik yang menghasilkan informasi yang bermanfaat untuk kegiatan komunikasi maupun komputasi, contohnya pada mesin Turing.

Pada awal tahun 1980, beberapa peneliti menyadari bahwa prinsip-prinsip mekanika kuantum memiliki implikasi pada perspektif mengenai pemrosesan informasi. Fisikawan Feynman, Yuri Manin dan peneliti lain kemudian menemukan bahwa fenomena keterkaitan partikel tidak dapat disimulasikan dengan baik oleh mesin Turing, yang menggunakan bita 0 dan 1 dalam melakukan komputasi. Menggunakan fenomena ini, peneliti lain mencoba menggeser konsep "komputasi" yang menggunakan dua jenis bita digital: 0 dan 1, menjadi menggunakan *[[qubit]]* yang memiliki lebih dari dua "keadaan" (*state*) atau superposisi.

Dengan menggunakan komputasi dalam qubit, seseorang dapat melakukan komputasi pada fungsi dengan menggunakan beberapa "keadaan" secara bersamaan. Penemuan-penemuan ini mengangkat kajian terhadap konsep komputer kuantum pada paruh kedua abad ke-20. Salah satu kajian pada awal tahun 1990an yang dilakukan oleh Peter Shor meneliti suatu algoritma untuk memfaktorkan bilangan besar dalam kompleksitas waktu polinomial dengan memanfaatkan prinsip kuantum. Melalui penelusuran lebih lanjut, ditemukan bahwa algoritma ini berpotensi membuat algoritma kriptografi kunci publik seperti RSA menjadi tidak aman.

Kajian riset ilmu komputer teoretis modern didasarkan pada perkembangan-perkembangan dasar yang telah dibahas sebelumnya, namun juga mencakup ragam kajian matematika dan interdisipliner lain, seperti yang ditunjukkan di bawah ini:

## Topik-topik dalam kajian ilmu komputer teoretik

### Algoritma
Suatu algoritma adalah langkah atau prosedur komputasi. Algoritma digunakan untuk proses penghitungan, pemrosesan data, dan penalaran otomatis.

Algoritma adalah metode efektif berupa daftar  dari instruksi yang didefinisikan dengan akurat untuk menghitung suatu fungsi. Daftar langkah tersebut dimulai dari keadaan (*state*) awal dan masukan (*input*) awal, atau bisa jadi berisi nilai kosong. Rangkaian instruksi pada algoritma menjelaskan langkah-langkah komputasi yang menghasilkan keadaan (*state*) yang tetap di tiap langkah. Pada akhir algoritma, rangkaian instruksi akan menghasilkan "keluaran" (*output*) dan kemudian berhenti. Peralihan dari satu keadaan ke keadaan berikutnya tidak selalu bersifat deterministik (memiliki hubungan sebab-akibat yang jelas secara kasat mata). Sebagai contoh, algoritma acak, menambahkan tiap masukan secara acak, sehingga hasil algoritma tidak terlihat deterministik.

### Teori automata
Teori automata adalah kajian mengenai *[[mesin abstrak]]* dan *[[Automaton|automata]]*, serta pemanfaatan keduanya dalam memecahkan permasalahan. Bidang kajian ini termasuk dalam kajian matematika diskrit (irisan antara bidang kajian matematika dan ilmu komputer ). Kata *Automata* berasal dari kata Yunani αὐτόματα yang berarti "bertindak sendiri".

Secara ringkas, teori automata membahas mesin (mesin mekanik maupun fungsi matematis) yang meniru sebagian fitur aksi manusia. Mesin-mesin ini melakukan konversi informasi dari bentuk satu ke bentuk yang lain. Sebagai contoh, dalam mesin mekanik dikenal suatu sistem pendulum, yang memiliki keadaan awal (*initial state*), masukan berupa faktor peubah (seperti gaya) dan luaran berupa kondisi akhir yang menjadi keadaan awal bagi langkah berikutnya. Dalam matematika, fungsi yang menggambarkan relasi antara dua variabel dapat menghasilkan luaran berbeda tiap kali variabel masukan berubah.  Teori automata mengkaji kelakuan dinamis dari hubungan antara masukan dan luaran dari automaton dan memberikan pembuktian matematis dari tingkah laku dinamis tersebut.

### Teori pengkodean
Teori pengkodean mengkaji aspek matematika dari metode (dalam konteks kajian ini disebut sebagai "kode") untuk mengoreksi galat pada transmisi informasi. Kode merepresentasikan data sedemikian rupa sehingga informasi tetap dapat diterima, meskipun ditemukan galat/kesalahan pada data. Sebagai contoh, kode digunakan untuk kompresi data, kriptografi, koreksi kesalahan, dan pengkodean jaringan. Kode dikaji dalam ragam bidang ilmu—seperti teori informasi, teknik elektro, matematika, dan ilmu komputer—dengan tujuan untuk merancang metode transmisi data yang efisien dan andal. Hal ini biasanya melibatkan penghapusan redundansi dan koreksi (atau deteksi) kesalahan pada transmisi data.

### Biologi komputasi
Biologi komputasi merupakan cabang dari ilmu biologi yang beririsan dengan ilmu komputer yang mengkaji pemahaman serta pemodelan proses dan struktur makhluk hidup. Biologi komputasi mengembangkan dan menerapkan metode analisis dan teori data biologis, pemodelan matematika dari struktur dan proses biologis dan teknik komputasi simulasi dalam sistem biologis, perilaku, dan sosial.  Bidang ini didefinisikan secara luas dan beririsan dengan kajian-kajian dalam ilmu komputer, matematika terapan, animasi, statistik, biokimia, kimia, biofisika, biologi molekuler, genetika, genomik, ekologi, evolusi, anatomi, ilmu saraf, dan visualisasi.

*Biologi komputasi* berbeda dengan ''komputasi biologi'', yang merupakan subbidang di bawah kajian ilmu komputer dan teknik komputer yang memanfaatkan bioteknologi dan biologi untuk membangun sistem komputer. Namun, kajian biologi komputasi memiliki kemiripan dengan kajian bioinformatika, yaitu ilmu interdisipliner yang mengkaji penyimpanan dan pemrosesan data biologis menggunakan komputer.

### Teori kompleksitas komputasi
Teori kompleksitas komputasi adalah bagian dari kajian teori komputasi mengenai pengelompokkan masalah komputasi sesuai tingkat kompleksitas komputasinya, dan membahas hubungan antar tingkatan kompleksitas tersebut satu sama lain. Dalam kajian ini, yang dimaksud dengan masalah komputasi adalah tugas yang pada prinsipnya dapat diselesaikan oleh komputer. Masalah komputasi tersebut dapat diartikan juga sebagai masalah yang dapat diselesaikan dengan penerapan langkah-langkah matematika secara terstruktur, seperti dengan menggunakan solusi algoritma tertentu.

Suatu masalah komputasi dianggap kompleks/sulit bila pencarian solusi membutuhkan sumber daya komputasi yang besar dalam menjalankan algoritma yang diberikan (penggunaan ruang pada penyimpanan, atau penggunaan memori maupun prosesor atau prosesor grafik). Kajian teori kompleksitas komputasi menelusuri pola-pola masalah-masalah komputasi secara matematika, dan kemudian menyusun model komputasi matematis untuk mempelajari masalah-masalah ini. Model komputasi tersebut juga menghitung jumlah sumber daya yang dibutuhkan untuk pencarian solusi, seperti waktu proses dan ruang penyimpanan.

Teori kompleksitas komputasi juga mengkaji ukuran-ukuran kompleksitas lainnya, seperti jumlah komunikasi (digunakan dalam kajian kompleksitas komunikasi), jumlah gerbang dalam suatu rangkaian digital (digunakan dalam kajian kompleksitas rangkaian) dan jumlah unit prosesor yang bekerja (digunakan dalam kajian komputasi paralel). Salah satu peran teori kompleksitas komputasi adalah untuk menentukan batasan praktis tentang apa yang dapat dan tidak dapat dilakukan oleh komputer.

### Geometri komputasi
Geometri komputasi adalah cabang ilmu komputer yang mengkaji secara sistematis algoritma dan struktur data yang digunakan pada objek-objek geometri, dengan fokus untuk menemukan algoritma yang dapat dengan cepat menyelesaikan masalah-masalah geometris. Beberapa masalah dalam kajian geometri murni juga ditemukan dan dapat dipecahkan melalui studi algoritma geometri komputasi.

Kajian geometri komputasi sebagai disiplin ilmu bermula dari perkembangan kajian grafika komputer serta desain dan manufaktur berbantuan komputer (*computer-aided design/*CAD, *computer-aided manufacturing/*CAM). Seiring dengan perkembangan kajian geometri komputasi, banyak masalah geometri klasik dibahas melalui perspektif geometri komputasi seperti topologi, geometri konveks, dan geometri polihedron.

Penerapan algoritma hasil kajian geometri komputasi dimanfaatkan dalam ragam bidang, termasuk robotika (perencanaan gerak dan masalah visibilitas), sistem informasi geografis (*Geographical Information System/*GIS; lokasi dan pencarian geometris, perencanaan rute), desain sirkuit terpadu (*integrated circuit/IC*; desain dan verifikasi geometri IC), teknik berbantuan komputer (*Computer-aided Engineering/*CAE; generasi jaring), visi komputer (rekonstruksi 3D).

### Teori komputasi pembelajaran
Teori komputasi pembelajaran mengkaji proses kognisi secara matematis, memberikan penjelasan menggunakan nalar matematika yang kaku (*rigor*) mengenai bagaimana proses pembelajaran terjadi. Teori ini mengambil fokus dalam pembelajaran terarah (*supervised learning*) dalam konteks pembelajaran mesin. 

Dalam pembelajaran terarah, suatu algoritma diberikan sampel-sampel yang telah diberi label untuk belajar/berlatih dengan sampel-sampel berlabel tersebut. Sebagai contoh, tupel pada sampel jamur berisi data-data deskriptif ragam spesies jamur, dan labelnya bisa berupa apakah jamur-jamur tersebut dapat dimakan atau tidak. Algoritma yang akan dilatih mengambil sampel yang telah dilabeli terlebih dahulu dan membuat suatu fungsi klasifikasi yang mempelajari secara induksi pola-pola relasi antara label jamur dan sampel data jamur.

Kemudian, fungsi klasifikasi memberikan label pada sampel uji ataupun sampel baru yang belum diproses melalui algoritma tersebut. Dari hasil pelabelan sampel uji, akan dilakukan perbandingan dengan sampel latih dan dilihat keakuratan prediksi fungsi klasifikasi dalam mengklasifikasikan jamur yang bisa dimakan dan tidak bisa dimakan.

Teori komputasi pembelajaran fokus dalam melakukan analisis formal matematis terhadap keakuratan fungsi klasifikasi dalam contoh. Pada contoh sebelumnya, analisis keakuratan tergolong mudah, karena label bersifat biner (bisa dimakan/1 dan tidak bisa dimakan/0). Teori komputasi pembelajaran juga melakukan eksplorasi formal matematis terhadap ragam bentuk klasifikasi lain, yang terbukti sangat sulit dilakukan.

### Teori komputasi bilangan
Teori komputasi bilangan adalah irisan dari ilmu komputer dan teori bilangan, dengan tujuan mengkaji permasalahan dalam teori bilangan dari sudut pandang ilmu komputer, dan mencari algoritma yang efisien untuk memecahkan masalah-masalah tersebut.  Permasalahan-permasalahan bilangan yang dibahas dalam teori bilangan komputasi umumnya melibatkan bilangan bulat (*integer*) yang berukuran terlalu besar untuk ditampung atau diproses dalam komputer dengan prosesor 32 maupun 64 bita.

Topik-topik yang dibahas dalam kajian teori bilangan komputas contohnya adalah faktorisasi prima, bilangan kongruen, uji primalitas bilangan. Karena berhubungan dengan bilangan prima, kajian ini memiliki aplikasi, salah satunya, dalam bidang kriptografi dan kriptoanalisis.

## Catatan

## Referensi