Wikipedia

Ilmu komputer teoretis

bagian dari ilmu komputer dan matematika
Revisi sejak 20 Desember 2023 12.18 oleh Athayahisyam (bicara | kontrib) (Perbaikan blok kutipan)

Ilmu komputer teoretis (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 .

Representasi artistik dari mesin Turing . Mesin Turing digunakan untuk memodelkan perangkat komputasi umum.

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):

TCS covers a wide variety of topics including algorithms, data structures, computational complexity, parallel and distributed computation, probabilistic computation, quantum computation, automata theory, information theory, cryptography, program semantics and verification, algorithmic game theory, machine learning, computational biology, computational economics, computational geometry, and computational number theory and algebra. Work in this field is often distinguished by its emphasis on mathematical technique and rigor.[1]

Sejarah

Pada tahun 1931[2], 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.[3]

Kajian mengenai teori informasi dimulai kemudian dengan publikasi teori matematika pada proses komunikasi digital pada tahun 1948 oleh Claude Shannon.[4][5] Pada dekade yang sama, Donald Hebb memperkenalkan model matematis yang menggambarkan proses biologis aktivitas pembelajaran di otak manusia.[6] Hipotesis Hebb tersebut didukung oleh banyaknya data biologis dari penelitian-penelitian mengenai jaringan syaraf. Dari penelitian-penelitian tersebut, mulai dikenal kajian jaringan saraf tiruan[7][8] dan pemrosesan terdistribusi paralel.[8] Pada tahun 1971, Stephen Cook[9] dan Leonid Levin[10][11] secara independen[11] 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.[12]

Pada awal tahun 1980, beberapa peneliti menyadari bahwa prinsip-prinsip mekanika kuantum memiliki implikasi pada perspektif mengenai pemrosesan informasi.[12] 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.[13] 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.[12][14]

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.[15] Melalui penelusuran lebih lanjut, ditemukan bahwa algoritma ini berpotensi membuat algoritma kriptografi kunci publik seperti RSA menjadi tidak aman.[16]

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:

   </img>  </img>  </img>  </img> P = NP ?
Logika matematika Teori automata Teori bilangan Teori grafik Teori komputasi Teori kompleksitas komputasi
GNITIRW-TERCES    </img>  </img>  </img>  </img>
Kriptografi Teori tipe Teori kategori Geometri komputasi Optimasi kombinatorial Teori komputasi kuantum

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 terbatas dari instruksi yang didefinisikan dengan akurat untuk menghitung suatu fungsi.[17] Daftar langkah tersebut dimulai dari keadaan (state) awal dan masukan (input) awal, atau bisa jadi berisi nilai kosong.[18] 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)[18] 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.[19]

Teori automata

Teori automata adalah kajian mengenai mesin abstrak dan 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.[20] 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.[21] Dalam matematika, fungsi yang menggambarkan relasi antara dua variabel dapat menghasilkan luaran berbeda tiap kali variabel masukan berubah.[20] Teori automata mengkaji kelakuan dinamis dari hubungan antara masukan dan luaran dari automaton dan memberikan pembuktian matematis dari tingkah laku dinamis tersebut.[22]

Teori pengkodean

Teori pengkodean mengkaji aspek matematika dari metode (dalam konteks kajian ini disebut sebagai "kode"[23]) untuk mengoreksi galat pada transmisi informasi. Kode merepresentasikan data sedemikian rupa sehingga informasi tetap dapat diterima, meskipun ditemukan galat/kesalahan pada data.[24] 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.[25]

Biologi komputasi

Biologi komputasi merupakan cabang dari ilmu biologi yang beririsan dengan ilmu komputer yang mengkaji pemahaman serta pemodelan proses dan struktur makhluk hidup.[26] 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. [27] 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.[28]

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.[26] Namun, kajian biologi komputasi memiliki kemiripan dengan kajian bioinformatika, yaitu ilmu interdisipliner yang mengkaji penyimpanan dan pemrosesan data biologis menggunakan komputer.[26]

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.[29] Dalam kajian ini, yang dimaksud dengan masalah komputasi adalah tugas yang pada prinsipnya dapat diselesaikan oleh komputer.[30] 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).[31] Kajian teori kompleksitas komputasi menelusuri pola-pola masalah-masalah komputasi secara matematika, dan kemudian menyusun model komputasi matematis untuk mempelajari masalah-masalah ini.[31] 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),[32] jumlah gerbang dalam suatu rangkaian digital (digunakan dalam kajian kompleksitas rangkaian)[33] dan jumlah unit prosesor yang bekerja (digunakan dalam kajian komputasi paralel).[34][35] 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.[36] 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).[36] Seiring dengan perkembangan kajian geometri komputasi, banyak masalah geometri klasik dibahas melalui perspektif geometri komputasi seperti topologi, geometri konveks, dan geometri polihedron.[37]

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

Referensi

  1. ^ "SIGACT". Diakses tanggal 2017-01-19. 
  2. ^ Wolchover, Natalie, ed. (2020-07-20). "How Gödel's Proof Works". Quanta Magaznie. Diakses tanggal 2023-12-19. 
  3. ^ Raatikainen, Panu (2022). "Gödel's Incompleteness Theorems". Dalam Zalta, Edward N. Stanford Encyclopedia of Philosophy (edisi ke-Spring 2022). Metaphysics Research Lab, Stanford University. 
  4. ^ Tse, David, ed. (2020-12-22). "How Claude Shannon Invented the Future". Quanta Magazine. Diakses tanggal 2023-12-19. 
  5. ^ O'Regan, Gerard (2016). Introduction to the History of Computing. Undergraduate Topics in Computer Science. Cham: Springer International Publishing. doi:10.1007/978-3-319-33138-6. ISBN 978-3-319-33137-9. 
  6. ^ Langille, Jesse J.; Brown, Richard E. (2018-10-26). "The Synaptic Theory of Memory: A Historical Survey and Reconciliation of Recent Opposition". Frontiers in Systems Neuroscience. 12. doi:10.3389/fnsys.2018.00052. ISSN 1662-5137. 
  7. ^ Lee, Chuang-Chung (2008). "Kinetic modeling of amyloid fibrillation and synaptic plasticity as memory loss and formation mechanisms" (Academic dissertation). Massachusetts Institute of Technology. 
  8. ^ a b Karaminis, Themis N.; Thomas, Michael S. C. (2012). Seel, Norbert M., ed. Connectionist Theories of Learning (dalam bahasa Inggris). Boston, MA: Springer US. hlm. 771–774. doi:10.1007/978-1-4419-1428-6_398. ISBN 978-1-4419-1427-9. 
  9. ^ Cook, Stephen A. (1971). "The complexity of theorem-proving procedures" (dalam bahasa Inggris). ACM Press: 151–158. doi:10.1145/800157.805047. 
  10. ^ Levin, Leonid A. (1973). "Universal Sequential Search Problems". Probl. Peredachi Inf. (dalam bahasa Rusia). 9 (3): 265–266. 
  11. ^ a b Trakhtenbrot, B.A. (1984-10). "A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms". IEEE Annals of the History of Computing. 6 (4): 384–400. doi:10.1109/MAHC.1984.10036. ISSN 1058-6180. 
  12. ^ a b c Rieffel, Eleanor; Polak, Wolfgang (2014). Quantum computing: a gentle introduction. Scientific and engineering computation (edisi ke-First MIT Press paperback edition). Cambridge, Massachusetts London, England: The Mit Press. ISBN 978-0-262-52667-8. 
  13. ^ Feynman, Richard (2013). "Quantum Behavior". Dalam Gottlieb, Michael A.; Pfeiffer, Rudolf. The Feynman Lectures. California: California Institute of Technology. 
  14. ^ "The Very Strange—And Fascinating— Ideas Behind Quantum Computing | Digital Tonto". Digital Tonto | (dalam bahasa Inggris). 2016-07-31. Diakses tanggal 2023-12-19. 
  15. ^ Shor, Peter W. (1997-10). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Journal on Computing. 26 (5): 1484–1509. doi:10.1137/S0097539795293172. ISSN 0097-5397. 
  16. ^ Brubaker, Ben (2023-10-17). "Thirty Years Later, a Speed Boost for Quantum Factoring". Quanta Magazine. Diakses tanggal 2023-12-19. 
  17. ^ Rogers, Hartley (2002). Theory of recursive functions and effective computability (edisi ke-5. print). Cambridge, Mass.: MIT Press. ISBN 978-0-262-68052-3. 
  18. ^ a b Knuth, Donald Ervin; Knuth, Donald Ervin (1990). Fundamental algorithms. The art of computer programming / Donald E. Knuth (edisi ke-2. ed., [Nachdr.]). Reading, Mass.: Addison-Wesley. ISBN 978-0-201-03821-7. 
  19. ^ Whether or not a process with random interior processes (not including the input) is an algorithm is debatable. Rogers opines that: "a computation is carried out in a discrete stepwise fashion, without the use of continuous methods or analog devices . . . carried forward deterministically, without resort to random methods or devices, e.g., dice" (Rogers 1967).
  20. ^ a b Aziz, Amar Dar; Cackler, Joe; Yung, Raylene. "Basics of Automata Theory". Automata Theory (dalam bahasa Inggris). Stanford Computer Science Department. Diakses tanggal 2023-12-19. 
  21. ^ Rankin, Bayard; Nelson, R.J. "Automata theory | Finite State Machines, Turing Machines & Algorithms | Britannica". Encyclopaedia Britannica (dalam bahasa Inggris). Diakses tanggal 2023-12-20. 
  22. ^ Sipser, Michael (2013). Introduction to the theory of computation (edisi ke-Third edition, international edition). United States: Cengage Learning. ISBN 978-1-133-18779-0. 
  23. ^ Weisstein, Eric W. "Coding Theory". mathworld.wolfram.com (dalam bahasa Inggris). Diakses tanggal 2023-12-19. 
  24. ^ Guruswami, Venkatesan; Rudra, Atri; Sudan, Madhu (2023). Essential Coding Theory. New York: Department of Computer Science and Engineering, University at Buffalo, SUNY. 
  25. ^ van Lint, J. H. (1999). Introduction to Coding Theory. Graduate Texts in Mathematics. 86. Berlin, Heidelberg: Springer Berlin Heidelberg. doi:10.1007/978-3-642-58575-3. ISBN 978-3-642-63653-0. 
  26. ^ a b c Searls, David B. "Computational biology | Algorithms, Data Analysis & Modeling | Britannica". www.britannica.com (dalam bahasa Inggris). Diakses tanggal 2023-12-19. 
  27. ^ "NIH working definition of bioinformatics and computational biology" (PDF). Biomedical Information Science and Technology Initiative. 17 July 2000. Diarsipkan dari versi asli (PDF) tanggal 5 September 2012. Diakses tanggal 18 August 2012. 
  28. ^ "About the CCMB". Center for Computational Molecular Biology. Diakses tanggal 18 August 2012. 
  29. ^ Dean, Walter (2021). Zalta, Edward N., ed. Computational Complexity Theory (edisi ke-Fall 2021). Metaphysics Research Lab, Stanford University. 
  30. ^ Arora, Sanjeev; Barak, Boaz (2016). Computational complexity: A Modern Approach (edisi ke-4th printing 2016). New York: Cambridge University Press. ISBN 978-0-521-42426-4. 
  31. ^ a b Goldberg, Lesile Ann (2019). "Computational Complexity Theory: An introduction". Research - St. Edmund Hall - University of Oxford (dalam bahasa Inggris). Diakses tanggal 2023-12-20. 
  32. ^ Braverman, Mark (2023-12-15). Communication and information complexity. hlm. 284–320. doi:10.4171/icm2022/208. 
  33. ^ Savage, John E. (2003). "Circuit Commplexity" (PDF). Models of computation: exploring the power of computing (edisi ke-cetak ulang). Reading, Mass.: Addison-Wesley. ISBN 978-0-201-89539-1. 
  34. ^ Wylie, James C. (1979). The Complexity of Parallel Computations. Cornell University. 
  35. ^ Fürer, Martin (2008). Floudas, Christodoulos A.; Pardalos, Panos M., ed. Parallel Computing: Complexity Classes (dalam bahasa Inggris). Boston, MA: Springer US. hlm. 2900–2903. doi:10.1007/978-0-387-74759-0_498. ISBN 978-0-387-74758-3. 
  36. ^ a b c d e f Berg, Mark de (2008). Computational Geometry: Algorithms and Applications (edisi ke-3d Edition). Berlin, Heidelberg: Springer-Verlag Berlin Heidelberg. ISBN 978-3-540-77974-2. 
  37. ^ a b c Goodman, Jacob E.; O'Rourke, Joseph; Tóth, Csaba D., ed. (2018). Handbook of discrete and computational geometry. Discrete mathematics and its applications (edisi ke-Third edition). Boca Raton London New York: CRC Press, Taylor & Francis Group, a Chapman & Hall book. ISBN 978-1-4987-1139-5. 
  38. ^ "What is Computational Geometry?". Computer Science Degree Hub (dalam bahasa Inggris). Diakses tanggal 2023-12-20. 
Diperoleh dari "https://wiki-indonesia.club/w/index.php?title=Ilmu_komputer_teoretis&oldid=25038369"