soal logika dan algoritma

Rabu, 20 November 2019

PENGERTIAN METODE DIVIDE AND CONQUER

METODE

DIVIDE AND CONQUER

1. Pengertian

Algoritma Divide And Conquer merupakan algoritma yang sangat populer di dunia ilmu komputer. Divide and conquer merupakan algoritma yang berprinsip memecah-mecah permasalahan yang terlalu besar menjadi beberapa bagian kecil sehingga lebih mudah untuk diselesaikan.

Langkah-langkah umum algoritma Divide and Conquer :

· Divide : Membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil ( idealnya berukuran hampir sama).

· Conquer : Memecahkan ( menyelesaikan ) masing-masing upa-masalah (secara reurtfi ).

· Combine : Menghubungkan solusi masing-masing upa-masalah sehingga membentuk solusi masalah semula.

2. Penerapan Algoritma

Pemecahan masalah Convex Hull dengan algoritma divide and conquer

Pada penyelasaian masalah pencarian Convex Hull dengan menggunakan algoritma divide and conquer, sebagai generalisasi dari algoritma pengurutan mergesort.

Adapun permasalahan convex hull adalah sebuah permasalahan yang memiliki aplikasi terapan yang cukup banyak, seperti pada permasalahan grafik komputer, otomatis desain, pengenalan pola (pattern recognition), dan penelitian operasi. Divide And Conquer adalah metode pemecahan masalah yang bekerja dengan membagi masalah menjadi beberapa upa-masalah yang lebih kecil, kemudian menyelesaikan masing-masing upa-masalah tersebut secara independent.

3. Penyelesaian Dengan Algoritma Divide And Conquer

a. Asumsi : n = 2k dan titik-titik diurut berdasarkan absis (x).

b. Algoritma closest pair :

ü Solve : jika n = 2, maka jarak kedua titik dihitung langsung dengan rumus Eculidean.

ü Divide : bagi titik-titik itu ke dalam dua bagian, Pleft dan Pright, setiap bagian mempunyai jumlah titik yang sam.

ü Conquer : secara rekurtif, terapkan algoritma D-and-C pada masing-masing bagian.

c. Pasang titik yang jaraknya terdekat ada tiga kemungkinan letaknya :

ü Pasangan titik terdekat terdapat di bagian Pleft.

ü Pasangan titik terdekat terdapat di bagian Pright;

ü Pasangan titik terdekat dipisahkan oleh garis batas L, yaitu satu titik di Pleft dan satu titik di Pright.

Jika kasusnya adalah ( C ), maka lakukan tahap COMBINE untuk mendapatkan jarak dua titik terdekat sebagai solusi persoalan semula.

Latihan Soal dan jawaban Bab METODE DIVIDE AND CONQUER

Latihan Soal

Terdapat deret angka : 99, 34, 11, 50, 23, 89, 65, 2, 6, 37, 74, 44

Urutkanlah deret angka tersebut dengan menggunakan Teknik sort yang sudah dijelaskan.

Jawab :

1.SELECTION SORT

Angka : 99, 34, 11, 50, 23, 89, 65, 2, 6, 37, 74, 44.

Langkah 1 = 99, 34, 11, 50, 23, 89, 65, 2, 6, 37, 74, 44.

Langkah 2 = 99, 34, 11, 50, 23, 89, 65, 2, 6, 37, 74, 44.

Langkah 3 = 2, 34, 11, 50, 23, 89, 65, 99, 6, 37, 74, 44.

Langkah 4 = 2, 6, 11, 50, 23, 89, 65, 99, 34, 37, 74, 44.

Langkah 5 = 2, 6, 11, 50, 23, 89, 65, 99, 34, 37, 74, 44.

Langkah 6 = 2, 6, 11, 23, 50, 89, 65, 99, 34, 37, 74, 44.

Langkah 7 = 2, 6, 11, 23, 34, 89, 65, 99, 50, 37, 74, 44.

Langkah 8 = 2, 6, 11, 23, 34, 37, 65, 99, 50, 89, 74, 44.

Langkah 9 = 2, 6, 11, 23, 34, 37, 44, 99, 50, 89, 74, 65.

Langkah 10 = 2, 6, 11, 23, 34, 37, 44, 50, 99, 89, 74, 65.

Langkah 11 = 2, 6, 11, 23, 34, 37, 44, 50, 65, 89, 74, 99.

Langkah 12 = 2, 6, 11, 23, 34, 37, 44, 50, 65, 74, 89, 99.

2. BUBBLE SORT

Angka : 99, 34, 11, 50, 23, 89, 65, 2, 6, 37, 74, 44.

Langkah 1 = 99, 34, 11, 50, 23, 89, 65, 2, 6, 37, 74, 44.

Langkah 2 = 99, 34, 11, 50, 23, 89, 2, 65, 6, 37, 74, 44.

Langkah 3 = 2, 99, 34, 11, 50, 23, 89, 65, 6, 37, 74, 44.

Langkah 4 = 2, 6, 99, 34, 11, 50, 23, 89, 65, 37, 74, 44.

Langkah 5 = 2, 6, 11, 99, 34, 50, 23, 89, 65, 37, 74, 44.

Langkah 6 = 2, 6, 11, 23, 99, 34, 50, 89, 65, 37, 74, 44.

Langkah 7 = 2, 6, 11, 23, 34, 99, 50, 89, 65, 37, 74, 44.

Langkah 8 = 2, 6, 11, 23, 34, 37, 99, 50, 89, 65,74, 44.

Langkah 9 = 2, 6, 11, 23, 34, 37, 44, 99, 50, 89, 65,74.

Langkah 10 = 2, 6, 11, 23, 34, 37, 44, 50, 99, 89, 65,74.

Langkah 11 = 2, 6, 11, 23, 34, 37, 44, 50, 65, 99, 89, 74.

Langkah 12 = 2, 6, 11, 23, 34, 37, 44, 50, 65, 74, 99, 89.

Langkah 13 = 2, 6, 11, 23, 34, 37, 44, 50, 65, 74, 89, 99.

3. QUICK SORT

4. INSERTION SORT

Angka : 99, 34, 11, 50, 23, 89, 65, 2, 6, 37, 74, 44

Langkah 1 = 99, 34, 11, 50, 23, 89, 65, 2, 6, 37, 74, 44

Langkah 2 = 34, 99, 11, 50, 23, 89, 2, 65, 6, 37, 44, 74

Langkah 3 = 34, 11, 99, 23, 50, 2, 89, 65 ,6, 37, 44, 74

Langkah 4 = 11, 34, 23, 99, 2, 50, 6, 89, 37, 65, 44, 74,

Langkah 5 = 11, 23, 34,2, 99, 6, 50, 37, 89, 44, 65, 74

Langkah 6 = 11, 23, 2, 34, 6, 99, 37, 50, 44, 89, 65, 74

Langkah 7 = 11, 22, 36, 34, 37, 99, 44, 50, 65, 89, 74

Langkah 8 = 2, 11, 6, 23, 34, 37, 44, 99, 50, 65, 74, 89

Langkah 9 = 2, 6, 11, 23, 34, 37, 44, 50, 99, 65, 74, 89

Langkah 10 = 2, 6, 11, 23, 34, 37, 44, 50, 65, 99, 74, 89

Langkah 11 =2, 6, 11, 23, 34, 37, 44, 50, 65, 74, 99, 89

Langkah 12 = 2, 6, 11, 23, 34, 37, 44, 50, 65, 74, 89, 99

5. MERGE SORT

Angka : 99, 34, 11, 50, 23, 89, 65, 2, 6, 37, 74, 44

Langkah 1 = 99, 34, 11, 50, 23, 89, 65, 2, 6, 37, 74, 44

Langkah 2 = 34, 99, 11, 50, 23, 89, 65, 26, 37, 74, 44

Langkah 3 = 11, 34, 50, 99, 22, 37, 58, 99, 37, 44, 74

Langkah 4 = 2, 11, 23, 34, 50, 99, 6, 37, 44, 65, 74, 89

Langkah 5 = 2, 6, 11, 23, 34, 37, 50, 99, 44, 65, 74, 89

Langkah 6 = 2, 6, 11, 23, 34, 37, 44, 50, 65, 99, 74, 89

Langkah 7 = 2, 6, 11, 23, 34, 37, 44, 50, 65, 74, 89, 99

Selasa, 19 November 2019

Soal dan Kunci jawaban Array atau Larik

Silahkan jawab pertanyaan dibawah ini!!

1.Type data dibawah ini, yang tidak termasuk dalam tipe data sederhana tunggal, adalah:

a. Boolean b. Integer c. String d. float e. Char

2. ==, <=, >= ,!=, termasuk dalam operator …

a. Aritmatika b. Relasi c. Unary d. Bitwise e. Binary

3.Type data yang menghasilkan bentuk keluaran nilai Truedan False(Benar dan Salah) , adalah :

a. Boolean b. Integer c. String d. float e. Char

4. void main()

{

....(a).... x,y,z;

clrscr();

cout <<“\n input nilai X=“; cin >> x;

cout <<“\n input nilai Y=“; cin >> y; z = x + y;

cout <<“\n hasil penjumlahan =“ << z;

getch();

}

Tipe data yang tepat untuk (a) adalah ….

a. Boolean b. Integer c. String d. Array e. Char

5. void main()

{

int r = 10; int s;

clrscr();

s = 10 + ++r;

cout <<“r = “<< r << ‘\n’;

cout <<“s = “<< s << ‘\n’;

getch();

}

Hasil eksekusi dari program diatas adalah ….

a. r = 11, s = 21 c. r = 11, s = 20

b. r = 10, s = 21 d. r = 10, s = 20 e. r = 12, s = 21

6. Setiap elemen dari sebuah Array haruslah mempunyai type data yang sama, termasuk dalam karakteristik array yaitu :

a. Statis b. Heterogen c. Dinamis d. Homogen e. Terurut

7. Array yang sering digunakan dalam menterjemahkan matriks pada pemrograman, adalah array berdimensi :

a. Satu b. Satu dan Dua c. Dua d. Satu dan Tiga e. Tiga

8. Contoh aplikasi array dimensi dua adalah…..

a. Input data suhu

b. Input nilai mahasiswa perkelas dan matakuliah

c. Input nama hari

d. Input nilai ipk mahasiswa

e. Input nama bulan

9. Terdapat Array : A [5][4] maka jumlah elemen Array tersebut adalah ……

a. 25 b. 15 c. 35 d. 20 e. 9

10. Array yang sangat banyak elemen nol-nya, dikenal sebagai :

a. Upper tringular Array c. Lower tringular Array

b. One Dimensional Array d. Multi Dimensional Array e. Sparse Array

11.Sekumpulan data yang bertipe sama dan antara data satu dengan data yang lain dibedakan dengan indeksnya merupakan pengertian dari …

a. Integer. b.Array. c.Variabel. d.Char. e. Booelan.

12. Jumlah titik pada indeks array harus berjumlah …

a.Satu titik. b.Dua titik. c.Tiga titik. d.Empat titik. e.Lima titik.

13. SUM adalah …

a.Nilai rata-rata dari seluruh indeks array

b.Banyaknya indeks yang ada di dalam array.

c.Hasil dari penjumlahan seluruh data dalam array.

d.Indeks akhir dari array.

e.Nama variabel dari array.

14.Yang bukan merupakan tipe data composite adalah …

a.Image b.Date time c.Character d.Enumerasi e.Record.

15. Identifier adalah …

a.Tipe data c.Nama

b.Variabel d.Nilai e.Konstanta.

16.Nama lain dari flowchart adalah …

a.Algoritma c.Bagan alir

b.Alur d.Tree e.Diagram.

17. Di bawah ini yang bukan termasuk teknik pengurutan data adalah….

a.Bubble sort c.Selection sort

b.Tree sort d.Merge sort e.Head sort.

18. Array yang sering digunakan dalam menterjemahkan matriks pada pemrograman, adalah array berdimensi…

a.Satu. c.Dua.

b.Satu dan Dua d.Satu dan Tiga. e.Tiga.

19. Jika tail=null, maka kondisi Linked List adalah…

a.Terisi. c.Kosong

b.Penuh. d.Tidak dapat ditambah. e.Baru.

20. Perintah yang tepat untuk menyatakan Linked list berada dalam kondisi kosong, adalah…

a.Head=tail. c.Bantu=null

b.Head=tail=null. d.Bantu=head. e.Bantu

Array atau Larik

Array/Larik

ARRAY adalah adalah Tipe terstruktur yang terdiri dari sejumlah komponen-komponen yang mempunyai tipe yang sama. Suatu Array mempunyai jumlah komponen yang banyaknya tetap.

1) Array Satu Dimensi

Bentuk Umum pendeklarasian array :

Keterangan :

· Type Data : Untuk menyatakan type data yang digunakan.

· Ukuran : Untuk menyatakan jumlah maksimum elemen array.

Contoh Pendeklarasian Array

float Nil_Akhir[5];

Suatu array dapat digambarkan sebagai kotak panjang yang berisi kotakkotak kecil didalam kotak panjang tersebut.

Subscript atau Index array pada C++, selalu dimulai dari Nol ( 0 )

Suatu array, dapat diakses dengan menggunakan subscript atau indexnya: Bentuk umum pengaksesan dengan bentuk :

Contoh : Nilai_Akhir[4];

Nilai_Akhir[6];

Nilai_Akhir[2];

Inisialisasi adalah memberikan nilai awal terhadap suatu variabel. Bentuk pendefinisian suatu array dapat dilihat dari contoh berikut :

Tipe_data nama_array[jml_elemen] = { nilai array };

1) Array Dua Dimensi

Array dimensi dua tersusun dalam bentuk baris dan kolom, dimana indeks pertama menunjukan baris dan indeks kedua menunjukan kolom. Array dimensi dua dapat digunakan seperti pendatan penjualan, pendataan nilai dan lain sebagainya.

Bentuk Umum pendeklarasian array :

Keterangan :

· Type Data : Untuk menyatakan type data yang digunakan.

· Index-1 : Untuk menyatakan jumlah baris

· Index-2 : Untuk menyatakan jumlah kolom

Suatu array, dapat diakses dengan menggunakan subscript atau indexnya Bentuk umum pengaksesan dengan bentuk :

Contoh: data_jual[2][2];

data_jual[1][2];

Inisialisasi adalah memberikan nilai awal terhadap suatu variabel. Bentuk pendefinisian suatu array dapat dilihat dari contoh berikut :

Tipe_data nama_array[jml_elemen] = { nilai array };

Sistem Rekursif

Struktur Rekurtif

A. Rekurtif

Salah satu konsep paling dasar dalam ilmu komputer dan pemograman adalah pengunaan fungsi sebagai abstraksi untuk kode-kode yang digunakan berulang kali.

Kedekatan ilmu komputer dengan matematika juga menyebabkan konsep-konsep fungsi pada matematika seringkali dijumpai. Salah satu konsep fungsi pada matematika yang ditemui pada ilmu komputer adalah fungsi yang memanggil dirinya sendiri.

B. Fungsi rekurtif memiliki dua ciri khas :

§ Fungsi rekurtif selalu memiliki kondisi yang menyatakan kapan fungsi tersebut berhenti. Kondisi ini harus dapat dibuktikan akan tercapai, karena jika tidak tercapai maka kita tidak dapat membuktikan bahwa fungsi akan berhenti, yang berarti algoritma kita tidak benar.

§ Fungsi rekurtif selalu memanggil dirinya sendiri sambil mengurangi atau memecahkan data masukan setiap panggilanya. Hal ini penting diingat, karena tujuan utama dari rekurtif ialah memecahkan masalah dengan mengurangi masalah tersebut menjadi masalah-masalah kecil.

C. Fungsi rekurtif dan iterasi

Fungsi rekurtif digunakan untuk menyimpan posisi pengujian dan ditemukannya elemen yang dicari, jika menggunakan iterasi variabel pos tidak dibutuhkan lagi karena posisi ini akan didapatkan secara otomatis ketika sedang menelusuri list.

Dengan melihat jumlah argument dan pengecekan yang harus dilakukan, dapat dilihat bahwa implementasi linier search menjadi lebih sederhana dan mudah dengan menggunakan metode iterasi.

D. Tail Call

Tail call merupakan pemanggilan fungsi sebagai perintah terakhir di dalam fungsi lain sederhananya, ketika kita memanggil sebuah fungsi pada bagian akhir dari fungsi lain, pemanggilan fungsi lain sebagai kode terakhir yang dieksekusi oleh fungsi dapat dikatakan sebagai tail call.