Ilmu komputer teoretis: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Penambahan header referensi |
Fitur saranan suntingan: 3 pranala ditambahkan. |
||
| (12 revisi perantara oleh 3 pengguna tidak ditampilkan) | |||
Baris 1:
[[Berkas:Maquina.png|jmpl| Representasi artistik dari [[mesin Turing]] . Mesin Turing digunakan untuk memodelkan perangkat komputasi umum.]]
'''Ilmu komputer <span lang="Krystal" dir="ltr">teoretis</span>''' ([[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 ==
Baris 11 ⟶ 9:
Kajian mengenai [[teori informasi]] dimulai kemudian dengan publikasi teori matematika pada proses komunikasi digital pada tahun 1948 oleh [[Claude Shannon]].<ref>{{Cite news|date=2020-12-22|editor-last=Tse|editor-first=David|title=How Claude Shannon Invented the Future|url=https://www.quantamagazine.org/how-claude-shannons-information-theory-invented-the-future-20201222/|work=Quanta Magazine|access-date=2023-12-19}}</ref><ref>{{Cite book|last=O'Regan|first=Gerard|date=2016|url=http://link.springer.com/10.1007/978-3-319-33138-6|title=Introduction to the History of Computing|location=Cham|publisher=Springer International Publishing|isbn=978-3-319-33137-9|series=Undergraduate Topics in Computer Science|doi=10.1007/978-3-319-33138-6}}</ref> Pada dekade yang sama, [[Donald O. Hebb|Donald Hebb]] memperkenalkan model matematis yang menggambarkan proses biologis aktivitas [[Pembelajaran Hebbian|pembelajaran]] di otak manusia.<ref>{{Cite journal|last=Langille|first=Jesse J.|last2=Brown|first2=Richard E.|date=2018-10-26|title=The Synaptic Theory of Memory: A Historical Survey and Reconciliation of Recent Opposition|url=https://www.frontiersin.org/article/10.3389/fnsys.2018.00052/full|journal=Frontiers in Systems Neuroscience|volume=12|doi=10.3389/fnsys.2018.00052|issn=1662-5137}}</ref> 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]]<ref>{{Cite journal|last=Lee|first=Chuang-Chung|date=2008|title=Kinetic modeling of amyloid fibrillation and synaptic plasticity as memory loss and formation mechanisms|url=https://dspace.mit.edu/handle/1721.1/49893|journal=|type=Academic dissertation|publisher=Massachusetts Institute of Technology}}</ref><ref name=":0">{{Cite book|last=Karaminis|first=Themis N.|last2=Thomas|first2=Michael S. C.|date=2012|url=http://link.springer.com/10.1007/978-1-4419-1428-6_398|title=Connectionist Theories of Learning|location=Boston, MA|publisher=Springer US|isbn=978-1-4419-1427-9|editor-last=Seel|editor-first=Norbert M.|pages=771–774|language=en|doi=10.1007/978-1-4419-1428-6_398}}</ref> dan [[Koneksionisme|pemrosesan terdistribusi paralel]].<ref name=":0" /> Pada tahun 1971, [[Stephen Cook]]<ref>{{Cite journal|last=Cook|first=Stephen A.|date=1971|title=The complexity of theorem-proving procedures|url=http://portal.acm.org/citation.cfm?doid=800157.805047|language=en|publisher=ACM Press|pages=151–158|doi=10.1145/800157.805047}}</ref> dan [[Leonid Levin]]<ref>{{Cite journal|last=Levin|first=Leonid A.|date=1973|title=Universal Sequential Search Problems|url=https://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=ppi&paperid=914&option_lang=eng|journal=Probl. Peredachi Inf.|language=Rusia|volume=9|issue=3|pages=265–266}}</ref><ref name=":1">{{Cite journal|last=Trakhtenbrot|first=B.A.|date=1984-10|title=A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms|url=http://ieeexplore.ieee.org/document/4640789/|journal=IEEE Annals of the History of Computing|volume=6|issue=4|pages=384–400|doi=10.1109/MAHC.1984.10036|issn=1058-6180}}</ref> [[Penemuan berganda|secara independen]]<ref name=":1" /> 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]].<ref name=":2">{{Cite book|last=Rieffel|first=Eleanor|last2=Polak|first2=Wolfgang|date=2014|title=Quantum computing: a gentle introduction|url=https://archive.org/details/quantumcomputing0000rief|location=Cambridge, Massachusetts London, England|publisher=The Mit Press|isbn=978-0-262-52667-8|edition=First MIT Press paperback edition|series=Scientific and engineering computation}}</ref> ▼
▲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]].<ref name=":2">{{Cite book|last=Rieffel|first=Eleanor|last2=Polak|first2=Wolfgang|date=2014|title=Quantum computing: a gentle introduction|location=Cambridge, Massachusetts London, England|publisher=The Mit Press|isbn=978-0-262-52667-8|edition=First MIT Press paperback edition|series=Scientific and engineering computation}}</ref>
Pada awal tahun 1980, beberapa peneliti menyadari bahwa prinsip-prinsip mekanika kuantum memiliki implikasi pada perspektif mengenai pemrosesan informasi.<ref name=":2" /> 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.<ref>{{Cite book|last=Feynman|first=Richard|date=2013|title=The Feynman Lectures|location=California|publisher=California Institute of Technology|editor-last=Gottlieb|editor-first=Michael A.|chapter=Quantum Behavior|editor-last2=Pfeiffer|editor-first2=Rudolf|chapter-url=https://www.feynmanlectures.caltech.edu/III_01.html|url-status=live}}</ref> 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]].<ref name=":2" /><ref>{{Cite web|date=2016-07-31|title=The Very Strange—And Fascinating— Ideas Behind Quantum Computing {{!}} Digital Tonto|url=https://digitaltonto.com/2016/the-very-strange-and-fascinating-ideas-behind-quantum-computing/|website=Digital Tonto {{!}}|language=en|access-date=2023-12-19}}</ref>
Baris 22 ⟶ 18:
{| cellspacing="15" style="border:1px solid #ddd; text-align:center; margin: 0 auto;"
|<math> P \rightarrow Q \,</math>
|[[Berkas:DFAexample.svg|96x96px]]
|[[Berkas:Elliptic_curve_simple.svg|107x107px]]
|[[Berkas:6n-graf.svg|96x96px]]
|[[Berkas:Wang_tiles.svg|96x96px]]
| '''P = NP''' ?
|-
Baris 32 ⟶ 28:
| [[Teori bilangan]]
| [[Teori graf|Teori grafik]]
| [[Teori komputasi]]
| [[Teori kompleksitas komputasi]]
|-
| '''GNITIRW-TERCES'''
| <math>\Gamma\vdash x: \text{Int}</math>
|[[Berkas:Commutative_diagram_for_morphism.svg|96x96px]]</img>
|[[Berkas:SimplexRangeSearching.svg|104x104px]]
|[[Berkas:TSP_Deutschland_3.png|103x103px]]
|[[Berkas:Blochsphere.svg|96x96px]]
|-
| [[Kriptografi]]
| [[Teori tipe]]
| [[Teori kategori]]
| [[Geometri komputasi]]
| [[Optimasi kombinatorial]]
| [[Komputasi kuantum|Teori komputasi kuantum]]
|}
Baris 63 ⟶ 59:
=== 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.<ref>{{Cite web|last=Weisstein|first=Eric W.|title=Coding Theory|url=https://mathworld.wolfram.com/CodingTheory.html|website=mathworld.wolfram.com|language=en|access-date=2023-12-19}}</ref>
=== Biologi komputasi ===
[[Biologi komputasi]] merupakan cabang dari ilmu biologi yang beririsan dengan ilmu komputer yang mengkaji pemahaman serta pemodelan proses dan struktur [[makhluk hidup]].<ref name=":5">{{Cite web|last=Searls|first=David B.|title=Computational biology {{!}} Algorithms, Data Analysis & Modeling {{!}} Britannica|url=https://www.britannica.com/science/computational-biology|website=www.britannica.com|language=en|access-date=2023-12-19}}</ref> 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. <ref name="nih">
{{Cite web|date=17 July 2000|title=NIH working definition of bioinformatics and computational biology|url=http://www.bisti.nih.gov/docs/compubiodef.pdf|publisher=Biomedical Information Science and Technology Initiative|archive-url=https://web.archive.org/web/20120905155331/http://www.bisti.nih.gov/docs/CompuBioDef.pdf|archive-date=5 September 2012|access-date=18 August 2012|url-status=dead}}
</ref> 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]].<ref name="brown">
Baris 87 ⟶ 83:
Penerapan algoritma hasil kajian geometri komputasi dimanfaatkan dalam ragam bidang, termasuk [[robotika]] (perencanaan gerak dan masalah visibilitas),<ref name=":7" /> [[sistem informasi geografis]] (''Geographical Information System/''GIS; lokasi dan pencarian geometris, perencanaan rute),<ref>{{Cite web|title=What is Computational Geometry?|url=https://www.computersciencedegreehub.com/faq/what-is-computational-geometry/|website=Computer Science Degree Hub|language=en-US|access-date=2023-12-20}}</ref><ref name=":7" /> desain [[sirkuit terpadu]] (''integrated circuit/IC''; desain dan verifikasi geometri IC),<ref name=":7" /> [[CAE|teknik berbantuan komputer]] (''Computer-aided Engineering/''CAE; generasi jaring),<ref name=":8" /> [[visi komputer]] (rekonstruksi 3D).<ref name=":7" /><ref name=":8" />
=== Teori komputasi pembelajaran ===
Teori komputasi pembelajaran mengkaji proses [[kognisi]] secara matematis,<ref>{{Cite book|last=Anthony|first=Martin|last2=Biggs|first2=Norman|date=1997|title=Computational learning theory: an introduction|location=Cambridge|publisher=Cambridge Univ. Press|isbn=978-0-521-41603-0|edition=1. paperback ed. (with corr.)|series=Cambridge tracts in theoretical computer science}}</ref> memberikan penjelasan menggunakan nalar matematika yang kaku (''rigor'') mengenai bagaimana proses pembelajaran terjadi.<ref>{{Cite journal|last=Angluin|first=Dana|date=1992|title=Computational learning theory: survey and selected bibliography|url=http://portal.acm.org/citation.cfm?doid=129712.129746|language=en|publisher=ACM Press|pages=351–369|doi=10.1145/129712.129746|isbn=978-0-89791-511-3}}</ref> Teori ini mengambil fokus dalam [[Pemelajaran terarah|pembelajaran terarah]] (''supervised learning'') dalam konteks pembelajaran mesin. <ref name=":02">{{Cite web|last=Brownlee|first=Jason|date=2020-09-07|title=A Gentle Introduction to Computational Learning Theory|url=https://machinelearningmastery.com/introduction-to-computational-learning-theory/|website=Machine Learning Mastery|access-date=2023-12-21}}</ref>
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).<ref name=":02" /> Teori komputasi pembelajaran juga melakukan eksplorasi formal matematis terhadap ragam bentuk klasifikasi lain, yang terbukti sangat sulit dilakukan.<ref>{{Cite book|last=Russell|first=Stuart J.|last2=Norvig|first2=Peter|date=2021|title=Artificial intelligence: a modern approach|location=Hoboken, NJ|publisher=Pearson|isbn=978-0-13-461099-3|edition=Fourth Edition|series=Pearson Series in Artificial Intelligence|others=Ming-wei Chang, Jacob Devlin, Anca Dragan, David Forsyth, Ian Goodfellow, Jitendra Malik, Vikash Mansinghka, Judea Pearl, Michael J. Wooldridge}}</ref>
=== 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.<ref name=":03">{{Cite web|last=Weisstein|first=Eric W.|title=Computational Number Theory|url=https://mathworld.wolfram.com/|website=mathworld.wolfram.com|language=en|access-date=2023-12-21}}</ref> 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.<ref name=":12">{{Cite book|last=Wagstaff, Jr.|first=Samuel S.|date=2010|url=https://dl.acm.org/doi/book/10.5555/1882757|title=Algorithms and theory of computation handbook. 1: General concepts and techniques|location=|publisher=Chapman & Hall|isbn=978-1-58488-822-2|editor-last=Atallah|editor-first=Mikhail J.|edition=2. ed|chapter=Computational Number Theory|editor-last2=Blanton|editor-first2=Marina|chapter-url=https://dl.acm.org/doi/pdf/10.5555/1882757.1882773|url-status=live}}</ref>
Topik-topik yang dibahas dalam kajian teori bilangan komputas contohnya adalah [[faktorisasi prima]],<ref name=":03" /><ref name=":12" /> [[Kongruen|bilangan kongruen]],<ref name=":03" /> uji primalitas bilangan.<ref name=":12" /> Karena berhubungan dengan bilangan prima, kajian ini memiliki aplikasi, salah satunya, dalam bidang [[kriptografi]] dan [[Analisis kriptografi|kriptoanalisis]].<ref>{{Cite book|last=Das|first=Abhijit|date=2013|title=Computational number theory|location=Boca Raton, Fla.|publisher=CRC Press, Taylor & Francis|isbn=978-1-4398-6615-3|series=Discrete mathematics and its applications}}</ref>
== Catatan ==
{{Notelist}}
== Referensi ==
<references />
[[Kategori:Ilmu formal]]
[[Kategori:
| |||