ABSTRAC
The working paper discus that implementation dynamic programming . the discussion working paper counting fibonanci number and binomial coefficient with dynamic programming. Fibonanci number and binomial coefficient is numeral rekursif. We can count fibonanci number and binomial coefficient with rekursif algorithm, apropate with definite that numeral. While, if we more pay attention rekursif algorithm for two problems very not efficient calculation continued.
This is slow computation for more values. Rekursif algorithm can used for count Fibonanci number and binomial coefficient have exponential complexity. With dynamic programming we can reduction so we have complexity linear solution algorithm. Calculation above can losted.
INTRODUCTION
Dynamic programming found by Richard bellman at 1953, it is one method solution when solution of problem can meet decisiomn series have connect. Dynamic programming is one of them effective method used usually for simplification rekursif problems. Like that greedy algorithm, dynamic programming also one of approach for finish optimation problem. But,the greedy method just only decisions series. Dynamic programming focus for overlapping sub problems. Decisions series make from optimal structure, when optimum solution can used for find optimum solution for totalyti problems. The opticasion dynamic programming very large. For example, simple,for count Fibonacci number and binomial coefficient. Also other algorithm based from dynamic programming like cooke-younger-kasami algorithm for determine what one string can accept that context-free grammar, viterby algorithm for method hidden markow. Erly algorithm for charts passer, nedleman- wunch algorithm used bioninformatic, floyd’s all-pairs algorithm for hunt short flash, selingger algorithm for query optimation . it is based data for evaluated B. spline curve ,and etc.
Dynamic Programming For count Fibonacci Number
One of them application form dynamic programming is counting Fibonacci number . dynamic programming is alternative for count Fibonacci number with fast, substitute for rekursif algorithm very inefficient
Fibonancci Number
0,n= 0
F(n)=1 n=1
F(n-1)+ F(n-2), n>1
So, the numbers is sum form last two numeral
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610,
987, 1597, 2584, 4181, 6765, 10946, 17711, 28657,
46368, 75025, 121393, 196418, 317811…
Fibonacci number have an interesting characteristic
We can devided one numeral in above
This facta, the numeral valuabe permanent after the numeral to-13 in above Fibonacci number . the number called golden ratio (phi), whwn Fibonacci number also have identity:
1. F(n + 1) = F(n) + F(n − 1)
2. F(0) + F(1) + F(2) + … + F(n) = F(n + 2) − 1
3. F(1) + 2 F(2) + 3 F(3) + … + n F(n) = n F(n + 2) −
F(n + 3) + 2
4. F(0)2 + F(1)2 + F(2)2 + … + F(n)2 = F(n) F(n + 1)
Application Dynamic programming
From the definition of fibonacci number , we can make rekursif algorithm for count Fibonacci number like that
Function Fibonacci (input n=integer)
Type data can substituted with long interger or an other.
Input : n
Out put : Fibonacci number to-n
Declaration algorithm
If n=0 then
Return 0
Else if n=1 then return 1else
Return Fibonacci (n-1)+ Fibonacci (n-2)
End if
If T (n) is time for count F(n) is Fibonacci number to-n, so by using above function clear that
T(n) = T(n – 1) + T(n – 2)
And
T(1) = T(2) = c
When C is constant, because that
T(n) = c F(n),so
T(n) = O(F(n)) = O(1,618...n)
The simple function have exponential time complexity. So algorithm like that can used, but very not effective for more than value. We can see, that Fibonacci (n+1) must carry out all counting fgrom Fibonacci (n) and Fibonacci (n+1) . and in count Fibonacci number continued.
With dynamic programming, we can repair rekursif algorithm, so computation become efficient. We can use two concept in dynamic programming : top-dow and botton up. Solution with two concept explained like that :
With top-down approach
In here, we use one array, exemple FIB array have measurement-n when FIB(i) have contens Fibonacci number to(i+1) , that algorithm function (input interger)
(count Fibonacci number to-n with top-down approach)
Input(n)
Out put : Fibonacci number to-n
Declaration
I= interger
FIB : array [i….n] of interger
Algorithm if n=0 then
return 0
else if n=1 or n=2 then
return 1
else
Fib[1] �� 1
Fib[2] �� 1
for i��3 to n do
Fib[i] �� Fib[i-1] + Fib[i-2]
endfor
return Fib[i]
endif
With that , we can have value Fib[3], Fib[4], and etc, we keep that value in array. While loop finish, the function will restore finish element of array, it is Fibonacci number to-n that counted.
With bottom-up approach
There, we count Fibonacci small then, then calculation more then value from previously values. This is a repair from previously concept when this array, it lost by us.
The algorithm like
Funtion Fibonacci (input n ;interger)
(count Fibonacci number to-n with dynamic programming(bottom-up approach))
Input=n
Out put : Fibonacci number to-n
Declaration
I=interger
PrevF,currF,new F : interger
Algorithm
prevF �� 0
currF �� 1
for i��2 to n do
newF �� prevF + currF
prevF �� currF
currF �� newF
endfor
return currF
two mentioned approaches have equel complexity , it is 0(n). linear complexity and it is more than rekursif algorithm. Sed difference just used memory, whwn top-down, we need much memory for array Dynamic programming, we can lost calculation.
Dynamic programming foe count binomial coefficient
Binomial coefficient
In mathemathics , first combinational, binomial coefficient fron numeral and interger numeral k is sum combination . such as ,if given interger s including zero, method choose k ball equal binomiqal coefficient.
Binjomial coefficient defined that
for n ≥ k ≥ 0 and
for k < 0 or k > n.
For value n and k non-negative, so we have albert Ion Eiting hausen notasion. It is introduce by Albert at 1826. An other notasion usually used like c(n,k),nCk, or C nk (C for combination)
Applycation Dynamic pRogaramming
From definition of binomial coefficient , we can make algorithm like
Function binomial (input n,k intrger)
(count buinomial coefficient from (n,k) with rekursif. For more than numeral, type data can subtitude witjh longinterger or an other)
Input :n,k
Out-put: binomial coefficient (n,k)
Declaration
Algorithm if n
else if k=0 or k=n then
return 1
else
return Binomial(n-1,k-1) +
Binomial(n-1,k)
Endif
Complexity of algorithm above is
T(n,k) = T(n – 1, k – 1) + T(n – k, k)
or
T(n,k) = O(nk)
With algorithm that, much computation continued
Fir example, counting C(5,3) with counting Fibonacci number like in counting Fibonacci number , we can repair algorithm with dynamic programming. Principles used is:
Make matriks (n+1) × (k+1)f0r keep crop of count
Inisialitation matriks with smaller from problems instansiation.
Set element matriks , use crop count. One element counted just only one.
Finish value from count is solution from problem
In tgere, we implementation interatif, not rekursif
That explained
With top-dow approach
The algorithm
Function binomial (input n, k : interger)
{count binomial coefficient from (n, k) with dynamic programming , tpo-down approach}
Input : n , k
Output :binomial coefficient (n,k)
Declaration
i,j : integer
Bin : array [1..n+1][1..k+1] of integer
Algoritma
{inisialisasi matriksa}
for i��1 to n+1 do
for j��1 to k+1 do
Bin[i][j] �� 0
endfor
endfor
n – 1
k – 1
n – 1
k
+
, 0 < k < n
1 , k=0 or k=n
n =k
binomial coeeficient written with
C(5,3)
C(4,2) C(4,3)
C(3,1) C(3,2) C(3,2) C(3,3)
{count binomial coefficient}
if n=k or k=0 then
return 1
else if Bin[n+1][k+1]>0 then
return Bin[n+1][k+1]
else
Bin[n+1][k+1] �� Binomial[n][k] +
Binomial[n][k-1]
return Bin[n+1][k+1]
With bottom-up approach
The algorithm
Function binomial (input n,k : interger)
{count binomial coefficient from(n, k) with bottom-up appriach}
Input : n,k
Output : binomial coefficient (n, k)
Declaration
i,j : integer
Bin : array [1..n+1][1..k+1] of integer
Algoritma
{inisialisasi matriksa}
for i��1 to n+1 do
for j��1 to k+1 do
Bin [i][j] �� 0
endfor
endfor
{menghitung koefisien binomial}
for i��1 to n+1 do
for j��1 to (Min(i,k)+1) do
if j=0 or j=k then
Bin[i][j] �� 1
else
Bin[i][j] �� Bin[i-1][j-1] +
Bin[i-1][j]
endif
endfor
endfor
return Bin[n+1][k+1]
two concept have equel complexity it is O(nk), or at problems (k=n/2)
that complexity O(n2). This complexity more better than rekursif algorithm
Conclution
Used dynamic programming for count fibonaccy number and binomial coefficient more effective beter than rekursif algorithm.
