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