OBEB – Öklid Algoritması

Galatasaray Üniversitesi
Bilgisayar Mühendisliği Bölümü
INF101
Bilgisayar Mühendisliğine Giriş
09/12/2013 - Programlama Dilleri
Ozan Çağlayan
[email protected]
ozancaglayan.com
Başlarken
●
●
İlk bilgisayarlar bir fabrika kadar enerji
tüketen, birkaç oda büyüklüğünde ve milyon
dolarlara mâl olan (1940) cihazlardı.
Tüm bu devasalığın getirdiği hesaplama gücü,
günümüzün hesap makinelerinden daha fazla
değildi.
Başlarken
UNIVAC 1232
Başlarken
Delikli Kart
Makine Dili
1st Generation Languages (1GL)
●
●
●
O zamanın programcıları bu bilgisayarları
doğrudan makine diliyle programlıyorlardı,
Makine dili, bir işlemciyi doğrudan kontrol
ederek
işlemcinin
toplama,
çıkarma,
karşılaştırma gibi temel işlemleri yapmasını
sağlayan bit serileridir,
Programları bu seviyede tasarlamak inanılmaz
güç ve karmaşıktır.
Makine Dili
1st Generation Languages (1GL)
●
●
2 tamsayının ortak bölenlerinin en büyüğünü
(OBEB) Öklid yöntemiyle hesaplayan program:
MIPS mimarisinin makine dilinde yazılan
program, 16'lık rakamlarla ifade edilmiştir.
Assembly
2nd Generation Languages (2GL)
●
●
İnsanlar daha büyük programlar yazmaya
başlayınca, hataya daha az açık bir gösterimin
gerekliliği ortaya çıktı.
Assembly dilleri, işlemlerin daha anlaşılabilir
şekilde ifade edilmesini sağlamak için
geliştirildiler.
Assembly
2nd Generation Languages (2GL)
●
Makine dilinde yazılan OBEB programının
MIPS Assembly dilindeki karşılığı:
Assembly
2nd Generation Languages (2GL)
●
Makine dilinde yazılan OBEB programının
MIPS Assembly dilindeki karşılığı:
Mnemonik (Anımsatıcı)
Assembly
2nd Generation Languages (2GL)
●
●
●
Assembly dilleri daha okunabilir olsalar da,
mimariye özel olarak geliştirilmişlerdir,
Her işlemci mimarisinin kendine özel komutları
ve dolayısıyla kendine özel bir Assembly dili
vardır,
Assembly dilindeki kaynak kod, Assembler adlı
yazılımla makine koduna dönüştürüldükten
sonra çalıştırılabilir hâle gelir.
Assembly
2nd Generation Languages (2GL)
●
İşlemci ailesi/mimari odaklı programlama
pratiği programcıların,
–
Her farklı makine için programı tekrar
kodlamalarına,
–
Tasarım esnasında makinenin yeteneklerine
göre düşünmelerine,
yol açıyordu.
Arayış
●
Makine/Mimari bağımsız
●
Daha okunabilir
●
Matematiksel hesaplamaların kolayca ifade
edilebileceği
Genel amaçlı bir programlama dili arayışı!
Arayış
●
Makine/Mimari bağımsız
●
Daha okunabilir
●
Matematiksel hesaplamaların kolayca ifade
edilebileceği
Genel amaçlı bir programlama dili arayışı!
1950'lerin ortası FORTRAN
Daha sonra
ALGOL, COBOL, ...
Yüksek Seviyeli Diller
3rd Generation Languages (3GL)
●
●
2GL diller yazılıma mantıksal bir yapı getirdi
3GL diller ise bu yapıyı ileriye götürüp daha
programcı dostu olmayı hedefledi:
–
Yazılımı bilgisayara göre değil, insana göre ifade
etmek,
–
Programcı açısından önemsiz detaylarla ilgilenme
görevini programcıdan bilgisayara devretmek.
Yüksek Seviyeli Diller
3rd Generation Languages (3GL)
●
İlk olarak FORTRAN (FORmula TRANslation)
●
ALGOL, COBOL, C, C++, Java, BASIC, Pascal, ...
●
Günümüzde kullanılan genel amaçlı dillerin
büyük çoğunluğu 3GL dillerdir.
●
Yüksek seviyeli
İnsana yakın
●
Düşük seviyeli
Makineye yakın
Yüksek Seviyeli Diller
3rd Generation Languages (3GL)
●
●
Yüksek seviyeli dillerde yazılmış kodları
assembly veya makine diline çeviren
yazılımlara derleyici (compiler) adı verilir.
Derleyici tasarımı önemli çünkü yüksek
seviyeli
dillerde
yazılan
programların
performansına doğrudan etkiyor.
Yüksek Seviyeli Diller
3rd Generation Languages (3GL)
●
C
C ve Python dillerinde OBEB örneği:
int gcd(int a, int b) {
if (b == 0)
return a;
else
return gcd(b, a % b);
}
Yüksek Seviyeli Diller
3rd Generation Languages (3GL)
●
C
C ve Python dillerinde OBEB örneği:
int gcd(int a, int b) {
if (b == 0)
return a;
else
return gcd(b, a % b);
}
def gcd(a, b):
if b == 0:
return a
Python
else:
return gcd(b, a % b)
Alana Özel Diller
Domain Specific Languages (DSL)
●
Genel amaçlı olmayan, özel bir uygulama
alanı için tasarlanmış programlama dilleri
●
HTML, XML, SGML, vb.. (İşaretleme dilleri)
●
Verilog & VHDL (Donanım betimleme dilleri)
●
MATLAB, GNU Octave (Bilimsel programlama)
●
Mathematica, Maxima (Sembolik Matematik)
●
...
Alana Özel Diller
Domain Specific Languages (DSL)
●
MATLAB'da OBEB örneği:
x = gcd(12,24)
●
MATLAB, matematiksel ve bilimsel
programlama alanına özel bir dil olduğu için,
OBEB işini yapan gcd() fonksiyonu içinde
mevcut!
Çalışma Modelleri
Execution Models
Yorumlamalı
(Interpreted)
Compiled
(Derlemeli)
Çevrimli
(Translated)
Yorumlamalı Diller
Interpreted Languages
●
●
●
Yorumlamalı dillerde yazılan programlar,
makine koduna derlenmeden, satır satır
çalıştırılırlar,
Programın kaynak kodunu dinamik olarak
makine koduna dönüştürerek çalıştıran araca
yorumlayıcı (interpreter) adı verilir.
Makine koduna dönüştürülmüş bir programı
ilk işleyen işlemci iken, yorumlamalı dilde
yazılan kodu ilk işleyen başka bir yazılımdır.
Yorumlamalı Diller
Interpreted Languages
●
Platform-bağımsız
–
●
Hızlı geliştirme ve prototipleme süreci
–
●
Kaynak kodu dağıtmak, çalıştırmak için
yeterli
Kod tekrar derlenmeden hemen değiştirilip
tekrar çalıştırılabilir
Kodun yorumlanarak çalıştırılması, derlenmiş
programa göre genellikle yavaş
Çalışma Modelleri
Execution Models
Yorumlamalı
(Interpreted)
Compiled
(Derlemeli)
Çevrimli
(Translated)
Çalışma Modelleri
Execution Models
Yorumlamalı
(Interpreted)
ASP, PHP
ActionScript
JavaScript
Octave
MATLAB
Perl, Python
Lua, R
Awk, Shell
Java, .NET
Compiled
(Derlemeli)
Çevrimli
(Translated)
Derlemeli Diller
Compiled Languages
●
●
●
Derleyici tarafından makine diline
dönüştürülen dillerdir,
Doğrudan makine dilinde veya assembly'de
yazılmış programlara çok yakın ~ aynı
performansta sonuç alınmasını sağlarlar,
Yazılım geliştirme sürecinde kaynak kodlar
her değişiklikten sonra tekrar derlenmelidir.
Çalışma Modelleri
Execution Models
Yorumlamalı
(Interpreted)
ASP, PHP
ActionScript
JavaScript
Octave
MATLAB
Perl, Python
Lua, R
Awk, Shell
Java, .NET
Compiled
(Derlemeli)
Çevrimli
(Translated)
Çalışma Modelleri
Execution Models
Yorumlamalı
(Interpreted)
ASP, PHP
ActionScript
JavaScript
Octave
MATLAB
Perl, Python
Lua, R
Awk, Shell
Java, .NET
Compiled
(Derlemeli)
FORTRAN
Ada, ALGOL
Cobol, BASIC
Pascal, Delphi
C, C++
Objective-C
Go
LISP
Çevrimli
(Translated)
Arakod
Intermediate Representation
●
Melez yaklaşım
–
Amaç: Yorumlamalı ve derlemeli dillerin
avantajlarını en az performans kaybı olacak
şekilde birleştirmek,
Arakod
Intermediate Representation
●
Melez yaklaşım
–
Amaç: Yorumlamalı ve derlemeli dillerin
avantajlarını en az performans kaybı olacak
şekilde birleştirmek,
–
Kaynak kod önce arakoda derlenir, sanal makine
adı verilen yorumlayıcı bu arakodu dinamik olarak
çalıştırır.
–
Bu arakod genelde bytecode olarak adlandırılır.
Çalışma Modelleri
Execution Models
Yorumlamalı
(Interpreted)
ASP, PHP
ActionScript
JavaScript
Octave
MATLAB
Perl, Python
Lua, R
Awk, Shell
Java, .NET
Compiled
(Derlemeli)
FORTRAN
Ada, ALGOL
Cobol, BASIC
Pascal, Delphi
C, C++
Objective-C
Go
LISP
Çevrimli
(Translated)
Çalışma Modelleri
bytecode
Execution Models
Yorumlamalı
(Interpreted)
ASP, PHP
ActionScript
JavaScript
Octave
MATLAB
Perl, Python
Lua, R
Awk, Shell
Java, .NET
Compiled
(Derlemeli)
FORTRAN
Ada, ALGOL
Cobol, BASIC
Pascal, Delphi
C, C++
Objective-C
Go
LISP
Çevrimli
(Translated)
Çalışma Modelleri
bytecode
Execution Models
Yorumlamalı
(Interpreted)
ASP, PHP
ActionScript
JavaScript
Octave
MATLAB
Perl, Python
Lua, R
Awk, Shell
Java, .NET
Compiled
(Derlemeli)
FORTRAN
Ada, ALGOL
Cobol, BASIC
Pascal, Delphi
C, C++
Objective-C
Go
LISP
Çevrimli
(Translated)
Dönüştürücü bir
program tarafından
derleyicisi olan
hedef bir dile
çevrildikten sonra o
dilin derleyicisiyle
derlenen
diller.
(Pek yaygın değil)
Nesneye Yönelik Programlama
Object Oriented Programming (OOP)
●
●
Klasik programlama modelinde, programlar
yapılacak işlerin bir listesi olarak görülürler,
Okunabilirlik, modülerlik ve tekrar kullanılabilirlik
açısından sıkça kullanılan işler bir fonksiyon
olarak tanımlanabilirler:
–
Bir sayı kümesinin ortalamasını alan fonksiyon
–
Bir sayı kümesinin en küçük elemanını bulan
fonksiyon
–
...
Nesneye Yönelik Programlama
Object Oriented Programming (OOP)
●
●
OOP modelindeyse birbirleriyle etkileşime
giren nesneler vardır:
–
Sınıflar bir kavramın soyut tanımlarıdır,
–
Nesneler sınıflardan yaratılan somut görüntülerdir,
–
Nesnelerin özellikleri ve bu özellikler üzerinde
işlem yapabilen metodları vardır.
C++, Java, Smalltalk, Perl, Objective-C, Python,
Ruby, C#, vb.
Nesneye Yönelik Programlama
Object Oriented Programming (OOP)
●
●
●
Grafik arayüz tasarımında, web
programlamada oldukça sık kullanılır,
Sıkı fanatikleri ve sıkı karşıtları vardır,
OOP klasik modelden daha iyidir veya tersi
gibi kesin bir yargı yoktur ve olamaz:
–
Her dil ve yaklaşım belirli kullanım alanları için
daha idealdir.
Nesneye Yönelik Programlama
Object Oriented Programming (OOP)
Sınıf
Telefon
Nokia 3310
Galaxy S3
Iphone 5
Alt-sınıf
Nesne
Nesneye Yönelik Programlama
Object Oriented Programming (OOP)
benim_telefonum = new Nokia3310()
benim_telefonum.ara(“4440333”)
benim_telefonum.sms_gonder(“05353453434”, “naber?”)
nesne
metod
çağrısı
benim_telefonum nesnesi
Nokia3310 sınıfından üretiliyor
Esin kaynağı diller
Esin kaynağı diller
Programlama Dilleri
●
●
●
Programlama dilleri, bilgisayar bilimlerinin
merkezi bir elemanıdır,
Öğrenciler, 1-2 programlama diliyle yoğunca
vakit geçirdikten sonra genelde başka dilleri
merak etmeye başlarlar,
Dil öğrenmek ilginçtir ve sizi geliştirir.
Peki programlama nedir?
“Programming is the art of telling another
human what one wants the computer to do.”
“Programlama, bilgisayara ne yaptırmak
istediğini, başka bir insana anlatma
sanatıdır.”
Donald Knuth
Problemler
●
Problemler geneldir,
●
Örnek:
–
●
Bir tamsayı kümesindeki en küçük değeri bulun.
Belli bir veri kümesi için problemin somut
görünümü:
–
{17, 6, 42, 24} kümesindeki en küçük değeri bulun.
Problem Tanımı
●
Kötü örnek:
–
En küçük elemanın sırasını bulun.
●
●
{4, 2, 5, 2, 42} kümesi için 2 yanıt var = {2, 4}
İyi örnek:
–
L en küçük değerlerin sıralarından oluşan küme
olsun. L 'nin en küçük elemanını bulun.
Problem Tanımı
●
İyi örnek:
–
L en küçük değerlerin sıralarından oluşan küme olsun. L
'nin en küçük elemanını bulun.
{4, 2, 5, 2, 42}
L = {2, 4}
min(L) = 2
Algoritma
“Düzgünce ortaya konmuş bir problemin
çözüm sürecinin detaylı tanımı”
“Problem verisi üzerinde çalışarak
amaçlanan sonuca varan işlem serisi”
Algoritma
Programlamadan önce problemin nasıl
çözüleceğini tanımlayın (Soyutlama)
Algoritma
●
●
●
●
İnsan tarafından anlaşılabilir olmalıdır,
Bir programlama diline, derleyiciye veya
makineye bağımlı değildir,
Çok büyük olmayan problemler için akış
diyagramıyla ifade edilebilir,
pseudo-code adı verilen ve anlatımı öne
çıkaran basit dillerde ifade edilebilir.
Akış Diyagramları
Pseudocode (Sözdekod)
●
●
Bir algoritmanın işleyişinin yüksek seviyeli bir
tanımı,
Programlama dillerini andıran bir yapısı olsa da
aslında bazı basit kuralları olan, konuşma diline
yakın bir anlatım tarzıdır.
Algoritmalar size yabancı mı?
IKEA masa parçaları
Kurulum Kılavuzu
Masa
Yumurta, süt, un
Kek Tarifi
Kek
2 tane 6 haneli sayı
Toplama
Toplam
Öğrenci listesi
Labirent haritası
Sıralama Algoritması
Çıkış Algoritması
Sıralı liste
Çıkış
Basit bir örnek
Klavyeden bir sayı bekle
Sayıyı A değişkenine kaydet
Klavyeden bir sayı bekle
Sayıyı B değişkenine kaydet
A+B'yi T değişkenine kaydet
T'yi ekrana yazdır Pseudocode
A = input(“Bir sayı girin: “)
B = input(“Bir sayı girin: “)
T = A + B
Python
print “Toplam: “, T
int A, B, T;
printf(“Bir sayı girin: “);
scanf(“%d”, &A);
printf(“Bir sayı girin: “);
scanf(“%d”, &B);
T = A + B;
printf(“Toplam: %d\n”, T);
C
OBEB'e geri dönersek...
●
●
OBEB
–
Hem a'yı hem b'yi kalansız bölen en büyük
tamsayı.
–
OBEB(8, 12) = 4
Nasıl hesaplarız?
OBEB “brute-force” yöntem
1 a ve b'den küçük olanı t değişkenine kaydet
2 a'nın t'ye bölümünden kalan 0 değilse VEYA
b'nin t'ye bölümünden kalan 0 değilse;
t'y 1 azalt ve 2. adıma geri dön.
3 Cevap t'dir.
Pseudocode
def obeb(a,b):
t = min(a,b)
while a % t != 0 or b % t != 0:
t = t – 1
return t
Python
OBEB “brute-force” yöntem
In [12]: %timeit obeb(100, 24)
100000 loops, best of 3: 4.24 us per loop
In [13]: %timeit obeb(461952, 116298)
10 loops, best of 3: 19.1 ms per loop
●
●
●
100 ve 24 sayılarının OBEB'i kaba kuvvet algoritmayla
ortalama 4.24 mikrosaniyede hesaplanıyor.
461952 ve 116298 sayılarının OBEB'i kaba kuvvet
algoritmayla ortalama 19.1 milisaniyede hesaplanıyor.
Daha iyi bir algoritma olamaz mı?
OBEB – Öklid Algoritması
●
●
Kaba kuvvet yöntemden çok daha hızlı çalışan
bir algoritma yaklaşık 2000 yıl önce Euclid
tarafından keşfedilmiş,
a ve b'nin OBEB'i, b ve a'nın b'ye
bölümünden kalan sayının OBEB'iyle
aynıdır.
OBEB – Öklid Algoritması
a ve b ile
başla
b=0 mı?
EVET
OBEB(a,b) = b
HAYIR
b = a % b
a = b
OBEB – Öklid Algoritması
1
a = 54
b = 36
b=0 mı?
EVET
OBEB(a,b) = b
HAYIR
b = 54 % 36
a = 36
OBEB – Öklid Algoritması
2
a = 36
b = 18
b=0 mı?
EVET
OBEB(a,b) = b
HAYIR
b = 36 % 18
a = 18
OBEB – Öklid Algoritması
3
a = 18
b = 0
b=0 mı?
b = 36 % 18
a = 18
HAYIR
EVET
OBEB(a,b) = b
18
OBEB – Öklid Algoritması
def obeb_euclid(a,b):
if b == 0:
return a
return obeb_euclid(b, a % b)
OBEB – Öklid Algoritması
def obeb_euclid(a,b):
if b == 0:
return a
return obeb_euclid(b, a % b)
In [12]: %timeit obeb_euclid(100, 24)
100000 loops, best of 3: 768ns per loop
In [13]: %timeit obeb_euclid(461952, 116298)
10 loops, best of 3: 2.11us per loop
●
●
~4 mikrosaniye -> 0.8 mikrosaniye
~20 milisaniye -> 0.002 milisaniye
OBEB – Öklid Algoritması
def obeb_euclid(a,b):
if b == 0:
return a
return obeb_euclid(b, a % b)
In [12]: %timeit obeb_euclid(100, 24)
100000 loops, best of 3: 768ns per loop
In [13]: %timeit obeb_euclid(461952, 116298)
10 loops, best of 3: 2.11us per loop
●
●
~4 mikrosaniye -> 0.8 mikrosaniye
~20 milisaniye -> 0.002 milisaniye
~116298 adım
~8 adım
OBEB – Öklid Algoritması
def obeb_euclid(a,b):
if b == 0:
return a
return obeb_euclid(b, a % b)
In [12]: %timeit obeb_euclid(100, 24)
100000 loops, best of 3: 768ns per loop
In [13]: %timeit obeb_euclid(461952, 116298)
10 loops, best of 3: 2.11us per loop
~8 adım
(461952, 116298)
(116298, 113058)
(113058, 3240)
(3240, 2898)
(2898, 342)
(342, 162)
(162, 18)
(18, 0)
“Bilgisayar bilimleri, bir problemi doğru şekilde
modelleyerek problemi çözmek için uygun tekniği
ortaya çıkaran bir soyutlama bilimidir.”
Alfred Aho & Jeffrey Ullman
“Yukarıdaki koddaki hatalara dair temkinli olun;
ben sadece doğru olduğunu kanıtladım,
denemedim.”
Donald Knuth
Kütüphanede
mevcut!
“Yukarıdaki koddaki hatalara dair temkinli olun;
ben sadece doğru olduğunu kanıtladım,
denemedim.”
Donald Knuth
Dijkstra en kısa yol (Shortest path) algoritması
“Astronomi ne kadar teleskoplarla ilgiliyse,
bilgisayar bilimleri de en fazla o kadar
bilgisayarlarla ilgilidir.”
Edsger W. Dijkstra
Katedral ve Pazar (ücretsiz e-kitap)
http://www.emo.org.tr/ekler/d362d95ed1876eb_ek.pdf
“Nasıl ki fırça ve boyaları derinlemesine bilmek
kişiyi usta bir ressam yapmaz ise, bilgisayar
bilimleri eğitimi almak da kişiyi usta bir
programcı yapmaz.”
Eric S. Raymond
Bilgisayar Bilimlerinin
Temel İlgi Alanları
●
Hesaplanabilirlik
–
Bir problem verildiğinde, o problemi çözen bir
algoritma olup olmadığını gösterebilir miyiz?
–
Hangi problemler için hiç algoritma mevcut
değildir? Nasıl sınıflandırabiliriz?
Bilgisayar Bilimlerinin
Temel İlgi Alanları
●
Karmaşıklık
–
Algoritmam ne kadar sürede sonuca ulaşıyor?
–
Algoritmam ne kadar bellek kullanıyor?
–
Algoritmam iyi mi yoksa daha iyisi mevcut mu?
Bilgisayar Bilimlerinin
Temel İlgi Alanları
●
Doğruluk
–
Bir algoritmanın daima sonuca ulaştığından emin
olabilir miyiz?
–
Bir algoritmanın daima doğru sonuca ulaştığından
emin olabilir miyiz?
Bazı kriterler
●
Sadelik: KISS! (Keep it simple and stupid)
●
Verimlilik: Hızlı, az bellek kullanımı.
●
Kararlılık: Girdideki ufak bir değişiklik çıktıyı
etkilememeli.
Verimlilik
●
Gözleme dayalı (Ampirik)
–
Gerçeklenen algoritmanın ne kadar sürede çözüme
ulaştığını, düz çalışma zamanından çıkartırsak, bu
karşılaştırılabilir bir ölçü olmaz çünkü:
●
–
Makineye, dile, programcıya, derleyiciye, derleyici
seçeneklerine, işletim sistemine, ... göre değişebilir.
Örnek: OBEB örneğinde yaptığımız süre bazlı
karşılaştırma.
Verimlilik
●
Matematiksel
–
Toplam (temel) işlem sayısını, girdinin uzunluğu
cinsinden ifade etmek daha basit, genel geçer ve
yeterli bir ölçü yöntemidir.
–
“big Oh” gösterimi: O()
–
O(1), O(n), O(n2), O(lg(n)), ... sınıfı algoritmalar
Faydalı Linkler
●
https://developers.google.com/edu/python/?csw=1
●
http://learnpythonthehardway.org/book/
●
https://cs.uwaterloo.ca/~shallit/Courses/134/history.html
●
http://en.wikipedia.org/wiki/History_of_computer_science
●
http://scratch.mit.edu/
●
http://www.repl.it
●
http://www.youtube.com/watch?v=kPRA0W1kECg
●
http://www.youtube.com/user/AlgoRythmics/videos
Galatasaray Üniversitesi
Bilgisayar Mühendisliği Bölümü
Sorusu olan?
Ozan Çağlayan
[email protected]
ozancaglayan.com