OBEB – Öklid Algoritması
Transkript
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