Burak IŞIKLI :))

Dinamik Programlama(Dynamic Programming)

Posted in Algorithm, C/C++ by Burak IŞIKLI on 14 Ağustos 2009

Dinamik programlama bir problemi çözerken aynı alt-problemi birden fazla çözmemiz gereken durumlarda bu alt-problemi birden fazla kez çözmemizi engelleyen bir tekniktir. Dinamik programalama, matematik ve bilgisayar bilimlerinde karmaşık problemleri çözmek için kullanılan bir metottur. Overlapping subproblems ve optimal substructure denilen problemlerde uygunabiliyor.

Eğer problemimiz kendi içinde alt problemlere ayrılabiliyorsa overlapping subproblems’dir. Buna en iyi örnek Fibanicci serisidir. Daha önceden bu yazımda fibonacci serisini anlatmıştım.

Shortest Path Optimal SubstructureFakat problemimiz kendi içinde alt problemlere ayrıldığında daha iyi bir performans sağlıyorsa buna optimal substructure deniliyor. Buna en iyi örnek ise greedy algoritmasıdır. Dinamik programlamada geçen programlama sözcüğü sadece bilgisayar programlarını kapsamamaktadır, çünkü burada kullandığımız program sözcüğü “matematiksel programlama” dan gelmektedir, ki bu da kısaca sıkça kullandığımız optimizasyon(bir nevi iyileştirme demek optimizasyon belki kullanmayan da vardır 🙂 kelimesine denk gelmektedir.

Dinamik programlama uygulamalarımızda temel olarak 3 teknikten faydalanacağız:

  • Çözümü aynı olan alt-problemler
  • Büyük bir problemi küçük parçalara bölmek ve bu küçük parçaları kullanarak baştaki büyük problemimizin sonucuna ulaşmak
  • Çözdüğümüz her alt-problemin sonucunu bir yere not almak ve gerektiğinde bu sonucu kullanarak aynı problemi tekrar tekrar çözmeyi engellemek.

Şimdi örneğimiz olan fibonacci dizimize başlayalım. Fibonacci dizimizi kısaca bir hatırlayalım.

Eğer herhangi bir sayının Fibonacci karşılığına F(n) dersek,

F(0) = F(1) = 1 olmak üzere

F(n) = F(n-1) + F(n-2)’dir.

İlk yaptığımız prosesimizin fonksiyonunu hatırlayalım:

fib.cpp

// Recursive Function
int fib(int num) {
 if ((num == 0) || (num == 1))
 return num;
 else
 return (fib(num - 1) + fib(num - 2));
}

Bu kadar kısa bir kod yazarak çözümü sağlamıştık. Ancak bu yöntem kodun kısa olmasına rağmen performans açısından kötü bir yöntemdir.  Nedenine gelirsek mesela F(3)’ü adım adım hesaplayalım:

F(4) = (F(2) + F(1)))

= ((F(1) + F(0)) + F(1)) + F(2)

= ((F(1) + F(0)) + F(1)) + (F(1) + F(0))

Görüldüğü gibi F(4) değerini hesaplarken F(1)’ye 2 defa ihtiyacımız oldu ama 2 seferde de hesapladık. Prosesimizi değiştirerek bir de şu hale getirelim.

fib2.cpp

/*
 *
 * Program:  Fibonacci Series v2
 * Programmer: Burak ISIKLI
 *
 */

#include <iostream.h>

unsigned int fib2(unsigned int num);

unsigned int fibArray[1000];

// Main Function
int main() {
 unsigned int number, result;
 cout << "Fibonacci serisinin(fib(x)) sayisini giriniz x = ";
 cin >> number;

 result = fib2(number);
 cout << "fib( " << number << " ) = " << result << "\n\n";

 return 0;
}

unsigned int fib2(unsigned int num)
{
 unsigned int i = 2;
 fibArray[0] = fibArray[1] = 1;
 while(i <= num)
 {
 fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
 i++;
 }
 return fibArray[num];
}

Burada yaptığımız işlem ise şu. Hesapladığımız Fibonacci sayılarını bir diziye kaydediyoruz. Daha sonra lazım olunca bu değerleri direkt diziden hazır bi şekilde alıyoruz. Böylece aynı işlemi tekrar tekrar yapmaktan kurtuluyoruz.

Performans karşılaştırması yapacak olursak kendi bilgisayarımda fibonacci(50) 8dk. 36 sn’de sonuç verirken fibonacci2(50) 0.003 sn’de sonuç veriyor. Daha bilimsel konuşacak olursak problemi temelde aynı mantıkla çalışan iki fonksiyonun birincisi O(2^n) iken ikincisi O(n) zamanda çözmektedir.

Kaynaklar:

http://en.wikipedia.org/wiki/Dynamic_programming

http://en.wikipedia.org/wiki/Optimal_substructure

http://e-bergi.com/2008/Mart/Dinamik-Programlama

/*
 *
 * Program:  Fibonacci Series v2
 * Programmer: Burak ISIKLI
 *
 */

#include <iostream.h>

unsigned int fib2(unsigned int num);

unsigned int fibArray[1000];

// Main Function
int main() {
 unsigned int number, result;
 cout << "Fibonacci serisinin(fib(x)) sayisini giriniz x = ";
 cin >> number;

 result = fib2(number);
 cout << "fib( " << number << " ) = " << result << "\n\n";

 return 0;
}

unsigned int fib2(unsigned int num)
{
 unsigned int i = 2;
 fibArray[0] = fibArray[1] = 1;
 while(i <= num)
 {
 fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
 i++;
 }
 return fibArray[num];
}

Web Service ile Sıcaklık Dönüşümü

Posted in Java, Web Services by Burak IŞIKLI on 29 Temmuz 2009

Daha önceden blogumdaki Axis 2 Kullanılarak Web Servis Oluşturma adlı yazımda web servisin nasıl oluşturulacağını anlatmıştım. Fakat çok iyi bir örnek vermediğim için biraz havada kaldı. Şimdi anlatacağım örnekle konu tam anlamıyla oturmuş olacak. Web servislerde internette biraz araştırma yaparsanız en sık öne çıkan örnekler sıcaklık dönüşümü, para dönüşümü, kimlik sorgulama gibi hizmetler olacaktır. Bende bunlardan biri olan sıcaklık dönüşümünü java ve jsp kullanarak anlatacağım.

Yapacağımız programı iki aşamalı olarak anlatacağım. Birinci versiyonumuz için paket adımız “edu.burakkk.webservice.tempConverter.v1”. İlk önce birinci versiyonu yapalım.

TempConverter.java


package edu.burakkk.webservice.tempConverter.v1;

/**
 * Web Service
 * Temp Converter
 *
 *@version 1.0 Release 1
 *@author burakkk
 *
 **/

public class TempConverter{
 public String FahrenheitToCelsius(String Input) {
 if (!Input.isEmpty() && isNumber(Input)) {
 double result = 0;
 result = Double.parseDouble(Input);
 result = (((result) - 32) / 9) * 5;
 Input = Double.toString(result);
 return Input;
 } else {
 return "ERROR! Please enter the input number...";
 }
 }

 public String CelsiusToFahrenheit(String Input) {
 if (!Input.isEmpty() && isNumber(Input)) {
 double result = 0;
 result = Double.parseDouble(Input);
 result = (((result) * 9) / 5) + 32;
 Input = Double.toString(result);
 return Input;
 } else {
 return "ERROR! Please enter the input number...";
 }
 }

 private boolean isNumber(String num) {
 try {
 Double.parseDouble(num);
 } catch (NumberFormatException nfe) {
 return false;
 }
 return true;
 }
}

Aslında yaptığımız programı bu şekilde kullanmak doğru olmaz. Çünkü her metodu çağırmak için ayrı bir forma gerek olur ki bu da gereksiz yer, yük ve işlem getirir. Ancak bu şekilde yaparak anlatmak istediğim bir başka konu var. Bu web servis yerine başka bir web servis düşünün. Öyle ki bu web servisin iki metodundan biri özel yani sadece üyelere açık, diğeri ise public yani herkese açıktır. İşte bu işlemi bu şekilde iki ayrı metoda bölerek rahatlıkla yapabiliriz. Özel olan metoda önce kullanıcı üye mi değil mi diye üyelik testi yaptırırız. Bu sebeple de sınıfımıza private olan ayrı bir metod daha ekleriz. Bu private metod, gelen kullanıcının üye olup olmadığını kontrol eder. Örneğin boolean türünde olursa true sonuç döndürürse istediğimiz webservisin sonucunu döndürürüz aksi takdirde üye olmadığına dair hata sonucunu döndürürüz.

Bu prosesimizi(web servisimizi) kullanacağımız zaman yani çağırmak için olan prosesimizi yapalım. Aslında bunu bir web sayfası olarak JSP ile yapacağız. Ancak daha öncedende anlattığım gibi web servis genel bir konsept olduğu için her programlama dilinde yapmak mümkündür. Ben sadece örnek olarak JSP kullanacağım.

TempConverter.v1.jsp

<?xml version="1.0" encoding="utf-8" ?>
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>Temp Converter</title>
</head>
<body>
<form
action='http://localhost:8080/WebService/services/TempConverter/FahrenheitToCelsius'
method="post" target="_blank">
<table>
<tr>
<td>Fahrenheit to Celsius:</td>
<td><input type="text" size="30" name="Input"></td>
</tr>
<tr>
<td></td>
<td align="right"><input type="submit" value="Convert"></td>
</tr>
</table>
</form>

<form
action='http://localhost:8080/WebService/services/TempConverter/CelsiusToFahrenheit'
method="post" target="_blank">
<table>
<tr>
<td>Celsius to Fahrenheit:</td>
<td><input type="text" size="30" name="Input"></td>
</tr>
<tr>
<td></td>
<td align="right"><input type="submit" value="Convert"></td>
</tr>
</table>
</form>
</body>
</html>

Ekran Görüntüsü:

Result

Sayfamızı çalıştırdığımızda yukarıdaki gibi bir ekran karşımıza gelecektir. Buraya fahrenheit olarak veya celcius olarak çevirmek istediğimiz rakamı girip convert butonuna bastığımızda karşımıza sonuç gelecektir. Ancak web servis bir xml tabanlı olduğu için sonucumuz da xml formatında gelecektir.

Programımızın ikinci aşamasına gelelim. İkinci programımızın paket adı “edu.burakkk.webservice.tempConverter.v2”dır. Web servisimizi yaratalım.

TempConverter.java


package edu.burakkk.webservice.tempConverter.v2;

/**
 * Web Service
 * Temp Converter
 *
 *@version 1.1 Release 1
 *@author Burak ISIKLI
 *
 **/

public class TempConverter {
 public String Convert(String type, String Input) {
 if (Input.isEmpty() || !isNumber(Input)) {
 return "ERROR! Please enter the input number...";
 }
 // Fahrenheit To Celsius
 if (type.equals("F")) {
 double result = 0;
 result = Double.parseDouble(Input);
 result = (((result) - 32) / 9) * 5;
 Input = Double.toString(result);
 return Input;
 }
 // Celsius To Fahrenheit
 else if (type.equals("C")) {
 double result = 0;
 result = Double.parseDouble(Input);
 result = (((result) * 9) / 5) + 32;
 Input = Double.toString(result);
 return Input;
 }
 return "ERROR! Please enter the input number...";

 }

 private boolean isNumber(String num) {
 try {
 Double.parseDouble(num);
 } catch (NumberFormatException nfe) {
 return false;
 }
 return true;
 }
}

Bu prosesimiz bir öncekinden biraz daha farklı oldu. Bu prosesimizde tek fonksiyonda olayı çözdük. Ancak fahrenheit mı celcius mu olduğunu kısaca hangi tür olduğunu kullancıdan başkan bir değişken isteyerek yaptık. Bu istediğimiz değişkeni formda belirleyerek programa derdimizi anlattık. Böylelikle tek hamlede istediğimiz web servisi yapmış olduk. Aslında benim yaptığım hata döndürme olaylarını da web tarafında yapmak daha doğru olur. Basit bir örnek vermek istediğim için detaylı incelemedim. Formda javascriptle gerekli eklemeler yapılarak hatta ajax kullanılarak çok daha kullanışlı bir sayfa yapmak mümkün olabilir.

TempConverter.v1.1.jsp

<?xml version="1.0" encoding="utf-8" ?>
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>Temp Converter</title>
</head>
<body>
<form
 action='http://localhost:8080/WebService/services/TempConverter/Convert'
 method="post">
<table>
<tr>
<td>Enter the input number: <input type="text" size="30" name="Input"></td>
</tr>
<tr>
<td><input type="radio" name="type" value="F" /> Fahrenheit
 <input type="radio" name="type" value="C" checked /> Celsius</td>
</tr>
<tr>
<td align="left"><input type="submit" value="Convert"
 class="button"></td>
</tr>
</table>
</form>
</body>
</html>

Ekran Görüntüsü:

Result-245 Celcius’u Fahrenheit’e çevirmek istediğimizde karşımıza gelen ekran şu şekilde olacaktır.

Ekran Görüntüsü:

Result-3

Programların Kullanım Alanları

Posted in Miscellaneous by Burak IŞIKLI on 29 Temmuz 2009

Hayatımıza son yıllarda çok fazla çeşitte kendi alanlarında özelleşmiş programlar girdi. Ancak biz bu programların kullanım alanlarının neler olduğunu bilmeden ve bazen yanlış yerlerde yanlış amaçla kullanıyoruz.  Bu nedenle bu yazımda bazı özellikle web tasarımıyla ilgili programların nerelerde ne amaçla kullanıldığını sırayla yazıyorum.Ve başlıyorum…

Adobe Dreamweaver: Web tasarımında kullanılıyor. Daha çok kodlamaya yönelik avantajlar sağlayan bu programımızda aynı zamanda görsel olarak web sayfaları da hazırlayabiliyoruz. Hepimizin bildiği zamanında kullandığı Frontpage’in gelişmiş versiyonu olarak da düşünebiliriz.

Adobe Flash: Özellikle animasyon yapanların vazgeçemeyeceği bir program. Animasyonlara çok güzel ve kolaylıkla hareket verebilen action script denilen kendine özgü bir de programlama diliyle de geliştirilebilen bir programdır. Zamanında çok tutan “Karete Kamil”, “Karşı takım taraftarını yumruklama” gibi projelerin yapıldığı bu programda aynı zamanda şu anda hayatımızda olan grafi2000 ve atv’de halen yayımlanmakta olan “harbi tivi” adlı programın animasyonları da bu programla yapılmaktadır.

Adobe Illustrator: Broşür, kapak türü tasarım yapanlar için ideal bir program. Amacı kapsamlı vektör grafiği geliştirmektir.

Adobe Photoshop: Namı çok duyulmuş “fotoşop” programı. Resimleri değiştirmek hatta modifiye edip olmayan bir durum yaratmada kullanıldığını düşündüğümüz ve bunu düşündüren filmlerin aslında yanıldığını biliyor musunuz? Bu programın aslında 3D grafik tasarımı için dizayn edilmiştir 🙂

Adobe Fireworks: Özellikle web sitelerinde kullanılan bu program grafik dizayn ve web sitesi için prototip tasarlamada kullanılıyor.

Device Control: Mobil aygıtlarda veya mobil içerikte tasarım yapmak ve ön görünüm almak için bu program kullanılıyor.

Bridge: Medya yönetimi veya diğer bi deyişle dosya yönetimini sağlıyor.

Version Cue: Özellikle web sitelerindeki versiyon kontrolünde kullanılıyor. Bir tür versiyon kontrol sistemidir.