Bazen farkında olmasak da algoritmaları günlük hayatımızda kullanırız. Bilgisayarlardan, akıllı telefonlardan uzay bilimine kadar, algoritma günümüzde önemli bir araç veya araçların birleşimidir.
Başlıklar
Algoritma nedir?
Algoritma, bir görevi gerçekleştirmek veya bir sorunu çözmek için basit bir “ reçete”dir. Bilgisayar bilimi bu aracı özellikle programlama alanında çok kullanır.
Algoritmaların çok önemli bir yönü verimliliktir. Birçok problem için, doğru cevabı veren bir prosedür bulmak oldukça kolaydır, ancak asıl zorluk, cevabı verimli bir şekilde bulan bir algoritma bulmaktır.
Bir algoritmanın işlemleri birbiri ardına çalışıyorsa sıralı, paralel çalışıyorsa paralel algoritmadır. Algoritma, bir işlemci ağı üzerinde çalışan görevlerden yararlanırsa, dağıtılmış bir algoritmadan söz ederiz.
“Algoritma” kelimesi, 9. yüzyılda lineer ve ikinci dereceden denklemlerin çözümü üzerine ilk sistematik çalışmayı yazan matematikçi Al Khuwarizmi’nin (Orta Çağ’da Algoritmi olarak Latinceye çevrilmiştir) adından gelmektedir.
Algoritmaya bir Örnek
Abbas ve Orhan bir oyun oynarlar: Abbas 1 ile 100 arasında bir sayı düşünür ve Orhan onu tahmin etmeye çalışır. Orhan belirli bir sayı isteyebilir ve Abbas, bu sayının düşündüğü sayı olup olmadığını veya sayı düşündüğünden daha büyük veya daha küçük olup olmadığını yanıtlar.
Orhan, Abbas haklı olduğunu söyleyene kadar 1, sonra 2, sonra 3 ve bu şekilde devam edebilir. Bu algoritma çok basittir ve her zaman çalışır. Ama bunu diğer algoritmayla karşılaştıralım: Orhan 50 sayısını önererek başlar. Başarılı olursa oyun biter.
Öte yandan, Abbas sayının daha yüksek olduğunu söylerse, Orhan devam eder ve 75’i önerir. Veya Abbas sayının daha düşük olduğunu söylerse, Orhan’ın önerdiği bir sonraki sayı 25’tir. Orhan bu stratejiyi her seferinde birkaç kez tekrarlar. Abbas’in seçtiği sayıya kesin olarak ulaşana kadar olası sayıların aralığını yarıya indirir.
Bu ikinci algoritma da her seferinde cevabı bulur, ancak çok daha verimlidir. Böylece, ilk algoritmada Orhan 100’e kadar soru sormak zorunda kalabilirken, ikinci algoritmada, Abbas hangi sayıyı seçerse seçsin, Orhan en fazla 6 soru soracaktır. Bu “halving” fikri, algoritmalar alanında çok yaygındır.
Özetlemek gerekirse, algoritmik, bir çözüme götüren tanımlanmış bir sürece göre temel işlem dizilerini uygulayarak problem çözme çalışmasını içerir.
Algoritma yapısı
Algoritmalarda uygulanan kavramlar, örneğin N. Wirth’in en yaygın diller (Pascal, C, vb.) için yaklaşımına göre, sayıca azdır, iki sınıfa aittirler:
- Kontrol Yapıları
- sekanslar
- koşullu
- döngüler
- veri yapıları
- değişmezler
- değişkenler
- tablolar
- özyinelemeli yapılar (listeler, ağaçlar, grafikler)
Bu ayrımın bazen belirli diller için (Lisp, Prolog, vb.) algılanması zordur, daha çok, belirli kontrol yapılarının örtük olduğu (ve bu nedenle ortadan kaybolduğu) özyineleme kavramına dayanır.
Algoritmaların verimliliğine ilişkin bazı göstergeler
Çoğu zaman, bir algoritmanın verimliliği yalnızca asimptotik olarak bilinir, yani n parametresinin büyük değerleri için. Bu parametre yeterince küçük olduğunda, daha yüksek bir karmaşıklık algoritması pratikte daha verimli olabilir.
Bu nedenle, 30 satırlık bir diziyi sıralamak için (bu küçük bir parametredir), Hızlı Sıralama (ortalama olarak en verimli sıralama algoritmalarından biri) gibi gelişmiş bir algoritma kullanmak işe yaramaz: çoğu önemsiz sıralama algoritması yeterince verimli olacaktır.
Karmaşıklığı aynı olan iki algoritma arasında bellek işgali en düşük olanı kullanmaya çalışmak daha mantıklıdır.
Algoritmik karmaşıklık analizi, bir algoritmanın bellek kullanımını değerlendirmek için de kullanılabilir. Son olarak, girdi olarak sağlanması beklenen verilere dayanarak bir algoritmanın diğerine göre seçimi yapılmalıdır.
Bu nedenle, hızlı sıralama (veya hızlı sıralama), ilk öğeyi pivot olarak seçtiğimizde, onu zaten sıralanmış bir değerler listesine uygularsak verimsiz bir şekilde davranır. Bu nedenle, programın zaten neredeyse girdi olarak sıralanmış listeleri alması bekleniyorsa, onu kullanmak akıllıca değildir.
Dikkate alınması gereken bir diğer parametre de algoritmanın yerelliğidir. Örneğin, az belleğe sahip bir sanal bellek sistemi için (işlenecek veri sayısına kıyasla), Hızlı Sıralama normalde Yığın Sıralamadan daha verimli olacaktır. Çünkü birincisi belleğin her bir öğesinden yalnızca bir kez geçer, ikincisi ise belleğe süreksiz bir şekilde erişir (bu, değiş tokuş riskini artırır).
Son olarak, karmaşıklığı sönümlü olduğu söylenen bazı algoritmalar vardır.
Bu, algoritmanın bazı yürütmeleri için (uç durumlar), algoritmanın karmaşıklığının ortalama durumdan çok daha yüksek olacağı anlamına gelir. Tabii ki, sönümlü karmaşıklık kavramı sadece bu reaksiyonun çok marjinal olduğu durumlarda kullanılır.
