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

DIFERENSIAL CINTA

Oleh Limit Menuju Tak Hingga

Saat aku bersua dengan eksponen jiwamu
Sinus cosinus hatiku bergetar
Membela rasa penuh peluang


Diagonal-diagonal ruang hatiku membentuk kurva
Bersentuhan dengan diagonal-diagonal bidang hatiku


Jika aku adalah akar-akar persamaan x₁ dan x<sub>2
Maka engkaulah persamaan dengan akar-akar 2x1 dan 2x2


Aku ini binatang jalang dari himpunan kosong
Kaulah integral belahan jiwaku
Kaulah kodomain fungsi hatiku


Kemana harus kumencari modulus vektor hatimu
Dengan besaran apakah harus kunyatakan cintaku


Kulihat variabel dimatamu
Matamu bagaikan asymtot-asymtot hiperbola
Kulihat grafik cosinus dimulutmu
Kadang-kadang membentuk kurva normal


Modus ponens, modus tolens
Entah dengan modus apa kusingkap logika hatimu


Beribu-ribu matriks ordo 2 x 2 kutempuh
Bagaimana kuungkap adjoin padamu


Kujalani tiap barisan geometri yang tak hingga jumlahnya
Bagaikan limit x menuju nol</sub>


Akhirnya kutemui matriks hatimu
Tepat saat jarum panjang dan pendek berimpit
Pada pukul 12.00 sehingga 4 durian dibagi
Dengan makhluk hidup dikampus UNRI
Jawabannya kucari dekat nol