Algoritma (Algorithm)

Matematik ve bilgisayar bilimlerinde, bir algoritma ( ), genellikle belirli bir sorun kategorisine çözüm bulmak veya bir hesaplama görevini yürütmek için kullanılan, kesin olarak tanımlanmış sonlu bir dizi talimattan oluşur. Bu sistematik prosedürler, hesaplamaların yapılması ve verilerin işlenmesi için spesifikasyon görevi görür. Gelişmiş algoritmalar, kod yürütme akışını farklı yollara yönlendirmek için koşullu mantığı (otomatik karar verme olarak bilinen bir süreç) ve otomatik muhakeme olarak adlandırılan geçerli sonuçlar elde etmeyi içerebilir.

Tersine, buluşsal yöntem, açıkça tanımlanmış doğru veya optimal sonuçları olmayan bir problem çözme metodolojisini temsil eder. Örneğin, sosyal medya öneri sistemleri sıklıkla "algoritmalar" olarak adlandırılsa da, nesnel olarak "doğru" bir önerinin bulunmaması nedeniyle temelde buluşsal yöntemlere dayanırlar.

Etkili bir yöntem olarak kabul edilebilmesi için, bir algoritmanın, işlev hesaplaması için kesin olarak tanımlanmış bir resmi dil kullanarak, sonlu mekansal ve zamansal kısıtlamalar dahilinde ifade edilebilir olması gerekir. Bir başlangıç ​​durumundan ve bir başlangıç ​​girdisinden (boş olabilir) başlayarak, talimatlar, yürütme üzerine, sonlu bir farklı durumlar dizisi boyunca ilerleyen, sonuçta bir "çıktı" veren ve nihai bir durumda sonuçlanan bir hesaplamayı tanımlar. Durumlar arasındaki ilerleme her zaman deterministik değildir; belirli algoritmalar, özellikle de rastgeleleştirilmiş algoritmalar stokastik girdiyi entegre eder.

Etimoloji

İranlı bilgin ve bilge Muḥammad ibn Mūsā al-Khwārizmī, MS 825 civarında, kitāb al-ḥisāb al-hindī ("Hint hesaplama kitabı" olarak tercüme edilir) ve kitab al-jam' wa'l-tafriq al-ḥisāb al-hindī'yi (anlamı) yazdı "Hint aritmetiğinde toplama ve çıkarma"). 12. yüzyılın başlarında, Hindu-Arap rakam sistemini ve aritmetiğini tanıtan bu eserlerin Latince tercümeleri ortaya çıktı. Dikkate değer örnekler arasında Seville'li John'a atfedilen Liber Alghoarismi de practica arismetrice ve Bath'lı Adelard'a atfedilen Liber Algorismi de numero Indorum yer alır. Bu bağlamlarda, alghoarismi veya algorismi, Al-Khwarizmi'nin adının Latince biçimini temsil eder; ilgili metin, "Harizmi böyle konuştu" anlamına gelen Dixit Algorismi ifadesiyle başlar.

İngilizce algorism terimi, hesaplamalarda yer değeri gösteriminin uygulanmasını belirtmek üzere gelişti; ilk ortaya çıkışı 1225 civarında Ancrene Wisse'dedir. 14. yüzyılın sonlarında, Geoffrey Chaucer Canterbury Masalları'nı yazdığında, basamak değeri hesaplaması için kullanılan büyü taşlarını karakterize etmek için bu kelimenin bir varyasyonunu kullanmıştı. 15. yüzyılda Latince kelime, Yunanca ἀριθμός (arithmos, "sayı" anlamına gelir; cf. "aritmetik") teriminden etkilenen algorithmus'a dönüştü. 1596'ya gelindiğinde Thomas Hood, bu değiştirilmiş form olan algoritmayı İngilizce olarak kullandı.

Tanım

Gayri resmi bir tanım, bir algoritmayı, tüm bilgisayar programlarını (sayısal hesaplamalar yapmayanları bile) ve ayrıca herhangi bir resmi bürokratik süreci veya yemek tarifini kapsayan "bir dizi işlemi kesin olarak tanımlayan bir dizi kural" olarak öne sürer. Genel olarak, sonsuz döngülerin zaman zaman avantajlı olabilmesine rağmen, bir program ancak sonunda sona ererse algoritma olarak nitelendirilir. Boolos, Jeffrey &; 1974, 1999, bir algoritmayı, bir bilgi işlem makinesi veya semboller üzerinde yalnızca belirli temel işlemleri gerçekleştirebilen bir insan tarafından yürütülebilen, bir çıktıyı tespit etmek için açık talimatlar topluluğu olarak nitelendirir.

Geçmiş

Eski algoritmalar

Matematiksel zorlukları çözmeye yönelik sistematik, adım adım metodolojiler eski çağlardan beri belgelenmiştir. Bu tür örnekler Babil matematiğinde (MÖ 2500 civarı), Mısır matematiğinde (MÖ 1550 civarı), Hint matematiğinde (MÖ 800 civarı ve sonraki dönemler), Ifa Kahini'nde (MÖ 500 civarı), Yunan matematiğinde (MÖ 240 civarı), Çin matematiğinde (MÖ 200 civarı ve sonrası) ve Arap matematiğinde (MS yaklaşık 800) açıkça görülmektedir.

Algoritmaların ilk belirtileri eski Mezopotamya matematiğine kadar izlenebilir. Bağdat yakınlarındaki Şuruppak'ta keşfedilen ve yaklaşık olarak c. 2500 BC yılına tarihlenen bir Sümer kil tableti, bilinen en eski bölme algoritmasının ayrıntılarını vermektedir. Hammurabi hanedanlığı sırasında, yaklaşık c. 1800 – c. 1600 BC aralığını kapsayan Babil kil tabletleri, formülsel hesaplamalar için algoritmaları tanımladı. Dahası, tabletler, dikkate değer astronomik olayların zamanlamasını ve konumunu belirlemek için algoritmik süreçleri açıklayan ve kullanan tabletlerle Babil astronomisinin ayrılmaz bir parçasıydı.

Aritmetik algoritmalar aynı zamanda eski Mısır matematiğinde de belgelenmiştir ve Rhind Mathematical Papyrus'tan elde edilen kanıtlar yaklaşık olarak c. 1550 BC yılına tarihlenmektedir. Daha sonra antik Helenistik matematikte algoritmalar kullanılmaya başlandı. Dikkate değer örnekler arasında Nicomachus'un Aritmetiğe Giriş adlı eserinde ayrıntıları verilen Eratosthenes Eleği ve ilk olarak c. MÖ 300 civarında Euclid'in Öğeleri'nde sunulan Öklid algoritması yer alır. Kadim Hint matematiğinden alınan diğer örnekler arasında Shulba Sutraları, Kerala Okulu ve Brāhmasphuṭasiddhānta yer alıyor.

Kod deşifre etmeye yönelik öncü kriptografik algoritma, 9. yüzyıl Arap matematikçisi Al-Kindi tarafından Kriptografik Mesajların Deşifre Edilmesi Üzerine Bir El Yazması adlı çalışmasıyla tasarlandı. Ayrıca, bilinen en eski kod kırma algoritmasını temsil eden frekans analizi yoluyla kriptanalizin ilk tanımını da sağladı.

Bilgisayarlar

Ağırlığa dayalı saatler

David Bolter, ağırlıkla çalışan saatin icadını, özellikle de karakteristik tik-tak hareketinden sorumlu olan kenar eşapman mekanizmasını "[Orta Çağ'da Avrupa'nın] temel icadı" olarak nitelendiriyor. Bu "doğru otomatik makine", 13. yüzyılda "mekanik otomatların" ve ardından 19. yüzyılın ortalarında Charles Babbage ve Ada Lovelace'in farkı ve analitik motorlarının örneklediği "hesaplamalı makinelerin" ortaya çıkmasını doğrudan kolaylaştırdı. Lovelace, yalnızca bir hesap makinesinden ziyade, gerçek anlamda Turing'i tamamlayan ilk bilgi işlem cihazı olarak kabul edilen, Babbage'in analitik motoru olan bir bilgisayarda yürütülmek üzere tasarlanan ilk algoritmayı tasarladı. Analitik motorun tam anlamıyla gerçekleşmesi ölümünden onlarca yıl sonra gerçekleşmesine rağmen Lovelace, geniş çapta "tarihin ilk programcısı" olarak kabul ediliyor.

Elektromekanik röle

Bell ve Newell'e (1971) göre, Hollerith delikli kartlarından önce gelen Jakarlı dokuma tezgahı ve "telefon değiştirme teknolojileri" ilk bilgisayarların doğuşuna katkıda bulundu. Küresel olarak telefonun öncüsü olan telgraf, 19. yüzyılın ortalarında faaliyete geçmişti. 19. yüzyılın sonları, yaklaşık olarak c. 1870'ler'de şerit bantların ve 1890 civarında Hollerith kartlarının benimsenmesine tanık oldu. Daha sonra, Baudot kodlu delikli kağıt bant kullanan teleprinter c. 1910 civarında ortaya çıktı.

Elektromekanik röle tabanlı telefon anahtarlama ağları 1835'te geliştirildi. Bu yenilik daha sonra George Stibitz'in 1937'de dijital bir toplama cihazı icat etmesine yol açtı. Bell Laboratuvarlarındaki görev süresi boyunca Stibitz, dişlilere dayanan mekanik hesap makinelerinin "külfetli" doğasına dikkat çekti. 1937'de konseptini test etmek için bir akşam projesine girişti ve bunun sonucunda ikili toplama cihazının yapımıyla sonuçlandı.

Resmileştirme

Modern algoritmik kavram, David Hilbert'in Entscheidungsproblem(karar problemi) sorununu çözme çabalarının etkisiyle 1928'de kısmi resmileştirmeye başladı. Daha sonraki formalizasyonlar "etkili hesaplanabilirliği" veya "etkili bir yöntemi" tanımlamayı amaçladı. Bu biçimlendirmeler Gödel-Herbrand-Kleene özyinelemeli fonksiyonlarını (1930, 1934, 1935), Alonzo Church'ün lambda hesabını (1936), Emil Post'un Formülasyon 1'ini (1936) ve Alan Turing'in Turing makinelerini (1936–37, 1939) kapsıyordu.

Modern Algoritmalar

Algoritmalar zaman içinde önemli bir evrim geçirdi ve geliştirildi. Algoritmaların çağdaş uygulamaları Instagram ve YouTube gibi sosyal medya platformlarında yaygındır. Bu algoritmalar, bireylere alakalı içerik önermek için kullanıcı tercihlerini analiz eder. Kuantum hesaplama, hızlandırılmış problem çözme için kuantum algoritmik prosedürlerden yararlanır. 2024'te NIST, kuantum bilişimi tabanlı saldırılara karşı savunmayı güçlendirmek için yeni şifreleme algoritmaları ekleyerek kuantum sonrası şifreleme standartlarını güncelledi.

Temsilciler

Algoritmalar, doğal diller, sözde kod, akış şemaları, drakon şemaları, programlama dilleri veya (yorumlayıcılar tarafından işlenen) kontrol tabloları gibi çeşitli gösterimler kullanılarak ifade edilebilir. Algoritmaların doğal dildeki temsilleri tipik olarak ayrıntılıdır ve belirsizliğe eğilimlidir, bu da onları karmaşık veya teknik algoritmalar için uygunsuz hale getirir. Bunun tersine, sözde kod, akış şemaları, drakon şemaları ve kontrol tabloları, doğal dilin doğasında olan belirsizlikleri azaltan yapılandırılmış algoritmik ifadeler sunar. Programlama dilleri öncelikle algoritmaları bilgisayarda çalıştırılabilir bir biçimde ifade etmeye hizmet etse de, algoritma tanımı ve belgelenmesine yönelik araçlar olarak da işlev görür.

Turing makineleri

Turing makinesi programları, makine tabloları dizileri, akış şemaları, drakon şemaları dahil olmak üzere çeşitli biçimlerde veya genellikle "dörtlü kümeler" olarak adlandırılan temel bir makine veya montaj kodu olarak temsil edilebilir. Algoritma temsilleri genellikle Turing makinesi tanımının üç farklı seviyesine kategorize edilir: yüksek seviye, uygulama ve resmi. Üst düzey bir açıklama, algoritmanın doğasında var olan özelliklerini tasvir ederek, onun bir Turing makinesindeki özel uygulamasını soyutlar. Bir uygulama açıklaması, kesin durumları belirtmeden, algoritmayı yürütmek için gereken kafa hareketi ve veri depolama gibi genel operasyonel mekaniği ayrıntılarıyla anlatır. En ayrıntılı ve resmi açıklama, Turing makinesinin tam durum tablosunu ve geçişlerin tam listesini sağlar.

Akış Şeması Gösterimi

Akış şemaları, ilgili bilgisayar programları da dahil olmak üzere algoritmaları tanımlamak ve belgelemek için grafiksel bir araç görevi görür. Tipik olarak dört ana sembol kullanırlar: program akışını gösteren oklar, sıralı işlemler veya GOTO ifadeleri için dikdörtgenler, koşullu dallar (IF-THEN-ELSE) için baklava desenleri ve OR-bağlantı bağlantıları için noktalar. Alt yapılar, etrafını saran üst yapının tek bir çıkış noktası sağlaması koşuluyla dikdörtgenler içine yerleştirilebilir.

Algoritmik Analiz

Bir algoritmanın gerektirdiği zaman, depolama veya diğer ilgili maliyetler gibi hesaplama kaynaklarının belirlenmesi çoğu zaman çok önemlidir. Sonuç olarak, bu niceliksel tahminleri elde etmek için algoritmik analize yönelik çeşitli yöntemler oluşturulmuştur. Örneğin, n sayıdan oluşan bir listedeki öğeleri toplamak için tasarlanmış bir algoritma, ⁠${\displaystyle O(n)$⁠, büyük O notasyonu kullanılarak ifade edilir. Bu algoritma yalnızca iki değerin korunmasını gerektirir: o ana kadar işlenen öğelerin kümülatif toplamı ve girdi listesindeki geçerli dizini. Giriş sayıları için ayrılan alan hariç tutulduğunda, alan karmaşıklığı ⁠${\displaystyle O(1)$⁠; aksi halde, ⁠${\displaystyle O(n)$⁠.

Aynı görevleri yerine getirmek için tasarlanan algoritmalar, zaman, alan ve hesaplama çabası da dahil olmak üzere kaynak tüketimi açısından önemli ölçüde farklılık gösterebilir. Örneğin, ⁠${\displaystyle O(\log n)$⁠, ⁠${\displaystyle O(n)$⁠, özellikle sıralanmış listeler veya diziler üzerinde tablo aramaları yaparken.

Resmi ve Ampirik

Algoritmaların titiz analizi ve incelenmesi, bilgisayar biliminde temel bir disiplini oluşturur. Algoritmalar sıklıkla herhangi bir programlama dilinden veya somut uygulamadan bağımsız olarak soyut bir şekilde incelenir. Algoritmik analiz, öncelikle bir algoritmanın belirli uygulama ayrıntılarından ziyade doğal özelliklerine odaklanarak diğer matematik alanlarıyla özellikleri paylaşır. Sözde kod, temsil olarak basitliği ve genelliği nedeniyle analiz için yaygın olarak kullanılır. Çoğu algoritma sonuçta belirli donanım ve yazılım platformlarında uygulansa da, pratik verimlilikleri gerçek dünyadaki kod yürütme yoluyla değerlendirilir. Belirli bir algoritmanın verimliliği çok sayıda tekil, "tek seferlik" problemler için ihmal edilebilir düzeyde olabilir; ancak hızlı etkileşimli sistemlere, ticari uygulamalara veya uzun vadeli bilimsel çabalara yönelik algoritmalar için çok önemli hale gelir. Küçükten büyüğe giriş boyutlarından (n) performans ölçeklendirmesi, genellikle algoritmalardaki normalde zararsız görünebilecek verimsizlikleri ortaya çıkarır.

Deneysel testler, performansı etkileyen öngörülemeyen etkileşimleri belirleme açısından değerli olduğunu kanıtlıyor. Program optimizasyonunun ardından olası algoritmik iyileştirmelerin etkisini değerlendirmek için karşılaştırmalardan yararlanılabilir. Bununla birlikte ampirik değerlendirmeler, resmi analizin yerini tutmaz ve adil ve tarafsız uygulamanın sağlanmasında önemli zorluklar sunar.

Yürütme Verimliliği

Olgun algoritmik çerçevelerde bile geliştirme potansiyelini gösteren, görüntü işlemede yaygın olarak kullanılan Hızlı Fourier Dönüşümü (FFT) algoritmalarında yakın zamanda gerçekleşen önemli bir gelişme, tıbbi görüntüleme gibi uygulamalarda işlem sürelerini bin kata kadar azaltma kapasitesini ortaya koydu. Genel olarak bu tür performans iyileştirmeleri, pratik senaryolarda sıklıkla karşılaşılan belirli sorun özelliklerine bağlıdır. Bu ölçekteki hızlanmalar, dijital kameralar ve tıbbi cihazlar da dahil olmak üzere görüntü işlemeyi yoğun şekilde kullanan bilişimsel cihazlarda güç tüketiminin azaltılmasını kolaylaştırıyor.

En İyi Durum ve En Kötü Durum Analizi

Bir algoritma veya veri yapısı için en iyi durum senaryosu, görevin tamamlanması için minimum zaman ve hesaplama kaynağı harcamasını gerektiren girdi veya operasyonel bağlam tarafından tanımlanır. Tersine, en kötü senaryo, algoritmanın veya veri yapısının maksimum süreyi ve hesaplama kaynaklarını talep ettiği girdiyi veya koşulu temsil eder.

Tasarım

Algoritma tasarımı, problem çözme ve algoritma geliştirme için kullanılan sistematik bir metodoloji veya matematiksel prosedür oluşturur. Bu tasarım süreci, özellikle yöneylem araştırması alanında böl ve yönet stratejileri ve dinamik programlama dahil olmak üzere çeşitli çözüm paradigmalarının ayrılmaz bir parçasıdır. Algoritmik yapıların kavramsallaştırılması ve gerçekleştirilmesine yönelik spesifik teknikler sıklıkla algoritma tasarım modelleri olarak adlandırılır ve şablon yöntemi ve dekoratör gibi modellerle örneklenir. Algoritma tasarımında en önemli husus, yürütme süresi ve bellek tüketimi gibi faktörleri kapsayan kaynak verimliliğidir; Örneğin Büyük O gösterimi, artan giriş boyutuyla ilişkili olarak bir algoritmanın çalışma zamanı ölçeklenebilirliğini ölçer.

Yapılandırılmış Programlama

Church-Turing tezine göre, hesaplanabilir herhangi bir algoritma, herhangi bir Turing-tam hesaplama modeli tarafından yürütülebilir. Tamlığı turlamak temel olarak yalnızca dört talimat türünü gerektirir: koşullu GOTO, koşulsuz GOTO, atama ve HALT. Bununla birlikte Kemeny ve Kurtz, koşulsuz GOTO'ların ve koşullu IF-THEN GOTO'ların sınırsız bir uygulamasının "spagetti koduna" yol açabilmesine rağmen, bir programcının yalnızca bu talimatlarla yapılandırılmış programlar oluşturma yeteneğini koruduğunu belirtti. Tersine, yapılandırılmış bir programlama dilinde bile kötü yapılandırılmış programlar geliştirmenin "çok zor olmadığını" da gözlemlediler. Tausworthe, iki ek yapıyı tanıtarak üç kanonik Böhm-Jacopini yapısını (SEQUENCE, IF-THEN-ELSE ve WHILE-DO) genişletti: DO-WHILE ve CASE. Yapılandırılmış programlamanın bir başka avantajı da, genellikle matematiksel tümevarım yoluyla elde edilen resmi doğruluk kanıtlarına uygun olmasıdır.

Yasal Durum

Temel olarak algoritmalar genellikle patent korumasına uygun değildir. Amerika Birleşik Devletleri'nde, yalnızca soyut kavramların, sayısal verilerin veya sinyallerin temel manipülasyonlarını içeren bir patent talebi, bir "süreç" olarak nitelendirilmez (USPTO 2006), dolayısıyla Gottschalk v. Benson kararında belirtildiği gibi algoritmaları patentlenemez kılar. Bununla birlikte, algoritmaların pratik uygulamaları zaman zaman patentlenebilir. Örneğin, Diamond v. Diehr davasında, sentetik kauçuğun vulkanizasyonunu kolaylaştırmak için basit bir geri bildirim algoritmasının kullanılmasının patentlenebilir olduğu belirlendi. Yazılımın patentlenebilirliği tartışmalı bir konu olmaya devam ediyor; çeşitli algoritmalar, özellikle de Unisys'in LZW patenti gibi veri sıkıştırma algoritmaları ciddi eleştirilere maruz kalıyor. Ayrıca belirli şifreleme algoritmaları dışa aktarma denetimlerine tabidir.

Sınıflandırma

Uygulamaya Göre

Yineleme

Özinelemeli bir algoritma, işlevsel programlamada yaygın bir yaklaşımı temsil eden, önceden tanımlanmış bir sonlandırma koşulu sağlanana kadar kendisini tekrar tekrar çağırarak çalışır. Buna karşılık, yinelemeli algoritmalar, hesaplama sorunlarını çözmek için döngüler gibi tekrarlayan yapılar kullanır veya yığınlar gibi veri yapılarından yararlanır. Belirli problemler, özyinelemeli veya yinelemeli bir uygulamaya daha uygun olabilir. Örneğin Hanoi Kulesi bulmacası sıklıkla yinelemeli algoritmik bir yaklaşımla çözülür. Temel olarak, her özyinelemeli algoritmanın eşdeğer bir yinelemeli karşılığı vardır ve bunun tersi de geçerlidir; ancak bunların karmaşıklıkları farklılık gösterebilir.

Seri, Paralel veya Dağıtılmış

Algoritmaların geleneksel anlayışı genellikle bunların seri hesaplama sistemlerinde aynı anda işlenen tek bir talimatla sıralı olarak yürütüldüğünü varsayar. Seri algoritmalar, paralel veya dağıtılmış algoritmik yaklaşımların aksine, bu tür ortamlar için özel olarak tasarlanmıştır. Paralel algoritmalar, bir sorunun birden fazla işlemcide eşzamanlı olarak işlenmesine olanak tanıyan hesaplama mimarilerinden yararlanır. Tersine, dağıtılmış algoritmalar bir bilgisayar ağı içindeki birbirine bağlı birkaç makineyi kullanır. Hem paralel hem de dağıtılmış paradigmalar, bir problemi daha küçük alt problemlere ayırmayı ve ardından ilgili çözümlerini birleştirmeyi içerir. Bu algoritmalardaki kaynak kullanımı, yalnızca bireysel işlemcilere harcanan işlemci döngülerini değil, aynı zamanda işlemciler arası veri alışverişi sırasında ortaya çıkan iletişim yükünü de kapsar. Belirli sıralama algoritmaları verimli paralelleştirmeye olanak sağlarken, çoğunlukla önemli miktarda iletişim yükü gerektirir. Yinelemeli algoritmalar tipik olarak paralelleştirmeye uygundur; ancak bazı problemlerin paralel algoritmik çözümleri yoktur ve dolayısıyla doğası gereği seri problemler olarak adlandırılır.

Deterministik ve Deterministik Olmayan Algoritmalar

Deterministik algoritmalar, her hesaplama adımında kesin kararlar vererek sorunları çözerken, deterministik olmayan algoritmalar problem çözmeye spekülatif seçimler yoluyla yaklaşır. Bu spekülatif seçimler genellikle buluşsal yöntemler kullanılarak hassaslaştırılır ve doğruluk açısından iyileştirilir.

Tam ve Yaklaşık Algoritmalar

Çok sayıda algoritma kesin bir çözüm üretirken, yaklaşım algoritmaları gerçek optimal sonuca yakın bir şekilde yaklaşan bir çözüm bulmaya çalışır. Bu algoritmaların hesaplama açısından zorlu birçok problemin çözümünde özellikle değerli olduğu kanıtlanmıştır. İlgili bir örnek, kümülatif değerlerini en üst düzeye çıkarmak için belirli bir koleksiyondan bir öğe alt kümesinin seçilmesini içeren Sırt Çantası problemidir. Her öğenin ilişkili bir ağırlığı ve değeri vardır. Seçilen öğelerin toplam ağırlığı, X olarak belirtilen, önceden tanımlanmış bir kapasiteyi aşmamalıdır. Sonuç olarak çözüm, hem öğe ağırlıklarının hem de bunlara karşılık gelen değerlerin aynı anda dikkate alınmasını gerektirir.

Kuantum Algoritmaları

Kuantum algoritmaları gerçekçi bir kuantum hesaplama çerçevesi dahilinde yürütülür. Bu tanımlama tipik olarak doğası gereği kuantum olan veya kuantum süperpozisyonu veya kuantum dolaşıklığı gibi kuantum hesaplamanın temel özelliklerinden yararlanan algoritmalar için geçerlidir.

Tasarım Paradigmasına Göre Sınıflandırma

Algoritmalar aynı zamanda temel tasarım metodolojilerine veya paradigmalarına göre de kategorize edilebilir. Öne çıkan birkaç paradigma şunları içerir:

Kaba Kuvvet veya Kapsamlı Arama

Kaba kuvvet araması, en uygun çözüm belirlenene kadar akla gelebilecek her seçeneği sistematik olarak değerlendiren bir problem çözme metodolojisidir. Bu yöntem, tüm potansiyel değişken kombinasyonlarının incelenmesini gerektirdiğinden hesaplama açısından yoğun olabilir. Alternatif yaklaşımların pratik olmadığı veya aşırı derecede karmaşık olduğu durumlarda sıklıkla kullanılır. Kaba kuvvet teknikleri, iki düğüm arasındaki en kısa yolun belirlenmesi ve kriptografik şifre kırma gibi çeşitli sorunlara uygulanabilir.

Böl ve Fethet

Bir böl ve yönet algoritması, bu alt problemler doğrudan çözülebilecek kadar önemsiz hale gelinceye kadar, tipik olarak yinelemeli uygulama yoluyla, bir problemi sistematik olarak bir veya daha fazla daha küçük, kendine benzer alt problemlere ayrıştırır. Birleştirme sıralaması, sıralanmamış bir listenin her biri bağımsız olarak sıralanan ve daha sonra yeniden birleştirilen daha küçük alt listelere yinelemeli olarak bölündüğü bu paradigmayı örneklendirmektedir. Budama ve arama veya azaltma ve fethetme algoritması olarak bilinen daha akıcı bir değişken, sorunun daha küçük tek bir örneğini ele alır ve birleştirme aşamasına olan ihtiyacı ortadan kaldırır. İkili arama algoritması, budama ve arama yaklaşımının klasik bir örneğidir.

Arama ve Numaralandırma

Satranç gibi stratejik oyunlar da dahil olmak üzere çok sayıda problem, grafikle ilgili zorluklar olarak etkili bir şekilde modellenebilir. Grafik keşfetme algoritmaları, bir grafiğin geçişine yönelik sistematik prosedürleri tanımlar ve bu tür sorunların çözümünde etkilidir. Bu sınıflandırma ayrıca genel arama algoritmalarını, dal ve sınır numaralandırma tekniklerini ve geri izleme metodolojilerini de kapsar.

Rastgele Algoritmalar

Bu algoritmalar, yürütülmeleri sırasında rastgele veya sözde rastgele kararlar içerir. Kesin çözümler elde etmenin hesaplama açısından mümkün olmadığı durumlarda yaklaşık çözümler elde etmek için kullanılırlar. Belirli problemler için en verimli yaklaşım algoritmaları doğası gereği stokastik öğelere dayanır. Polinom zaman karmaşıklığına sahip rastgeleleştirilmiş algoritmaların belirli problemler için en hızlı yaklaşımı temsil edip etmediğinin belirlenmesi, ünlü olarak P'ye karşı NP problemi olarak bilinen, çözülmemiş bir araştırma olmaya devam etmektedir. Bu algoritmaların iki ana kategorisi mevcuttur:

1. Monte Carlo algoritmaları yüksek doğruluk olasılığıyla doğru bir çözüm sunar. Örneğin, karmaşıklık sınıfı RP, polinom zaman içinde çalışan Monte Carlo algoritmalarının bir alt sınıfını temsil eder.
2. Las Vegas algoritmaları, yürütme süreleri yalnızca olasılıksal olarak sınırlı olmasına rağmen sürekli olarak doğru çözümü sağlar; ZPP karmaşıklık sınıfı bunun bir örneğidir.

Karmaşıklığın Azaltılması

Bu metodoloji, karmaşık sorunları daha tanıdık sorunlara dönüştürür ve bunlar daha sonra ideal olarak asimptotik olarak optimal olan algoritmalar kullanılarak çözülebilir. Amaç, hesaplama karmaşıklığı dönüştürülmüş problemlere uygulanan algoritmalarınkini gölgede bırakmayan bir indirgeme algoritması tanımlamaktır. Örneğin, bir seçim algoritması, başlangıçta listeyi sıralayarak (hesaplama açısından yoğun aşama) ve ardından merkezi öğeyi sıralı diziden çıkararak (daha az talepkar aşama) sıralanmamış bir listenin medyanını belirler. Bu yaklaşım aynı zamanda dönüştür ve yönet olarak da adlandırılır.

Geri izleme

Bu metodoloji, birden fazla potansiyel çözümün aşamalı olarak oluşturulmasını içerir; bu çözümlerin, tam ve geçerli bir çözüm sağlayamadıkları belirlenirse daha sonra atılır.

Optimizasyon Sorunları

Optimizasyon sorunları, algoritmaların daha uzmanlaşmış bir şekilde sınıflandırılmasını gerektirir. Bu problemler için tasarlanan bir algoritma, aşağıdaki kategorilerden birine ek olarak, daha önce özetlenen genel sınıflandırmaların bir veya daha fazlasına ait olabilir:

Doğrusal Programlama

Doğrusal eşitlik ve eşitsizlik koşullarıyla kısıtlanan doğrusal bir fonksiyon için en iyi çözümlerin arayışında, en iyi sonuçları elde etmek için bu kısıtlamalardan doğrudan yararlanılabilir. Yaygın olarak tanınan simpleks algoritması gibi, bu alandaki herhangi bir sorunu çözebilecek algoritmalar mevcuttur. Doğrusal programlamaya uygun problemlerin örnekleri, yönlendirilmiş grafiklerdeki maksimum akış problemini içerir. Bir problem ayrıca değişkenlerinden herhangi birinin tamsayı olmasını gerektiriyorsa, tamsayı programlama altında kategorize edilir. Doğrusal bir programlama algoritması, tüm tam sayı değer kısıtlamalarının bağlayıcı olmadığı, yani çözümlerin doğası gereği bu koşulları karşıladığı gösterilebilirse böyle bir sorunu çözebilir. Genellikle, problemin doğasındaki karmaşıklığa bağlı olarak ya özel bir algoritma ya da bir yaklaşım algoritması kullanılır.

Dinamik Programlama

Bir problem optimal altyapılar sergilediğinde (bu, optimal çözümünün alt problemlerinin optimal çözümlerinden sentezlenebileceği anlamına gelir) ve aynı alt problemlerin çeşitli problem örneklerinde tekrarlandığı örtüşen alt problemler sergilediğinde, gereksiz hesaplamaları önlemek için dinamik programlama olarak bilinen daha verimli bir metodoloji kullanılır. Örneğin, Floyd-Warshall algoritmasında, ağırlıklı bir grafikte başlangıç ​​noktası ile hedef tepe noktası arasındaki en kısa yol, tüm bitişik köşelerden hedefe giden en kısa yollardan yararlanılarak belirlenir. Dinamik programlama özünde not alma ile bağlantılıdır. Böl ve yönet paradigmasının aksine, dinamik programlamadaki alt problemler sıklıkla örtüşme sergiler. Dinamik programlama ile basit özyineleme arasındaki ayırt edici özellik, yinelemeli çağrılardan elde edilen sonuçların önbelleğe alınmasında veya not edilmesinde yatmaktadır. Alt problemler bağımsızsa ve tekrarlanmıyorsa not almanın hiçbir faydası yoktur; sonuç olarak dinamik programlama tüm karmaşık problemlere evrensel olarak uygulanamaz. Dinamik programlama, notlandırmayı kullanarak çok sayıda problemin hesaplama karmaşıklığını önemli ölçüde azaltabilir ve çoğu zaman bunları üstel zamandan polinom zamanına dönüştürebilir.

Açgözlü Yöntem

Açgözlü algoritmalar, dinamik programlamaya benzer şekilde, altyapıları analiz ederek çalışır; ancak bu bağlamda inceleme sorunun kendisiyle değil, önerilen çözümle ilgilidir. Bu algoritmalar bir başlangıç ​​çözümüyle başlar ve onu küçük ayarlamalar yoluyla yinelemeli olarak iyileştirir. Belirli problemler için sürekli olarak en iyi çözümü sağlarken, diğerleri için yerel optimumlara yakınlaşabilirler. Açgözlü algoritmaların öne çıkan bir uygulaması, negatif döngülerden yoksun grafiklerde minimum yayılan ağaçların belirlenmesini içerir. Huffman Ağacı yapısı, Kruskal algoritması, Prim algoritması ve Sollin algoritması, bu optimizasyon sorununu çözebilecek açgözlü yaklaşımların örnekleridir.

Sezgisel Yöntem

Optimizasyon sorunları alanında, özellikle gerçek optimumun belirlenmesinin hesaplama açısından mümkün olmadığı durumlarda, optimal sonuca yaklaşan çözümleri keşfetmek için buluşsal algoritmalar kullanılır. Bu algoritmalar, yürütmeleri boyunca aşamalı olarak en uygun çözüme doğru yakınlaşır. Teorik olarak, sonsuz bir yürütme süresi verildiğinde, bu yöntemler sonuçta en uygun çözümü bulacaktır. İdeal durumda, nispeten kısa bir zaman dilimi içerisinde optimuma oldukça yakın bir çözümü belirleme kapasitesine sahiptirler. Bu tür algoritmaların örnekleri arasında yerel arama, tabu arama, benzetilmiş tavlama ve genetik algoritmalar yer alır. Tavlama benzetimi gibi belirli buluşsal yöntemler deterministik değildir, oysa tabu arama gibi diğerleri deterministik olarak çalışır. Eğer alt-optimal çözüm için ölçülebilir bir hata sınırı belirlenirse, algoritma daha sonra bir yaklaşım algoritması olarak ayrıca sınıflandırılır.

Örnekler

Temel bir algoritma, rastgele sıralanmış bir sayı listesindeki maksimum değeri tanımlamayı içerir. Bu çözümün belirlenmesi listedeki her unsurun incelenmesini gerektirmektedir. Sonuç olarak, doğal dilde şu şekilde ifade edilebilecek basit bir algoritma ortaya çıkıyor:

Üst Düzey Açıklama:

1. Bir sayısal kümenin öğelerden yoksun olması durumunda, içinde hiçbir maksimum değer belirlenemez.
2. Başlangıçta küme içinde karşılaşılan ilk öğe en büyüğü olarak konumlandırılır.
3. Daha sonra, kümede kalan her sayı için değeri halihazırda tanımlanan en büyüğü aşarsa yeni en büyük sayı olarak atanır.
4. Küme içindeki tüm sayıların kapsamlı incelemesi sonucunda, belirlenen son en büyük sayı tüm kümenin maksimum değerini temsil eder.

(yarı-)Resmi Açıklama:

Notlar

Notlar

Kaynakça

• Zaslavsky, C. (1970). Yoruba Halkının ve Güney Nijerya'daki Komşularının Matematiği. İki Yıllık Üniversite Matematik Dergisi, 1(2), 76–99.
• NIST İlk 3 Kesinleşmiş Kuantum Sonrası Şifreleme Standardını Yayınladı.

• "Algoritma." Matematik Ansiklopedisi. EMS'ye basın. 2001 [1994].Weisstein, Eric W. "Algorithm." MathWorld.
• Algoritmalar ve Veri Yapıları Sözlüğü – Ulusal Standartlar ve Teknoloji Enstitüsü

Algoritma Depoları

• Stony Brook Algoritma Havuzu – Stony Brook'taki New York Eyalet Üniversitesi
• ACM'nin Toplanan Algoritmaları – Bilgisayar Makineleri Birlikleri
• Stanford GraphBase – Stanford Üniversitesi