CHAPTER 3 ALGORITHMS 3.1 ALGORITHMS
Algoritma Definisi 1. Algoritma adalah himpunan hingga perintah yang terinci dalam melakukan perhitungan atau pemecahan masalah. Contoh 1. Program komputer adalah suatu algoritma. Catatan. Dalam matematika, suatu algoritma merepresentasikan fungsi. Namun, Alan Turing membuktikan bahwa beberapa fungsi tidak dapat direpresentasikan suatu algoritma.
Contoh 1 Deskripsikan suatu algoritma untuk mencari bilangan terbesar dalam barisan hingga bilangan bulat. Solusi. Dilakukan langkah berikut: 1. Buat nilai maksimum sementara sama dengan bilangan bulat pertama dalam barisan. 2. Bandingkan bilangan bulat berikut dalam barisan dengan maksimum sementara, jika ia lebih besar dari maksimum sementara, maka maksimum sementara dibuat sama dengan bilangan tersebut. 3. Ulangi langkah sebelumnya jika terdapat bilangan bulat lain dalam barisan. 4. Berhenti jika tidak ada bilangan bulat lain di barisan. 5. Nilai maksimum sementara adalah bilangan terbesar dalam barisan.
Pseudocode Pseudocode dari suatu algoritma memberikan representasi yang jelas dari suatu algoritma dan juga dapat diubah ke dalam satu atau lebih bahasa pemrograman. Algoritma 1. Cari_Maksimum
Sifat Algoritma • Input. Algoritma memiliki input dari himpunan tertentu. • Output. Dari setiap himpunan input, algoritma menghasilkan output yang merupakan solusi dari masalah. • Definiteness. Setiap langkah dalam algoritma harus didefinisikan secara rinci. • Correctness. Algoritma harus menghasilkan nilai output yang benar. • Finiteness. Algoritma harus menghasilkan output yang diinginkan dalam sejumlah berhingga langkah. • Effectiveness. Setiap langkah dalam algoritma dapat dilakukan dalam waktu yang berhingga. • Generality. Prosedur harus dapat diterapkan secara umum, bukan hanya untuk himpunan input tertentu.
Soal 1 Jelaskan Input, Output, Definiteness, Correctness, Finiteness, Effectiveness, dan Generality dari Algoritma 1.
Algoritma Greedy • Untuk memecahkan masalah optimasi. • Pendekatan termudah adalah dengan menentukan pilihan terbaik dalam setiap langkah; dan tidak mempertimbangkan keseluruhan langkah. • Algoritma yang mencari pilihan “terbaik” dalam setiap langkah disebut algoritma greedy. • Namun demikian, algoritma greedy tidak selalu memberikan solusi optimal. Sehingga setelah suatu algoritma greedy menemukan suatu solusi, perlu diperiksa apakah solusi tersebut optimal.
Contoh 2 Pandang masalah menukar n rupiah dengan lembar uang 100 ribuan, 50 ribuan, 20 ribuan, 10 ribuan, 5 ribuan, dan seribuan di mana digunakan sesedikit mungkin lembar uang. Kita dapat merancang algoritma greedy dengan melakukan optimasi pada setiap langkah, yaitu, dalam setiap langkah kita memilih lembar uang dengan nilai terbesar untuk ditukarkan yang tidak melebihi nilai n. Sebagai contoh, untuk menukar 287 ribu rupiah, kita memilih lembar 100 ribu (menyisakan 187 ribu). Kemudian dipilih lembar 100 ribu kedua (menyisakan 87 ribu), disusul oleh lembar 50 ribu (menyisakan 37 ribu), lembar 20 ribu (menyisakan 17 ribu), lembar 10 ribu (menyisakan 7 ribu), lembar 5 ribu (menyisakan 2 ribu), lembar seribu (menyisakan seribu), dan lembar seribu.
Contoh 2 (Algoritma) Algoritma 2. Tukar_uang_greedy
Contoh 2 (Bukti solusi optimal) Lema 1 Misalkan n bilangan bulat positif. Jika n rupiah ditukarkan dengan lembar uang 100 ribuan, 50 ribuan, 20 ribuan, 10 ribuan, 5 ribuan, dan seribuan di mana digunakan sesedikit mungkin lembar uang, maka paling banyak digunakan 1 lembar 50 ribuan, paling banyak 2 lembar 20 ribuan, paling banyak 1 lembar 10 ribuan, paling banyak 1 lembar 5 ribuan, dan paling banyak 4 lembar seribuan. Selain itu, tidak mungkin terdapat 2 lembar 20 ribuan dan 1 lembar 10 ribuan. Banyaknya uang yang ditukarkan dalam lembar 50 ribuan, 20 ribuan, 10 ribuan, 5 ribuan, dan seribuan tidak dapat melebihi 99 ribu rupiah. Bukti. Dengan kontradiksi
Contoh 2 (Bukti solusi optimal) Teorema 1 Algoritma greedy (Algoritma 2) menukarkan uang dengan menggunakan sesedikit mungkin lembar uang. Bukti. Dengan kontradiksi dan menggunakan Lema 1.
3.2 THE GROWTH OF FUNCTIONS
Notasi Big-O Pertumbuhan fungsi biasanya dijelaskan dengan menggunakan notasi big-O. Definisi 2. [Paul Bachmann (1892), dipopulerkan oleh Donald Knuth] Misalkan f dan g fungsi dari bilangan bulat/real ke bilangan real. f(x) adalah O(g(x)), atau kadangkala ditulis f(x) = O(g(x)), jika terdapat konstanta C dan k sehingga |f(x)| C|g(x)| untuk setiap x > k. Catatan. f(x) adalah O(g(x)) menyatakan bahwa f(x) tumbuh lebih lambat dibandingkan suatu hasil kali konstan dari g(x) pada saat x membesar tanpa batas.
Contoh 3 Tunjukkan bahwa f(x) = x2 + 2x + 1 adalah O(x2). Solusi. Untuk x > 1 berlaku x2 + 2x + 1 x2 + 2x2 + x2 x2 + 2x + 1 4x2 Maka, untuk C = 4 dan k = 1: f(x) C x2 jika x > k.
Jadi, f(x) adalah O(x2).
Contoh 3 (Grafik)
Orde Terkecil Jika f(x) adalah O(x2), apakah f(x) juga O(x3)? Ya. x3 bertumbuh lebih cepat dari x2, sehingga x3 juga bertumbuh lebih cepat dari f(x). Maka, biasanya dicari fungsi sederhana terkecil g(x) yang mengakibatkan f(x) adalah O(g(x)).
Contoh 4. 1. Tunjukkan bahwa 30n+8 adalah O(n). Misalkan c=31, k=8. Asumsikan n>k=8. Maka cn = 31n = 30n + n > 30n+8, sehingga 30n+8 < cn. 2. Tunjukkan bahwa n2+1 adalah O(n2). Misalkan c=2, k=1. Asumsikan n>1. Maka cn2 = 2n2 = n2+n2 > n2+1, atau n2+1< cn2.
30n+8 tidak lebih kecil dari n di mana-mana (n>0), tetapi lebih kecil dari 31n di semua titik sebelah kanan n=8.
Value of function
Contoh 4 (Grafis) cn = 31n
30n+8
n n>k=8 Increasing n
30n+8 = O(n)
Soal 2 Tunjukkan bahwa n2 bukan O(n).
Big-O untuk polinom Teorema 2. Misalkan f(x) = anxn + an-1xn-1 + … + a0 suatu polinom dengan a0, a1, …, an bilangan real. Maka f(x) adalah O(xn).
Soal 3. 1. Tentukan Big-O dari 1 + 2 + 3 + … + n 2. Tentukan Big-O dari n! 3. Dengan menggunakan sifat n < 2n, untuk setiap n bilangan bulat positif, tunjukkan bahwa log n adalah O(n).
Fungsi “Populer” Fungsi yang “populer” digunakan sebagai g(n) adalah 1, log n, n, n log n, n2, 2n, n!
Big-O untuk Kombinasi Fungsi Teorema 3.
• Jika f1(x) adalah O(g1(x)) dan f2(x) adalah O(g2(x)), maka (f1 + f2)(x) adalah O(max(g1(x), g2(x))) • Jika f1(x) adalah O(g(x)) dan f2(x) adalah O(g(x)), maka (f1 + f2)(x) adalah O(g(x)). • Jika f1(x) adalah O(g1(x)) dan f2(x) adalah O(g2(x)), maka (f1f2)(x) adalah O(g1(x) g2(x)).
Big-Omega dan Big-Theta Definisi 3. [Knuth (1970)] Misalkan f dan g fungsi dari bilangan bulat/real ke bilangan real. f(x) adalah (g(x)) jika terdapat konstanta C dan k sehingga |f(x)| ≥ C|g(x)| untuk setiap x > k. f(x) adalah (g(x)) jika f(x) adalah O(g(x)) dan f(x) adalah (g(x)). Jika f(x) adalah (g(x)), maka dikatakan f(x) berorde g(x) atau f(x) dan g(x) memiliki orde yang sama.
Soal 4. 1. Telah ditunjukkan (di Soal 3) bahwa 1 + 2 + … + n adalah O(n2). Apakah deret ini berorde n2? 2. Tunjukkan 3𝑥 2 + 8𝑥 log 𝑥 berorde 𝑥 2 .
Orde Polinom Teorema 4. Misalkan f(x) = anxn + an-1xn-1 + … + a0 suatu polinom dengan a0, a1, …, an bilangan real. Maka f(x) berorde xn.
3.3 COMPLEXITY OF ALGORITHMS
Kompleksitas Waktu Kompleksitas waktu dari suatu algoritma dapat diekspresikan dalam banyaknya operasi yang digunakan oleh algoritma tersebut dengan input berukuran tertentu. Operasi yang digunakan meliputi perbandingan, penjumlahan, perkalian, pembagian, dan operasi dasar lainnya. Kompleksitas waktu dinyatakan dalam banyaknya operasi, bukan waktu real yang dibutuhkan, karena setiap komputer membutuhkan waktu yang berbeda untuk melakukan operasi dasar. Misalnya, suatu processor dengan kapasitas 100-Mhz dapat memproses sampai 1 juta instruksi setiap detik.
Elemen Maksimum dalam Barisan
Tentukan kompleksitas waktu dari Algoritma 1.
Solusi Banyaknya perbandingan akan digunakan sebagai ukuran kompleksitas waktu. Dalam setiap langkah, dilakukan dua kali perbandingan: • i ≤ n untuk menentukan apakah akhir dari barisan telah dicapai, dan • max < ai untuk menentukan apakah maksimum sementara perlu diganti. Di akhir prosedur, dilakukan satu kali perbandingan untuk keluar dari loop. Sehingga, terdapat tepat 2(n − 1) + 1 = 2n − 1 perbandingan yang digunakan. Jadi, Algoritma 1 memiliki kompleksitas waktu (n).
Contoh 6. Apakah yang dihitung oleh algoritma berikut dan apakah kompleksitasnya? procedure siapa_tahu(a1, a2, …, an: integers) m := 0 for i := 1 to n-1 for j := i + 1 to n if |ai – aj| > m then m := |ai – aj| Solusi. Algoritma menghitung m yang merupakan beda maksimum antara setiap dua bilangan dalam barisan input. Banyaknya iterasi yang dilakukan adalah: n-1 + n-2 + n-3 + … + 1 = (n – 1)n/2 = 0.5n2 – 0.5n Di dalam iterasi tersebut dilakukan perbandingan untuk variable j, perbandingan |ai – aj| dengan m dan paling banyak 2 kali operasi selisih. Sedangkan perbandingan untuk variable i dilakukan n-1 kali. Sehingga total operasi yang dilakukan paling banyak 4 (0.5n2 – 0.5n) + n – 1 = 2n2 – n – 1. Jadi, kompleksitas algoritma adalah (n2).
Contoh 6. (2) Algoritma lain yang menyelesaikan masalah yang sama: procedure max_diff(a1, a2, …, an: integers) min := a1 max := a1 for i := 2 to n if ai < min then min := ai else if ai > max then max := ai m := max - min
Banyaknya perbandingan? Paling banyak 3 (n – 1) = 3n – 3 Sehingga kompleksitas algoritma adalah (n).
Kompleksitas Perkalian Matriks Misalkan C = [cij] adalah matriks m × n yang merupakan hasil kali A = [aij] matriks m × k dengan B = [bij] matriks k × n. Algoritma 3. Perkalian_matriks
.
Contoh 6. Ada berapa banyak operasi penjumlahan dan perkalian bilangan bulat yang digunakan dalam Algoritma 3 untuk mengalikan dua matriks berukuran nxn? Solusi. Ada n2 entri dalam hasil kali A and B. Untuk memperoleh setiap entri diperlukan n perkalian dan n − 1 penjumlahan. Maka digunakan n3 perkalian dan n2(n − 1) penjumlahan. Catatan: Akan ada pula operasi perbandingan.
Kompleksitas Perkalian Matriks (2) Contoh 6 menunjukkan bahwa mengalikan dua matriks n x n memerlukan O(n3) operasi perkalian dan penjumlahan. Namun ternyata ada algoritma lain yang lebih efisien dari Algoritma 3. • [Volker Strassen (1969)] Menggunakan O(n2.807) operasi. • [Don Coppersmith and Shmuel Winograd (1990)] Menggunakan O(n2.376) operasi. • [Andrew Stothers (2010)] Menggunakan O(n2.3736) operasi. • [Virginia Williams (2013)] Menggunakan O(n2.3729) operasi. • [Francois Le Gall (2014)] Menggunakan O(n2.37286) operasi.
Mengapa Perlu Algoritma yang Lebih Baik untuk Operasi Matriks? Aplikasi dunia nyata melibatkan matriks dalam ukuran
sangat besar
.
Algoritma Google’s page rank memerlukan perhitungan nilai eigen dari matriks dengan ukuran baris dan kolom sebanyak webpage yang ada di internet (!!!).
Webpage di Internet
sumber: http://www.worldwidewebsize.com/
Kompleksitas Algoritma
Solvability dan Tractability Masalah yang dapat diselesaikan dengan menggunakan suatu algoritma disebut solvable. Masalah di mana tidak ada algoritma yang dapat menyelesaikannya disebut unsolvable. Masalah yang dapat diselesaikan menggunakan algoritma dengan kompleksitas polinomial disebut tractable. Masalah yang tidak memiliki algoritma dengan kompleksitas polinomial disebut intractable.
P Versus NP Masalah tractable masuk ke dalam Kelas P. Masalah intractable yang solusinya dapat diperiksa dengan menggunakan algoritma dengan kompleksitas polinomial masuk ke dalam Kelas NP (Nondeterministic Polynomial). Contoh. Integer Factorization Algorithm
Masalah P Versus NP mempertanyakan Apakah P = NP? Merupakan salah satu dari 7 Millennium Prize Problems. Pada tahun 2000, Clay Mathematics Institute menawarkan hadiah $1,000,000 untuk solusi setiap problem. 7 Millennium Prize Problems 1. P versus NP 2. The Hodge conjecture 3. The Poincaré conjecture (dibuktikan oleh Grigori Perelman pada tahun 2003) 4. The Riemann hypothesis 5. Yang–Mills existence and mass gap 6. Navier–Stokes existence and smoothness 7. The Birch and Swinnerton-Dyer conjecture
