BİL204U-ALGORİTMALAR
Ünite 1: Temel Kavramlar
Giriş
Yaşantılarımızın büyük bir bölümü bilgi ve bilgi işlemeye dayalı süreçlerle devam ediyor. Eğlence, e-Ticaret, e-Öğrenme, e-Bankacılık gibi pek çok alanda bilişim sistemleri kullanılıyor. Bu sistemlerin bilgileri işleme yöntemlerini belirleyen algoritmalar da bu nedenle yaşantılarımızın çok önemli bir parçasıdır. Oyunlar, alışveriş sistemleri ya da bankacılık sistemleri gibi yazılımların özünde, aslında bilgisayarlara hedeflenen görevin gerçekleştirilmesi için hangi özel adımların hangi sırayla işlenmesi gerektiğini belirten algoritmalar bulunur. Bilgisayar yazılımları algoritmaların bilgisayarlar tarafından işletilebilen hâlleridir. Bir problemin çözülmesi için birçok strateji geliştirilebileceğinden, birçok algoritma da oluşturulabilir. Bu algoritmalar, problem durumunu farklı stratejiler, zaman maliyeti ve bellek maliyeti ile çözebilir. Bilgisayar bilimcileri de bu algoritmaların zaman ve işlem gücü bakımından verimliliğini inceler.
Algoritma Kavramı
Algoritmalar bir problemin çözümü ya da bir hesaplamanın yapılması için hazırlanmış ve genellikle bilgisayarlar tarafından yürütülen yönerge kümeleridir. Bu tanımı biraz açacak olursak; algoritmalar verileri girdi olarak alan, bu veriler üzerinde iyi tanımlanmış prosedürleri işleten ve bu işlemlerin sonucunda çıktı üreten hesaplama prosedürleridir. Bu gözle bakılacak olursa algoritmalar girdiler alan ve bunları çıktılara dönüştüren hesaplama fonksiyonlarıdır.
Algoritmalar hesaplamalı problemleri (computational problems) çözen araçlar olarak da ele alınabilir. Bu tanımdaki hesaplama yoluyla çözüm kavramı problem durumunun matematiksel olarak ve girdiler üzerinde çalışabilecek işlem adımlarının tanımlanmasını ifade etmektedir. Algoritmalar bu girdiler üzerinde tanımlı hesaplamaları yaparak çıktılar üretir. Örneğin, verilen bir sayı listesinin küçükten büyüğe doğru sıralanması hesaplamalı bir problemdir. Bu tür problemleri çözen algoritmalara sıralama algoritmaları adı verilir.
Döngüler algoritmalar içinde belirli bir şart sağlandığı sürece tekrar tekrar işletilen kod bloklarıdır.
Algoritmalar bilişim, matematik ve bilgisayar bilimleri alanlarında sıklıkla kullanılır. Matematik ve bilgisayar bilimleri alanında genellikle tekrarlı işlemler gerektiren problemlerin çözümünde kullanılırken, bilişim alanlarında verilerin işlenmesini otomatikleştiren tanımlamalar şeklinde kullanılırlar. Algoritma kavramı “bir problemin çözümü için sonlu sırada iyi tanımlanmış kurallar kümesi” şeklinde tanımlanmaktadır.
Algoritmaların Tarihçesi
Algoritma kavramı Antik Çağlardan beri bilinmektedir. Babilli (MÖ 2500) ve Mısırlı (MÖ 1550) matematikçilerin bölme işlemleri için algoritmalar kullandıkları bilinmektedir. Yunanlı (MÖ 240) matematikçilerin asal sayıları bulmak için Eratosten Kalburunu, en büyük ortak
bölenleri bulmak için de Ökli algoritmasını kullandıkları bilinmektedir. 9. yüzyılda Kindî gibi Arap matematikçilerin şifreleri kırabilmek için frekans analizlerine dayalı şifreleme algoritmaları kullanmıştır. Tarihte Mısır, Yunan ve Roma uygarlıklarında, hesaplama işlerinin herkes tarafından seri biçimde yapılabilmesi amacıyla dört işlem ve bazı basit fonksiyonlar için algoritmaların yaygın olarak kullanıldığı görülmüştür. Daha yakın zamanlarda ise (18.- 19. yy.) Araplar ve Ruslar tarafından iki temel çarpma algoritması geliştirilmiş ve kullanılmıştır. Algoritma ismi 9. yüzyılda bugün Özbekistan sınırları içinde yer alan Harezm topraklarında yaşamış Muhammed İbn Musa el Harezmi’den gelir. Hisab el-Cebir ve el-Mukabala (Cebir ve Kıyaslama) kitabı ilk cebir kitabı ve ilk algoritma koleksiyonu olarak ele alınmaktadır. Harezmi bu kitabın ön sözünde kitabı alimler için değil, matematiğin uygulamasını yapan kişiler için yazdığını belirtmiştir. Batı dillerinde algoritma kavramının en eski kullanımları İngiliz (1230 ve 1391 yıllarında Chaucer) ve Fransız (1240 Alexandre de Villedieu) yazarlar tarafından yapılmıştır. Fakat bu kullanımlar daha çok ondalıklı sayılarla hesaplama yapılmasını ifade etmektedir.
Algoritmaların Özellikleri
Bir algoritmanın aşağıdaki özelliklere sahip olması gerekir.
1. Girdi 2. Çıktı 3. Açıklık 4. Sonluluk 5. Başarım ve Performans 6. Bağımsızlık
Algoritmanın Verimliliği
Algoritmalar bilgisayar programlarının temelini oluşturur. Bir bilgisayar sisteminde aynı anda onlarca program (uygulama) yürütülmeye çalışılır. İşletim sistemlerindeki görev yöneticiler incelendiğinde sistem üzerinde bir anda çalıştırılmakta olan uygulama sayısı görülebilir. Her bir görevin işletilmesi için işlemci zamanı ve ana bellek alanı (RAM) zorunlu olduğundan, bilgisayar sistemlerindeki en değerli kaynaklar bu ikisidir. Bu iki kaynağın tükenmesi bilgisayar sisteminin çalışamaz hâle gelmesi anlamına gelmektedir. Bu nedenle algoritmaların verimliliği, çözüm üretmek için kullandıkları bilgisayar kaynakları dikkate alınarak belirlenir.
Bir bilgisayar programının, dolayısıyla da algoritmanın çözüm üretmek için harcadığı işlemci zamanı, algoritmanın zaman karmaşıklığını ifade eder. Bilgisayar sistemlerinde kullanılan işlemcilerin bir saniye içinde yapabilecekleri işlem sayıları değişkendir. Algoritmanın alan karmaşıklığı ise çözüm üretmek için harcadığı bellek alanı ile ilgilidir. Algoritma tarafından tanımlanan her bir değişken ya da her bir fonksiyon çağrısının bir bellek maliyeti bulunur.
Algoritma Türleri
Farklı görevleri yerine getirmek amacıyla birçok algoritma türü geliştirilmiştir.
Arama Motoru Algoritmaları
Metinler ve işleçleri girdi olarak (ör.: “izmir VE konser”) alan, ilgili veri tabanı üzerinde arama yapıp olası sonuçları öneren (ör.: internet siteleri, restoranlar, kitaplar, kişiler) algoritmalardır. İnternet siteleri ya da kütüphanelerdeki kitapları bulmaya yarayan arama motorlarında bu algoritmalar kullanılmaktadır.
Şifreleme Algoritmaları
Girdi olarak verilen bilgileri korumak amacıyla, bu verileri işleyerek dönüştüren algoritmalardır (Kitabınızın 7 sayfasında şekil 1.2). AES (Advanced Encryption Standard-Gelişmiş Şifreleme Standardı) gibi simetrik anahtarlı algoritmalar şifreleme ve çözümleme amacıyla aynı anahtarları kullanırken RSA (Rivest-Shamir- Adleman) gibi algoritmalar şifreleme ve çözümleme için genel (public key) ve özel (private key) anahtarlar kullanabilmektedir. Şifreleme algoritmaları anahtarlar yoluyla verileri şifreleyebilir ve çözümleyebilir.
Açgözlü (Greedy) Algoritmalar
Bu algoritmalar optimizasyon problemlerinin çözümü için bilinen verilere dayalı kararlar verir. Kısıtlı verilere dayanarak çözüm arandığından bu algoritmalar en iyi çözümü garanti etmezler. Şehirler arası bir yolculuk için en kısa yolu arayan açgözlü bir algoritma bir sonraki şehrin seçiminde her zaman en kısa yolu tercih edebilir.
Özyinelemeli (Recursive) Algoritmalar
Özyinelemeli algoritmalar bir problemin çözümüne ulaşabilmek için kendi kendilerini sürekli çağırırlar. Bu algoritmaların en bilinen örneği, bir sayının faktöriyelinin hesaplanmasıdır. Bu amaçla tanımlanan fonksiyon içinde parametre olarak gelen sayının 1’den büyük olma durumu kontrol edilir. Sayı 1 ise geriye 1 değeri döndürülür. Sayı 1’den büyükse fonksiyon içinden aynı fonksiyona sayının 1 eksiği ile çağrı yapılır ve bu çağrıdan gelen değer sayı ile çarpılarak geri çevrilir.
Kaba Güç (Brute-force) Algoritmaları
Kaba güç algoritmaları verilen problemin çözümü herhangi bir strateji geliştirmeden tüm olasılıkları deneyen algoritmalardır. Bu algoritmaların çalışma stili dört haneli bir şifrenin bulunması için 0000’dan başlayarak 9999’a kadar tüm sayıların denenmesine benzetilebilir.
Sıralama Algoritmaları
Sıralama algoritmaları girdi olarak verilen veri setini, belirlenen kriterlere göre düzene koyan algoritmalardır. Bir sıralama algoritması verilen girdi setini küçükten büyüğe ya da büyükten küçüğe doğru sıralayarak çıktı verebilir. Sıralama algoritmaları ile verilerin sıralanması sayesinde verilerin insanlar tarafından daha rahat okunması ya da aranan değerlerin daha kolay bulunması sağlanabilir. Oldukça sık kullanılan bir işlem olduğundan sıralama işleminin zaman ve alan bakımından verimli yapılabilmesi çok önemlidir. Kabarcık sıralaması anlaşılması en kolay sıralama algoritmaları arasındadır. Bu stratejide veri kümesinde yan yana iki element birbirleri ile karşılaştırılır.
Gerileme (Backtracking) Algoritmaları
Gerileme algoritmaları, verilen problemler gelişen çözüm ağaçları oluşturarak çözmeye çalışır.
Böl ve Fethet (Divide and Conquer) Algoritmaları
Böl ve fethet algoritmaları verilen problemleri üç aşamada çözümler. Öncelikle problem durumu daha küçük problem durumlarına bölünür. Her bir alt problem kendi içinde çözümlendikten sonra bu çözümler birleştirilerek ana problemin çözümüne ulaşılır. Böl ve fethet algoritmalarının en klasik uygulamalarından biri tümleştirerek ayıklama (merge sort) sıralama algoritmasıdır. Bu algoritmada verilen girdi seti sürekli ikiye bölünerek tekil elementlere ulaşılır. Daha sonra bu tekil elementler önce kendi aralarında sıralı alt listelere dönüştürülür. Bu işlemler tekrarlandıkça sıralı tam liste oluşturulmuş olur.
Dinamik Programlama Algoritmaları
Dinamik programlama algoritmaları da problemleri küçük alt problemlere bölerek çözümler. Bununla birlikte, bu yaklaşımda çözümler saklanarak ileriki hesaplamalara uygulanır. Dinamik programlama özünde özyinelemenin optimizasyonudur. Özyineleme yoluyla çözülebilecek problemler dinamik programlama yaklaşımı ile çözülebilir. Üretilen ara çözümlerin saklanması sayesinde ara hesaplamaların tekrar yapılmasına gerek kalmaz. Bu sayede özellikle özyinelemeli işlemlerde işlem yükü ciddi oranda azaltılabilir. Bu süreç Fibonacci sayılarının bulunması ile açıklanabilir. Fibonacci dizilerinde bir elementin değeri kendisinden önce gelen iki elementin değerinin toplamı yoluyla bulunur. Bu dizide elementlerin sıra numarası arttıkça elementlerin birbirine oranı altın orana (1,618) yaklaşır. Fibonacci dizileri istenen iki sayı ile başlatılabilir.
Karıştırma (Hashing) Algoritmaları
Karıştırma algoritmaları girdi olarak verilen herhangi bir uzunluktaki değerleri karıştırma fonksiyonuna tabi tutarak birörnek çıktılar üretir. Üretilen çıktılar verilen girdinin uzunluğu ya da içeriğine bakılmaksızın aynı uzunluktadır.
Rastgele (Randomized) Algoritmalar
Rastgele algoritmalar, zaman ve bellek kullanımı kısıtları altında çözüm üretebilmek için rastgele değerleri kullanırlar. Bu algoritmalar verilen bir aralıkta rastgele değer üreterek bu değerler üzerinden sonuç üretebilirler. Kaba kuvvet algoritmalarında tüm olası değerler denenirken rastgele algoritmalarda, olası değerler arasından rastgele seçimler yapılmaktadır. Doğal olarak rastgele algoritmalar kesin doğru çözümler üretemeyebilir fakat verilen zaman ve bellek alanı kısıtları içinde kabul edilebilir çözümler üretilmesine olanak tanırlar. Rastgele algoritmaların önemli örneklerinden biri Monte Carlo tekniğidir. Monte Carlo tekniği sayısal değerlerin hesaplanması için yüksek sayıda rastgele değer üretilmesi esasına dayanır. Pi sabitinin yakınsak değerlerinin bulunması için bu teknik kullanılabilir.