Algoritma tasarım ve üretim kural ve tanım ve tasarımında katılmaktadırlar teknikler olduğunu algoritmalar , yani, bir çözmek için kesin adımlar açıklamak için bir problem çözme sistematik süreç algoritmik problemi .
Kelime "algoritma" adını geliyor matematikçi Harizmi (hiç Latince'ye Ortaçağ'da içinde Algoritmi at), IX inci yüzyıl yazdı ilk sistematik çalışmayı çözüm üreten lineer denklem ve kuadratik . Etimoloji tarafından doğrulanmayan sessiz h, Yunanca ἀριθμός (arithmós) ile karşılaştırıldığında bir deformasyondan gelir . "Algoritma", "algoritmik" verdi. Örneğin 1811'de Wronski tarafından kullanılan eski bir kelime olan "algoritma" eş anlamlısı hala bazen kullanılmaktadır.
Açıklamaları bulunmuştur ilk algoritmalar kadar uzanmaktadır Babilliler , III inci bin MÖ. AD . Örnekler kullanarak hesaplama yöntemlerini ve denklem çözümlerini açıklar .
Ünlü algoritma bulunan biridir Kitap 7 arasında Öklid Elementler ve denilen Öklid algoritması . İki sayının en büyük ortak bölenini veya GCD'yi bulur . Özellikle dikkat çekici bir nokta, açıkça bir yineleme içermesi ve 1. ve 2. önermelerin doğruluğunu göstermesidir .
π'nin hesaplanması için bir algoritma öneren ilk kişi Arşimet'ti .
Sistematize algoritmalara sahip olan ilk kişi , 813 ve 833 yılları arasında faaliyet gösteren İranlı matematikçi Al-Khwârizmî'dir. Abrégé du Computation by restorasyon ve karşılaştırma adlı çalışmasında , tüm ikinci dereceden denklemleri inceler ve algoritma generalleri tarafından çözümlerini verir. Babillilerinkine benzer yöntemler kullanır , ancak Babillilerin yalnızca örnekler verdiği sistematik açıklamalarında farklılık gösterir.
Endülüslü bilgin Averroès ( 1126 - 1198 ) , belirli bir yakınsamaya kadar ve bunun bir algoritmanın ilerlemesine uygun olarak, tezin adım adım, yinelemeli olarak rafine edildiği bir akıl yürütme yöntemini çağrıştırır . Aynı zamanda, içinde XII inci yüzyılda , keşiş Bath Adelard dönem tanıttı Latince için Algorismus Al Khwarizmi adında. Bu kelime 1554'te Fransızca bir algoritma verir .
In XVII inci yüzyıl , bazı kinaye için algoritmik yöntem bakış olabilir René Descartes tarafından önerilen genel yaklaşımda Yöntem söylevi ( 1637 özellikle ikinci bölümünde, Fransız matematikçi önerilen), "hangi isterim her zorluklar bölmek mümkün olduğunca çok parça halinde ve bunları daha iyi çözmek için gerektiği kadar inceleyin. " Açıkça kavramlar yinelemenin veya döngü uyandırmak olmadan ikiliği , Descartes'ın yaklaşım kavramını yerleştirmek için mantık açmaları programda , kelime Fransızca olarak doğar 1677'de .
1843 yılında, matematikçi ve bilgisayar biliminin öncüsü, Lord Byron'ın kızı ve Charles Babbage'ın asistanı Ada Lovelace , bir program biçiminde bir algoritmanın ilk uygulamasını (Bernoulli sayılarının hesaplanması ) gerçekleştirdi.
Onuncu Hilbert sorun listesinin bir parçası olan 23 sorunlardan yarattığı David Hilbert Paris'te 1900 yılında açıkça algoritmik bir sorundur. Bu durumda cevap, ortaya konan probleme cevap veren bir algoritma olmadığıdır.
Algoritmik XX inci ve XXI inci örneğin formalizminin matematiksel temeli, yüzyıllar Bunun Turing makineleri tam "özgü" tarafından "adımlar" ve "kesin" ile ne kastedildiğini tanımlamak için izin ve hangi çalışmak için bilimsel bir çerçeve sağlar, algoritmaların özellikleri. Ancak seçilen formalizme göre aynı problemi çözmek için farklı algoritmik yaklaşımlar elde edilir. Örneğin , özyinelemeli algoritmik, paralel algoritmik veya kuantum hesaplama , yinelemeli algoritmiklerden farklı algoritma sunumlarına yol açar.
ALGORITHMICS ikinci yarısında ağırlıklı olarak geliştirmiştir XX inci bu dönemde BT gelişiminde bilgisayar programlama kavramsal destek olarak, yüzyılın. Donald Knuth , çok sayıda algoritmayı açıklayan The Art of Computer Programming (Bilgisayar Programlama Sanatı) adlı incelemenin yazarı, diğerleriyle birlikte, analizlerinin matematiksel temellerini atmalarına yardımcı oldu.
İsim algoritmik , algoritma oluşturmak için kullanılan tüm yöntemleri belirtir. Terim sıfat olarak da kullanılır.
Bir algoritma , gerçekleştirilecek bir işlemler zinciri biçiminde bir soruna bir çözüm belirtir .
Bilgisayar bilimcileri , algoritmanın bir programlama dilinde uygulanmasına atıfta bulunmak için sıklıkla uygulama açıcılığı kullanır . Bu uygulama, algoritmayı oluşturan işlemlerin transkripsiyonunu gerçekleştirir ve bu işlemlerin çağrılma şeklini belirtir. Bilgisayar dilindeki bu yazı da sıklıkla “ kodlama ” terimi ile ifade edilir. Metni belirtmek, programı oluşturmak, algoritmayı yürütmek için " kaynak kodundan " bahsediyoruz . Kod az ya da çok bir pişirme tarifi aşçı deneyimlerine göre az ya da çok detaylı olmalıdır, tıpkı kullanılan dilin soyutlama düzeyine bağlı olarak ayrıntılı.
Algoritmaları tanımlamak, onları incelemek, niteliklerini ifade etmek ve bunları karşılaştırabilmek için birçok resmi veya teorik araç geliştirilmiştir:
Algoritmik olarak 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. İki sınıfa aittirler:
Bu ayrımın bazen belirli diller için ( Lisp , Prolog …) daha çok, belirli kontrol yapılarının örtük olduğu ve bu nedenle ortadan kaybolduğu özyineleme kavramına dayalı olarak algılanması zordur .
Bu "düzeltme", "tamlık", "sonlandırma" kavramları birbiriyle ilişkilidir ve bir problemi çözmek için bir algoritmanın yazıldığını varsayalım.
Sonlandırma güvence sonlu bir zaman algoritma uçlarının. Sonlandırma kanıtları genellikle algoritmanın her "adımında" kesin olarak azalan bir pozitif tamsayı fonksiyonunu içerir.
Bir algoritmanın biteceği garantisi verildiğinde, doğruluk kanıtı, algoritma bir sonuç vererek sona ererse, o zaman bu sonucun gerçekten ortaya konan soruna bir çözüm olduğuna dair güvence sağlamalıdır. Doğruluk kanıtları genellikle, problemin çözümleriyle doğrulanması gereken mantıksal bir belirtimi içerir. Bu nedenle doğruluğun kanıtı, algoritmanın sonuçlarının bu belirtimi karşıladığını göstermekten ibarettir.
Bütünlüğün kanıtı, verilen bir problem uzayı için, eğer tamamlanırsa, algoritmanın problem uzayının çözümlerini vereceğini garanti eder. Tamlık kanıtları, algoritmanın gerçekten birinciden ikinciyi ürettiğini göstermek için problem uzayını ve çözüm uzayını tanımlamayı gerektirir.
Kesin bir algoritma maliyetinin hesaplanmasında ana matematik kavramdır hakimiyeti kavramları (gösterilen O (f (n)) , "büyük O"), f a, matematiksel fonksiyon arasında n , değişken bilgi miktarını tayin ( bit cinsinden , kayıt sayısı vb. ) algoritmada kullanılır. Algoritmada genellikle şu türden karmaşıklıklar buluruz:
Değerlendirme | karmaşıklık türü |
---|---|
sabit karmaşıklık (verinin boyutundan bağımsız) | |
logaritmik karmaşıklık | |
doğrusal karmaşıklık | |
yarı doğrusal karmaşıklık | |
ikinci dereceden karmaşıklık | |
kübik karmaşıklık | |
polinom karmaşıklığı | |
yarı polinom karmaşıklığı | |
üstel karmaşıklık | |
faktör karmaşıklığı |
Matematiksel ayrıntılara girmeden, bir algoritmanın etkinliğini ( algoritmik karmaşıklığı ) hesaplamak, iki önemli niceliği bulmaktan ibarettir. İlk nicelik, ölçülen yürütme süresinde tercih edilecek olan, işlenecek veri miktarına göre temel komut sayısının evrimidir (örneğin, bir sıralama algoritması için bu, sıralanacak veri sayısıdır). saniye cinsinden (çünkü ikincisi, algoritmanın yürütüldüğü makineye bağlıdır). İkinci tahmini miktar, hesaplamaları gerçekleştirmek için gereken bellek miktarıdır. Bir algoritmanın karmaşıklığının hesaplanmasını, belirli bir bilgisayarın söz konusu algoritmayı gerçekleştirmek için aldığı zamana veya etkin bellek miktarına dayandırmak, algoritmanın iç yapısını veya algoritmanın özelliğini dikkate almaz. iş yükü, işlemcisinin hızı, verilere erişim hızı, algoritmanın (şans içerebilir) yürütülmesi veya bellek organizasyonu, yürütme süresi ve bellek miktarı aynı olmayacaktır.
Çoğu zaman, performans "en kötü ihtimalle" incelenir, yani çalışma zamanı veya bellek alanı gibi yapılandırmalarda en fazladır. Bir algoritmanın verimliliğini değerlendirmenin başka bir yönü daha vardır: “ortalama” performans. Bu, algoritma verilerinin istatistiksel dağılımının bir modeline sahip olmayı gerektirirken, analiz tekniklerinin uygulanması, özellikle seri oluşturma ve karmaşık analizin gelişmiş yöntemlerini kullanarak oldukça ince kombinatorik ve asimptotik değerlendirme yöntemlerini gerektirir . Bu yöntemlerin tümü, analitik kombinatorik adı altında bir araya toplanmıştır .
Genellikle yukarıda önerilen değerlerin ötesine geçen ve algoritmik problemleri (algoritmalar yerine) karmaşıklık sınıflarına ayıran diğer karmaşıklık değerlendirmeleri, algoritmaların karmaşıklığı teorisi hakkındaki makalede bulunabilir .
Algoritmaların verimliliği ve önyargıları hakkında bazı göstergelerAlgoritmik verimlilik genellikle yalnızca asimptotik olarak bilinir, yani n parametresinin büyük değerleri için . Bu parametre yeterince küçük olduğunda, daha büyük asimptotik karmaşıklığa sahip bir algoritma 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 (asimptotik olarak ortalama olarak en verimli sıralama algoritmalarından biri) gibi gelişmiş bir algoritma kullanmak gereksizdir : l Yazması en kolay sıralama algoritması yeterince verimli ol.
Aynı karmaşıklığa sahip iki bilgisayar algoritması arasında, daha az bellek işgal edeni kullanacağız. Algoritmik karmaşıklık analizi, bir algoritmanın bellek işgalini değerlendirmek için de kullanılabilir. Son olarak, diğerinden ziyade bir algoritmanın seçimi, onu girdi olarak sağlaması beklenen verilere göre yapılmalıdır. Bu nedenle, hızlı sıralama , bir pivot olarak ilk öğeyi seçtiğimizde, onu zaten sıralanmış bir değerler listesine uygularsak feci şekilde davranır. Bu nedenle, programın zaten neredeyse sıralanmış girdi listeleri olarak alması bekleniyorsa veya pivotu rastgele seçmeniz gerekecekse, onu kullanmak mantıklı değildir.
Dikkate alınması gereken diğer parametreler şunlardır:
Algoritmik, sorunları çözmek için bazı stratejiler geliştirmiştir:
Bazı problemler için, algoritmalar, olağanüstü bir hesaplama gücü kullanılabilse bile, makul bir sürede bir sonuç elde etmek için çok karmaşıktır. Bu nedenle, çözümü sistematik olmayan bir şekilde aramaya ( Las Vegas algoritması ) ya da ardışık testler yaparak ( Monte-Carlo algoritması ) en uygun çözüme mümkün olduğunca yakın bir çözümle tatmin olmaya yönlendiriliriz . Tüm kombinasyonlar denenemeyeceği için bazı stratejik seçimler yapılmalıdır. Genellikle ele alınan soruna çok bağlı olan bu seçimler, buluşsal olarak adlandırılan şeyi oluşturur . Bu nedenle bir buluşsal yöntemin amacı, olası tüm kombinasyonları denemek değil, makul bir sürede ve başka bir yolla, örneğin rastgele çekilişler yaparak bir çözüm bulmaktır. Çözüm kesin (Las Vegas) veya yaklaşık (Monte-Carlo) olabilir. Atlantic City algoritmaları , diğer taraftan, muhtemelen etkili bir sorulan soruya (Yanılmaktan yüz milyon bir ihtimal ile söz) bir olasılıkla doğru cevabı verir.
Bu nasıl satranç veya oyun programları gitmek çok sık sezgisellerin o modeli bir oyuncunun deneyim kullanmak (ama bir kaç isim için). Bazı virüsten koruma yazılımları , veritabanlarında listelenmeyen bilgisayar virüslerini tanımak için, bilinen virüslerle benzerliklere dayanarak buluşsal yöntemlere de dayanır ; bu, Atlantic City algoritmasının bir örneğidir. Aynı şekilde, NP-tam probleminin arketipi olan ve bu nedenle çok zor olan SAT problemi , buluşsal yöntemlerin geliştirilmesiyle pratik ve verimli bir şekilde çözülmüştür .
Problemleri çözmek için veya daha basit olarak programlama yöntemlerini göstermek için kullanılan bir dizi klasik algoritma vardır. Daha fazla ayrıntı için aşağıdaki makalelere bakın (ayrıca algoritmaların listesine bakın ):