Tolong Ajarin Algoritma optimasi khususnya pascal. . .

Diskusi seputar dunia IT

Tolong Ajarin Algoritma optimasi khususnya pascal. . .

Postby darkstalker » 13 Jan 2011, 18:48

Kk kk, saya baru dalam bidang pemrograman karena tertarik buat ikut kontes kontes yg ada. sampai saat ini aku udah ikut 2 kontest yg di binus sama yg di UNPAR. tapi waktu pembahasan soal di BNPCHS binus, aku gak ngerti itu ngomongin Bruteforce, greedy, ataupun Dynamic programing. . .
ada yg bisa kasih pencerahan gak kk buat agoritma ini ?? mungkin referensinya kk sama contoh soal dan penyelesaiannya. . . ini murni loh kk mau belajar. . . mumpung masih SMA. . .
Mohon yah kk. . . Thx. . hehehe. . .
darkstalker
Junior Member
 
Posts: 17
Joined: 05 Dec 2010, 10:45

RE: Tolong Ajarin Algoritma optimasi khususnya pascal. . .

Postby leledumbo » 13 Jan 2011, 20:38

Di tingkat universitas aja itu ilmu baru diajarin semester 7 (kecuali kami2 yang emang tim lomba). Ta' coba jelasin dalam tempo jang sesingkat-singkatnya.

Bruteforce:
Biasa juga disebut cara naif, yaitu menterjemahkan plek apa yang diminta soal. Seringkali berguna untuk soal2 termudah ketika kompetisi (harus pinter nyari, liat batasan-batasan di soal) karena kita ngejer waktu solve tercepat (bukan running time). Tapi untuk problem di atas itu jangan samsek soale dijamin TLE (Time Limit Exceeded, lewat batas waktu) / MLE (Memory Limit Exceeded, lewat batas memori).

Greedy:
Teknik pemrograman yang mencari jawaban secara incremental dan memilih jalan terbaik dari posisi saat ini. Teknik ini mengasumsikan "jalan menuju jawaban" sebagai sebuah maze di mana dari posisi saat ini ada beberapa kemungkinan ke posisi berikutnya, dan dari sekian banyak pilihan itu kita langsung pilih yang dinilai "terbaik" dan jalan terus (HARAM mundur terus milih jalan lain). Contoh masalah yang bisa diselesein sama problem ini adalah fractional knapsack (silakan gugle).

Dynamic Programming:
Teknik pemrograman yang applicable untuk masalah-masalah rekursif di mana subproblem bisa muncul lebih dari sekali. Kalo pake rekursif biasa, tuh subproblem bakal keitung lebih dari sekali juga. Dalam DP, ketika suatu subproblem disolve, hasilnya disimpen ke suatu tabel. Jadi ketika ketemu lagi tuh subproblem, tinggal baca dari tabel. Contoh yang paling gampang ngitung fibonacci (gugle juga).
leledumbo
Senior Member
 
Posts: 262
Joined: 24 May 2010, 15:58

RE: Tolong Ajarin Algoritma optimasi khususnya pascal. . .

Postby darkstalker » 13 Jan 2011, 20:49

Neh kk saya punya contoh soal untuk yg DP, Greedy, sama Bruteforce yg gak bisa aku selesaiin waktu kontes karena gak ngerti kk. . . hohoho

http://www.suhendry.net/contest/bnpchs1 ... -probs.pdf

mungkin soal untuk DP tuh yang misteri rekursif Fibonacci. . Terus yg Greedy tw Bruteforce itu yg susun balok kk. . . mohon penjelasannya yah. . .
Maaf kk ngerepotin. mudah mudahan bisa jadi bekal wat kuliah nanti. . .
darkstalker
Junior Member
 
Posts: 17
Joined: 05 Dec 2010, 10:45

RE: Tolong Ajarin Algoritma optimasi khususnya pascal. . .

Postby leledumbo » 13 Jan 2011, 21:35

Buset, dari blognya suhendry. Bentar, gw nyembah (ngerjain) dulu.
leledumbo
Senior Member
 
Posts: 262
Joined: 24 May 2010, 15:58

RE: Tolong Ajarin Algoritma optimasi khususnya pascal. . .

Postby darkstalker » 13 Jan 2011, 21:44

Hohoho udah terkenal yah itu orang. . . Ok kk. . . Maaf yah ngerepotin. . . Btw Thx yah kk. . .
darkstalker
Junior Member
 
Posts: 17
Joined: 05 Dec 2010, 10:45

RE: Tolong Ajarin Algoritma optimasi khususnya pascal. . .

Postby leledumbo » 14 Jan 2011, 00:11

Coba yang Misteri Rekursif Fibonacci dulu. Let's see, yang paling penting sebelum kita memutuskan untuk menyelesaikan suatu problem DP, cari tahu dulu apa itu emang harus DP. Kalo ada solusi incremental atau bahkan konstan ya jelas DP gak perlu.

Program di bawah nunjukkin berapa kali F(M) diitung pas ngitung F(N).
Code: Select all
  1. var

  2.   Counter: QWord;

  3.   M: Word;

  4.  

  5. function f(const N: Word) : QWord;

  6. begin

  7.   if N = M then Inc(Counter);

  8.   if (n <= 1) then f := n

  9.   else f := f(n - 1) + f(n - 2);

  10. end;

  11.  

  12. var

  13.   i,N: word;

  14. begin

  15.   for N := 1 to 10 do begin

  16.     WriteLn('Pada perhitungan fib(',N,')');

  17.     for i := 0 to N - 1 do begin

  18.       Counter := 0;

  19.       M := i;

  20.       f(N);

  21.       WriteLn(i,' dihitung ',Counter,' kali');

  22.     end;

  23.   end;

  24. end.


Nah, dari outputnya. Ada kesimpulan gak?[hr]
Yang susun balok solusi greedynya: sort tinggi masing2 balok secara descending, terus di-loop deh selama tinggi sekarang - tinggi balok yang mau diambil >= 0, tinggi sekarang -= tinggi balok yang mau diambil. Kalo pas 0, break, berarti bisa. Kalo sampe ujung gak 0 juga, berarti gak bisa.
leledumbo
Senior Member
 
Posts: 262
Joined: 24 May 2010, 15:58

RE: Tolong Ajarin Algoritma optimasi khususnya pascal. . .

Postby pebbie » 14 Jan 2011, 09:00

di universitas itu ada di tahun kedua (semester 3-4). variasi teknik tersebut biasanya enak dibandingkan kalau persoalannya merupakan famili persoalan pencarian kombinatorial (combinatorial search/combinatorial optimization).

kalo soal fibonacci secara dynamic programming itu sebetulnya cukup menyimpan 2 variabel (f(n-1), dan f(n-2)), setelah menghitung f(n), nilai f(n-1) diassign ke f(n-2) dan f(n) ke f(n-1). jadinya tidak perlu lagi mengulang menghitung f(n-1) secara rekursif. untuk Problem misteri fibonacci, jawabannya trivial : N-M

Problem A : linear search, cari aja yang nilainya paling tinggi, itu yang menang
Problem B : image processing, ekstrak semua angka 1 yang terhubung pake floodfill, lalu cek ada lubang atau tidak
Problem C : Quad Tree, bisa pake rule, maksimal punya 4 tetangga. setiap level pasti punya 2 tetangga, tiap tambah level tetangganya ditambah atau diganti
Problem D : iterasi penjumlahan biasa
Problem E : trivial, cek huruf ke n dan n+2, kalau sama tambahkan ke output dan loncat
Problem F : rekursif 2^n, stop jika 'YA'
Problem G : *Knapsack*
Problem H : rekursif 2^n, n: iterasi fibonacci maksimal yang nilainya dibawah x
Problem I : N-M
Problem J : trivial
pebbie
Junior Member
 
Posts: 32
Joined: 12 May 2010, 15:50

RE: Tolong Ajarin Algoritma optimasi khususnya pascal. . .

Postby D.E » 14 Jan 2011, 10:28

OOT: Wah mantap nih thread... lanjut maaang :)

Ane agak OOT deh kalo masalah ginian, maklum waktu kuliah masuk pas ujian aja, ngandalin insting dan naluri ngetik wkwkwk :D
Mari yang pakar silahken bahas sedetil mungkin, terutama bagian awal mengerjakan; bagaimana menentukan cara penyelesaiannya, biar saya juga ikutan belajar hehehe
:idea: Dude, if you don't understand the basics and just want to get someone else write the code for you, it means you really shouldn't study computer science. Find different field!
User avatar
D.E
Senior Member
 
Posts: 638
Joined: 04 May 2010, 18:12

RE: Tolong Ajarin Algoritma optimasi khususnya pascal. . .

Postby bee » 14 Jan 2011, 10:49

Wahahahaha... seru nih! Saya udah lama gak utak-atik algoritma kek begini lagi. Udah lewat masanya coding low level. Udah gak sempat juga. *alibi :D

Monggo dilanjut. Tetap semangat! :)
bee
Member
 
Posts: 175
Joined: 12 May 2010, 14:15

RE: Tolong Ajarin Algoritma optimasi khususnya pascal. . .

Postby darkstalker » 14 Jan 2011, 14:16

Mmmmm aku udah pernah pake cara itu kk. . Hasilnya Time Limit Exceed. . .
Itu kan inputnya bisa besar kk input N bisa sampai 10000. . . Makanya harus DP kata suhendry. . . tapi ane gak ngerti gimana T_T. . .
Btw thx yah kk codingnya hohoho. . .
darkstalker
Junior Member
 
Posts: 17
Joined: 05 Dec 2010, 10:45

Next

Who is online

Users browsing this forum: No registered users and 1 guest

cron