EITC/IS/CCTF Computational Complexity Theory Fundamentals adalah program Sertifikasi TI Eropa pada aspek teoretis dasar ilmu komputer yang juga merupakan dasar kriptografi kunci publik asimetris klasik yang banyak digunakan di Internet.
Kurikulum Dasar-dasar Teori Kompleksitas Komputasi EITC/IS/CCTF mencakup pengetahuan teoretis tentang dasar-dasar ilmu komputer dan model komputasi berdasarkan konsep dasar seperti mesin keadaan hingga deterministik dan nondeterministik, bahasa reguler, tata bahasa bebas konteks dan teori bahasa, teori automata, Turing Mesin, pemecahan masalah, rekursi, logika, dan kompleksitas algoritme untuk aplikasi keamanan mendasar dalam struktur berikut, yang mencakup konten didaktik video yang komprehensif sebagai referensi untuk Sertifikasi EITC ini.
Kompleksitas komputasi algoritma adalah jumlah sumber daya yang dibutuhkan untuk mengoperasikannya. Sumber daya waktu dan memori diberi perhatian khusus. Kompleksitas masalah didefinisikan sebagai kompleksitas algoritma terbaik untuk menyelesaikannya. Analisis algoritma adalah studi tentang kompleksitas algoritma yang diberikan secara eksplisit, sedangkan teori kompleksitas komputasi adalah studi tentang kompleksitas solusi masalah dengan algoritma yang paling dikenal. Kedua domain tersebut saling terkait karena kompleksitas suatu algoritma selalu menjadi kendala atas kompleksitas masalah yang dipecahkannya. Selain itu, sering kali diperlukan untuk membandingkan kompleksitas algoritma tertentu dengan kompleksitas masalah yang akan dipecahkan saat membangun algoritma yang efisien. Dalam kebanyakan keadaan, satu-satunya informasi yang tersedia mengenai kesulitan masalah adalah bahwa hal itu kurang dari kompleksitas teknik yang diketahui paling efisien. Akibatnya, ada banyak tumpang tindih antara analisis algoritma dan teori kompleksitas.
Teori kompleksitas berperan penting tidak hanya dalam fondasi model komputasi sebagai dasar ilmu komputer tetapi juga dalam fondasi kriptografi asimetris klasik (disebut kriptografi kunci publik) yang tersebar luas di jaringan modern, terutama di Internet. Enkripsi kunci publik didasarkan pada kesulitan komputasi dari masalah matematika asimetris tertentu seperti misalnya faktorisasi bilangan besar menjadi faktor prima (operasi ini merupakan masalah yang sulit dalam klasifikasi teori kompleksitas, karena tidak diketahui algoritma klasik yang efisien untuk dipecahkan. dengan sumber daya penskalaan polinomial daripada eksponensial dengan peningkatan ukuran input masalah, yang berbeda dengan operasi kebalikan yang sangat sederhana mengalikan ke faktor prima yang diketahui untuk memberikan jumlah besar asli). Menggunakan asimetri ini dalam arsitektur kriptografi kunci publik (dengan mendefinisikan hubungan asimetris komputasional antara kunci publik, yang dapat dengan mudah dihitung dari kunci privat, sedangkan kunci privat tidak dapat dengan mudah dikomputerisasi dari kunci publik, seseorang dapat secara publik mengumumkan kunci publik dan memungkinkan pihak komunikasi lain menggunakannya untuk enkripsi data asimetris, yang kemudian hanya dapat didekripsi dengan kunci pribadi yang digabungkan, tidak tersedia secara komputasi untuk pihak ketiga, sehingga membuat komunikasi menjadi aman).
Teori kompleksitas komputasi dikembangkan terutama pada pencapaian ilmu komputer dan pelopor algoritmik, seperti Alan Turing, yang karyanya sangat penting untuk memecahkan sandi Enigma Nazi Jerman, yang memainkan peran penting dalam memenangkan Perang Dunia Kedua oleh sekutu. Kriptanalisis bertujuan merancang dan mengotomatisasi proses komputasi menganalisis data (terutama komunikasi terenkripsi) untuk mengungkap informasi tersembunyi yang digunakan untuk menembus sistem kriptografi dan mendapatkan akses ke konten komunikasi terenkripsi, biasanya kepentingan militer strategis. Itu juga kriptanalisis yang mengkatalisasi pengembangan komputer modern pertama (yang awalnya diterapkan pada tujuan strategis pemecah kode). Colossus Inggris (dianggap sebagai komputer elektronik dan program modern pertama) didahului oleh "bom" Polandia, perangkat komputasi elektronik yang dirancang oleh Marian Rejewski untuk membantu memecahkan sandi Enigma, dan diserahkan ke Inggris Raya oleh intelijen Polandia bersama dengan mesin enkripsi Enigma Jerman yang ditangkap, setelah Polandia diserbu oleh Jerman pada tahun 1939. Atas dasar perangkat ini, Alan Turing mengembangkan rekan yang lebih maju untuk berhasil memecahkan komunikasi terenkripsi Jerman, yang kemudian dikembangkan menjadi komputer modern.
Karena jumlah sumber daya yang diperlukan untuk menjalankan suatu algoritma bervariasi dengan ukuran input, kompleksitas biasanya dinyatakan sebagai fungsi f(n), di mana n adalah ukuran input dan f(n) adalah kompleksitas kasus terburuk ( jumlah maksimum sumber daya yang diperlukan di semua input ukuran n) atau kompleksitas kasus rata-rata (rata-rata jumlah sumber daya di semua input ukuran n). Jumlah operasi dasar yang diperlukan pada input berukuran n biasanya dinyatakan sebagai kompleksitas waktu, di mana operasi dasar diyakini memakan waktu yang konstan pada komputer tertentu dan hanya berubah dengan faktor konstan ketika dijalankan pada mesin yang berbeda. Jumlah memori yang dibutuhkan oleh suatu algoritma pada input berukuran n dikenal sebagai kompleksitas ruang.
Waktu adalah sumber daya yang paling sering dianggap. Ketika istilah "kompleksitas" digunakan tanpa kualifikasi, biasanya mengacu pada kompleksitas waktu.
Satuan waktu tradisional (detik, menit, dan seterusnya) tidak digunakan dalam teori kompleksitas karena terlalu bergantung pada komputer yang dipilih dan kemajuan teknologi. Misalnya, komputer saat ini dapat mengeksekusi algoritme secara substansial lebih cepat daripada komputer dari tahun 1960-an, namun, hal ini disebabkan oleh terobosan teknologi dalam perangkat keras komputer daripada kualitas yang melekat pada algoritme. Tujuan teori kompleksitas adalah untuk mengukur kebutuhan waktu yang melekat pada algoritma, atau batasan waktu mendasar yang akan diterapkan oleh suatu algoritma pada komputer mana pun. Hal ini dicapai dengan menghitung berapa banyak operasi dasar yang dilakukan selama perhitungan. Prosedur-prosedur ini biasanya disebut sebagai langkah-langkah karena dianggap membutuhkan waktu yang konstan pada mesin tertentu (yaitu, tidak terpengaruh oleh jumlah input).
Sumber daya penting lainnya adalah jumlah memori komputer yang dibutuhkan untuk melakukan algoritma.
Sumber daya lain yang sering digunakan adalah jumlah operasi aritmatika. Dalam skenario ini, istilah "kompleksitas aritmatika" digunakan. Kompleksitas waktu umumnya produk dari kompleksitas aritmatika dengan faktor konstan jika kendala atas pada ukuran representasi biner dari angka yang terjadi selama perhitungan diketahui.
Ukuran bilangan bulat yang digunakan selama perhitungan tidak dibatasi untuk banyak metode, dan tidak realistis untuk mengasumsikan bahwa operasi aritmatika memerlukan jumlah waktu yang tetap. Akibatnya, kompleksitas waktu, juga dikenal sebagai kompleksitas bit, mungkin jauh lebih tinggi daripada kompleksitas aritmatika. Kesulitan aritmatika menghitung determinan matriks bilangan bulat nn, misalnya, adalah O(n^3) untuk teknik standar (eliminasi Gaussian). Karena ukuran koefisien mungkin berkembang secara eksponensial selama perhitungan, kompleksitas bit dari metode yang sama adalah eksponensial dalam n. Jika teknik ini digunakan bersama dengan aritmatika multi-modular, kompleksitas bit dapat dikurangi menjadi O(n^4).
Kompleksitas bit, dalam istilah formal, mengacu pada jumlah operasi pada bit yang diperlukan untuk menjalankan suatu algoritma. Ini sama dengan kompleksitas temporal hingga faktor konstan di sebagian besar paradigma komputasi. Jumlah operasi pada kata-kata mesin yang dibutuhkan oleh komputer sebanding dengan kompleksitas bit. Untuk model komputasi yang realistis, kompleksitas waktu dan kompleksitas bit identik.
Sumber daya yang sering diperhatikan dalam pengurutan dan pencarian adalah perbandingan jumlah entri. Jika data diatur dengan baik, ini merupakan indikator yang baik dari kompleksitas waktu.
Pada semua input potensial, menghitung jumlah langkah dalam suatu algoritma tidak mungkin dilakukan. Karena kompleksitas input meningkat dengan ukurannya, biasanya direpresentasikan sebagai fungsi dari ukuran input n (dalam bit), dan kompleksitas adalah fungsi dari n. Namun, untuk input berukuran sama, kompleksitas suatu algoritma dapat sangat bervariasi. Akibatnya, berbagai fungsi kompleksitas digunakan secara rutin.
Kompleksitas kasus terburuk adalah jumlah dari semua kompleksitas untuk semua input berukuran n, sedangkan kompleksitas kasus rata-rata adalah jumlah dari semua kompleksitas untuk semua input berukuran n (ini masuk akal, karena jumlah input yang mungkin dari ukuran tertentu adalah terbatas). Ketika istilah "kompleksitas" digunakan tanpa didefinisikan lebih lanjut, kompleksitas waktu kasus terburuk diperhitungkan.
Kompleksitas kasus terburuk dan kasus rata-rata terkenal sulit untuk dihitung dengan benar. Lebih jauh lagi, nilai eksak ini hanya memiliki sedikit aplikasi praktis karena setiap perubahan pada mesin atau paradigma kalkulasi akan sedikit mengubah kompleksitasnya. Selanjutnya, penggunaan sumber daya tidak penting untuk nilai n kecil, oleh karena itu kemudahan implementasi seringkali lebih menarik daripada kompleksitas rendah untuk n kecil.
Untuk alasan ini, sebagian besar perhatian diberikan pada perilaku kompleksitas untuk n tinggi, yaitu, perilaku asimtotiknya saat n mendekati tak terhingga. Akibatnya, notasi O besar biasanya digunakan untuk menunjukkan kompleksitas.
Model komputasi
Pilihan model komputasi, yang terdiri dari menentukan operasi penting yang dilakukan dalam satuan waktu, sangat penting dalam menentukan kompleksitas. Ini kadang-kadang disebut sebagai mesin Turing multitape ketika paradigma komputasi tidak dijelaskan secara khusus.
Model komputasi deterministik adalah model di mana keadaan mesin berikutnya dan operasi yang akan dilakukan sepenuhnya ditentukan oleh keadaan sebelumnya. Fungsi rekursif, kalkulus lambda, dan mesin Turing adalah model deterministik pertama. Mesin akses acak (juga dikenal sebagai mesin RAM) adalah paradigma populer untuk mensimulasikan komputer dunia nyata.
Ketika model komputasi tidak didefinisikan, mesin Turing multitape biasanya diasumsikan. Pada mesin Turing multitape, kompleksitas waktu sama seperti pada mesin RAM untuk sebagian besar algoritme, meskipun perhatian yang cukup besar dalam cara data disimpan dalam memori mungkin diperlukan untuk mencapai kesetaraan ini.
Berbagai pilihan dapat dibuat pada beberapa langkah komputasi dalam model komputasi non-deterministik, seperti mesin Turing non-deterministik. Dalam teori kompleksitas, semua opsi yang layak dipertimbangkan pada saat yang sama, dan kompleksitas waktu non-deterministik adalah jumlah waktu yang dibutuhkan ketika pilihan terbaik selalu dibuat. Dengan kata lain, komputasi dilakukan secara bersamaan pada prosesor (identik) sebanyak yang diperlukan, dan waktu komputasi non-deterministik adalah waktu yang dibutuhkan prosesor pertama untuk menyelesaikan komputasi. Paralelisme ini dapat digunakan dalam komputasi kuantum dengan menggunakan keadaan terjerat superposisi saat menjalankan algoritme kuantum khusus, seperti faktorisasi bilangan bulat kecil Shor misalnya.
Bahkan jika model komputasi seperti itu saat ini tidak dapat dipraktikkan, ia memiliki signifikansi teoretis, terutama dalam kaitannya dengan masalah P = NP, yang menanyakan apakah kelas kompleksitas yang dihasilkan dengan menggunakan "waktu polinomial" dan "waktu polinomial non-deterministik" sebagai yang paling atas batasnya sama. Pada komputer deterministik, mensimulasikan algoritma NP membutuhkan “waktu eksponensial.” Jika tugas dapat diselesaikan dalam waktu polinomial pada sistem non-deterministik, itu termasuk kelas kesulitan NP. Jika suatu masalah ada di NP dan tidak lebih mudah dari masalah NP lainnya, dikatakan NP-complete. Masalah Knapsack, masalah travelling salesman, dan masalah kepuasan Boolean adalah semua masalah kombinatorial NP-complete. Algoritma yang paling terkenal memiliki kompleksitas eksponensial untuk semua masalah ini. Jika salah satu dari masalah ini dapat diselesaikan dalam waktu polinomial pada mesin deterministik, maka semua masalah NP dapat diselesaikan dalam waktu polinomial juga, dan P = NP akan ditetapkan. Pada tahun 2017, diasumsikan secara luas bahwa P NP, yang menyiratkan bahwa situasi terburuk dari masalah NP pada dasarnya sulit untuk dipecahkan, yaitu, membutuhkan waktu yang jauh lebih lama daripada rentang waktu (dekade) yang memungkinkan dengan panjang input yang menarik.
Komputasi paralel dan terdistribusi
Komputasi paralel dan terdistribusi melibatkan pembagian pemrosesan di beberapa prosesor yang semuanya beroperasi pada waktu yang sama. Perbedaan mendasar antara berbagai model adalah metode pengiriman data antar prosesor. Transmisi data antar prosesor biasanya sangat cepat dalam komputasi paralel, sedangkan transfer data antar prosesor dalam komputasi terdistribusi dilakukan melalui jaringan dan dengan demikian jauh lebih lambat.
Sebuah komputasi pada prosesor N membutuhkan setidaknya hasil bagi N dari waktu yang dibutuhkan pada prosesor tunggal. Pada kenyataannya, karena beberapa subtugas tidak dapat diparalelkan dan beberapa prosesor mungkin perlu menunggu hasil dari prosesor lain, batas ideal secara teoritis ini tidak akan pernah tercapai.
Dengan demikian, masalah kompleksitas utama adalah mengembangkan algoritme sehingga produk waktu komputasi dengan jumlah prosesor sedekat mungkin dengan waktu yang diperlukan untuk melakukan komputasi yang sama pada prosesor tunggal.
Perhitungan kuantum
Komputer kuantum adalah komputer dengan model komputasi berbasis mekanika kuantum. Tesis Church–Turing berlaku untuk komputer kuantum, menyiratkan bahwa masalah apa pun yang dapat dipecahkan oleh komputer kuantum juga dapat diselesaikan oleh mesin Turing. Namun, beberapa tugas mungkin secara teoritis diselesaikan menggunakan komputer kuantum daripada komputer klasik dengan kompleksitas temporal yang jauh lebih rendah. Untuk saat ini, ini hanya teoretis, karena tidak ada yang tahu bagaimana mengembangkan komputer kuantum praktis.
Teori kompleksitas kuantum diciptakan untuk menyelidiki berbagai jenis masalah yang dapat diselesaikan oleh komputer kuantum. Ini digunakan dalam kriptografi pasca-kuantum, yang merupakan proses pembuatan protokol kriptografi yang tahan terhadap serangan komputer kuantum.
Kompleksitas masalah (batas bawah)
Kompleksitas terkecil dari algoritma yang dapat memecahkan masalah, termasuk teknik yang belum ditemukan, adalah kompleksitas masalah. Akibatnya, kompleksitas masalah sama dengan kompleksitas algoritma apa pun yang menyelesaikannya.
Akibatnya, setiap kompleksitas yang diberikan dalam notasi O besar mewakili kompleksitas algoritma dan masalah yang menyertainya.
Di sisi lain, memperoleh batas bawah nontrivial pada kompleksitas masalah seringkali sulit, dan hanya ada sedikit strategi untuk melakukannya.
Untuk menyelesaikan sebagian besar masalah, semua data masukan harus dibaca, yang membutuhkan waktu yang sebanding dengan besarnya data. Akibatnya, masalah tersebut memiliki setidaknya kompleksitas linier, atau, dalam notasi omega besar, kompleksitas (n).
Beberapa masalah, seperti yang ada di aljabar komputer dan geometri aljabar komputasi, memiliki solusi yang sangat besar. Karena output harus ditulis, kompleksitas dibatasi oleh ukuran maksimum output.
Jumlah perbandingan yang diperlukan untuk algoritma pengurutan memiliki batas bawah nonlinier (nlogn). Akibatnya, algoritma pengurutan terbaik adalah yang paling efisien karena kompleksitasnya adalah O(nlogn). Fakta bahwa ada n! cara untuk mengatur n hal mengarah ke batas bawah ini. Karena setiap perbandingan membagi kumpulan n! pesanan menjadi dua bagian, jumlah perbandingan N yang diperlukan untuk membedakan semua pesanan harus 2N > n!, menyiratkan O(nlogn) dengan rumus Stirling.
Mengurangi masalah ke masalah lain adalah strategi umum untuk mendapatkan kendala kompleksitas berkurang.
Pengembangan algoritma
Mengevaluasi kompleksitas algoritma merupakan elemen penting dari proses desain karena memberikan informasi yang berguna tentang kinerja yang mungkin diharapkan.
Ini adalah kesalahpahaman yang sering terjadi, sebagai akibat dari hukum Moore, yang memprediksi pertumbuhan eksponensial dari kekuatan komputer modern, mengevaluasi kompleksitas algoritma akan menjadi kurang relevan. Ini tidak benar karena peningkatan daya memungkinkan pemrosesan data dalam jumlah besar (big data). Misalnya, algoritme apa pun harus berfungsi dengan baik dalam waktu kurang dari satu detik saat menyortir menurut abjad daftar beberapa ratus entri, seperti bibliografi buku. Di sisi lain, untuk satu juta entri (misalnya, nomor telepon kota besar), algoritme dasar yang memerlukan perbandingan O(n2) harus melakukan satu triliun perbandingan, yang akan memakan waktu tiga jam dengan kecepatan 10 juta perbandingan per detik. Quicksort dan merge sort, di sisi lain, hanya memerlukan perbandingan nlogn (sebagai kompleksitas kasus rata-rata untuk yang pertama, sebagai kompleksitas kasus terburuk untuk yang terakhir). Ini menghasilkan sekitar 30,000,000 perbandingan untuk n = 1,000,000, yang hanya membutuhkan waktu 3 detik pada 10 juta perbandingan per detik.
Akibatnya, menilai kompleksitas memungkinkan penghapusan banyak algoritma yang tidak efisien sebelum implementasi. Ini juga dapat digunakan untuk menyempurnakan algoritme kompleks tanpa harus menguji semua varian yang mungkin. Studi kompleksitas memungkinkan memfokuskan upaya untuk meningkatkan efisiensi implementasi dengan menentukan langkah paling mahal dari algoritma yang kompleks.
Untuk mengenal diri Anda secara detail dengan kurikulum sertifikasi, Anda dapat memperluas dan menganalisis tabel di bawah ini.
Kurikulum Sertifikasi Dasar Teori Kompleksitas Komputasi EITC/IS/CCTF mereferensikan materi didaktik akses terbuka dalam bentuk video. Proses pembelajaran dibagi menjadi struktur langkah demi langkah (program -> pelajaran -> topik) yang mencakup bagian kurikulum yang relevan. Konsultasi tak terbatas dengan pakar domain juga disediakan.
Untuk perincian tentang prosedur Sertifikasi, periksa Bagaimana itu bekerja.
Bahan bacaan kurikulum pendukung utama
S. Arora, B. Barak, Kompleksitas Komputasi: Pendekatan Modern
https://theory.cs.princeton.edu/complexity/book.pdf
Bahan bacaan kurikulum pendukung sekunder
O. Goldreich, Pengantar Teori Kompleksitas:
https://www.wisdom.weizmann.ac.il/~oded/cc99.html
Bahan bacaan kurikulum yang mendukung pada matematika diskrit
J. Aspnes, Catatan tentang Matematika Diskrit:
https://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf
Bahan bacaan kurikulum yang mendukung teori graf
R. Diesel, Teori Grafik:
https://diestel-graph-theory.com/
Download materi persiapan belajar mandiri offline lengkap untuk program Fundamental Teori Kompleksitas Komputasi EITC/IS/CCTF dalam file PDF
Materi persiapan EITC/IS/CCTF – versi standar
Materi persiapan EITC/IS/CCTF – versi diperluas dengan pertanyaan tinjauan