UAS – MATEMATIKA DISKRIT 1 KAMPUS ITBI MILENIAL

Nama       : IDE KRISTIANI ZEGA

Jurusan   : TEKNIK INFORMATIKA S1

Kelas       : PAGI

Soal dan jawaban :

1.      Tentukan apakah graf dibawah ini memiliki sirkuit Hamilton. Jika tidak, berikan alasannya. Jika memiliki, carilah sirkuit Hamilton tersebut

Penyelesaian :

 

Sirkuit Hamilton adalah sirkuit yang melalui tiap simpul di dalam graf tepat satu kali, kecuali simpul asal (sekaligus simpul akhir) yang dilalui dua kali. Graf diatas termasuk graf Hamilton, yaitu graf yang memiliki sirkuit Hamilton {a,b,c,d,e,a}

2.      Tentukan apakah graf dibawah ini isomorfis. Jika ya atau tidak berikan alasannya

Penyelesaian :

 

 

Dua buah graf yang isomorfis adalah graf yang sama, kecuali penamaan simpul dan sisinya saja yang berbeda. Ini benar karna sebuah graf dapat digambarkan dalam banyak cara. Jika G dan G^' isomorfis, maka terdapat beberapa hal yang pasti terpenuhi :

-        Jumlah titik G = jumlah titik G^'

-        Jumlah garis G = jumlah garis G^'

-        Jumlah garis sama dengan derajat tertentu dalam G dan G^' sama

Perhatikan kedua gambar diatas, dari syarat yang ada hanya 2 dari 3 syarat yang terpenuhi. Jumlah titik G adalah 5 = jumlah titik G^' adalah 5, kemudian jumlah garis G adalah 7 = jumlah garis G^' adalah 7. Tetapi pada derajat G ada yang tidak berkesinambungan dengan G^' . Derajat d pada G adalah 3 tetapi pada G^' derajat d' hanya memiliki 2. Dari penjelasan ini, maka disimpulkan bahwa kedua graf diatas tidak isomorfis.

3.      Misalkan A = {2,3,4} dan B = {6,8,10}. Didefinisikan relasi biner R dari A ke B sebagai berikut : untuk semua (x,y) ϵ A × B (x,y) ϵ R jika dan hanya jika x habis membagi y.

a.       Tulis R sebagai pasangan berurut

b.      Buatlah R dalam bentuk graf

Penyelesaian :

a.       R = {(2,6), (2,8), (2,10), (3,6), (4,8)}

b.      

4.      Misalkan W = {1, 2, 3, 4}. Perhatikan relasi-relasi dalam W berikut ini :

R­­­­_{1 ­}= {(1,1), (1,2)}, R₂ = {(1,2), (2,4)}, R₃ = {(1,1), (2,2), (3,3)}. Selidiki apakah masing-masing relasi diatas bersifat Refleksif, Simetris, Transitif.

Penyelesaian :

-        R disebut relasi refleksif jika tiap-tiap anggota W berelasi dengan dirinya sendiri. Diketahui W = {1, 2, 3, 4} dan R₁ = {(1,1), (1,2)} tidak bersifat refleksif karena {(2,2), (3,3), (4,4)} tidak termasuk dalam elemen R. Hal ini juga berlaku pada R₂ dan R₃

-        Relasi R pada himpunan W disebut simetris jika (w, x) ϵ R, maka (x, w) ϵ R untuk w, x ϵ W. diketahui W = {1, 2, 3, 4} dan R₁ = {(1,1), (1,2)} tidak setangkup karena ada (w, x) ϵ R, tetapi (x, w) ∉ R, (1,2) ϵ R → (2,1) ∉ R.Relasi R₂ = {(1,2), (2,4)} tidak setangkup karena ada (w, x) ϵ R, tetapi (x, w) ∉ R, (2,4) ϵ R → (4,2) ∉ R. Sedangkan R₃ = {(1,1), (2,2), (3,3)} merupakan relasi yang simetris sekaligus relasi yang anti simetris. Suatu relasi R pada himpunan W dikatakan anti simetris jika untuk setiap w, x  ϵ W (w,x) ϵ R dan (x, w) ϵ R berlaku hanya jika w = x . Perhatikanlah bahwa istilah simetris dan anti simetris tidaklah berlawanan, karena suatu relasi dapat memiliki kedua sifat itu sekaligus. Namun, relasi tidak dapat memiliki kedua sifat tersebut sekaligus jika ia mengandung beberapa pasangan terurut berbentuk (w,x) yang mana w ≠ x

-        Sebuah relasi disebut transitif jika memiliki sifat, jika a berhubungan dengan b, dan b berhubungan dengan c, maka a berhubungan dengan c secara langsung.

W = {1, 2, 3, 4}

R­­­­_{1 ­}= {(1,1), (1,2)} jelas menghantar

R₂ = {(1,2), (2,4)} tidak menghantar karena (1,2) dan (2,4) ϵ R, tetap (1,4) ∉ R begitu juga dengan R₃ = {(1,1), (2,2), (3,3)}

5.      Hitunglah P(8,5) dan C(12,6)

Penyelesaian :

Permutasi P(n,r) = n!/(n-r)!

P(8,5) = 8!/ (8-5)!

= 8!/3!

= 8·7·6·5·4·3!/3!

=6. 720

Kombinasi C(n,r) = n!/r!(n-r)!

C(12,6) = 12!/6!(12-6)!

= 12·11·10·9·8·7·6!/6!·6!

= 12·11·10·9·8·7/6·5·4·3·2·1

=665.280/720

= 924

6.      Berapa banyak plat nomor kendaran yang bisa dibuat dari 2 huruf dan diikuti dengan 4 angka?

Penyelesaian :

P(26,2) × P(10,4) = 3. 276. 000

7.      Suatu komite yang beranggotakan paling sedikit 5 orang akan dipilih dari 9 calon yang ada. Berapa macam komite yang dapat dibuat?

Penyelesaian :

Komite adalah kelompok yang tidak berurut, artinya setiap anggota didalam kedudukannya sama. Misal 5 orang yang dipilih adalah A, B, C, D, dan E maka urutan penempatan masing-masingnya didalam panitia tidak penting. Maka banyaknya cara memilih anggota panitia yang terdiri dari 5 orang anggota adalah C(9,5) = 126

8.      Suatu kode akses komputer terdiri dari 3 huruf dengan mengizinkan perulangan. Berapa banyak di antara kode-kode tersebut memuat perulangan huruf?

Penyelesaian :

Misalnya ketiga huruf tersebut adalah = a, b, c

Karna terdiri dari tiga, maka banyaknya cara = 3×3×3 = 27 cara

9.      Buktikan deret dibawah ini dengan menggunakan induksi matematika di mana

 n ≥ 1 :

1 + 2 · 2 + 3 · 2² + … + n · 2^(n-1) = 1 + (n-1)2ⁿ

Penyelesaian :

Basis induksi : p(1) benar, karena untuk n = 1 kita peroleh

1 = 1 + (1-1)2¹

     = 1 + (0)2

 1 = 1 (benar)

Langkah induksi : kita juga harus memperlihatkan bahwa p(n-1) juga benar

1 + 2 · 2 + 3 · 2² + … + n · 2^(n-1) = 1 + (n-1)2ⁿ

Misal n = 1, maka

1 + 2 · 2 + 3 · 2² + … + 1 · 2^(1-1) = 1 + (1-1)2¹

                                                       = 1 + (0)2¹

                                                       = 1 + 0

                                                       = 1 maka terbukti benar

10.   Tuliskan pengaruh Algoritma terhadap komputasi atau program yang kita buat.

Algoritma adalah urutan langkah-langkah logis penyelesaian sebuah masalah yang disusun secara logis dan sistematis. Pada dasarnya fungsi utama dari algoritma adalah untuk memecahkan suatu masalah. Lebih jelasnya, adapun ketika kita sedang membuat sebuah program, algoritma punya pengaruh besar untuk membantu dalam membuat sebuah program untuk masalah tertentu. Algoritma juga memudahkan dalam membuat program yang lebih rapid an terstruktur sehingga lebih mudah dipahami dan dikembangkan. Ketika misalnya terjadi kesalahan, algoritma dapat membantu menemukannya karena alur kerja yang jelas

TUGAS MANDIRI 6 – MATEMATIKA DISKRIT 1 KAMPUS ITBI MILENIAL

Nama       : IDE KRISTIANI ZEGA

Jurusan   : TEKNIK INFORMATIKA S1

Kelas       : PAGI

Soal

1.      Jelakan hubungan antara algoritma dan bahasa pemrograman

2.      Apakah perbedaan antara algoritma dan logika?

3.      Jelaskan apa pentingnya mempelajari kompleksitas suatu algoritma tertentu

4.      Jelaskan pengertian flowchart

5.      Soal kombinatorial :

a)     Jelaskan perbedaan antara permutasi dan kombinasi kemudian buat masing-masing 1 contoh dan penyelesaiannya

b)     Berapakah jumlah kemungkinan membentuk 4 angka dari 6 angka berikut: {1,2,3,4,5,6} jika tidak boleh ada pengulangan angka (permutasi)?

 

                 Jawab:

1.      Hubungan antara algoritma dan bahasa pemrograman adalah:

Algoritma merupakan urutan langkah-langkah logis untuk menyelesaikan suatu masalah. Algoritma digunakan dalam bahasa komputer, karena komputer tidak mengerti bahasa manusia komputer dapat mengerti perintah yang diberikan melalui algoritma  yang berupa program dan kegiatan seperti mendesain hingga menulis program dinamakan pemrograman. Algoritma efektif jika dilaksanakan oleh sebuah pemroses (processor), biasanya berupa manusia, komputer, mesin ataupun robot. Supaya komputer mengerti instruksi yang dibacanya, maka instruksi tersebut harus ditulis dalam bahasa yang dipahami komputer. Bahasa komputer yang digunakan untuk menulis program tersebut bahasa pemrograman.

2.      Perbedaan antara algoritma dan logika adalah :

Logika dalam konteks komputer mengarah pada bagaimana pola berpikir yang rasional, tepat dan logis dalam memecahkan suatu masalah. Sedangkan algoritma merupakan urutan langkah-langkah logis untuk menyelesaikan suatu masalah artinya cenderung pada prosedur penyelesaian suatu masalah yang runtut dan logis.

3.      Pentingnya mempelajari kompleksitas suatu algoritma tertentu karena sebuah masalah dapat mempunyai banyak algoritma penyelesaian. Contoh : masalah pengurutan (sort), ada puluhan algoritma pengurutan. Sebuah algoritma tidak saja harus benar, tetapi juga harus efisien. Algoritma yang bagus adalah algoritma yang efisien. Efisiensi suatu algoritma diukur dari berapa jumlah waktu dan ruang (space) memori yang dibutuhkan untuk menjalankannya. Algoritma yang efisien adalah algoritma yang meminimumkan kebutuhan waktu dan ruang.

Kebutuhan waktu dan ruang suatu algoritma bergantung pada ukuran masukan (n), yang menyatakan jumlah data yang diproses. Efisiensi algoritma dapat digunakan untuk menilai algoritma yang terabit. Mengapa memerlukan yang efisien? Kita dapat mengukur waktu yang diperlukan oleh sebuah algoritma dengan menghitung banyaknya operasi/instruksi yang dieksekusi. Jika kita mengetahui besaran waktu (dalam satuan detik) untuk melaksanakan sebuah operasi tertentu, maka kita dapat menhitung berapa waktu sesungguhnya untuk melaksanakn algoritma tersebut. Selain bergantung pada komputer, kebutuhan waktu sebuah program juga ditentukan oleh compiler bahasa yang digunakan. Model abstrak pengukuran waktu/ruang harus independen dari pertimbangan mesin dan compiler. Besaran yang dipakai untuk menerangkan model abstrak pengukuran waktu/ruang ini adalah kompleksitas algoritma

4.      Flowchart adalah suatu bagan dengan simbol-simbol tertentu yang menggambarkan urutan proses secara mendetail dan hubungan antara suatu proses (instruksi) dengan proses lainnya dalam suatu program. Dalam perancangan flowchart sebenarnya tidak ada rumus atau patokan yang bersifat mutlak (pasti). Hal ini didasari oleh flowchart (bagan alir) adalah sebuah gambaran dari hasil pemikiran dalam menganalisa suatu permasalahan dalam komputer. Karena setiap analisa akan menghasilkan hasil yang bervariasi antara satu dan lainnya. Kendati begitu secara garis besar setiap perancangan flowchart selalu terdiri dari tiga bagian, yaitu input, proses dan output.

5.      Soal kombinatorial :

a)     Perbedaan antara permutasi dan kombinasi:

Permutasi adalah banyaknya cara untuk membuat susunan dengan jumlah pada suatu anggota tertentu dari anggota-anggota suatu himpunan. Sedangkan kombinasi adalah banyaknya cara memilih anggota pada jumlah tertentu dari anggota-anggota suatu himpunan. Atau dengan kalimat lain kombinasi yaitu banyaknya cara membuat himpunan bagian dengan jumlah anggota tertentu dari anggota-anggota suatu himpunan.

Rumus permutasi : misal diketahui himpunan memiliki anggota sejumlah n, maka susunan terurut yang terdiri dari r buah anggota dinamakan permutasi r dari n, ditulis sebagai P(n,r) dimana r lebih kecil atau sama dengan n. Rumus permutasi adalah sebagai berikut

Jika r = n, maka P(n,n) = n! (ingat 0!=1

Rumus kombinasi : missal diketahui suatu himpunan mempunyai anggota sejumlah n, maka pemilihan r buah anggota dinamakan kombinasi r dari n, dan ditulis sebagai C(n,r) dimana r lebih kecil atau sama dengan n. Rumus kombinasi adalah sebagai berikut

Contoh soal permutasi :

Di SMA Nusa Bangsa mengadakan pemilihan ketua, sekretaris dan bendahara. Setelah dilakukan seleksi, ada 7 orang siswa yang mendaftarkan diri. Banyak cara ketua, sekretaris dan bendahara adalah?

 

Penyelesaian:

Banyak kandidat yang mendaftar = 7 orang, maka n = 7

Karena akan dipilih 3 orang yaitu, ketua, sekretaris dan bendahara, maka banyak pilihannya adalah permutasi 3 dari 7

 

Contoh soal kombinasi :

Sebuah kotak berisi 8 kelereng biru, 6 kelereng putih dan 2 kelereng hitam. Banyak cara pengambilan 4 kelereng putih tersebut adalah?

 

Penyelesaian :

Karena akan dipilih 4 kelereng dari 6 kelereng putih, maka gunakan kombinasi 4 dari 6

b)     Berapakah jumlah kemungkinan membentuk 4 angka dari 6 angka berikut: {1,2,3,4,5,6} jika tidak boleh ada pengulangan angka (permutasi)?

 

Penyelesaian :

Dengan kaidah perkalian : (6)(5)(4)(3) = 360

Dengan rumus permutasi P(6, 4) = 6!/(6-4)! = 360

TUGAS MANDIRI 5 – MATEMATIKA DISKRIT 1 KAMPUS ITBI MILENIAL

Nama       : IDE KRISTIANI ZEGA

Jurusan   : TEKNIK INFORMATIKA S1

Kelas       : PAGI

Soal:

1.      Apakah yang dimaksud dengan metode pembuktian secara induksi matematika?

Jawab:

Induksi matematika adalah sebuah metode deduktif yang digunakan sebagai pembuktian pernyataan benar atau salah. Yang dimaksud dengan metode pembuktian secara induksi matematika adalah metode pembuktian untuk pernyataan perihal bilangan bulat atau dapat juga dipahami sebagai pembuktian dengan efek domino. Maksudnya, cara pembuktian kebenaran pada induksi matematika mengenai target utama secara tidak langsung (melalui perantara)

 

2.      Jelaskan langkah-langkah penyelesaian masalah menggunakan induksi matematika

Jawab:

Langkah-langkah penyelesaian masalah menggunakan induksi matematika

1)     Buktikan benar untuk n = 1

2)     Asumsikan benar untuk n = k,

3)     kemudian tunjukkan bahwa pernyataan benar untuk n = k+1

Penjelasan langkah-langkah pembuktian menggunakan metode induksi matematika dapat dijelaskan seperti berikut:

Pertama, pembuktian ditunjukkan benar untuk n yang mewakili angka 1. Ini syarat dasar yang harus dipenuhi untuk membuktikan pernyataan matematika menggunakan induksi matematika. Jika syarat pertama tidak dapat dipenuhi, maka tidak usah dilanjutkan ke langkah berikutnya karena sudah pasti pernyataan tersebut bernilai salah (rumus tidak terbukti benar). Jika terbukti benar untuk syarat pertama, selanjutnya adalah membuktikan benar untuk langkah selanjutnya, asumsikan benar (anggapan benar) untuk n = k. selanjutnya gunakan asumsi tersebut untuk membuktikan pernyataan benar untuk n = k + 1. Setelah terbukti benar untuk n = k + 1, kita dapat memahami bahwa jika nilai k diganti dengan angka 0 maka pernyataan akan sesuai dengan pernyataan pertama (terbukti benar untuk  n = 1). Selanjutnya, untuk k = 1 (nilai n = 2) juga akan benar karena sudah terbukti bahwa n = k + 1, maka n = 1+1 = 2 benar. Begitu seterusnya untuk nilai n lainnya, sehingga terbukti benar untuk semua n bilangan asli

3.      Buatlah 3 contoh pembuktian dengan induksi matematika

Jawab:

Contoh 1

Buktikan dengan induksi matematika bahwa : n² + 5n habis dibagi 2, untuk setiap n bilangan asli

Jawab:

Langkah 1

Untuk  n = 1

n² + 5n = 1² + 5.1 = 6 habis dibagi 2

Rumus atau teorema benar untuk n = 1

 

Langkah 2

Anggap bahwa rumus atau teorema benar untuk n = k, sehingga : k² + 5k habis dibagi 2

 

Langkah 3

Akan dibuktikan bahwa rumus atau teorema benar untuk n = k + 1

(k + 1)² + 5(k  + 1)) = k² + 2k⁵ + 2k ­_­+ 1 + 5k + 5

= (k² + 5k) + (2k⁵ + 2k ­_­+5)

= (k² + 5k) + 2(k⁵ + k + 1)

Karena dari langkah 2 kita sudah anggap bahwa k² + 5k habis dibagi 2 dan

 2(k⁵ + k + 1) pasti habis dibagi 2,

Maka (k² + 5k) + 2(k⁵ + k + 1) pasti habis dibagi 2.

[benar]

 

Kesimpulan:

n² + 5n habis dibagi 2. [terbukti]

 

Contoh 2

Buktikan dengan induksi matematika bahwa 10ⁿ  + 2 habis dibagi 6

Jawab:

Langkah 1

Untuk n = 1

10¹ + 2 = 12 habis dibagi 6. Rumus atau teorema benar untuk n = 1

 

Langkah 2

Anggap bahwa rumus atau teorema benar untuk n = k, sehingga :

10ᵏ + 2 habis dibagi 6

 

Langkah 3

Akan dibuktikan bahwa rumus atau teorema benar untuk n = k + 1.

10ᵏ⁺¹ + 2 = 10.10ᵏ + 2

= 10(10ᵏ + 2) – 12

Karena 10ᵏ + 2 habis dibagi 6, maka 10(10ᵏ + 2) pasti habis dibagi 6.

12 habis dibagi 6, berarti 10(10ᵏ + 2) – 12 habis dibagi 6.

[benar]

 

Kesimpulan:

10ⁿ + 2 habis dibagi 6. [terbukti]

 

Contoh 3

Buktikan dengan induksi matematika bahwa 4ⁿ < 8ⁿ , untuk setiap n bilangan asli

Jawab:

Langkah 1

Untuk n = 1

4¹ < 8¹

4 < 8 

Teorema benar untuk n = 1

 

Langkah 2

Anggap bahwa teorema benar untuk n = k, sehingga : 4ᵏ < 8ᵏ

 

Langkah 3

Akan dibuktikan bahwa teorema benar untuk n = k + 1

4ᵏ⁺¹ < 8ᵏ⁺¹

4ᵏ⁺¹ = 4.4ᵏ

4ᵏ⁺¹ < 4.8ᵏ karena 4ᵏ < 8ᵏ

4ᵏ⁺¹ < 8.8ᵏ karena 4 < 8

4ᵏ⁺¹ < 8ᵏ⁺¹ [benar]

 

Kesimpulan:

4ⁿ < 8ⁿ [terbukti]

 

TUGAS MANDIRI 4 – MATEMATIKA DISKRIT 1 KAMPUS ITBI MILENIAL

Nama       : IDE KRISTIANI ZEGA

Jurusan   : TEKNIK INFORMATIKA S1

Kelas       : PAGI

1.      3 contoh soal dan penyelesaian teori Graf:

1)     Berilah contoh graf berikut dengan paling banyak 6 titik

a.       Graf Hamilton yang bukan euler

Penyelesaian:

Graf Hamilton adalah graf yang memuat sikel Hamilton. Sikel Hamilton sendiri adalah jalan tertutup yang semua sisi dan titik interalnya berbeda serta melalui seluruh titik pada graf tersebut, sedangkan graf euler adalah graf yang semua sisinya berbeda dan setiap sisi dilalui tepat satu kali.

 

Graf G diatas mengandung sikel Hamilton dengan barisan titik a b d c a. Jelas bahwa jalan tersebut tertutup (kembali pada titik semula), melalui semua titik pada graf, dan titik internalnya berbeda (hanya di lalui 1 kali). Oleh karena itu, graf diatas disebut graf Hamilton dan bukan graf Euler karena ada sisi yang tidak dilaluinya, yaitu sisi bc

2)     Tuliskan matriks keterhubungan langsung dari graf berikut

 

 

 

Penyelesaian:

Matriks keterhubungan dari graf G diatas adalah sebagai berikut:

 

3)     Benar atau salahkah pernyataan berikut:

a.       Jika graf G dan H isomorfik, maka keduanya mempunyai banyak titik yang sama dan banyak titik yang sama pula

Penyelesaian:

Benar. Jika tidak, maka fungsi yang terbentuk bukan bijektif (korespondensi satu-satu) padahal itu adalah syarat keisomorfikan graf

2.      Buatlah representasi relasi berikut dalam diagram:

1)     R={(A, B)} = {(1, 2), (1, 3), (-1, 5), (0, 2)

2)     R={(M, N)} = {(10, 2), (11, 3), (12, 2), (13, 3), (13, 2), (14, 0)}

3)     R={(X, Y)} = {(1, 1,), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)}

Penyelesaian: