ders notları

Report
IT503
Veri Yapıları ve algoritmalar
Yrd. Doç. Dr. Yuriy Mishchenko
Tanıştırma ve Temel Kavramlar
Ders planı
• Algoritmalara giriş, algoritmalar nedir?
• Algortima temsil yöntemleri
• Algoritma türleri
• Algoritma analizi
Algoritmalar nedir?
Algoritmalar
• Algoritmalar, bilgisayar yazılım açısından
çoğunlukla biliriz
• Algoritmaların çoğunun matematiksel ve
bilgisayar program olmasına rağmen,
algoritmalar daha çok geniş kavramdır
Algoritmalar nedir?
Algoritmalar
• Matematiksel ve bilgisayar programları için
algoritmalar, bilgisayar biliminin (yani
computer science) konusudur
• Bilgisayar bilimi, matematiğin bir bölümüdür
Buradaki anlamda algoritmalar, bir
matematiksel problemin çözüm talimatı yada
planıdır
Algoritmalar nedir?
En basit matematiksel algoritma – ana okulda
verilen sayı ekleme süreci:
127
+
326
453
1
Algoritmalar nedir?
Matematiksel algoritmalar,
– Matematiksel bir soru var,
– Sorunun çözüm/amacına nasıl ulaşabileceğini
açıklayan detaylı bir plan, bu problemin
algoritmasıdır
Algoritmalar nedir?
Daha genel anlamda algoritmalar, her hangi
bir sorunun detaylı çözüm planı olarak
düşünülebilir
Sadece matematikte yada bilgisayar
programlamada değil, günlük hayatta hepimiz
bol bol algoritma kullanırız
Algoritmalar nedir?
• Çorba pisirme tarifi, aslında bir algoritmadır
– Sebzeleri hazırlamak
– Suyu kaynatmak
– Tavuğu ekleyip pişirmek
– Sebze kestirip kızartmak
– Herşeyi tencereye koymak
– Birkaç (birçok) dakika kaynatmak
– Ateşi kapatmak ve sakinleşmesini beklemek
Algoritmalar nedir?
• Okula ders için gelmek, bu da algoritmadır
– Evden çıkmak
– Evin kapısını kilitlelemek
– Dolmuşa binmek
– Dolmuşta para vermek
– Toros durağını beklemek
– Durağınızda durağını söyleyip inmek
– Dersliğe kadar yürümek
Algoritma temsilleri
• Algoritma belirtmek için, çözüm planı/tarifi belirli,
biçimsel ve biri tarafından kolayca anlanabilir şekilde
tanımlanması gerekmektedir
• Önceki örnekler gibi, bir talimat liste şeklinde sırayla
tanımlanan algoritmalara sözde kod denir
Algoritma temsilleri
• Sözde kod, algoritmanın talimatları adım adım ve
biçimsel şekilde belirtmek için normal dil ifadeleri
kullanır
• Sözde kod, normal bilgisayar programlara kollayca
dönüştürülebilmesi için, algoritmaların temel
tanımları vermek için genellikle kullanılır
Algoritma temsilleri
• Algoritmaların temsili için ikinci popüler yöntem akış
şemalarıdır
Sebzeleri hazırlamak
Suyu kaynatmak
Tavuğu ekleyip pişirmek
Sebze kestirip kızartmak
Herşeyi tencereye koymak
Birkaç (birçok) dakika
kaynatmak
Ateşi kapatmak ve
sakinleşmesini beklemek
Algoritma temsilleri
• Bu şekilde temsil edilen algoritmalara akış şeması
denir
• Akış şeması, algoritmanın talimat sırasını veya
algoritmanın işlem akışını belirtir
Algoritma temsilleri
• Algoritma, normalde belirli bir soru için geliştirilir ve
farklı sorular için farklı algoritmalara gerek vardır; bu
anlamda genel bir algoritma olamaz
• Ancak genel algoritma geliştirme stratejileri veya
birçok benzer soruyu çözen algortimalar olabilir
–
–
–
–
Özyineleme (recursion)
Böl ve fethet (divide and conquire)
Açgözlü/yerel (greedy or local)
Dynamik programlama (dynamic programming)
Algoritma türleri
Özyineleme (recursion)
• Çözüm adımları aynı işlemin tekrarlanması şeklindedir
• Sonuç aynı işlem yinelenen uygulamasıyla elde edilir
• Factöriyel özyinelemenin klasik örnektir:
•
•
•
•
Faktöriyel – “n!=1*2*3*…*n”
Özyineleme adımı: n!=n*(n-1)!
Özyineleme uygulaması: F(sayı)=sayı*F(sayı-1)
Bunun uygulanması faktöriyeldir, yani F(n)=n*F(n-1)=n*(n-1)*F(n-2)
...=n*(n-1)*(n-2)*...*1
Algoritmaların temel türleri
Böl ve fethet (divide and conquire)
• Problem birkaç daha küçük probleme bölünebilir
• Daha küçük problemlerin çözümü daha çok kolaydır
• Orijinal problem, altproblemlerin çözümlerini kullanarak daha
hızlı çözülebilir
• Sıralama böl-ve-fethet yaklaşımın klasik örneğidir
• Bir n-elemanlı dizi sıralanması n2 karşılaştırma işlemi gerekir
• Diziyi iki n/2-elemanlı parçaya bölüp parçaları ayrı ayrı sıralayıp
böylece 2*(n/2)2 = n2/2 karşılaştırma işlem olacak
• Parçaları geri birleştirip orijinal dizi n2/2+n işlemle sıralanacaktır
Algoritmaların temel türleri
Açgözlü/yerel (greedy/local)
• Genellikle optimizasyon problemlerinde kullanılan yaklaşım,
yani bir soru için en uygun (optimal olan) cevabı bulmak
gerekmektedir
• Böyle cevabı adım adım ararken, tüm adımlarda o adımda en
iyi olarak görünen seçimi yapmak gerekmektedir
• Açgözlü/yerel yol seçme örneği:
•
•
•
•
Evden çıktığımızda okula en yakın yere giden dolmuşu bineriz
Durakta inince, tekrar okula en yakın yere giden dolmuşu bineriz
... VB
Bu yol seçme sorunun açgözlü çözümüdür
Algoritmaların temel türleri
Dinamik programlama (dynamic programming)
• Bir tür optimizasyon problemlerinde kullanılan yaklaşım
• Bütün olabilir cevapların uygunluğu bir özyineleme kullanarak
hesaplanabilirse, dinamik programlama uygulanabilir
• Dinamik programlama ile yol seçme örneği
•
•
Fikir:
Bütün duraklar için o duraktan okula ulaşmak için optimal gereken zamanı
t(DURAK) olsun;
t-hesaplanması:
–
–
–
•
Okulda olan A durağında t(A)=0
A durağına bağlı duraklar için, t(B)=min(t(A)+t(A←B))
Bu adım bütün duraklar için uygulayınca, bütün duraklar için t(B) elde edilebilir
A’dan başlayınca, bütün bağlı duraklar adım adım inceleyip ona optimal
ulaşma zamanı seçin, bu duraklar için özyineleme şekilde ona bağlı
duraklar için t(B) hesaplayın, vb
Algoritmaların temel türleri
10 dk
5 dk
10 dk
10 dk
15 dk
Ev
10 dk
5 dk
Okul
5 dk
5 dk
15 dk
5 dk
5 dk
15 dk
10 dk
Algoritmaların temel türleri
15=min(5+10,10+10)
5=0+5
10 dk
5
15 dk
Ev
10
0
5 dk
Okul
20
10 dk
10 dk
5 dk
10 dk
15
5 dk
15
5 dk
15 dk
25
5 dk
5 dk
5
15 dk
20
30
10 dk
30
Algoritmaların temel türleri
Bu şekilde bulunmuş en hızlı yolun
tam zamanı 5+10+10+5=30 dk
10 dk
5
5 dk
15
Ev
10
0
5 dk
Okul
15 dk
10 dk
10 dk
10 dk
20
5 dk
15
5 dk
15 dk
25
5 dk
5 dk
5
15 dk
20
30
10 dk
30
Algoritmaların temel türleri
Fark edin ki açgözlü yolun zamanı
15+5+5+10=35 dk
10 dk
5
5 dk
15
Ev
10
0
5 dk
Okul
15 dk
10 dk
10 dk
10 dk
20
5 dk
15
5 dk
15 dk
25
5 dk
5 dk
5
15 dk
20
30
10 dk
30
Algoritmaların temel türleri
• Dinamik programlama yol seçme algoritması sadece
“yol seçme” için değil birçok durumda faydalı olabilir;
• Üretim süreç planlanması
• Belge işletme planlanması
• Benzer grafik şeklinde temsil edilebilir herhangi bir
problem çözülebilir
Algoritma analiz temelleri
• Herhangi algoritma biri tarafından uygulanması
düşünülmektedir (örneğin, bir kişi, bilgisayar, vb)
• Bu açıdan, herhangi algoritmanın çok önemli olan bir
noktası algoritmanın işlemlerini gerçekleştirmek için
gereken zaman ve herhangi diğer önemli maliyetidir
Algoritma analiz temelleri
• Algoritmanın işletme zamanı kesin durumuna bağlıdır
(örneğin, durakların sayısı, dizinin boyutu, ...)
• Bunun gibi kesin “durumlara” algoritmanın girişi
denir
• Böylece, algoritmaların işletme zamanı ve diğer
maliyetlerinin girişine bağlı dır
Algoritma analiz temelleri
• Algorıtma analizinin amacı, belirli bir giriş için
algoritmanın zaman ve bellek gereksinimleri
belirtmektedir
• Algoritmaların zaman ve bellek gereksinimleri giriş
boyutuyla genellikle artır
• Giriş boyutuna genellikle “n” denir
• Böylece “n”, girişin boyutunu herhangi şekilde
belirten bir niceliktir – sıralanacak sayıların sayısı, yol
için olabilir durak sayısı, vb
Algoritma analiz temelleri
• Böyle algoritmanın zamanı göstermek için genellikle
O notasyonu kullanılır;
• O(n), algoritmanın zamanı lineerdir, yani büyük n’ler için
yaklaşık olarak const*n gibi artır
• O(n2), algoritmanın zamanı kareseldir, yani büyük n’ler için
yaklaşık olarak const*n2 gibi artır
• VB
– Örneğin, sıralamanın basit algoritmalarının zamanı
O(n2) ve en iyi algoritmanın zamanı O(n log n) olarak
bilinir
Algoritma analiz temelleri
Problem: veritabanında verileri sıralamak gerekir;
•
•
•
•
Veritabanında kayıt sayısı “n”=1,000,000=106
O(n2) sıralama algoritmasının işletme zamanı n2=1012
O(n log n) algoritmasının işletme zamanı n log n=6*106
Eğer bilgisayar sanyede 10,000 işlem yaparsa, O(n2)
sıralama 108 saniye ve O(n log n) sıralama sadece 600
saniye gerekecektir!
• Veritabanlarında sıralama herhangi bilgisayar
uygulamalarında her gün defalarca yapılır, o yüzden
algoritmanın işletme zamanı büyük fark yaratır

similar documents