Soal 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

Catatan :

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 n untuk n > 3

Jawab :

Terdapat beberapa langkah pembuktian dengan induksi matematika:

Langkah 1:

Menunjukkan bahwa pernyataan tersebut benar untuk n0 = 4.

n = 4 maka 4! ≤ 24

4.3.2.1 ≤ 16

24 > 16

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

Dengan demikian pembuktian selesai, pernyataan tersebut tidak benar.

b. (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 n0 = 1.

n = 1 maka 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 maka 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. equation1.jpg

Jawab:

equation2.jpg

Langkah 1:

Menunjukkan bahwa pernyataan tersebut benar untuk n0 = 1.

n = 1 maka 3.jpg

41.jpg

51.jpg
61.jpg

Jadi pernyataan tidak benar untuk n = 1

Dengan demikian pembuktian selesai, pernyataan tersebut tidak benar.

d. 8.jpg

Jawab:

9.jpg

10.jpg

11.jpg

Langkah 1:

Menunjukkan bahwa pernyataan tersebut benar untuk n0 = 1.

n = 1 maka 2 = 2 + (1 – 1) 21+1

2 = 2 + 0 . 22

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 maka 2 + 8 + 24 + … + k 2k = 2 + (k – 1) 2k+1

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

Dari asssumsi diatas :

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

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

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

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

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

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

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

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

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

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

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

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

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

Jadi pernyataan tersebut benar untuk n = k + 1

Pembuktian selesai

Soal No 2:

Diketahui matriks 12.jpgHitunglah determinan dan inversnya.

Jawab :

Determinan matriks 12.jpg =13.jpg

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

=14.jpg

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

=15.jpg

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

=16.jpg

= (-1) x (-1 ) x 11 x 17.jpg

= – 47

Invers matriks

1.jpg

Operasi baris elementer

21.jpg

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

= 4.jpg

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

= 5.jpg

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

= 6.jpg

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.

= 7.jpg

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

= 71.jpg

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

= 81.jpg

Operasi pada baris ke -1 : baris ke-1 kali10.jpg

Operasi pada baris ke -2 : baris ke-2 kali11.jpg

Operasi pada baris ke -3 : baris ke-3 kali12.jpg

Operasi pada baris ke -4 : baris ke-4 kali13.jpg

=131.jpg

Jadi invers matriksnya =141.jpg

  1. Soal :

Ubahlah ekpresi rekursif berikut menjadi non rekursif.

Jawab :

Persamaan Karakteristik homogen

f

: xn-2

(n) = xn

xn = 4xn 1 + 12xn-2

x2 = 4x + 12

x2 – 4x – 12 = 0

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

Persamaan Karakteristik non homogen

2n n c = 2, d = 1

 (x – 2)1 + 1 = (x – 2)2

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

x1 = -3 x2 = 4 x3 = x4 = 2

f(n) = c1 x1n + c2 x2n + (c3 + c4 n) x3n

f(n) = c1 (-3)n + c2 (4)n + (c3 + c4 n) 2n

n = 1 f(1) = c1 (-3)1 + c2 (4)1 + (c3 + c4 1) 21 = 12 + 1

f(1) = – 3 c1 + 4 c2 + 2 c3 + 2 c4 = 2

n = 2 f(2) = c1 (-3)2 + c2 (4)2 + (c3 + c4 2) 22 = 22 + 1

f(2) = 9 c1 + 16 c2 + 4 c3 + 8 c4 = 5

n = 3 f(3) = c1 (-3)3 + c2 (4)3 + (c3 + c4 3) 23 = 4 f (3 – 1)+ 12 f (3 -2) + 23 .3

f(3) = – 27 c1 + 64 c2 + 8 c3 + 24 c4 = 4 f (2)+ 12 f (1) + 24

f(3) = – 27 c1 + 64 c2 + 8 c3 + 24 c4 = 4.5+ 12.2 + 24

f(3) = – 27 c1 + 64 c2 + 8 c3 + 24 c4 = 20+ 24 + 24

f(3) = – 27 c1 + 64 c2 + 8 c3 + 24 c4 = 68

n = 4 f(4) = c1 (-3)4 + c2 (4)4 + (c3 + c4 4) 24 = 4 f (4 – 1)+ 12 f (4 -2) + 24 .4

f(4) = 81 c1 + 256 c2 + 16 c3 + 64 c4 = 4 f (3)+ 12 f (2) + 64

f(4) = 81 c1 + 256 c2 + 16 c3 + 64 c4 = 4.68+ 12.5 + 64

f(4) = 81 c1 + 256 c2 + 16 c3 + 64 c4 = 272+ 60 + 64

f(4) = 81 c1 + 256 c2 + 16 c3 + 64 c4 = 396

Untuk mencari nilai c1, c2, c3, c4 dapat dilakukan dengan metode eliminasi, substitusi atau dengan eliminasi gauss. Dalam hal ini kita selesaikan dengan menggunakan eliminasi gauss.

=

Substitusi n = 3m , m = 3 log n

Substitusi f(3m) = g(m)

Persamaan Karakteristik homogen

g

: xm-2

(m) = xm

xm = 2xm 1 + 10xm-2

x2 = 2x + 10

x2 – 2x + 10 = 0

Persamaan Karakteristik non homogen

2n n c = 2, d = 1

 (x – 2)1 + 1 = (x – 2)2

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

x1 = -3 x2 = 4 x3 = x4 = 2

f(n) = c1 x1n + c2 x2n + (c3 + c4 n) x3n

f(n) = c1 (-3)n + c2 (4)n + (c3 + c4 n) 2n

n = 1 f(1) = c1 (-3)1 + c2 (4)1 + (c3 + c4 1) 21 = 12 + 1

f(1) = – 3 c1 + 4 c2 + 2 c3 + 2 c4 = 2

n = 2 f(2) = c1 (-3)2 + c2 (4)2 + (c3 + c4 2) 22 = 22 + 1

f(2) = 9 c1 + 16 c2 + 4 c3 + 8 c4 = 5

n = 3 f(3) = c1 (-3)3 + c2 (4)3 + (c3 + c4 3) 23 = 4 f (3 – 1)+ 12 f (3 -2) + 23 .3

f(3) = – 27 c1 + 64 c2 + 8 c3 + 24 c4 = 4 f (2)+ 12 f (1) + 24

f(3) = – 27 c1 + 64 c2 + 8 c3 + 24 c4 = 4.5+ 12.2 + 24

f(3) = – 27 c1 + 64 c2 + 8 c3 + 24 c4 = 20+ 24 + 24

f(3) = – 27 c1 + 64 c2 + 8 c3 + 24 c4 = 68

n = 4 f(4) = c1 (-3)4 + c2 (4)4 + (c3 + c4 4) 24 = 4 f (4 – 1)+ 12 f (4 -2) + 24 .4

f(4) = 81 c1 + 256 c2 + 16 c3 + 64 c4 = 4 f (3)+ 12 f (2) + 64

f(4) = 81 c1 + 256 c2 + 16 c3 + 64 c4 = 4.68+ 12.5 + 64

f(4) = 81 c1 + 256 c2 + 16 c3 + 64 c4 = 272+ 60 + 64

f(4) = 81 c1 + 256 c2 + 16 c3 + 64 c4 = 396

Tinggalkan Balasan

Please log in using one of these methods to post your comment:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s