Algoritma, Matematik, Bilgisayar Bilimi gibi ilgili alanlarda, bir aktivitenin onu gerçekleştiren kişi için ardışık adımlarla yürütülmesine izin veren, yeniden yazılmış, iyi tanımlanmış, sıralı ve sonlu talimatlar veya kurallar kümesidir.
Programlamada Algoritma Nedir?
Bir başlangıç durumu ve bir girdi verildiğinde, birbirini izleyen adımların ardından, son bir duruma ulaşılır ve bir çözüm elde edilir.
Tarihi
Algoritma kelimesi, aslen USSR’de bulunan eski Khowarism kentinden olan 9. yüzyıl Arap matematikçisi olan Muḥammad ibn Mūsā al-Khwārizmī’den gelmektedir. Ünlü matematikçi dört çok basamaklı aritmetik işlem için kuralları formüle etmeyi başardı.
Daha sonra bu formül genel olarak herhangi bir matematiksel görevin çözümüne götüren işlem dizilerini belirlemek için kullanılmaya başlandı.
Zaman geçtikçe, algoritmaları arama ve resmileştirme süreci sadece matematikçiler için bir görev olmaktan çıkarak farklı algoritma türleri elde edilmeye başlandı.
Böylece, nesnelerin bir sonraki adımını seçmenin gerekli olduğu şekiller ve pozisyonları içeren dama ve satranç gibi oyunlar için algoritmalar ortaya çıktı.
Bunlar bir elektrik akımının veya belirli bir makinenin eylemleridir veya örneğin, metinlerin kullanıldığı bir sözlükteki bir kelime için arama algoritmasıdır.
Ancak her durumda, algoritmaların gerçek dünyadaki nesnelerle değil, bunların temsilleri ve soyutlamalarıyla çalıştığı dikkate alınmalıdır. Bu nedenle değişkenler, semboller, kodlamalar onları belirtmek için kullanılır.
Özellikleri
Algoritmalar günlük yaşamda birçok kez problemleri çözmek için de kullanılır. Örneğin, bir cihazı kullanmaya yönelik algoritmaları veya bir çalışanın işvereninden aldığı talimatları gösteren kullanım kılavuzlarıdır.
Matematikte algoritma kullanıma örnek olarak, iki sayının bölümünü hesaplamak için bölme algoritması, iki pozitif tamsayının en büyük ortak bölenini elde etmek için Öklid algoritması veya doğrusal bir denklem sistemini çözmek için Gauss yöntemidir.
Genel olarak, bir algoritmanın resmi tanımı konusunda kesin bir fikir birliği yoktur. Pek çok yazar bunlardan soyut bir problemi çözmek için talimat listeleri olarak, yani bir problemin verilerini çözüme dönüştüren sınırlı adım sayısı olarak adlandırır.
Ancak, bazı algoritmaların belirli bir problemi bitirmesi veya çözmesi gerekmediği unutulmamalıdır. Örneğin, Eratosthenes eleğinin asal sayıları hesaplamayı asla bitirmeyen değiştirilmiş bir versiyonu hala bir algoritmadır.
Tarih boyunca, birçok yazar algoritmaların yanı sıra Turing makineleri gibi matematiksel modelleri kullanarak tanımlamaya çalıştı.
Bununla birlikte, bu modeller sayılar, semboller veya grafikler gibi belirli bir veri türüne tabidir. Ancak genel olarak algoritmalar büyük miktarda veri yapısı üzerinde çalışır.
Genel olarak, paralel algoritmaları dikkate almadığımız sürece, tüm tanımlardaki ortak kısım üçe ayrılabilir.
1. Sequential Time/Sıralı Zaman
Bir algoritma ayrıklaştırılmış zamanda adım adım çalışır, böylece her geçerli giriş için bir dizi hesaplama durumu tanımlar.
2. Abstract State/Soyut Durum
Her hesaplama durumu, bir birinci dereceden yapı kullanılarak tanımlanabilir ve her algoritma, uygulamasından bağımsızdır. Böylece bir algoritmada birinci dereceden yapılar, izomorfizm altında değişmezdir.
3. Bounded State/Sınırlı Durum
Bir durumdan diğerine geçiş tamamen sabit ve sonlu bir tanımla belirlenir. Kısacası, her durum ile bir sonraki arasında, mevcut durumun yalnızca sabit ve sınırlı sayıda terimi hesaba katılabilir.
Kısacası, bir algoritma, adım adım çalışan, her adımın belirli bir bilgisayara atıfta bulunmadan açık bir şekilde tanımlanabildiği ve ayrıca bir adımda okunabilen/yazılabilen veri miktarı için sabit bir limiti olan bir çözüm yöntemidir.
Bu geniş tanım, hem pratik algoritmaları hem de yalnızca teoride işe yarayanları kapsayabilir. Örneğin, Newton yöntemi ve Gauss-Jordan eleme çalışması, en azından prensipte sonsuz bir şekilde çalışır. Ancak bir bilgisayarda sonsuz bir işlem programlamak mümkün değildir.
Özellikle, hesaplanabilir her fonksiyonun bir Turing makinesinde programlanabileceğini doğrulamak için kullanılabilecek dördüncü bir özellik olarak Aritmetize düşünülebilir. İlk adımda yalnızca işlenemeyen hesaplanabilir işlemler mevcuttur.
Araçlar
Algoritmalar, doğal dil, pseudocode (sahte kod), akış şemaları ve programlama dilleri dahil olmak üzere birçok şekilde yapılabilir.
Doğal dil açıklamaları belirsiz ve uzun olma eğilimindedir. Ancak sahte kod ve akış şemaları kullanmak, birçok doğal dil belirsizliğini ortadan kaldırır.
Bu ifadeler, algoritmaları temsil etmenin daha yapısal yollarıdır. Ancak, belirli bir programlama dilinden bağımsız kalırlar.
Bir algoritmanın açıklaması genellikle üst düzey ifade, şekilsel ve uygulama olarak yapılır.
Üst düzey açıklamada, problem kurulur, matematiksel bir model seçilir ve algoritma sözlü olarak resimlerle ve ayrıntılarla açıklanır. Bir elemanın maksimumdan büyük olması durumunda, değeri maksimuma atanır.
Maksimum elemanı bulmak için, birinci elemanın değeri maksimum olduğu varsayılır. Daha sonra her değer, o ana kadar bulunan maksimum sayının değeriyle karşılaştırılır.
Şekilsel ifade de sahte kod, çözümü bulan adımların sırasını tanımlamak için kullanılır.
Uygulama yönteminde ise, belirli bir programlama dilinde ifade edilen algoritma veya komutları gerçekleştirebilen bazı nesneler gösterilir. Algoritmanın doğru olduğunu, karmaşıklık analizini veya her ikisini de gösteren bir teori de dahil etmek mümkündür.
Diyagramlar
Flowchart/Akış Şeması
Akış çizelgeleri, algoritmaların grafik açıklamalarıdır. Bunlar talimatların sırasını belirtmek için oklarla bağlantılı sembolleri kullanırlar ve ISO tarafından yönetilirler.
Küçük algoritmaları temsil etmek için kullanılırlar, çünkü çok yer kaplarlar ve oluşturmaları biraz zordur.
Okuma kolaylıkları nedeniyle, algoritmalara giriş, bir dilin açıklaması ve bilgi işlem dışındaki kişilere süreçlerin açıklaması olarak kullanılırlar.
Akış diyagramlarının zorluklarından biri, çözümün bir soruna yönelik akışını grafiksel olarak gösterme olasılığını sağlamasıdır.
Düzensiz bir programcının akış oklarını yanlış yerleştirmesi ve sonunda fikrin kendisinden daha karmaşık bir duruma yol açabilir. Diğer bir durumda, bir sorunun çözümünü temsil etmek için grafik araçları kullanmaya izin verir.
Tüm algoritmayı bir dikdörtgen çerçevesinde temsil etmeye dayanır ve önceki teknikten farklı olarak, temelde programlama mantığının temel yapılarının her birine karşılık gelen üç sembolün kullanımıyla devam eder.
Pseudocode/Sahte Kod
Sahte kod, bir programlama diline benzeyen ancak bazı doğal dil kurallarına sahip bir yöntemdir. Akış şemalarına göre birçok avantajı olduğu için özellikle karmaşık talimatları temsil eder. Ayrıca, herhangi bir standarda tabi değildir.
Sahte kod, hesaplama algoritmalarına yönelik bu tekniğin eylemlerini temsil etmek için kelime dağarcığını oluşturan bir grup anahtar kelimeye ve sembole sahiptir.
Bu tekniği kullanarak bir akış şeması çizmek için aşağıdaki kurallara uyulmalıdır:
1. İlk Adım
Kelime algoritması yazılır ve boşluktan sonra algoritmanın adını yazılır. Böylece ifade edilen duruma bir gönderme yapılır.
Sahte kodu X olarak adlandırırsak, amacının çok açık olması mümkün olmayabilir. Ancak sahte kod için Değişken adını verirsek, amacının değişken olduğunu daha kolay hayırlayabiliriz.
2. İkinci Adım
Algoritmanın tüm gövdesi, sahte kodun nerede başladığını ve nerede bittiğini gösterecek şekilde Başlangıç ve Bitiş sözcükleri arasına alınmalıdır.
3. Üçüncü Adım
Başla kelimesini yerleştirdikten sonra, yapılacak işin durumu ifade etmemiz gerekir.
4. Dördüncü Adım
Son adımda ise, yapılacak iş bildirildikten sonra eylemler yazılır.
Formal/Biçimsel
Otomata teorisi ve yinelemeli fonksiyonlar teorisi, algoritma kavramını resmileştiren matematiksel modeller sağlar. En yaygın modeller Turing makinesi, kayıt makinesi ve μ – özyinelemeli fonksiyonlardır.
Bu modeller bir makine dili kadar kesindir. Konuşma dili ifadeleri veya belirsizliği yoktur, ancak herhangi bir bilgisayardan ve herhangi bir uygulamadan bağımsızdırlar.
Implementation/Uygulama
Birçok algoritma, bir programda uygulanmak üzere tasarlanmıştır. Bununla birlikte, algoritmalar, bir sinir ağı, bir elektrik devresi veya bir mekanik ve elektrikli cihaz gibi başka ortamlarda da uygulanabilir.
Hatta bazı algoritmalar kalem ve kağıt kullanılarak uygulanmak üzere özel olarak tasarlanmıştır.
Geleneksel çarpma algoritması, Euclid’in algoritması, Eratosthenes’in eleği ve karekökü çözmenin birçok yolu sadece birkaç örnektir.
Fonksiyonel Algoritmalar
Hamilton döngüsü problemini çözen bir algoritmanın şemasıdır ve bir problemin (giriş) verilerini bir çözümün (çıktı) verilerine dönüştüren bir işlev olarak düşünülebilir.
Ayrıca, verilerin kendisi bit dizileri ve genel olarak herhangi bir simgenin dizileri olarak temsil edilebilir. Her bit dizisi doğal bir sayıyı temsil ettiğinden, algoritmalar hesaplanabilen doğal sayıların işlevleridir.
Her akış şeması, her doğal sayının bir problemin veya bir çözümün kodlaması olduğu bir işlevi hesaplar. Örneğin sonsuz bir döngüye girdiklerinde asla sona ermeyebilirler.
Böyle bir durumda, hiçbir zaman herhangi bir çıktı değeri döndürmez ve fonksiyonun o girdi değeri için tanımsız olduğunu söyleyebiliriz.
Bu nedenle, algoritmalar kısmi işlevler olarak kabul edilir, yani tüm tanım alanlarında tanımlanması gerekmez.
Bir fonksiyon algoritmik yöntemlerle hesaplanabildiğinde, kapladığı bellek miktarı veya aldığı süre ne olursa olsun, fonksiyonun hesaplanabilir olduğu söylenir. Veri dizileri arasındaki tüm işlevler hesaplanamaz.
Analiz
Bir algoritmanın verimliliğinin bir ölçüsü olarak, sistem tarafından tüketilen kaynaklar incelenir. Girdi değerlerinin büyüklüğünün bir fonksiyonu olarak zamanın ve hafıza harcamasının evrimini bir şekilde gösteren değerleri elde etmek için algoritma analizi geliştirilmiştir.
Algoritmaların analizi ve incelenmesi bilgisayar biliminin bir disiplinidir ve çoğu durumda, çalışması herhangi bir programlama dili veya başka bir uygulama kullanmadan tamamen soyuttur.
Dolayısıyla bu anlamda matematik disiplinlerinin özelliklerini paylaşmaktadır. Bu nedenle, algoritmaların analizi, belirli bir uygulamaya değil, algoritmanın temel ilkelerine odaklanır.
Bir algoritmayı oluşturmanın bir yolu, onu sahte kodda yazmak veya kodları programcının dilinde olabilen Lexicon gibi çok basit bir dil kullanmaktır.
Bazı yazılımcılar, algoritmanın tanımını bir noktada sona ermesi gereken prosedürlerle sınırlandırırken, diğerleri, sonsuza kadar çalışabilen bazı fiziksel aygıtların var olduğunu varsayarak, sonsuza kadar durmadan yürütülebilecek prosedürleri değerlendirir.
İkinci durumda, algoritmanın başarılı bir şekilde tamamlanması, tatmin edici bir çıktıyla sona erdirilmesi olarak tanımlanamaz.
Ancak başarı, algoritmanın çalıştırılmasının bir ömrü boyunca verilen çıktı dizilerinin bir fonksiyonu olarak tanımlanacaktır.
Örneğin, sonsuz bir ikili dizide birden fazla sıfır olduğunu doğrulayan bir akış şeması, kullanışlı bir değer döndürebilmesi için her zaman yürütülmelidir. Doğru uygulanırsa, sistem tarafından döndürülen değer, bir sonraki ikili rakamı değerlendirene kadar geçerli olacaktır.
Bu algoritmanın çıktısı, dizide birden fazla sıfır varsa, yalnızca pozitif değerlerin geri dönüşü olarak tanımlanır ve başka herhangi bir durumda, pozitif ve negatif sinyallerin bir karışımını döndürür.
Algoritma Türleri/Sınıflandırması
Greedy/Aç Gözlü
Bir çözüm bulana kadar en umut verici unsurlar uygulanır ve çoğu durumda çözüm optimal değildir.
Parallel/Paralel
Birden çok işlemcide aynı anda çalıştırılabilmeleri için bir problemin alt problemlere bölünmesine izin verirler.
Probabilistic/Olasılık
Bu tür algoritmadaki bazı adımlar sözde rasgele değerlere dayanmaktadır.
Deterministic/Belirleyici
Bu yöntemin davranışı doğrusaldır ve her adımında yalnızca bir ardıl ve bir öncül adım vardır.
Non-Deterministic/Belirleyici Olmayan
Algoritmanın davranışı ağaç şeklindedir ve her adımı, hemen ardından gelen herhangi bir sayıda adıma dallanabilir ve tüm dallar aynı anda yürütülür.
Divide and Conquer/Böl ve Yönet
Problemi ayrı alt gruplara bölerler, her biri için bir çözüm bulurlar ve sonra onları birleştirirler, böylece sorunun tamamını çözerler.
Metaheuristics/Sezgisel
Problemlerin önceki bilgilerine dayalı olarak problemlere yaklaşık optimal olmayan çözümler bulma yöntemine dayanır.
Dynamic Scheduling/Dinamik Planlama
Mekansal maliyeti artırarak, hesaplama maliyetini düşürerek sorunları çözmeye çalışır.
Branching and Dimensioning/Dallanma ve Boyutlandırma
En iyi çözümleri bularak kontrollü bir şekilde geçilen örtük bir ağaç vasıtasıyla soruna çözüm üretilmesine dayanır.
Backtracking/Geri İzleme
Problemin çözüm alanı, en ucuz çözümleri depolayan, tamamen incelenen bir ağaçta inşa etme yöntemine dayanır.