9. Information complexity and notion of randomness 10. Pseudo-random numbers

 Middle-Square Algorithm

- Algorithm:

1.Start with a number called the seed.
  (Mulailah dengan angka yang disebut benih)

2.Square it and extract the middle four digits. If the square has less than 8 digits, pad it with leading zeros until it’s eight digits long.

3.Repeat the process.

- Starting with a four digit seed, the middle square algorithm generates a sequence of random-looking numbers between 0 and 9,999. Xn+1 = middle four digits of (Xn ) 2

The subject of complexity theory

Teori kompleksitas, juga dikenal sebagai teori kompleksitas komputasi, adalah cabang ilmu komputer yang berfokus pada studi tentang kesulitan yang melekat pada masalah komputasi dan sumber daya yang diperlukan untuk menyelesaikannya. Ini berkaitan dengan mengklasifikasikan masalah berdasarkan kompleksitas komputasinya dan memahami batasan dan kemungkinan komputasi yang efisien. Tujuan utama dari teori kompleksitas adalah untuk memahami sifat dasar dan karakteristik masalah komputasi. Ini menyelidiki pertanyaan seperti: Klasifikasi masalah: Teori kompleksitas mengkategorikan masalah ke dalam kelas kompleksitas yang berbeda berdasarkan kesulitannya. Kelas kompleksitas yang paling terkenal termasuk P (masalah yang dapat diselesaikan secara efisien), NP (masalah yang dapat diverifikasi secara efisien), dan NP-complete (masalah tersulit dalam NP). Analisis kompleksitas komputasi: Teori kompleksitas menyediakan teknik dan alat untuk menganalisis kebutuhan waktu dan ruang dari algoritma. Ini membantu dalam mengkarakterisasi tingkat pertumbuhan sumber daya saat ukuran input meningkat dan menentukan efisiensi algoritme. Kekerasan dan kelengkapan: Teori kompleksitas mempelajari pengertian kekerasan dan kelengkapan. Kekerasan mengacu pada kesulitan memecahkan masalah, sedangkan kelengkapan berkaitan dengan sejauh mana masalah mewakili kelas masalah yang sulit. Masalah yang NP-lengkap, misalnya, diyakini menjadi salah satu masalah yang paling menantang di NP. Pengurangan dan bukti kelengkapan: Teori kompleksitas menggunakan pengurangan untuk membangun hubungan antara masalah yang berbeda. Pengurangan menunjukkan bagaimana satu masalah dapat diubah menjadi yang lain, yang memungkinkan wawasan ke dalam kompleksitas masalah dan menetapkan hasil kelengkapan. Model komputasi: Teori kompleksitas memeriksa model komputasi yang berbeda, seperti mesin Turing, sirkuit Boolean, dan mesin akses acak, untuk memahami kekuatan komputasi dan keterbatasan berbagai model komputasi. Teori kompleksitas memiliki implikasi praktis di berbagai bidang, termasuk desain algoritme, kriptografi, pengoptimalan, kecerdasan buatan, dan banyak lagi. Ini membantu dalam mengidentifikasi masalah yang secara komputasi tidak mungkin diselesaikan secara efisien dan memandu pengembangan algoritme dan heuristik untuk mengatasi masalah yang kompleks. Dengan mempelajari teori kompleksitas, peneliti dan praktisi mendapatkan pemahaman yang lebih dalam tentang kesulitan yang melekat pada masalah, memungkinkan mereka untuk membuat keputusan tentang pemilihan algoritma, strategi pemecahan masalah, dan pengembangan solusi yang efisien.

Algorithms? Complexity?

• Computational procedure (steps) for solving a problem

   (Prosedur komputasi (langkah-langkah) untuk memecahkan masalah)

   • Input -> algorithm -> output

• How to write an algorithm? Descriptive sentences, Flowchart, Pseudocode

  (Bagaimana cara menulis algoritma? Kalimat deskriptif, Flowchart, Pseudocode)

• Given an algorithm, how efficient is it for solving a problem given input of a particular size?

 (Diberikan sebuah algoritma, seberapa efisien algoritma itu untuk memecahkan masalah diberikan  masukan dari ukuran tertentu?)

  • How much time does it take to solve the problem?

    (Berapa lama waktu yang dibutuhkan untuk menyelesaikan masalah)

  • How much space does it use to solve the problem?

    (Berapa banyak ruang yang digunakan untuk menyelesaikan masalah?)

• Complexity is measured by the quantity of computational resources (time, space) used up by a particular task.
(Kompleksitas diukur dengan jumlah sumber daya komputasi (waktu, ruang) yang digunakan oleh tugas tertentu.)

Kompleksitas

Kompleksitas, dalam konteks ilmu komputer dan algoritme, mengacu pada analisis dan pengukuran sumber daya yang diperlukan oleh suatu algoritme untuk memecahkan masalah. Dua jenis kompleksitas yang umum adalah kompleksitas waktu dan kompleksitas ruang.

Kompleksitas waktu: Kompleksitas waktu adalah ukuran bagaimana waktu berjalan suatu algoritme tumbuh seiring dengan bertambahnya ukuran input. Ini memberikan perkiraan jumlah operasi atau langkah yang perlu dilakukan oleh algoritma untuk menyelesaikan masalah. Kompleksitas waktu biasanya diekspresikan menggunakan notasi O besar, yang menggambarkan batas atas atau skenario terburuk untuk laju pertumbuhan waktu berjalan algoritme.

Kompleksitas ruang: Kompleksitas ruang adalah ukuran berapa banyak memori atau ruang penyimpanan yang diperlukan suatu algoritme untuk menyelesaikan masalah saat ukuran input meningkat. Ini mempertimbangkan ruang tambahan yang digunakan oleh algoritme selain dari input itu sendiri. Serupa dengan kompleksitas waktu, kompleksitas ruang juga diekspresikan menggunakan notasi O besar, mewakili batas atas atau skenario kasus terburuk untuk tingkat pertumbuhan penggunaan ruang algoritme.

Menganalisis kompleksitas suatu algoritma sangat penting untuk mengevaluasi efisiensi dan skalabilitasnya. Algoritma dengan kompleksitas waktu dan kompleksitas ruang yang lebih rendah umumnya lebih disukai karena dapat menangani input yang lebih besar dengan lebih efisien. Namun, penting untuk dicatat bahwa analisis kompleksitas memberikan analisis asimtotik, yang berfokus pada tingkat pertumbuhan sumber daya daripada pengukuran waktu atau ruang yang tepat.

Dengan memahami kompleksitas algoritme, pengembang dan peneliti dapat membuat keputusan berdasarkan informasi tentang memilih algoritme yang sesuai untuk tugas tertentu, mengoptimalkan algoritme yang ada, dan merancang algoritme yang lebih efisien untuk mengatasi masalah yang kompleks.

Algoritma

Algoritma adalah seperangkat instruksi atau aturan yang digunakan untuk memecahkan masalah atau melakukan tugas tertentu. Mereka adalah prosedur langkah demi langkah yang dirancang untuk memecahkan masalah komputasi tertentu secara efisien. Algoritma dapat ditemukan di berbagai bidang, termasuk ilmu komputer, matematika, dan teknik.

Saat merancang suatu algoritme, pertimbangan dibuat untuk kebenaran, efisiensi, dan skalabilitasnya. Algoritme yang dirancang dengan baik memperhitungkan faktor-faktor akun seperti ukuran input, sumber daya yang tersedia, dan output yang diinginkan. Jenis algoritma yang umum termasuk algoritma pengurutan, algoritma pencarian, algoritma grafik, dan algoritma pembelajaran mesin.

Efisiensi adalah aspek penting dari algoritma, dan sering diukur dalam kompleksitas waktu dan kompleksitas ruang. Kompleksitas waktu mengacu pada jumlah waktu yang diperlukan untuk menjalankan algoritma sebagai fungsi dari ukuran input. Kompleksitas ruang, di sisi lain, mengacu pada jumlah memori atau ruang penyimpanan yang dibutuhkan oleh suatu algoritma.

Algoritma memainkan peran mendasar dalam ilmu komputer dan memiliki aplikasi praktis di banyak bidang, seperti analisis data, pengoptimalan, kriptografi, kecerdasan buatan, dan banyak lagi. Mereka membentuk dasar pemikiran komputasi dan pemecahan masalah di berbagai domain.