Sonlu sayıda adımda bir sorunun cevabını veya bir problemin çözümünü üreten sistematik prosedür olan algoritma. Bu isim, 9. yüzyıl Müslüman matematikçi el Harezmi'nin aritmetik incelemesinin “Hindu Hesaplaşma Sanatına İlişkin Al-Harezmi” nin Latince çevirisi Algoritmi de numero Indorum'dan kaynaklanmaktadır.
bilgisayar bilimi: Algoritmalar ve karmaşıklık
Algoritma, iyi tanımlanmış bir hesaplama problemini çözmek için özel bir prosedürdür. Algoritmaların geliştirilmesi ve analizi esastır
Yalnızca sınırlı sayıda vaka veya değer içeren sorular veya sorunlar için her zaman bir algoritma vardır (en azından prensipte); cevapların değerler tablosundan oluşur. Genel olarak, “Doğal sayı (1, 2, 3,…) Asal mıdır?” Gibi sınırsız sayıda vaka veya değere sahip soru veya sorunlara cevap vermek o kadar önemsiz bir prosedür değildir. veya “a ve b doğal sayılarının en büyük ortak böleni nedir?” Bu sorulardan ilki karar verilebilir denilen bir sınıfa aittir; evet veya hayır yanıtı üreten algoritmaya karar prosedürü denir. İkinci soru hesaplanabilir denilen bir sınıfa aittir; belirli bir sayı cevabına götüren algoritmaya hesaplama prosedürü denir.
Bu tür sonsuz soru sınıfları için algoritmalar vardır; MÖ 300 civarında yayınlanan Öklid Elemanları, iki doğal sayının en büyük ortak böleni bulmak için bir tane içeriyordu. Her ilkokul öğrencisi, “Doğal bir sayı a'yı başka bir doğal sayı b'ye böldükten sonra, bölüm ve kalan nedir?” Sorusu için bir algoritma olan uzun bir bölümde delinir. Bu hesaplama prosedürünün kullanılması, “b bölü a mı?” Şeklinde karar verilebilir sorunun yanıtına yol açar. (kalan sıfır ise cevap evettir). Bu algoritmaların tekrar tekrar uygulanması, sonunda “Asal mı?” (a, 1'in yanı sıra daha küçük doğal sayılarla bölünebilirse cevap hayırdır).
Bazen sonsuz bir problem sınıfını çözmek için bir algoritma, özellikle de kabul edilen metot üzerinde biraz daha kısıtlama yapıldığında var olamaz. Örneğin, Öklid'in zamanından, sadece bir pusula ve bir yeşillik (işaretlenmemiş cetvel) kullanılmasını gerektiren iki sorun - bir açıyı arttırmak ve belirli bir daireye eşit bir alana sahip bir kare inşa etmek - imkansız oldukları gösterilmeden yüzyıllar önce takip edildi.. 20. yüzyılın başında, etkili Alman matematikçi David Hilbert, matematikçilerin gelecek yüzyılda çözmeleri için 23 problem önerdi. Listesindeki ikinci sorun, aritmetik aksiyomlarının tutarlılığının araştırılmasını istedi. Çoğu matematikçi, Avusturya doğumlu mantıkçı Kurt Gödel'in kanıtlanamayan veya kanıtlanamayan aritmetik önermelerin (veya soruların) olması gerektiği şaşırtıcı sonucunu gösterdiği 1931 yılına kadar bu hedefe ulaşılmasından şüphe duymuyordu. Esasen, böyle bir öneri hiç bitmeyen bir belirleme prosedürüne yol açar (durma problemi olarak bilinen bir durum). En azından hangi önermelerin çözülemez olduğunu tespit etmek için başarısız bir çabada, İngiliz matematikçi ve mantıkçı Alan Turing, gevşek anlaşılmış bir algoritma kavramını titizlikle tanımladı. Turing, kararsız önerilerin olması gerektiğini kanıtlamasına rağmen, herhangi bir genel amaçlı algoritma makinesinin veya Turing makinesinin temel özelliklerini tanımlaması bilgisayar biliminin temeli oldu. Bugün, karar verilebilirlik ve hesaplanabilirlik konuları, özel bir algoritma türü olan bir bilgisayar programının tasarımında merkezi bir öneme sahiptir.
