Advertisements
Archive | Matematika RSS feed for this section

Cubic Spline Interpolation

5 Oct

Cubic Spline Interpolation merupakan salah satu metode interpolasi yang menggunakan polinomial orde rendah pada interval yang tidak terlalu besar. Interpolasi spline kubik S(x) biasanya polinomial dengan orde 3 (cubic) yang menghubungkan dua titik yang bersebelahan. Metode ini akan sangat berguna untuk meningkatkan akurasi pada hasil dari interpolasi. Cubic Spline Interpolation membagi-bagi interval fungsi menjadi sub-interval dimana setiap sub-sub interval akan dicari pendekatan fungsi cubic-spline-nya, kemudian dikonstruksikan menjadi satu fungsi polinomial yang utuh. Melalui cara pembagian ini menjadi sub-interval, maka error yang dihasilkan dapat dikurangi, sehingga fungsi yang dihasilkan akan mendekati fungsi aslinya.

Advertisements

Contoh soal dan solusi matematika kombinatorik

3 Jun

1. Pak Tino memiliki 4 anak perempuan dan 3 anak laki-laki yang semuanya berusia dibawah 17 tahun. Pak Tino ingin mengajak anak-anaknya ke restoran. Karena mobil Pak Tino hanya muat 5 penumpang termasuk dirinya, maka hanya 4 anaknya yang bisa naik mobilnya. Pak Tino perlu minimal satu anak laki-laki di mobilnya untuk menemaninya sebagai petunjuk jalan. Berapa banyaknya cara Pak Tino  memilih anak-anaknya untuk naik mobilnya jika

a.      Tempat duduk anak-anak tersebut diperhatikan

Cara 1: (difference rule)

Banyaknya cara = total seluruh kemungkinan – kemungkinan semua anak perempuan

= P(7,4) – P(4,4) = 816 cara

Cara 2: (addition rule)

Banyaknya cara =    (1 anak lelaki dan 3 anak perempuan ) +(2 anak lelaki dan 2 anak perempuan )+ (3 anak lelaki dan 1 anak perempuan )

=    (P(4) * C(3,1)*C(4,3)) +  ((P(4) * C(3,2)*C(4,2)) + (P(4) *C(3,3)*C(4,1))

=  (24*3*4) + (24*3*6) + (24*1*4)

=  288 +  432 + 96  =  816

Common Mistake:

C(3,1) x P (6,3) = 3 x 120 = 360

Jika jawabannya seperti ini, berarti sudah dipastikan bahwa yang diajak adalah (1 laki-laki dan 3 perempuan), padahal bisa saja yang diajak adalah (2 laki-laki + 2 perempuan kan)?

b.      Tempat duduk tidak diperhatikan

Cara 1: (difference rule)

Banyaknya cara = C(7,4) – C(4,4) = 34 cara

 Cara 2: (addition rule)

Banyaknya cara =    (1 anak lelaki dan 3 anak perempuan ) + (2 anak lelaki dan 2 anak perempuan ) + (3 anak lelaki dan 1 anak perempuan )

=    (C(3,1)*C(4,3)) +  (C(3,2)*C(4,2)) + (C(3,3)*C(4,1))

=  (3*4) + (3*6) + (1*4)

=  12 + 18 + 4 = 34

Common Mistake:

C(3,1) x C (6,3) = 3 x  20 = 60

Jika jawabannya seperti ini, berarti sudah dipastikan bahwa yang diajak adalah (1 laki-laki dan 3 perempuan), padahal bisa saja yang diajak adalah 2 laki-laki + 2 perempuan kan?

2. Terdapat 5 buah bola dan 3 buah kotak.

 a.      Jika setiap bola dapat dibedakan menjadi b1,b2,b3,b4,b5 dan setiap kotak dapat dibedakan menjadi k1, k2, k3, ada berapa cara untuk menempatkan 3 bola ke 3 kotak terebut? (masing-masing kotak berisi 1 bola)

Banyaknya cara menempatkan 3 bola ke 3 kotak = P(5,3) = 60 cara

b.      Jika semua bola tidak dapat dibedakan dan setiap kotak dapat dibedakan menjadi k1, k2, k3, ada berapa cara untuk menempatkan kelima bola ke 3 kotak tersebut?

Banyaknya cara menempatkan kelima bola ke 3 kotak tersebut = C (5+3-1,5) = 21 cara

c.       Jika semua bola tidak dapat dibedakan dan setiap kotak dapat dibedakan menjadi k1, k2, k3, ada berapa cara untuk menempatkan kelima bola ke dalam ketiga kotak tersebut agar setiap kotak terisi paling sedikit satu bola?

Banyaknya cara menempatkan kelima bola kedalam tiga kotak agar setiap kotak terisi paling sedikit 1 bola = C(2+3-1,2) = 6 cara

Contoh solusi penggunaan Master Theorem atau Metode Master untuk rekurensi

23 May

Teorema 1 (Metode Master) Diberikan suatu rekurensi T (n) = aT (n/b) + f (n) , jika n ≥ n0, untuk suatu n0 elemen N dan T (n) konstan untuk 0 ≤  n < n0. Apabila a ≥ 1, b > 1 keduanya adalah nilai yang konstan dan f (n) adalah fungsi yang asimtotik positif, maka:

master theorem

Gunakan Teorema 1 untuk mencari solusi dari setiap rekurensi berikut dalam notasi . Jika metode master tidak dapat diterapkan, gunakan metode lain yang Anda ketahui. Asumsikan bahwa T (n) konstan untuk n yang cukup kecil.

(a).  T (n) = 3T (n/2) + n.

Solusi T (n) = 3T (n/2) + n menggunakan master theorem kasus 1.

solusi master theorem 1

(b). T (n) = 2T (n/2) + n^3.

Solusi T (n) = 2T (n/2) + n^3 menggunakan master theorem kasus 3.

solusi master theorem 2

(c). T (n) = 7T (n/3) + n^2.

Solusi T (n) =  7T (n/3) + n^2 menggunakan master theorem kasus 3.solusi master theorem 3

(d).  T (n) = 2T (n/2) + n lg n.

Solusi T (n) =  2T (n/2) + n lg n menggunakan master theorem kasus 2.

solusi master theorem 4

(e). T (n) = 4T (n/2) + n^2 √n.

Solusi T (n) = 4T (n/2) + n^2 √n menggunakan master theorem kasus 3.

solusi master theorem 5

(f). T (n) = T (√n) + 1 (petunjuk: substitusikan n = 2^m).

Solusi T (n) = T (√n) + 1 menggunakan master theorem kasus 2.

solusi master theorem 6

 

(g). T (n) = 2T (n – 1) + 1 (asumsikan T (1) = 1).

Kita tidak dapat menggunakan master theorem untuk kasus ini. Dengan evaluasi iteratif, kita memiliki

solusi master theorem 7

 

(h). T (n) = T (n – 1) + lg n (asumsikan T (1) = 1).

Dengan evaluasi iteratif, kita memiliki

solusi master theorem 8-1

Dengan sifat logaritma lg a + lg b = lg ab, diperoleh

solusi master theorem 8-2

Dengan aproksimasi Stirling,  lg (n!) = Θ(n lg n). Akibatnya T (n) = 1 +Θ (n lg n) = Θ(n lg n)

(i). T (n) = T (n – 2) + 2 lg n (asumsikan T (0) = 2).

Karena paritas (genap-ganjil) dari n tidak berpengaruh pada nilai T (n) secara asimtotik, kita boleh mengasumsikan n genap. Dengan evaluasi iteratif, kita memiliki

solusi master theorem 9-1 solusi master theorem 9-2

(j). T (n) = √n T (√n) + 2013 n (petunjuk: misalkan T (n) = nS (n) dengan S (n) adalah fungsi yang asimtotik positif).

Misalkan T (n) = nS (n), maka T (√n) = √n S (√n). Akibatnya rekurensi pada soal setara dengan

solusi master theorem 10-1 solusi master theorem 10-2Demikianlah contoh penggunaan master theorem dalam masalah rekurensi, semoga bermanfaat!

 

Logika Proposisi

18 May

Logika Proposisi atau Kalkulus Proposisi dikembangkan oleh ahli filsafat Yunani Aristotle 2300 tahun lebih.

Definisi 1. 

Suatu proposisi (proposition) adalah suatu pernyataan (statement) yang memiliki nilai kebenaran true (benar, T) atau false (salah, F) tetapi tidak kedua-duanya pada saat dinyatakannya.

Contoh 1. 

Pernyataan berikut adalah proposisi:

(a)                    Jakarta adalah ibu kota Indonesia.

(b)                    Penang adalah ibu kota Malaysia.

(c)                    5 + 6 = 11.

(d)                   25 + 2 = 26.

Proposisi (a) dan proposisi (c) bernilai true, sedangkan proposisi (b) dan proposisi (d) bernilai  false.

Contoh 2.      

Pernyataan berikut bukan proposisi :

(a)             Jam berapa sekarang ?

(b)             Bacalah dengan teliti.

(c)             x + 1 = 2.

(d)            x + y = z.

Kalimat (a) dan kalimat (b) masing-masing bukan pernyataan, jadi bukan proposisi. Kalimat (c) merupakan pernyataan tetapi bukan suatu proposisi, karena variabel x dalam kalimat tersebut belum ada nilainya, jadi masih dapat bernilai true (bila x bernilai 1) juga dapat bernilai false (bila x ≠ 1). Begitu pula dengan kalimat (d).

Proposisi yang bernilai tetap pada setiap saat disebut konstanta proposisi. Dikenal dua buah konstanta proposisi:

  • Proposisi true atau T, yang selalu bernilai true
  • Proposisi false atau F, yang selalu bernilai false.

Proposisi lainnya, yang nilainya bisa true atau false pada saat yang berbeda disebut juga sebagai variabel proposisi, dapat dinyatakan oleh sebuah huruf. Misalnya,

                   p,q, r, s, ¼¼, p1, p2, ¼¼, q1, q2, ¼¼, r1, r2, ¼¼, s1, s2, ¼¼

Operator Logika atau Penghubung Logika (Logical Connectives)

 

Dari proposisi-proposisi yang ada dapat dibentuk proposisi baru dengan menggunakan penghubung atau operator logika. Yang dikenal ada 6 operator logika, yaitu negasi Ø, konjungsi Ù, disjungsi Ú, exclusive or Å, implikasi ®, dan bi-implikasi (biconditional) «, masing-masing didefinisikan sebagai berikut:

 

1.  Operator negasi Ø 

tabel kebenaran negasi                     

2.  Operator Konjungsi Ù

tabel kebenaran konjungsi

3.  Operator Disjungsi Ú

tabel kebenaran disjungsi 

4.  Operator Exclusive Or  Å

tabel kebenaran exclusive or

5.  Operator Implikasi ®

tabel kebenaran implikasi
6.  Operator 
Bi-implikasi (Biconditional) «

tabel kebenaran bi-implikasi

Muddy children puzzle

18 May

Seorang ayah menyuruh seorang putra dan seorang putrinya pergi main ke lapangan. Setelah kembali dari bermain, ternyata dahi masing-masing anaknya tercoreng kotoran. Setelah terlihat oleh ayahnya, si ayah menegur mereka dan bilang:

“Di antara kalian berdua ada yang dahinya tercoreng kotoran.”

Kemudian si ayah memberi pertanyaan

“Apakah anda tahu bahwa dahi anda yang tercoreng kotoran?”

kepada kedua anaknya, yang harus dijawab serentak “ya” atau “tidak” oleh kedua anaknya tersebut.

Dimisalkan bahwa kedua anak tersebut jujur, dan masing-masing tidak bisa melihat dahi sendiri, tetapi bisa melihat dahi saudaranya.

Jawaban serentak apa yang akan diberikan oleh kedua anak tadi untuk pertanyaan tersebut dilontarkan untuk pertama kali, dan untuk kedua kali pertanyaan tersebut dilontarkan?

Solusi:

Misalkan   s := dahi si putra kotor dan d := dahi si putri kotor

Diketahui faktanya adalah s bernilai true, dan d juga bernilai true.

Pernyataan si ayah kepada putra dan putrinya adalah

“Di antara kalian berdua ada yang dahinya tercoreng kotoran.”

yang dapat dinyatakan dengan proposisi

p := s –> d

dan berdasarkan pernyataan si ayah tersebut, berarti p bernilai true.

Dipertanyakan jawaban serentak apa yang diberikan oleh putra dan putrinya terhadap pertanyaan yang sama:

“Apakah anda tahu bahwa dahi anda yang tercoreng kotoran?”

untuk yang pertama kali dan yang kedua kalinya.

Jawaban serentak si putra dan si putri untuk pertanyaan pertama kali:

Si putra melihat dahi si putri kotor, berarti

d  bernilai true, yang mengakibatkan p juga bernilai true, tanpa mengetahui nilai dari s.

Jadi, si putra tidak dapat memastikan dahinya kotor atau tidak, maka ia akan beri jawaban “tidak”.

Begitu pula dengan si putri, ia melihat dahi si putra kotor berarti s bernilai true, tanpa mengetahui nilai dari d.

Jadi, si putri tidak dapat memastikan dahinya kotor atau tidak, maka ia akan beri jawaban “tidak” pula.

Jawaban serentak si putra dan si putri untuk pertanyaan kedua kali:

Setelah si putra mengetahui jawaban “tidak” dari si putri,

berarti si putri tidak mengetahui nilai d,

jadi d  bisa bernilai false, sedangkan p := s –> d  harus bernilai true,

maka si putra mengetahui bahwa s bernilai true,

sehingga si putra akan menjawab “ya” untuk pertanyaan yang sama untuk yang kedua-kalinya.

Begitu juga dengan si putri, ia akan menjawab “ya” pula.

Dependent Linear and Independent Linear

3 May

Untuk membuktikan bahwa sebuah himpunan fungsi adalah dependent linear, kita harus mencari konstanta a, b, c, dst yang tidak semuanya 0, sedemikian sehingga ap + bq + cr + … = 0. Jika kita tidak bisa menemukan konstanta a, b, c, dst yang tidak semuanya 0, maka dapat disimpulkan bahwa himpunan fungsi tersebut adalah independent linear.

Contoh 1:

Buktikan bahwa himpunan {2x, x – 1, 2 – x} dependen linier.

Misalkan:
p = 2x
q = x – 1
r = 2 – x

Agar {p, q, r} dependen linier, maka harus ada konstanta a, b, c, yang tidak semuanya 0, sedemikian
sehingga ap + bq + cr = 0.

Jika disederhanakan:
a(2x) + b(x – 1) + c(2 – x) = 0
2ax + bx – b + 2c – cx = 0
x(2a + b – c) – b + 2c = 0

Maka, terdapat sebuah sistem dengan 2 persamaan:
2a + b – c = 0
–b + 2c = 0

Dengan mengambil a = 1, b = –4, dan c = –2, maka sistem persamaan tersebut terpenuhi. Karena a, b, c
tidak semuanya 0, maka terbukti bahwa {p, q, r} dependen linier. (QED)

Contoh 2:

Buktikan bahwa himpunan {1, 2x – 1, x2 + 1} independen linier.

Misalkan:
p = 1
q = 2x – 1
r = x^2 + 1 (x^2 menyatakan x kuadrat)

Agar {p, q, r} dependen linier, maka harus ada konstanta a, b, c, yang tidak semuanya 0, sedemikian
sehingga ap + bq + cr = 0.

Jika disederhanakan:
a + b(2x – 1) + c(x^2 + 1) = 0
a + 2bx – b + cx^2 + c = 0
cx^2 + 2bx + a – b + c = 0

Maka, terdapat sebuah sistem dengan 3 persamaan:
c = 0
2b = 0
a – b + c = 0

Solusi yang memenuhi hanyalah a = 0, b = 0, c = 0. Karena a, b, c semuanya 0, maka terbukti bahwa
{p, q, r} independen linier. (QED)

Okay, demikianlah sedikit penjelasan mengenai dependent linear dan independent linear yang biasanya sering kita gunakan dalam pemasalahan matematika, terutama matriks dalam aljabar linear. Semoga kita semua mengerti dan bertambah ilmunya. Terima kasih.