SOAL UJIAN AKHIR MATEMATIKA INFORMATIKA 4 (A & B) Dosen: Dr. Asep Juarna Jumlah Soal: 3 Uraian Tanggal Ujian: 02/03/12 Waktu Ujian: 2 jam 1.
1 jika n 1 adalah: t(2n) = 1 + 2log n, yang dapat dibuktikan sbb: t (n) 1 jika n 1
Solusi t (2n)
t(2n) = t(n) + 1 = [t(n/2) + 1] + 1 = t(n/2) + 2 = t(n/4) + 3 = t(n/8) + 4 = t(n/16) + 5 = .... (perhatikan bahwa hubungan-hubungan: 2 dengan 2, 4 dengan 3, 8 dengan 4, 16 dengan 5, dst adalah: 2 = 2log 2 +1, 3 = 2log 4 +1, 4 = 2log 8 +1, 5 = 2log 16 +1, dst), sehingga: t(2n) = t(n/(n/2)) + (2log (n/2) + 1) = t(2) + 2log n - 2log 2 + 1 = 1 + 2log n -1 + 1 = 1 + 2log n
Soal A 1
jika n 1 2p(n) (n 1) jika n 1
Dengan cara yang sama, buktikan bahwa solusi p(2n)
adalah p(2n) = 1 + n 2log n. Verifikasi solusi tersebut dengan menggunakan Master Theorem (anda bisa mengkonversi 2n menjadi n dan n menjadi n/2). Solusi A Metoda Substitusi: p(2n) = 2p(n) + (n – 1) = 2[2p( n ) + ( n – 1)] + (n – 1) = 22p( n ) + 2n – 3 2
2
2
= 22[2p( n ) + ( n – 1) ]+ 2n – 2 – 1 = 23p( n ) + 3n – 7 4
4
4
= 23[2p( n ) + ( n – 1) ]+ 3n – 6 – 1 = 24p( n ) + 4n – 15 8
8
8
= 24[2p( n ) + ( n – 1) ]+ 4n – 14 – 1 = 25p( n ) + 5n – 31 16
16
16
dst Perhatikan perkembangan pasangan 4 bilangan (pangkat dari 2, denominator n, koefisien n, konstanta) yaitu (2, 2, 2, 3), (3, 4, 3, 7), (4, 8, 4, 15), (5, 16, 5, 31) = (5, 2 5-1, 5, 25 – 1) = (2log 16 + 1, 16, 2log 16 + 1, 2log 16+1 – 1) Karena diketahui p(2n) = 1 jika n = 1 (yaitu p(2) = 1), maka p( n ) menjadi p(2) jika x = n 2 x sehingga pasangan 4 bilangan adalah (dalam n ): (2log( n ) + 1, n , 2log( n ) + 1, 2log(n/2)+1 – 1) 2
2
2
2
= (2log n – 2log 2 + 1, n , 2log n – 2log 2 + 1, ( n )2 – 1) = (2log n, n , 2log n, n – 1), sehingga: 2
2
2
p(2n) = 2log n p(2) + (2log n)n – (n – 1) = n (1) + n 2log n – n + 1 = 1 + n 2log n Dalam notasi kompleksitas: p(2n) = (n log n) Master Theorem: Diberikan T(n) = aT(n/b) + f(n), maka dalam notasi big-Theta:
Θ(f(n)) b T(n) = Θ(n loga ) Θ(f(n) blogn
jika af(n/b) jika af(n/b) jika af(n/b)
κf(n), κ 1 κf(n), κ 1 f(n)
Formula p(2n) = p(n) + (n – 1) dapat dituliskan menjadi p(n) = p( n ) + ( n – 1) 2
2
sehingga berdasarkan Master Theorem formula tersebut mempunyai nilai-nilia berikut: a = 1, b = 2, dan f(n) = ( n – 1). Dengan demikian af(n/b) = 1( n /2 – 1) = (n – 1) = f(n) yang 2
2
merupakan kasus ketiga Master Theorem. Jelaslah T(n) = ((n-1) 2log n) = (n log n).
Soal B Dengan cara yang sama, buktikan bahwa solusi q(n)
b 2q(n/2) bn
jika n 2 jika n 2
adalah q(n) = bn + bn 2log n. Verifikasi solusi tersebut dengan menggunakan Master Theorem. Solusi B Metoda Substitusi: q(n) = 2q(n/2) + bn = 2[2q( n ) + b n ] + bn = 22q( n ) + 2bn 4
2
4
= 22[2q( n ) + b n ]+ 2bn = 23q( n ) + 3bn 8
4
8
= 23[2q( n ) + b n ]+ 3bn = 24q( n ) + 4bn 16
8
16
dst Perhatikan perkembangan pasangan 3 bilangan (pangkat dari 2, koefisien bn) yaitu (2, 4, 2), (3, 8, 3), (4, 16, 4). Karena diketahui q(n) = b jika n = 1 (yaitu q(1) = 1), maka q( n ) menjadi p(1) jika x = n x 2 sehingga pasangan 3 bilangan adalah (dalam n): (n, n, ( log n)), sehingga: q(n) = n q(1) + (2log n)bn = bn + bn 2log n. Dalam notasi kompleksitas: q(n) = (n log n)
Master Theorem: Diberikan T(n) = aT(n/b) + f(n), maka dalam notasi big-Theta:
Θ(f(n)) b T(n) = Θ(n loga ) Θ(f(n) blogn
jika af(n/b) jika af(n/b) jika af(n/b)
κf(n), κ 1 κf(n), κ 1 f(n)
Berdasarkan Master Theorem formula q(n) = 2q(n/2) + bn mempunyai nilai-nilia berikut: a = 2, b = 2, dan f(n) = bn. Dengan demikian af(n/b) = 2(b n /2) = 2 bn = 2f(n) yang 2
merupakan kasus ketiga Master Theorem. Jelaslah T(n) = ((n-1) 2log n) = (n log n). 2.
Selesikan persamaan rekursif berikut dengan metoda akar karakteristik dan generating function. Soal A
an
3an
dengan n
1
5(3 n ) 1, a0
(1) 2
Solusi A Metoda Akar Karakteristik Komponen persamaan homogen dari persamaan (1) adalah: an
3an
1
0 . Misalkan
n
solusinya adalah: a n = r , yang menghasilkan persamaan karakteristik: r – 3 = 0 atau r = 3. Dengan demikian solusi homogen persamaan (1) adalah: a n (h) = A3n Suku non-homogen (partikulir/khusus) dari persamaan (1) adalah: F(n) = 5(3n), dengan 3 adalah akar karakteristik berderajat satu sehingga solusi non-homogennya kita misalkan: a n (p) = p0n3n dengan p0 = (polinomial) konstan. Substitusi solusi ini ke persamaan (1) menghasilkan: p0n3n – 3(p0(n-1)3n-1 ) = 5(3n) p0n3n – (p0(n-1)3n ) = 5(3n) p0 = 5, sehingga solusi non-homogennya adalah: a n (p) = 5n3n
p03n = 5(3n)
Solusi umum: a n = a n (h) + a n (p) = A3n + 5n3n. Substitusi nilai awal: a 0 = 2 = A30 + 0 n
n
sehingga solusi umumnya adalah: an = 2(3 ) + 5n(3 ) Cek: a0 = 2(30) + 5(0)(30) = 2 Metoda Generating Function an x n
Misalkan G(x) = n
0
Kalikan persamaan (1) dengan xn dan sum over n
1 (sesuai soal), hasilnya:
A=2
a xn n
n
1
a
3 n
1
xn
n-1
n
n
a xn n 1 n
0
a
(2)
1
a n x n dengan manipulasi sehingga persamaan (2) menjadi:
Arahkan menjadi G(x) =
a
(3 n )x n
5
0
3x
0
a n
1
n-1
xn - 1
5
(3n )x n n 0
(3)
1
Perhatikan bahwa “1” di ruas kanan persamaan (3) adalah 30x0 dan sehingga ruas kanan ini ekuivalen dengan 5 dapat dituliskan sebagai: 3x
a n
1 . Selanjutnya suku kedua ruas kiri
3x
a n-1
1 1 3x
1-1
n-1
xn - 1
3x
a n-1
0
xn - 1 =
n-1
a x m = 3xG(x) sehingga persamaan (3) menjadi:
3x m
0
m
(G(x) – a0) – 3xG(x) = 5 G(x) (1 – 3x) = 5 G(x) = 5
5xn
1 1 3x
1 1 3x
1
(G(x) – 2) – 3xG(x) = 5
1 +2= 5
1 1 3x
1
3x +2 1 3x
3x + 2 2 1 3x (1 3x)
Tetapi: d 1 dx 1 3x
2
1
xn - 1
n-1
1 1 3x
(3 n )x n =
n 0
(3 n )x n-1 = 5n
n 0
3x 3 sehingga: 5 2 (1 3x) 2 (1 3x)
(4) = 5x d 1 = 5x d dx 1 3x dx
(3 n )x n . Dengan demikian persmaan (4) menjadi: G(x) = 5n
n 0
(3 n )x n =
n 0
(3 n )x n +
n 0
(3 n )x n atau an = 5n(3n) + 2(3n)
n 0
Soal B an 2 5an
1
dengan n
0 , a0
6an
2 3, a1
(5) 7
Solusi B Metoda Akar Karakteristik Komponen persamaan homogen dari persamaan (5) adalah: an
2
5an
1
6an
0.
Misalkan solusinya adalah: a n = rn, yang menghasilkan persamaan karakteristik: r2 – 5r + 6 = 0 atau r1 = 3 dan r2 = 2. Dengan demikian solusi homogen persamaan (5) adalah: a n (h) = A3n + B2n.
Suku non-homogen (partikulir/khusus) dari persamaan (5) adalah: F(n) = 2 sehingga solusi non-homogennya kita misalkan: a n (p) = bn + c. Sobstitusi solusi ini ke persamaan (5) menghasilkan: (b(n + 2) + c) - 5(b(n + 1) + c) + 6(bn + c) = 2 bn(1 – 5 + 6) + b(2 – 5) + c(1 – 5 + 6) = 2 – 5b + 2c = 2 yang memberikan b = 1, c = 7/2 sebagai salah satu solusi. Dengan demikian solusi non-homogennya adalah: a n (p) = n + 7/2. Solusi umum: a n = a n (h) + a n (p) = A3n + B2n + n + 7/2. Substitusi nilai awal meghasilkan: a0 = 3 = A + B + 7/2 A + B = -1/2 a1 = 7 = 3A + 2B + 1 + 7/2 3A + 3B = 5/2 A = 7/2, B = 4 Solusi umum: an = 7/2(3n) – 4(2n) + n + 7/2 Cek: a0 = 7/2 – 4 + 0 +7/2 = 7 – 4 + 0 = 3 a1 = 7/2(31) – 4(21) + 1 + 7/2 = 14 -8 + 1 = 7 Metoda Generating Function an x n
Misalkan G(x) = n
0
Kalikan persamaan (5) dengan xn dan sum over n a n
0
n
2
xn
5
a
n
0
n
xn
1
a xn
6 n
0
xn
2
n
0 (sesuai soal), hasilnya:
n
(6)
0
a n x n , mula-mula dengan mengalikan lagi semua suku dengan
Arahkan menjadi G(x) = n
0
2
x sehingga persamaan (6) menjadi: x2
a n
0
n
a n
0
2
n
2
xn
5x 2
a n
xn
2
0
5x n
a n
1
a
Perhatikan bahwa: G(x) (a0
n
0
0
n
2
n
xn
6x 2
a xn n
xn
1
1
0
2
6x 2
(a
0
xn n
a xn n
xn
2x 2
n
0
2x 2
n
a n
xn n
a x) 1
0
0
n
2
xn
(7)
0
2
(a0 xn
a1 x) , begitu juga analog untuk suku kedua, sedangkan n
demikian persamaan (7) menjadi:
G(x) a
0
ax
G(x) 3 7x
1
5x G(x) a0 5x G(x) 3
6 x 2 G(x)
6 x 2 G(x)
2x 2 1 x
2x 2 1 x
a1 x ) =
0
1 . Dengan 1 x
2 2 2 x 2 3(1 x) 8 x (1 x ) G(x)(1 – 5x + 6x2) = 2 x + 3 + 7x – 15x = 2 x + 3 – 8x = 1 x 1 x 1 x 2 G(x)(1 – 5x + 6x2) = 10 x 11x 3 1 x 2 10 x 2 11x 3 10 x 2 11x 3 G(x) = 10 x 11x 3 2 = = (1 x)(1 5x 6 x ) (1 x)( x 1/2)( x 1/3) (x 1)( x 1/2)( x 1/3)
G(x) = G(x) = G(x) = G(x) =
A (x 1)
B (x 1/2)
C (x 1/3)
A( x 1/2)( x 1/3) B(x 1)( x 1/3) C(x 1)( x 1/2) (x 1)( x 1/2)( x 1/3)
A( x 2
5x/6 1/6) B(x 2 4 x/3 1/3) C(x 2 (x 1)( x 1/2)( x 1/3)
3x/2 1/2)
(10/6) x 2 (11/6) x (1/2) (10/6) x 2 (11/6) x (1/2) 10 x 2 11x 3 = = (1 x)( x 1/2)( x 1/3) (1 x)(1/6 5x/ 6 x 2 ) (1 x)(1 5x 6 x 2 )
(10/6)x 2 (11/6)x (1/2) (x 1)( x 1/2)( x 1/3)
=
A (x 1)
G(x) =
A( x 1/2)( x 1/3) B(x 1)( x 1/3) C(x 1)( x 1/2) (x 1)( x 1/2)( x 1/3)
G(x) =
A( x 2
B (x 1/2)
C (x 1/3)
G(x) =
5x/6 1/6) B(x 2 4 x/3 1/3) C(x 2 (x 1)( x 1/2)( x 1/3)
3x/2 1/2)
Sehingga diperolah persamaan berikut: A + B + C = -10/6 - 5A/6 - 4B/3 - 3C/2 = 11/6 A/6 + B/3 + C/2 = -1/2 Diperoleh: A = -1, B = 0, dan C = -2/3 2/3 2/3 1 Jadi: G(x) = = 1 = 1 (x 1) (x 1/3) (1 x) (1/3 x) (1 x) =
n 0
xn + 2
2 (1 3x)
(3 n )x n
n 0
atau: an = 1 + 2(3n) Cek: a0 = 1 + 2(30) = 3 a1 = 1 + 2(31) = 7 Solusi ini berbed dengan solusi metoda karakteristik, yaitu: an = 7/2(3n) – 4(2n) + n + 7/2, tetapi cek a0 dan a1 menghasilkan nilai yang sama sesuai nilai awal yang diberikan.
3.
Soal A Sebuah perguruan tinggi bermaksud untuk menjadwalkan ujian untuk 8 mata kuliah berikut: A, B, C, D, E, F, G, dan H. Misalkan diketahui bahwa tidak ada mahasiswa yang mengambil pasangan-pasangan mata kuliah berikut: (A,B), (A,C), (A,D), (A,E), (A,F), (A,G), (A,H), (B,C), (B,E), (B,F), (B,G), (B,H), (C,H), (D,E), (D,F), dan (D,G). Tentukan berapa slot waktu ujian minimal yang dibutuhkan. Solusi A Misalkan Graf G(V,E) di mana V = himpunan mata kuliah, dan E = himpunan edge yang menghubungkan setiap 2 mata kuliah yang maksimal hanya 1 yang diambil seorang mahasiswa. Graf G’(V,E’) adalah komplemen dari G(V,E). Setiap edge menghubungkan 2 mata kuliah yang mungkin keduanya diambil seorang mahasiswa; jelas jadwalnya ujiannya harus berbeda. Tidak hanya itu, setiap 3 vertex yang membentuk segitiga harus tidak sewarna A B * *
C *
*D
E *
*F
* G
* H
Jadi ada 4 slot jadwal ujian. Tentu saja A punya 4 pilihan warna sedangkan B punya 3 pilihan. Pewarnaan di atas adalah salah satu 4 slot yang diambil. Soal B Graf berikut: --- --- --- dinyatakan dengan degree sequence sebagai graf (1,2,2,1). Gambarkan sebuah graf (3, 3, 3, 2, 3, 3) yang merupakan graf planar, mempunyai lintasan Euler, dan mempunyai lintasan Hamilton. Berapa jumlah regionnya? Tunjukan! Tunjukkan juga lintasan Euler dan lintasan Hamiltoniannya.
Solusi B
A *
B *
C *
*D
E *
*F
* G
* H
