Pembahasan Soal Mid Semester Analisis Algoritma

PROGRAM PASCA SARJANA, S2 ILMU KOMPUTER

SOAL UJIAN TENGAH SEMESTER I TAHUN 2007/ 2008

Mata Ujian : Analisis Algoritma

Hari/ tanggal : Kamis, 8 Nopember 2007

Waktu : 120 menit

Sifat Ujian : Hanya boleh membuka catatan kuliah

Penguji : Retantyo Wardoyo

Jawaban ini belum tentu benar. Jika ada yang punya jawaban berbeda, mohon di share dan didiskusikan bersama. Terima kasih.

Soal No 1:

Buktikan dengan induksi matematika pernyataan berikut:

a. n! ≤ 2 ⁿ untuk n > 3

Jawab :

Terdapat beberapa langkah pembuktian dengan induksi matematika:

Langkah 1:

Menunjukkan bahwa pernyataan tersebut benar untuk n₀ = 4.

n = 4 --> 4! ≤ 2⁴

4.3.2.1 ≤ 16

24 > 16

Jadi pernyataan n! ≤ 2 ⁿ untuk n > 3 tidak benar (salah) untuk n = 4

Dengan demikian pembuktian selesai, pernyataan tersebut tidak benar।

b. 1 (1!) + 2 (2!) + 3 (3!) + … + n (n!) = ( n + 1 )! – 1

Jawab:

Terdapat beberapa langkah pembuktian dengan induksi matematika:

Langkah 1:

Menunjukkan bahwa pernyataan tersebut benar untuk n₀ = 1.

n = 1 --> 1 (1!) = (1 + 1)! – 1

1.1 = 2! – 1

1 = 2 – 1

1 = 1

Jadi pernyataan tersebut benar untuk n = 1

Langkah 2:

Menunjukkan bahwa jika pernyataan tersebut benar untuk n = k, maka pernyataan tersebut juga benar untuk n = k + 1. Hal ini dilakukan dengan cara :

- Mengasumsikan pernyataan tersebut benar untuk n = k + 1, yaitu

n = k --> 1 (1!) + 2 (2!) + 3 (3!) + … + k (k!) = ( k + 1 )! – 1

- Selanjutnya akan ditunjukkan pernyataan tersebut juga benar untuk n = k + 1.

Dari asssumsi diatas :

1 (1!) + 2 (2!) + 3 (3!) + … + k (k!) = ( k + 1 )! – 1

Tambahkan (k + 1) ( k + 1 )! pada kedua ruas.

1 (1!) + 2 (2!) + 3 (3!) + … + k (k!) + (k + 1) (k + 1)! = (k + 1)! – 1 + (k+1)(k+1)!

1 (1!) + 2 (2!) + 3 (3!) + … + k (k!) + (k + 1) (k + 1)! = (k + 1)! + (k+1)(k+1)! – 1

1 (1!) + 2 (2!) + 3 (3!) + … + k (k!) + (k + 1) (k + 1)! = (k + 1)! (1 + (k+1)) – 1

1 (1!) + 2 (2!) + 3 (3!) + … + k (k!) + (k + 1) (k + 1)! = (k + 1)! (k +1 + 1) – 1

1 (1!) + 2 (2!) + 3 (3!) + … + k (k!) + (k + 1) (k + 1)! = (k + 1)! (k+2) – 1

1 (1!) + 2 (2!) + 3 (3!) + … + k (k!) + (k + 1) (k + 1)! = (k + 2)(k + 1)! – 1

1 (1!) + 2 (2!) + 3 (3!) + … + k (k!) + (k + 1) (k + 1)! = (k + 2)! – 1

1 (1!) + 2 (2!) + 3 (3!) + … + k (k!) + (k + 1) (k + 1)! = ((k + 1)+1)!– 1

Jadi pernyataan tersebut benar untuk n = k + 1

Pembuktian selesai

c।

Jawab:

Langkah 1:

Menunjukkan bahwa pernyataan tersebut benar untuk n₀ = 1.

n = 1 --> 1 ² =

Jadi pernyataan tidak benar untuk n = 1

Dengan demikian pembuktian selesai, pernyataan tersebut tidak benar.

d।

Jawab:

Langkah 1:

Menunjukkan bahwa pernyataan tersebut benar untuk n₀ = 1.

n = 1 à 2 = 2 + (1 - 1) 2¹⁺¹

2 = 2 + 0 . 2²

2 = 2 + 0

2 = 2

Jadi pernyataan tersebut benar untuk n = 1

Langkah 2:

Menunjukkan bahwa jika pernyataan tersebut benar untuk n = k, maka pernyataan tersebut juga benar untuk n = k + 1. Hal ini dilakukan dengan cara :

- Mengasumsikan pernyataan tersebut benar untuk n = k + 1, yaitu

n = k à 2 + 8 + 24 + … + k 2^k = 2 + (k – 1) 2^{k + 1}

- Selanjutnya akan ditunjukkan pernyataan tersebut juga benar untuk n = k + 1.

Dari asssumsi diatas :

2 + 8 + 24 + … + k 2^k = 2 + (k – 1) 2^k+1

Tambahkan (k + 1) 2^k+1 pada kedua ruas.

2 + 8 + 24 + … + k 2^k + (k + 1) 2^k+1 = 2 + (k – 1) 2^k+1 + (k + 1) 2^k+1

2 + 8 + 24 + … + k 2^k + (k + 1) 2^k+1 = 2 + 2^k+1 ((k - 1) + (k + 1))

2 + 8 + 24 + … + k 2^k + (k + 1) 2^k+1 = 2 + 2^k+1 ( k -1 + k + 1)

2 + 8 + 24 + … + k 2^k + (k + 1) 2^k+1 = 2 + 2^k+1 ( 2k)

2 + 8 + 24 + … + k 2^k + (k + 1) 2^k+1 = 2 + 2^k+1 .2( k)

2 + 8 + 24 + … + k 2^k + (k + 1) 2^k+1 = 2 + 2^k+1+1 (k)

2 + 8 + 24 + … + k 2^k + (k + 1) 2^k+1 = 2 + 2 ^k+1+1 ( k )

2 + 8 + 24 + … + k 2^k + (k + 1) 2^k+1 = 2 + ( k ) 2 ^(k+1)+1

2 + 8 + 24 + … + k 2^k + (k + 1) 2^k+1 = 2 + ( k + 0 ) 2 ^(k+1)+1

2 + 8 + 24 + … + k 2^k + (k + 1) 2^k+1 = 2 + ( k + 1 - 1 ) 2 ^(k+1)+1

2 + 8 + 24 + … + k 2^k + (k + 1) 2^k+1 = 2 + ( (k + 1) - 1 ) 2 ^(k+1)+1

Jadi pernyataan tersebut benar untuk n = k + 1

Pembuktian selesai

Soal No 2:

Diketahui matriks . Hitunglah determinan dan inversnya.

Jawab :

Determinan matriks =

Operasi pada baris ke- 2 : baris ke-2 dikurang (-2) kali baris ke-1

Operasi pada baris ke- 3 : baris ke-3 dikurang (-1) baris ke-1

=

Operasi pada baris ke- 3 : baris ke-3 dikurang (-4) kali baris ke-2

Operasi pada baris ke- 4 : baris ke-4 dikurang (-4) kali baris ke-2

=

Operasi pada baris ke- 4 : baris ke-4 dikurang baris ke-3

=

= (-1) x (-1 ) x 11 x

= - 47

Invers Matriks

Operasi baris elementer

Operasi pada baris ke- 2 : baris ke-2 dikurang (-2) kali baris ke-1

Operasi pada baris ke- 3 : baris ke-3 dikurang (-1) baris ke-1

=

Operasi pada baris ke-3 : baris ke-3 dikurang (-4) kali baris ke-2

Operasi pada baris ke-4 : baris ke-4 dikurang (-4) kali baris ke-2

=

Operasi pada baris ke-4 : 11 kali Baris ke-4 dikurang 13 kali baris ke-3

=

Operasi pada baris ke -1 : 47 kali Baris ke-1 tambah 3 kali baris ke-4

Operasi pada baris ke -2 : 47 kali baris ke-2 tambah 7 kali baris ke-4

Operasi pada baris ke -3 : 47 kali baris ke-3 tambah 29 baris ke-4.

=

Operasi pada baris ke -2 : 517 kali baris ke-2 kurang 141 kali baris ke-3

=

Operasi pada baris ke -1 : 24299 kali baris ke-1 kurang 94 kali baris ke-2

=

Operasi pada baris ke -1 : baris ke-1 kali

Operasi pada baris ke -2 : baris ke-2 kali

Operasi pada baris ke -3 : baris ke-3 kali

Operasi pada baris ke -4 : baris ke-4 kali

=

Jadi invers matriksnya =

3. Soal :

Ubahlah ekpresi rekursif berikut menjadi non rekursif.

a.

Jawab :

Persamaan Karakteristik homogen

: xn-2

f(n) = xⁿ

xⁿ = 4x^n‑1 + 12x^n-2

x² = 4x + 12

x² - 4x - 12 = 0

(x + 3) (x – 4) = 0

Persamaan Karakteristik non homogen

2ⁿ n à c = 2, d = 1

à (x – 2)^{1 + 1} = (x – 2)²

(x + 3) (x – 4) (x – 2)² = 0

x₁ = -3 x₂ = 4 x₃ = x₄ = 2

f(n) = c₁ x₁ⁿ + c₂ x₂ⁿ + (c₃ + c₄ n) x₃ⁿ

f(n) = c₁ (-3)ⁿ + c₂ (4)ⁿ + (c₃ + c₄ n) 2ⁿ

n = 1 à f(1) = c₁ (-3)¹ + c₂ (4)¹ + (c₃ + c₄ 1) 2¹ = 1² + 1

f(1) = - 3 c₁ + 4 c₂ + 2 c₃ + 2 c₄ = 2

n = 2 à f(2) = c₁ (-3)² + c₂ (4)² + (c₃ + c₄ 2) 2² = 2² + 1

f(2) = 9 c₁ + 16 c₂ + 4 c₃ + 8 c₄ = 5

n = 3 à f(3) = c₁ (-3)³ + c₂ (4)³ + (c₃ + c₄ 3) 2³ = 4 f (3 – 1)+ 12 f (3 -2) + 2³ .3

f(3) = - 27 c₁ + 64 c₂ + 8 c₃ + 24 c₄ = 4 f (2)+ 12 f (1) + 24

f(3) = - 27 c₁ + 64 c₂ + 8 c₃ + 24 c₄ = 4.5+ 12.2 + 24

f(3) = - 27 c₁ + 64 c₂ + 8 c₃ + 24 c₄ = 20+ 24 + 24

f(3) = - 27 c₁ + 64 c₂ + 8 c₃ + 24 c₄ = 68

n = 4 à f(4) = c₁ (-3)⁴ + c₂ (4)⁴ + (c₃ + c₄ 4) 2⁴ = 4 f (4 – 1)+ 12 f (4 -2) + 2⁴ .4

f(4) = 81 c₁ + 256 c₂ + 16 c₃ + 64 c₄ = 4 f (3)+ 12 f (2) + 64

f(4) = 81 c₁ + 256 c₂ + 16 c₃ + 64 c₄ = 4.68+ 12.5 + 64

f(4) = 81 c₁ + 256 c₂ + 16 c₃ + 64 c₄ = 272+ 60 + 64

f(4) = 81 c₁ + 256 c₂ + 16 c₃ + 64 c₄ = 396

Untuk mencari nilai c₁, c₂, c₃, c₄ dapat dilakukan dengan metode eliminasi, substitusi atau dengan eliminasi gauss. Dalam hal ini kita selesaikan dengan menggunakan eliminasi gauss.

=

b.

Substitusi n = 3^m , m = ³ log n

Substitusi f(3^m) = g(m)

Persamaan Karakteristik homogen

: xm-2

g(m) = x^m

x^m = 2x^m‑1 + 10x^m-2

x² = 2x + 10

x² - 2x + 10 = 0

Persamaan Karakteristik non homogen

2ⁿ n à c = 2, d = 1

à (x – 2)^{1 + 1} = (x – 2)²

(x + 3) (x – 4) (x – 2)² = 0

x₁ = -3 x₂ = 4 x₃ = x₄ = 2

f(n) = c₁ x₁ⁿ + c₂ x₂ⁿ + (c₃ + c₄ n) x₃ⁿ

f(n) = c₁ (-3)ⁿ + c₂ (4)ⁿ + (c₃ + c₄ n) 2ⁿ

n = 1 à f(1) = c₁ (-3)¹ + c₂ (4)¹ + (c₃ + c₄ 1) 2¹ = 1² + 1

f(1) = - 3 c₁ + 4 c₂ + 2 c₃ + 2 c₄ = 2

n = 2 à f(2) = c₁ (-3)² + c₂ (4)² + (c₃ + c₄ 2) 2² = 2² + 1

f(2) = 9 c₁ + 16 c₂ + 4 c₃ + 8 c₄ = 5

n = 3 à f(3) = c₁ (-3)³ + c₂ (4)³ + (c₃ + c₄ 3) 2³ = 4 f (3 – 1)+ 12 f (3 -2) + 2³ .3

f(3) = - 27 c₁ + 64 c₂ + 8 c₃ + 24 c₄ = 4 f (2)+ 12 f (1) + 24

f(3) = - 27 c₁ + 64 c₂ + 8 c₃ + 24 c₄ = 4.5+ 12.2 + 24

f(3) = - 27 c₁ + 64 c₂ + 8 c₃ + 24 c₄ = 20+ 24 + 24

f(3) = - 27 c₁ + 64 c₂ + 8 c₃ + 24 c₄ = 68

n = 4 à f(4) = c₁ (-3)⁴ + c₂ (4)⁴ + (c₃ + c₄ 4) 2⁴ = 4 f (4 – 1)+ 12 f (4 -2) + 2⁴ .4

f(4) = 81 c₁ + 256 c₂ + 16 c₃ + 64 c₄ = 4 f (3)+ 12 f (2) + 64

f(4) = 81 c₁ + 256 c₂ + 16 c₃ + 64 c₄ = 4.68+ 12.5 + 64

f(4) = 81 c₁ + 256 c₂ + 16 c₃ + 64 c₄ = 272+ 60 + 64

f(4) = 81 c₁ + 256 c₂ + 16 c₃ + 64 c₄ = 396