Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

2026-08-23T04:15:27Z

Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29440653; atribusi sumber disertakan.

2026-08-23T03:51:23Z

Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29440653; atribusi sumber disertakan.

Halaman baru

'''Ilmu komputer teoretis''' ([[Bahasa Inggris|en]]: ''Theoretical computer science,'' TCS) merupakan irisan dari [[ilmu komputer]] umum dan [[Matematika|ilmu matematika]] yang fokus pada teori matematis dari [[ilmu komputer]] yang mencakup [[teori komputasi]], [[Bahasa formal|teori bahasa formal]], [[Kalkulus Lambda|kalkulus lambda]], dan [[Ketik teori|teori tipe]] .

Kompleksitas dari istilah "teori/teoretis" membuat penentuan definisi ilmu komputer teoretis sulit. [[SIGAK ACM|Kelompok Minat Khusus Algoritma dan Teori Komputasi]] (''Special Interest Group on Algorithms and Computation Theory,'' SIGACT) dari [[Association for Computing Machinery|ACM]] menjelaskan bahwa ilmu komputer teoretik mencakup ragam topik seperti [[algoritma]], [[struktur data]], kompleksitas komputasi, [[komputasi paralel]] dan [[Komputasi terdistribusi|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 ketaklengkapan Gödel|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 O. Hebb|Donald Hebb]] memperkenalkan model matematis yang menggambarkan proses biologis aktivitas [[Pembelajaran Hebbian|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 syaraf|jaringan saraf tiruan]] dan [[Koneksionisme|pemrosesan terdistribusi paralel]]. Pada tahun 1971, [[Stephen Cook]] dan [[Leonid Levin]] [[Penemuan berganda|secara independen]] membuktikan bahwa terdapat permasalahan matematika yang bersifat [[NP-lengkap|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 [[Richard Feynman|Feynman]], Yuri Manin dan peneliti lain kemudian menemukan bahwa fenomena [[Keterkaitan kuantum|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 kuantum|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 [[Komputasi kuantum|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 [[Kompleksitas waktu|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]], [[Pengolahan data|pemrosesan data]], dan [[penalaran otomatis]].

Algoritma adalah [[Metode yang efektif|metode efektif]] berupa daftar [[wiktionary:finite|terbatas]] dari instruksi yang didefinisikan dengan akurat untuk menghitung suatu [[Fungsi (matematika)|fungsi]]. Daftar langkah tersebut dimulai dari keadaan (''state'') awal dan masukan (''input'') awal, atau bisa jadi berisi nilai [[String nol|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 [[Determinisme|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 otomata|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 [[Bahasa Yunani|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 (fisika)|gaya]]) dan luaran berupa kondisi akhir yang menjadi keadaan awal bagi langkah berikutnya. Dalam matematika, [[Fungsi (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 kode|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 listrik|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]], [[Statistika|statistik]], [[biokimia]], [[kimia]], [[biofisika]], [[biologi molekuler]], [[genetika]], [[Genomika|genomik]], [[ekologi]], [[evolusi]], [[anatomi]], [[ilmu saraf]], dan [[Visualisasi ilmiah|visualisasi]].

''Biologi komputasi'' berbeda dengan [[Perhitungan biologis|''komputasi biologi'']], yang merupakan subbidang di bawah kajian ilmu komputer dan [[teknik komputer]] yang memanfaatkan [[Rekayasa hayati|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 [[persoalan komputasi|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 [[Unit Pemroses Sentral|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 logika|gerbang]] dalam suatu rangkaian digital (digunakan dalam kajian [[Kompleksitas sirkuit|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 [[CAD|desain]] dan [[Manufaktur tertunjang komputer|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), [[CAE|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 [[Pemelajaran terarah|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]], [[Kongruen|bilangan kongruen]], uji primalitas bilangan. Karena berhubungan dengan bilangan prima, kajian ini memiliki aplikasi, salah satunya, dalam bidang [[kriptografi]] dan [[Analisis kriptografi|kriptoanalisis]].

== Catatan ==

== Referensi ==

== Sumber dan atribusi ==

Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Ilmu+komputer+teoretis&oldid=29440653 Wikipedia bahasa Indonesia], revisi 29440653 (2026-07-10T15:33:48Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

Ilmu komputer teoretis - Riwayat revisi

Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29440653; atribusi sumber disertakan.