Pembuktian Algoritma

TUGAS I

Pembuktian Algoritma

Nama : Muhammad Adet Karsa Pratama

NIM : 14.01.013.034

TEKNOLOGI INFORMATIKA

FAKULTAS TEKNIK INFORMATIKA

Universitas Teknologi Sumbawa 2016

Induksi matematika

Induksi matematika merupakan pembuktian deduktif, meski namanya induksi. Induksi matematika atau disebut juga induksi lengkap sering dipergunakan untuk pernyataan-pernyataan yang menyangkut bilangan-bilangan asli.

Pembuktian cara induksi matematika ingin membuktikan bahwa teori atau sifat itu benar untuk semua bilangan asli atau semua bilangan dalam himpunan bagiannya. Caranya ialah dengan menunjukkan bahwa sifat itu benar untuk n = 1 (atau S(1) adalah benar), kemudian ditunjukkan bahwa bila sifat itu benar untuk n = k (bila S(k) benar) menyebabkan sifat itu benar untuk n = k + 1 (atau S(k + 1) benar).

CONTOH

Buktikan bahwa jumlah n bilangan ganjil pertama adalah n2.

Persamaan yang perlu dibuktikan:

Langkah pembuktian pertama:
untuk , benar bahwa 

Langkah pembuktian kedua:
andaikan benar untuk , yaitu

, maka akan dibuktikan benar pula untuk , yaitu

sekarang sederhanakan persamaan pada sisi kiri dengan mengingat bahwa  sesuai dengan pengandaian awal

kemudian padankan bentuk sederhana tadi dengan sebelah kanan

, ingat bahwa 

 (terbukti benar)

Kesimpulan:

Ø  Jadi,  benar untuk semua bilangan asli karena memenuhi kedua langkah pembuktian.

Ø  Induksi Matematika merupakan suatu teknik yang dikembangkan untuk membuktikan pernyataan.

Ø  Induksi Matematika digunakan untuk mengecek hasil proses yang terjadi secara berulang sesuai dengan pola tertentu

Ø  Indukasi Matematika digunakan untuk membuktikan universal statements " n Î A S(n) dengan A Ì N dan N adalah himpunan bilangan positif atau himpunan bilangan asli.

Ø  S(n) adalah fungsi propositional

Pembuktian Kontradiktif

Kontradiksi adalah salah satu cara pembuktian matematis secara tidak langsung. Yaitu dengan cara kita asumsikan suatu kesimpulan dahulu, dan bila menemui hasil yang janggal (kontradiktif) maka asumsi tersebut dapat dinyatakan salah, serta secara otomatis ingkarannya benar.

Misal,

Akan dibuktikan bahwa untuk sebarang bilangan bulat a, berlaku : jika a² kelipatan 2, maka a juga kelipatan 2.

Andaikan a bukan kelipatan 2 ( asumsi awal ), maka a dapat ditulis sebagai berikut :

a = 2n + 1, n € Z.

akibatnya,

a² = (2n + 1)²

a² = 4n² + 4n + 1

a² = 2(2n² + 2n) + 1 , sehingga a² bukan kelipatan 2. Hal ini kontradiksi dengan fakta bahwa a² kelipatan 2. Jadi asumsi awal salah dan ingkarannya benar, yaitu a kelipatan 2. (Terbukti).

Pembuktian Kontrapositif

Pembuktian dengan kontrapositif (proof by contrapostive). Metode ini digunakan untuk membuktikan pernyataan implikasi

Jika P maka Q

Kontrapositif dari pernyataan implikasi  adalah . Dengan kata lain kontrapositif adalah menegasikan P dan Q lalu membalik arah panahnya. Dalam teori logika, Pernyataan implikasi dan kontraposisinya mempunyai nilai kebenaran yang sama. Coba kalian perhatikan tabel kebenaran berikut:

Dari tabel terlihat pernyataan  dan  adalah cara berbeda yang menunjukan suatu hal yang sama. Dengan membuktikan   , kita telah membuktikan  begitu pula sebaliknya.

Metode Formal

Dengan metode formal ini kita bisa melihat dari pembuktian dengan menggunakan pembuktian kebenaran sebuah algoritma, dari pembuktian dari metode formal ada yang terdiri dari pembuktian induksi matematika, pembuktian tidak langsung dan pembuktian tidak langsung.

Ø   Adapun pembuktian dari Induksi Matematika

Pembuktian menggunakan induksi matematika dilakukan dengan dua langkah, yaitu:

1.      Melakukan pembuktian kasus dasar (base case), yaitu membuktikan bahwa sebuah pernyataan (fungsi) matematika atau algoritma bernilai benar jika diaplikasikan pada bilangan pertama yang sah sesuai dengan spesifikasi fungsi atau algoritma tersebut.

2.      Melakukan induksi, yaitu membuktikan bahwa kebenaran dari fungsi \(P(k+1)\) jika kebenaran fungsi \(P(k)\) diketahui.

Dengan membuktikan kedua hal tersebut, kita dapat mengambil kesimpulan bahwa sebuah fungsi matematika atau algoritma bernilai benar untuk semua bilangan asli. Jika diimplementasikan dengan tepat, induksi matematika dapat juga digunakan untuk membuktikan kebenaran algoritma rekursif seperti penelusuran pohon (tree).

Misalkan contoh untuk membuktikan bahwa pernyataan matematika untuk perhitungan deret aritmatika berikut:

\[1 + 2 + 3 + ... + n = \frac{n(n + 1)}{2}\]

adalah benar untuk semua bilangan bulat \(n \geq 1\).

Untuk membuktikan pernyataan matematika di atas, terlebih dahulu kita harus mengubah pernyataan matematika tersebut menjadi sebuah fungsi matematika:

\[P(k) = 1 + 2 + 3 + ... + n = \frac{k(k + 1)}{2}\]

dan kemudian membuktikan kebenarannya menggunakan induksi matematika. Seperti yang telah dijelaskan sebelumnya, kita harus menjalankan dua langkah untuk melakukan pembuktian dengan induksi:

1.      Pembuktian Kasus Dasar

Karena pernyataan matematika pada soal menyatakan bahwa pernyataan benar untuk semua bilangan bulat \(k \geq 1\), maka untuk pembuktian kasus dasar kita harus membuktikan bahwa \(P(1)\) adalah benar untuk ruas kiri maupun ruas kanan dari \(P(k)\).

\[\begin{split}P(1)= 1 & = \frac{1(1+1)}{2} \\ 1 & = \frac{1(2)}{2} \\ 1 & = \frac{2}{2} \\ 1 & = 1\end{split}\]

karena hasil akhir dari ruas kanan dan ruas kiri adalah sama (\(1\)), maka dapat dikatakan bahwa kasus dasar telah terbukti.

2.      Induksi

Untuk pembuktian induksi, kita harus membuktikan bahwa \(P(k) \rightarrow P(k + 1)\) bernilai benar.

Langkah pertama yang dapat kita lakukan yaitu menuliskan fungsi matematis dari \(P(k + 1)\) terlebih dahulu:

\[P(k + 1) = 1 + 2 + ... + k + (k + 1) = \frac{(k + 1)((k + 1) + 1)}{2}\]

dan kemudian kita harus membuktikan bahwa ruas kiri dan ruas kanan dari \(P(k + 1)\) adalah sama. Pembuktian akan kita lakukan dengan melakukan penurunan pada ruas kiri agar menjadi sama dengan ruas kanan:

\[\begin{split}1 + 2 + ... + k + (k + 1) & = (1 + 2 + ... + k) + (k + 1) \\& = \frac{k(k + 1)}{2} + (k + 1) \\& = \frac{k(k + 1) + 2(k + 1)}{2} \\& = \frac{k^2 + 3k + 2}{2} \\& = \frac{(k + 1)(k + 2)}{2} \\& = \frac{(k + 1)((k + 1) + 2)}{2}\end{split}\]

dan seperti yang dapat dilihat, ruas kiri dari \(P(k + 1)\) telah menjadi sama dengan ruas kanannya, sehingga dapat dikatakan bahwa tahap induksi telah berhasil dibuktikan benar.

Dengan pembuktian kasus dasar dan induksi yang bernilai benar, kita dapat menyimpulkan bahwa \(P(n)\) bernilai benar untuk \(n \geq 1\).

Ø   Pembuktian Tidak Langsung dan Langsung

Bukti (proof) adalah argumen dari suatu premis ke suatu kesimpulan yang dapat meyakinkan orang lain agar dapat menerima kesimpulan baru tersebut. Pembuktian dalam matematika harus didasarkan pada dua hal yang sangat penting. Yang pertama pembuktian itu harus didasarkan pada pernyataan serta definisi yang jelas. Yang kedua, pembuktian tersebut harus didasarkan pada prosedur penarikan kesimpulan yang valid. Dikenal dua prosedur pembuktian, yaitu bukti langsung (direct proof) dan bukti tak langsung (indirect proof).

Contoh Pembuktian Langsung dan Tidak Langsung

Dengan Pembuktian Langsung

Perhatikan Gambar 2. Karena segi-5 ABCDE adalah segi-5 beraturan maka besar ÐAOB = 1/5  360° = 72° dengan mengingat bahwa AB = BC = CD = DE = EA dan OA = OB = OC = OD + OE. Karena ABO sama kaki (OA = OB) maka ÐOAB = ÐOBA = ½  (180 – 72)° = 54°. Jadi, besar setiap sudut dalam segi-5 beraturan adalah ÐBAE = 2  54° = 108°.

Dengan Pembuktian tidak Langsung

Dimisalkan bahwa besar setiap sudut dalam segi-5 beraturan bukan 108°. Perhatikan bahwa pemisalannya adalah dengan mengingkari yang akan dibuktikan.

Perhatikan Gambar 3 di samping kanan ini. Karena segi-5 ABCDE adalah segi-5 beraturan maka ABO dan empat segitiga yang lain adalah segitiga sama kaki. Karena sudah dimisalkan bahwa besar sudut dalam segi-5 beraturan bukan 108° maka ÐOAB = ÐOBA ¹ ½  108°. Akibat selanjutnya, besar ÐAOB ¹ (180 – 108)°.  ÐAOB ¹ 72°, sehingga ÐO ¹ 5  72°. Kesimpulan terakhir bahwa ÐO ¹ 360° merupakan keadaan yang bertentangan dengan teorema bahwa satu putaran penuh besarnya 360°. Suatu keadaan yang kontradiktif (absurd) terjadi. Karena langkah-langkah yang dilakukan adalah valid, maka sampailah kita pada kesimpulan bahwa keadaan yang kontradiktif (absurd) itu terjadi disebabkan oleh pemisalan bahwa besar setiap sudut dalam segi-5 beraturan bukan 108°, sehingga pemisalan tersebut harus diingkari. Jadi kesimpulannya besar setiap sudut dalam segi-5 beraturan adalah108°.

Pengembangan Model

Proses pengembangan model dapat dilakukan dengan beberapa langkah yang telah dibangun oleh para ahli matematika. Jika proses pengembangan model dilakukan mengikuti langkah-langkah yang ada, idealnya kita akan mendapatkan model yang tepat untuk permasalahan yang akan diselesaikan. Adapun langkah-langkah yang harus diambil untuk membangun sebuah model yaitu:

1.      Apakah masalah yang dihadapi merupakan masalah yang memerlukan solusi matematis? Jika masalahnya merupakan masalah numerik (perhitungan angka) atau logis, maka jawabannya sudah pasti “ya”. Jika solusi dari masalah berupa pendapat, maka kemungkinan jawabannya adalah “tidak”.

2.      Fakta-fakta relevan apa saja yang diketahui? Masalah umum yang dihadapi saat akan membangun solusi adalah informasi yang terlalu banyak, yang terkadang mencuri fokus kita dari akar masalah. Pisahkan antara fakta (informasi) yang relevan dari keseluruhan informasi yang didapatkan.

3.      Fakta atau informasi tambahan apa yang kita perlukan untuk menyelesaikan masalah? Di mana atau bagaimana cara agar kita mendapatkan fakta-fakta tersebut?

4.      Adakah langkah atau metode alami untuk menyelesaikan masalahnya? Metode alami artinya metode yang umumnya digunakan oleh manusia. Misalnya, untuk menghitung total dari sekumpulan nilai kita dapat menambahkan seluruh bilangan yang ada di dalam kumpulan nilai tersebut.

5.      Apakah fakta-fakta yang ada dapat direpresentasikan oleh simbol matematis dan dikategorikan menjadi fakta yang “diketahui” dan “tidak diketahui”?

6.      Apakah terdapat model lama yang dapat digunakan atau disesuaikan untuk menyelesaikan masalah kita?

7.      Jika terdapat model yang telah dikembangkan sebelumnya untuk masalah kita, apakah model tersebut dapat diaplikasikan pada komputer?

8.      Bagaimana kita dapat mengaplikasikan model dari solusi kita sehingga model tersebut dapat dibuat menjadi program komputer dengan mudah?

Contoh: Perhitungan Bunga Pinjaman

Kita diminta untuk mengembangkan sebuah program komputer untuk sebuah perusahaan kredit ACME. Program yang akan kita kembangkan merupakan sistem untuk menghitung total jumlah yang harus dibayar oleh peminjam uang per tahunnya. Bunga pinjaman yang diberikan ACME adalah sebesar 15% per tahunnya.

Untuk membangun sistem perhitungan yang diminta, tentunya terlebih dahulu kita harus membangun modal solusi untuk perhitungan bunganya. Mari kita ikuti langkah-langkah untuk membangun model yang telah dijelaskan sebelumnya:

1.      Apakah masalah yang dihadapi merupakan masalah yang memerlukan solusi matematis?

Ya. Perhitungan total bunga bunga jelas akan melibatkan matematika.

2.      Fakta-fakta relevan apa saja yang diketahui?

Bunga pinjaman sebesar 15% per tahun.

3.      Fakta atau informasi tambahan apa yang kita perlukan untuk menyelesaikan masalah?

Beberapa fakta tambahan yang harus ada tetapi tidak disebutkan secara eksplisit pada deskripsi masalah:

1. Jumlah pinjaman awal. Untuk menghitung total pinjaman dengan bunganya jelas kita harus mengetahui jumlah pinjaman awal terlebih dahulu.

2. Lama pinjaman. Tanpa adanya lama pinjaman, kita tidak dapat mengetahui dengan pasti total bunga yang harus ditambahkan.

4.       Adakah langkah atau metode alami untuk menyelesaikan masalahnya?

Ya, lakukan perhitungan bunga tiap tahunnya, dan tambahkan hasil kalkulasi tersebut sampai  tahun pinjaman terakhir.

5.      Apakah fakta-fakta yang ada dapat direpresentasikan oleh simbol matematis?

Dari fakta-fakta yang kita dapatkan pada langkah kedua dan ketiga, kita dapat mendefinisikan simbol matematis seperti berikut:

\[\begin{split}\text{let }b & = \text{bunga} \\ \text{let }p & = \text{jumlah pinjaman} \\ \text{let }t & = \text{waktu pinjaman (per tahun)} \\ \text{let }T & = \text{total pinjaman}\end{split}\]

6.      Apakah terdapat model lama yang dapat digunakan untuk menyelesaikan masalah kita?

Ya, perhitungan bunga majemuk yang dimodelkan dengan rumus: \(T = p(1 + b)^t\).

7.      Apakah model yang ada sebelumnya pada langkah 6 dapat diaplikasikan pada komputer?

Kemungkinan tidak, karena perhitungan bunga majemuk merupakan perhitungan yang tidak banyak diketahui orang (terutama pada bidang pemrograman), dan juga memiliki banyak aturan kompleks yang harus dimengerti terlebih dahulu.

Karena kasus yang sederhana, kita akan lebih mudah mengimplementasikan algoritma kita sendiri, yang cukup melakukan iterasi dan menambahkan total pinjaman setiap tahunnya. Mari kita coba kembangkan model iterasi yang dapat digunakan.

Untuk tahun pertama, peminjam akan berhutang sebanyak:

\[T = p + (15\% * p)\]

selanjutnya, untuk tahun kedua hutangnya akan bertambah menjadi:

\[T' = T + (15\% * T)\]

di mana \(T'\) adalah nilai baru dari \(T\). Kita cukup melakukan perhitungan yang sama terus menerus, sebanyak $t$ kali untuk mendapatkan hasil akhir berupa \(T\) yang menyimpan total hutang yang dipinjam. Jika dikembangkan, maka model matematis akhir yang kita dapatkan adalah:

\[T = T + (\frac{15}{100} * T)\]

yang akan dijalankan sebanyak $t$ kali, dengan nilai $T$ yang bertambah setiap iterasinya. Dengan informasi ini, kita dapat mengimplementasikan pseudocode seperti berikut:

b = 15

T = 0

READ p, t

T = p

for i = 1 to t do

    T = T + (15 / 100 * T)

end for

WRITE T

yang kemudian akan kita implementasikan sebagai fungsi penghitung total pinjaman.

8.      Bagaimana kita dapat mengaplikasikan model dari solusi kita sehingga model tersebut dapat dibuat menjadi program komputer dengan mudah?

Pseudocode yang ada sudah sangat jelas, dan baris per barisnya dapat diimplementasikan secara langsung menggunakan bahasa pemrograman apapun.

Setelah mendapatkan model penyelesaian masalah sampai pada pseudocode-nya, kita kemudian dapat mengimplementasikan solusi yang dikembangkan menggunakan bahasa pemrograman yang diinginkan. Berikut adalah contoh implementasi algoritma tersebut pada python:

b = 15

T = 0

p = input("Masukkan jumlah pinjaman: ")

t = input("Masukkan lama pinjaman: ")

T = int(p)

for i in range(1, int(t)):

    T = T + (15 / 100 * T)

print("Total pinjaman yang harus dibayarkan adalah: " + str(T))