Oleh: Hedri Wahyudi | Desember 14, 2007

Pembahasan 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

           


          Responses

          1. Good day!,

          2. untuk pengetikan formula atau persamaan matematik di web coba pakai aja ASCIMATH, jadi tidak diakalin pakai image dan jauh lebih cepat

          3. pusing

          4. No. 1 pke’ AM-GM bs! Tinggal dbktiin klo n>3 pzt brlaku!

          5. gunakan latex untuk rumus2 matematika, tampilan akan lebih baik.

          6. soal yang sangat myulitkan bgi saya

          7. Halo Pak, bisakah saya minta file word nya? Terima kasih. email saya: tikansari.mail@gmail.com


          Tinggalkan Balasan

          Isikan data di bawah atau klik salah satu ikon untuk log in:

          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

          Kategori

          %d blogger menyukai ini: