AP2C - Metode Greedy Dan Divide Conquer

1. Greedy

Diketahui 3 buah benda dan sebuah knapsack dengan kapasitas maksimum 20. Berat dan profit dari masing-masing benda tersebut adalah (18, 15, 10) dan (25, 24, 15). Tentukanlah Z agar diperoleh total profit yang maksimal ! Jawab :Pertama, kita periksa apakah rasio pi/wi -nya tidak menaik.p0/w0 = 25/18p1/w1 = 24/15p2/w2 = 15/10Terlihat bahwa syarat rasio pi/wi -nya tidak menaik belum terpenuhi. Jadi susunan (urutan) -nya untuk sementara kita ubah, agar syarat rasio pi/wi -nya tidak menaik terpenuhi dan kita dapat menyelesaikan masalah tersebut dengan procedure GREEDY_KNAPSACK.Untuk itu, kita ubah sementara urutan benda-bendanya (setelah diperoleh jawaban sementara, kita kembalikan urutan ke susunan semula). Perubahan yang kita lakukan adalah sebagai berikut :urutan ke-(yang lama) urutan ke-(yang baru)0 21 02 1sehingga syaratnya terpenuhi ;24/15 * 15/10 * 25/18 * rasio pi/wi -nya tidak menaikSekarang kita sudah dapat menggunakan procedure GREEDY_KNAPSACK untuk menyelesaikan masalah tersebut. Adapun hasil trace-nya adalah sebagai berikut :

Z * 0cu * 20i = 0 karena W(0) * cu yaitu : 15 * 20 berarti : Z(0) * 1cu * 20 - 15 = 5i = 1 karena W(2) * cu yaitu : 10 * 5 berarti : keluar dari loop (exit)Karena 1 * 2 maka Z(1) * cu/W(1) = 5/10 = 0,5Jadi diperoleh : Z(0) = 1 ; Z(1) = 0,5 ; Z(2) = 0Sekarang urutannya kita kembalikan seperti semula, yakni : urutan ke-(yang saat ini) urutan ke-(yang semula) Z(i)2 0 00 1 11 2 0,5Jadi optimisasi masalah knapsack diperoleh bila Z = { 0; 1; 0,5 }Sehingga Q = 0 x 25 + 1 x 24 + 0,5 x 15 = 0 + 24 + 7,5 = 31,5 

Algoritma Divide dan Conquer

Pemrogram bertanggung jawab atas implementasi solusi. Pembuatan program akan menjadi lebih sederhana jika masalah dapat dipecah menjadi sub masalah - sub masalah yang dapat dikelola.
Penyelesaian masalah dengan komputer berhadapan dengan 4 hal, yaitu :
1. Pemahaman keterhubungan elemen-elemen data yang relevan terhadap solusi secara menyeluruh.
2. Pengambilan keputusan mengenai operasi-operasi yang dilakukan terhadap elemen-elemen data.
3. Perancangan representasi elemen-elemen data di memori sehingga memenuhi kriteria berikut:
a. Memenuhi keterhubungan logik antara elemen-elemen data.
b. Operasi-operasi terhadap elemen-elemen data dapat dilakukan secara mudah dan efisien.
4. Pengambilan keputusan mengenai mengenai bahasa pemrograman terbaik untuk menerjemahkan solusi persoalan menjadi program.


STRATEGI DIVIDE DAN CONQUER

Metode
Strategi Divide dan Conquer memecah masalah menjadi submasalah-submasalah independen yang lebih kecil sehingga solusi submasalah-submasalah dapat diperoleh secara mudah, solusi submasalah-submasalah digabung menjadi solusi seluruh masalah.
Skema umum algoritma divide dan conquer

Procedure DNC ( i,j : integer )
Var K : integer ;
If SMALL (i,j) then SOLVE (i,j)
Else begin
K : = DIVIDE (i,j)
COMBINE (DNC(i,k),DNC(k+1,j))
End if
Keterangan :
1. SMALL adalah fungsi yang mengirim BOOLEAN, menentukan apakah ukuran telah cukup kecil sehingga solusi dapat diperoleh. Ukuran dinyatakan sebagai telah berukuran kecil bergantung masalah.
2. DIVIDE adalah fungsi membagi menjadi 2 bagian pada posisi K. Biasanya bagian berukuran sama.
3. COMBINE adalah fungsi menggabungkan solusi X dan Y submasalah. Solusi diperoleh dengan memanggil prosedur rekursif DNC.
Jika ukuran kedua submasalah sama, waktu komputasi DNC dideskripsikan hubungan rekuren berikut :
T(n) = g (n), n kecil
2 T (n/2) + f (n), selainnya
dimana :
• T(n) adalah waktu untuk DNC dengan n masukan,
• g(n) adalah waktu komputasi jawaban secara langsung untuk masukan kecil dan
• f(n) adalah waktu COMBINE.

Untuk algoritma divide dan conquer yang menghasilkan submasalah-submasalah dengan tipe masalah yang sama dengan masalah awal, sangat alami untuk mendeskripsikan algoritma secara rekursi. Kemudian untuk meningkatkan efisiensi dilakukan penerjemahan menjadi bentuk iterasi.
Pemakaian teknik Divide dan Conquer banyak digunakan dalam menyelesaikan berbagai macam persoalan, antara lain :
1. Searching
2. Sorting

Binary Search (Pencarian Biner) dapat dilakukan jika data sudah dalam keadaan urut. Dengan kata lain, apabila data belum dalam keadaan urut, pencarian biner tidak dapat dilakukan. Dalam kehidupan sehari-hari, sebenarnya kita juga sering menggunakan pencarian biner. Misalnya saat ingin mencari suatu kata dalam kamus.
Prinsip dari pencarian biner dapat dijelaskan sebagai berikut :
1. Mula-mula diambil posisi awal = 1 dan posisi akhir = N
2. Cari posisi data tengah dengan rumus (posisi awal + posisi akhir) / 2
3. Data yang dicari dibandingkan dengan data tengah.
4. Jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama dengan posisi tengah – 1.
5. Jika lebih besar, proses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah + 1.
6. Demikian seterusnya sampai data tengah sama dengan yang dicari.

Untuk lebih jelasnya, perhatikan contoh berikut. Misalkan kita ingin mencari 17 pada sekumpulan data berikut :


3
9
11
12
15
17
23
31
35


awal tengah akhir
1. Mula–mula dicari data tengah, dengan rumus (1+ 9) / 2 = 5.
2. Berarti data tengah adalah data ke-5, yaitu 15.
3. Data yang dicari, yaitu 17, dibandingkan dengan data tengah ini.
4. Karena 17 > 15, berarti proses dilanjutkan tetapi kali ini posisi awal dianggap sama dengan posisi tengah + 1 atau 6.


3
9
11
12
15
17
23
31
35


awal tengah akhir

1. Data tengah yang baru didapat dengan rumus (6 + 9) / 2 = 7. Berarti data tengah yang baru adalah data ke-7, yaitu 23.
2. Data yang dicari, yaitu 17 dibandingkan dengan data tengah ini.
3. Karena 17 < 23, berarti proses dilanjutkan tetapi kali ini posisi akhir dianggap sama dengan posisi tengah – 1 atau 6.


3
9
11
12
15
17
23
31
35


awal = akhir
1. Data tengah yang baru didapat dengan rumus (6 + 6) / 2 = 6. Berarti data tengah yang baru adalah data ke-6, yaitu 17.
2. Data yang dicari dibandingkan dengan data tengah ini dan ternyata sama. Jadi data ditemukan pada indeks ke-6.
3. Bagaimana jika data yang dicari tidak ada, misalnya 16?
4. Pencarian biner ini akan berakhir jika data ditemukan atau posisi awal lebih besar dari posisi akhir.
5. Jika posisi awal sudah lebih besar daripada posisi akhir berarti data tidak ditemukan.
Untuk lebih jelasnya perhatikan proses pencarian 16 pada data di atas. Prosesnya hampir sama dengan pencarian 17. Tetapi setelah posisi awal = posisi akhir = 6, proses masih dilanjutkan lagi dengan posisi awal = 6 dan posisi akhir = 5


3
9
11
12
15

17

23
31
35


akhir awal
Disini dapat dilihat bahwa posisi awal lebih besar daripada posisi akhir, yang artinya data tidak ditemukan.
Secara umum, algoritma pencarian biner dapat dituliskan sebagai berikut :
1. l ← 1.
2. r ← N.
3. ketemu ← false.
4. selama ( l < = r ) dan (not ketemu) kerjakan baris 5 sampai dengan 8.
5. m ← ( l + r ) / 2
6. Jika ( Data [m] = x ) maka ketemu ← true.
7. Jika ( x < Data [m] ) maka r ← m – 1.
8. Jika ( x > Data [m] ) maka l ← m + 1.
9. If (ketemu) maka m adalah indeks dari data yang dicari, jika tidak data tidak ditemukan.

Berikut ini adalah contoh fungsi untuk mencari data menggunakan pencarian biner.
Function BinarySearch (x: word) : integer;
var
l, r, m : word;
ketemu : boolean;
begin
l : = 1;
r : = N;
ketemu : = false;
while (1 <= r ) and ( not ketemu ) do
begin
m : = (1 + r ) div 2;
if (Data [m] = x ) then
Ketemu := true
else if (x < Data [m] ) then
r : = m – 1
else
l : = m + 1;
end;

if ( ketemu ) then
BinarySearch : = m
else
BinarySearch : = -1;
end;

Fungsi di atas akan mengembalikan indeks dari data yang dicari. Apabila data tidak ditemukan, maka yang yang dikembalikan adalah –1.
Jumlah pembandingan minimum pada pencarian biner adalah 1 kali, yaitu bila data yang dicari tepat berada di tengah-tengah. Jumlah pembandingan maksimum yang dilakukan dengan pencarian biner dapat dicari dengan rumus logaritma, yaitu : C = ²log (N)

Metode Quick atau yang sering disebut juga metode partisi diperkenalkan pertama kali oleh C. A. R. Hoare pada tahun 1962. Pada metode quick, jarak dari kedua elemen yang ditukarkan dibuat cukup besar dengan tujuan untuk mempertinggi efektivitasnya. Hal ini mengingat metode gelembung yang menggunakan jarak cukup dekat ternyata kurang efektif.
Proses pengurutan dengan metode quick dapat dijelaskan sebagai berikut : mula-mula dipilih data tertentu yang dinamakan pivot, misalnya x. Pivot ini harus diletakkan pada posisi ke-j sedemikian hingga data antara 1 sampai dengan (j – 1) lebih kecil daripada x; sedangkan data pada posisi ke-(j+1) sampai dengan N lebih besar daripada x. Cara pengaturannya adalah menukarkan data di antara posisi 1 sampai dengan (j – 1) yang lebih besar daripada x dengan data di antara posisi (j + 1) sampai dengan N yang lebih kecil daripada x.
Algoritma penyisipan langsung sendiri dapat dituliskan sebagai berikut:
1. x ← Data [( L + R) / 2)].
2. i ← L
3. j ← R
4. Selama ( i < = j ) kerjakan baris 5 sampai dengan 12.
5. Selama ( Data [ i ] < x ) kerjakan i ← i + 1
6. Selama ( Data [ j ] > x ) kerjakan i ← j - 1
7. Jika (i < = j ) maka kerjakan baris 8 sampai dengan 10; jika tidak kerjakan baris 11.
8. Tukar Data [ i ] dengan Data [ j ].
9. i ← i + 1
10. j ← j - 1
11. Jika ( L < j ) kerjakan lagi baris 1 dengan R = j.
12. Jika ( i < R ) kerjakan lagi baris 1 dengan L = i.

Jika suatu barisan yang terdiri dari n elemen yang ditempatkan dalam suatu array dan urutan yang diinginkan adalah urutan yang tidak turun (non decreasing) maka dapat digunakan metode Quick Sort yang dengan teknik Divide and Conquer.
Adapun algoritma Quick Sort tersebut terdiri dari dua prosedur yaitu prosedur PARTITION dan prosedur QUICKSORT. Berikut ini disajikan algoritma Quick Sort yang dimaksud, yaitu :
PROCEDURE QUICKSORT(p,q)
IF p < q then j q + 1
CALL PARTITION(p,j)
CALL QUICKSORT(p,j-1)
CALL QUICKSORT(j+1,q)
END IF
END QUICKSORT
PROCEDURE PARTITION(m,p)
INTEGER m,p,i ; GLOBAL A(m-1,p)
V A(m) ; i m
LOOP
LOOP i i + 1 UNTIL A( i ) > = V REPEAT
LOOP p p - 1 UNTIL A( p ) < = V REPEAT
IF i < p THEN CALL INTERCHANGE (A(i),A(p))
ELSE EXIT
END IF
REPEAT
A(m) A(p)
A(p) V
END PARTITION

Contoh :
Suatu Array A terdiri dari 9 elemen, yaitu :
A(1) = 65 A(4) = 80 A(7) = 60
A(2) = 70 A(5) = 85 A(8) = 50
A(3) = 75 A(6) = 60 A(9) = 45

Elemen-elemen tersebut akan disusun secara tidak turun berdasarkan algoritma Quick Sort.
Jalannya proses pada algoritma tersebut disajikan dalam bentuk tabel sebagai berikut :

1 2 3 4 5 6 7 8 9 10 i p
65 70 75 80 85 60 55 50 45 2 9
65 45 75 80 85 60 55 50 70 3 8
65 45 50 80 85 60 55 75 70 4 7
65 45 50 55 85 60 80 75 70 5 6
65 45 50 55 60 85 80 75 70 6 5


1 2 3 4 5 6 7 8 9 10 i p
65 45 50 55 60 85 80 75 70 6 9
65 45 50 55 60 70 80 75 85 7 8
65 45 50 55 60 70 75 80 85 8 7


Dan seterusnya

EXIT

Analisisnya :
Hitung jumlah dari perbandingan-perbandingan elemennya dalam hal ini disimpan dalam variable C(n) dan kita asumsikan bahwa :
• n elemen yang disortir berbeda,
• proses pembagian (partisi) elemen V dalam prosedur PARTITION dilakukan dengan proses seleksi secara acak.

Worst Case dari C(n) dinotasikan dengan Cw(n). C(n) di dalam setiap pemanggilan prosedur PARTITION maksimum sebesar ( p – q + 1 ) kali.
Misalkan r adalah jumlah kumulatif dari elemen-elemen di dalam seluruh pemanggilan prosedur PARTITION pada setiap tingkat dari teknik rekursif tersebut. Pada tingkat pertama terjadi pemanggilan prosedur PARTITION sebanyak satu (1) kali yakni CALL PARTITION ( 1, n + 1 ) dan nilai r = n. Pada tingkat kedua terjadi pemanggilan prosedur PARTITION paling banyak dua (2) kali dan nilai r = n – 1, dan seterusnya dengan cara yang sama pada tingkat berikutnya. Dengan demikian dari proses tersebut diperoleh Cw(n) akan sama dengan jumlah seluruh tingkat (r) dan nilai r berkisar didalam interval [ 2 , n ].
Jadi kompleksitas waktunya (Worst Case) = Cw (n ) = O ( n² ) dan
Average Case = CA(n) = O ( n log n ).

Source : google.com

Nama : Wada Ismail

Kelas  : 1IA24

NPM  : 5C414110

English (Future Tense, Conditional Sentence, And Relative Clause

Understanding Of Simple Future Tense

Simple future tense is a verb form used to claim that an action happens in the future, spontaneous or planned. This tense can also be used to form conditional sentence type 1.

Rumus Simple Future Tense

Simple future tense formed from modal “will” or “shall” and bare infinitive (prototype verb) or formed from phrasal modal “be going to” and bare infinitive (base form verb).

Thus, the formula of simple future tense for positive sentences, negative, and interogative as follows.

Types of Sentences	Formula	Example of Simple Future Tense
positive (+)	S + will + bare infinitive S + be (am/is/are) going to + bare infinitive	You will win
		They are going to come
negative (-)	S + will + not + bare infinitive S + be (am/is/are) + not + going to + bare infinitive	You won’t win
		They aren’t going to come
interogative (?)	Will + S + bare infinitive Be (am/is/are) + S + going to + bare infinitive?	Will you win
		Are they going to come

A Example Sentences Of Function Simple Future Tense

Function	A Example Sentences Of Function Simple Future Tense
Simple future tense (will) to make a spontaneous decision to do something (without a plan).	Wait a minute. I will change my clothes. (Tunggu sebentar. Saya akan mengganti baju.)
	You look nervous. I’ll give you a glass of water. (Kamu tampak cemas. Saya akan memberimu segelas air.)
Simple future tense (will) to predict the future (without a plan).	The doom will not happen in 2014. (Kiamat tidak akan terjadi pada tahun 2014.)
	Which hotels do you think will offer the best service? (Hotel yang mana yang kamu pikir akan menawarkan pelayanan terbaik?)
	He’ll be angry. (Dia akan marah.)
	The sandstorm will come. (Badai pasir akan datang.)
	I think he will pass. (Saya pikir dia akan lulus.)
Simple future tense with "going + to" to declare intention (plan the future that have been thought previously).	I’m going to send this letter tomorrow. (Saya akan mengirimkan surat ini besok.)
	He is going to go to French to continue his study. (Dia akan pergi ke Perancis untuk melanjutkan sekolahnya.)
Simple future tense is used to form a conditional sentence type 1.	I will come if they invite me. (Saya akan datang jika mereka mengundang saya.)

Functions and Formulas Conditional Sentence Type 1 2 3

A.Understanding

Conditional sentence according to formulas and functions are divided into three types: type 1, 2 and 3. The definition of Conditional Sentence itself is a combination of two words where one of them is a condition of the sentence, and the other is a result of the implementation of these requirements.

For example, if you later I passed the exam with a score 10 all, then I will treat all classmates. If the graduation requirement is met, then I'll pay the consequences, if it does not pass, then I would not treat. So there is always a If (If).

B. Function Conditional Sentence

The formula Conditional Sentence is divided into three types depending on the degree of likelihood of occurrence or the implementation of the proposed requirements. (If you want to learn more explanation details, please click on the appropriate conditional sentence you want).

1.       Conditional Sentence Type 1.
Conditional sentence of this first type can be used to make a conditional sentence is still possible to achieve all of the conditions as will occur in the future. Example: I will give you money if my car is sold. When saying the car has not been sold and there are great opportunities to be sold so the opportunity to give money still great.

2.       Conditional Sentence Type 2.
Conditional sentence of the second type can be used to indicate the possibility of a conditional sentence would be difficult to fulfill.
Example: If I found your home, I would see you. If I find your house, I'll see you but in fact I have trouble finding your house. Although if you want to try even harder to meet.

3.        Conditional Sentence Type 3.
Conditional sentence third type is used to indicate the conditional sentence can not be met because his time has past.
Example: If I had Knew that your name is Salimah, I would not have gone to your wedding party. If only the (then) I know that Salimah your name, I could not have attended your wedding. So already overdo come and intention not to attend the wedding can not be fulfilled.

C. Formula Conditional Sentence Type 1 2 3.

1. Conditional Sentence Type 1.
   If + Subject + will + infinitive, Subject + verb-1.
2. Conditional Sentence Type 2.
   If + Subject + would + infinitive, Subject + verb-2.
3. Conditional Sentence Type 3.
   If + Subject + would + have + Verb-3, Subject + had + verb-3.

We use relative clauses to give additional information about something without starting another sentence. By combining sentences with a relative clause, your text becomes more fluent and you can avoid repeating certain words.

Relative Clause

How to Form Relative Clauses

Imagine, a girl is talking to Tom. You want to know who she is and ask a friend whether he knows her. You could say:

A girl is talking to Tom. Do you know the girl?

That sounds rather complicated, doesn't it? It would be easier with a relative clause: you put both pieces of information into one sentence. Start with the most important thing  – you want to know who the girl is.

Do you know the girl …

As your friend cannot know which girl you are talking about, you need to put in the additional information  – the girl is talking to Tom. Use „the girl“ only in the first part of the sentence, in the second part replace it with the relative pronoun (for people, use the relative pronoun „who“). So the final sentence is:

Do you know the girl who is talking to Tom?

Relative Pronouns

relative pronoun	use	example
who	subject or object pronoun for people	I told you about the woman who lives next door.
which	subject or object pronoun for animals and things	Do you see the cat which is lying on the roof?
which	referring to a whole sentence	He couldn’t read which surprised me.
whose	possession for people animals and things	Do you know the boy whose mother is a nurse?
whom	object pronoun for people, especially in non-defining relative clauses (in defining relative clauses we colloquially prefer who)	I was invited by the professor whom I met at the conference.
that	subject or object pronoun for people, animals and things in defining relative clauses (who or which are also possible)	I don’t like the table that stands in the kitchen.

Subject Pronoun or Object Pronoun?

Subject and object pronouns cannot be distinguished by their forms - who, which, that are used for subject and object pronouns. You can, however, distinguish them as follows:
If the relative pronoun is followed by a verb, the relative pronoun is a subject pronoun. Subject pronouns must always be used.

the apple which is lying on the table

If the relative pronoun is not followed by a verb (but by a noun or pronoun), the relative pronoun is an object pronoun. Object pronouns can be dropped in defining relative clauses, which are then called Contact Clauses.

the apple (which) George lay on the table

Relative Adverbs

A relative adverb can be used instead of a relative pronoun plus preposition. This often makes the sentence easier to understand.

This is the shop in which I bought my bike.
→ This is the shop where I bought my bike.

relative adverb	meaning	use	example
when	in/on which	refers to a time expression	the day when we met him
where	in/at which	refers to a place	the place where we met him
why	for which	refers to a reason	the reason why we met him

Defining Relative Clauses

Defining relative clauses (also called identifying relative clauses or restrictive relative clauses) give detailed information defining a general term or expression. Defining relative clauses are not put in commas.
Imagine, Tom is in a room with five girls. One girl is talking to Tom and you ask somebodywhether he knows this girl. Here the relative clause defines which of the five girls you mean.

Do you know the girl who is talking to Tom?

Defining relative clauses are often used in definitions.

A seaman is someone who works on a ship.

Object pronouns in defining relative clauses can be dropped. (Sentences with a relative clause without the relative pronoun are called Contact Clauses.)

The boy (who/whom) we met yesterday is very nice.

Non-Defining Relative Clauses

Non-defining relative clauses (also called non-identifying relative clauses or non-restrictive relative clauses) give additional information on something, but do not define it. Non-defining relative clauses are put in commas.
Imagine, Tom is in a room with only one girl. The two are talking to each other and you ask somebody whether he knows this girl. Here the relative clause is non-defining because in this situation it is obvious which girl you mean.

Do you know the girl, who is talking to Tom?

Note: In non-defining relative clauses, who/which may not be replaced with that.
Object pronouns in non-defining relative clauses must be used.

Jim, who/whom we met yesterday, is very nice

https://www.ego4u.com/en/cram-up/grammar/relative-clauses

inggrisonline.com/pengertian-fungsi-dan-rumus-conditional-sentence-type-1-2-3/

http://www.wordsmile.com/pengertian-rumus-contoh-kalimat-simple-future-tense

Sesuatu Yang Membuat Resah dan Solusi Untuk Menghadapi Keresahan Tersebut

Terkadang orang lain melihat kita senang-senang saja dalam menghadapi hidup,tetapi tanpa orang lain sadari bahwa setiap orang memiliki keresahan tersendiri yang tentu saja dapat mempengaruhi diri kita, tetapi disamping itu kita pasti memiliki cara khusus atau solusi untuk menghadapi keresahan tersebut.

Saya sendiri memiliki sebuah keresahan yang sering kali menggangu saya dalam menjalani aktifitas saya sendiri, keresahan tersebut yaitu ketakutan saya gagal dimasa depan dan mengecewakan orang tua saya yang sudah membesarkan saya dan menyekolahakan saya sampai setinggi ini, terkadang hal tersebut menjadi sebuah tantangan, tetapi dalam satu sisi hal tersebut dapat membuat saya menjadi resah.

Menurut saya kesuksesan dimasa depan merupakan tujuan utama, tidak hanya sukses didunia, tetapi saya juga ingin sukses diakhirat. Dalam menghadapi keresahan tersebut solusinya yaitu dengan bekerja keras dan selalu mengingat apa pengorbanan yang sudah diberikan oleh orang tua saya, dengan menanamkan pemikiran tersebut maka muncul tekad dalam hati untuk dapat membanggakan dan membalas semua hal yang sudah orang tua berikan kepada saya, dengan begitu maka keresahan saya dapat sedikit tertutupi. Tetapi tentunya keresahan tersebut akan hilang ketika saya sudah mencapai tujuan hidup saya.