Algoritma

Açılış sahnesi

Kerem, iki el yazmasının sayfa sayılarını karşılaştırıyor. Birinin iki yüz elli iki, ötekinin yüz beş sayfası var. Grup, müstensihin iki el yazmasını da aynı büyüklükte formalar hâlinde, yani aynı sayıda sayfadan oluşan kâğıt demetleriyle mi hazırladığını merak ediyor. Böyle bir forma büyüklüğü varsa, iki sayfa sayısını da tam bölmeliydi. Kerem, en büyük ortak böleni bulmak için bir yöntem hatırlıyor: büyük sayıyı küçüğe böl, kalanı al, küçük sayıyı kalana böl, kalan sıfır olana kadar sürdür.

Tolga, bu yöntemin bir yemek tarifinden farkını soruyor: ikisi de adım adım ilerliyordu. Selin, bazı yöntemlerin hiçbir zaman bitmeyebileceğini, "bulana kadar ara" diyen bir talimatın bir yöntem sayılıp sayılamayacağını düşünüyor. Lina, bir sözlükte bir sözcük aramanın bir yöntem olduğunu, ama bir cümleyi çevirmenin öyle olmadığını söylüyor. Barış, bir mahkemede davaların yargıçlara kurayla dağıtılmasının bir yöntem olup olmadığını, kuranın sonucunu kimse önceden bilemediğine göre, merak ediyor. Defne ise bir tanı kılavuzunun akış şemasının bir algoritma olup olmadığını, şemanın bazı kutularının "hastanın genel durumunu değerlendir" dediğini hatırlayarak soruyor. Bu ders, Mantık ve Akıl Yürütme programının Metalojik ve Hesaplanabilirlik kursunda, bir algoritmanın sezgisel kavramının hangi özellikleri taşıdığını, bu kavramı kesinleştirmek için önerilen birbirinden farklı tanımların neden aynı kapsama sahip çıktığını ve bir yöntemi mekanik kılan şeyin tam olarak ne olduğunu soruyor.

Bu derste ne olacak

Önce bu dersin yerini belirleyelim. Metateori modülünün Karar verilebilirlik dersi, karar yöntemi ve yarı karar verilebilirlik kavramlarını tanımladı, Turing'in mekanik yöntemi kesin olarak tanımlayan 1936 tarihli makalesini ve durma problemini tanıttı. Birinci derece mantık modülünün son dersi ise tam ve sonlu aksiyomlu bir kuramın karar verilebilir olduğunu gösterdi. Akademinin önceki derslerinde Öklid'in Elemanlar'ı da iki kez ele alınmıştı. Bu ders, Hesaplanabilirlik modülünü açıyor: şimdiye kadar sezgisel olarak kullanılan "mekanik yöntem" kavramının kendisini inceliyor. Turing makinesinin ayrıntıları ve kesin tanımların denkliği, modülün sonraki derslerinde ele alınacak.

Sonra üç kaynağa bakacağız. Öklid, Elemanlar'ın yedinci kitabının ilk iki önermesinde, iki sayının en büyük ortak ölçüsünü bulan ve bugün onun adıyla anılan yöntemi verir. Andrey Markov, 1954'te yayımladığı Algoritmalar Kuramı kitabında, algoritma kavramını, işaret dizilerini yeniden yazan kurallar aracılığıyla kesinleştirir. Donald Knuth ise 1968'de yayımladığı Bilgisayar Programlama Sanatı dizisinin ilk cildinde, bir algoritmanın taşıması gereken beş özelliği sayar.

Ardından üç itirazı tartacağız: algoritmanın bilgisayarların yaptığı şey olduğu ve ayrıca çözümlenmeye ihtiyaç duymadığı, algoritma kavramının kendisinin belirsiz sözcüklere dayandığı ve gerçek hayattaki önemli yöntemlerin çoğunun yargı içerdiği için algoritma olmadığı itirazları.

Sonda, bir yöntemin algoritma olup olmadığını sınamanın dört adımını göstereceğiz: yöntemin adımlarını açıkça yazmak, her adımın yoruma yer bırakıp bırakmadığını denetlemek, yöntemin her girdi için sonlu sayıda adımda bitip bitmediğini sormak ve adımların yargı değil yalnızca kurala uymayı gerektirip gerektirmediğini belirlemek.

Merkez soru

Sorumuz şu: bir algoritmanın sezgisel kavramı hangi özellikleri taşır ve bir yöntemi yalnızca adım adım ilerleyen bir tariften ayırıp mekanik kılan şey nedir?

Ölçülü iddiam şu: bir algoritma, belirli bir sorun sınıfının her örneğine uygulanabilen, sonlu uzunlukta bir talimatlar dizisidir. Sezgisel kavram birkaç özellik taşır. Birincisi sonluluktur: talimatlar sonlu bir metinle yazılır ve her girdi için yöntem sonlu sayıda adımda biter. İkincisi belirliliktir: her adım, onu uygulayan için yoruma yer bırakmaz ve ne yapılacağı tam olarak bellidir. Üçüncüsü etkinliktir: her adım, kalem ve kâğıtla, anlayış ya da sezgi gerektirmeden, yalnızca kurala uyarak yapılabilecek kadar basittir. Dördüncüsü genelliktir: yöntem tek bir örneği değil, bir sınıftaki bütün örnekleri çözer. Öklid'in yöntemi bu özelliklerin hepsini taşır ve yazılı olarak bilinen en eski algoritmalardan biridir. Knuth, bu özellikleri, girdi ve çıktı şartlarıyla birlikte beş madde olarak sistemleştirdi. Ama bu özellikler kesin bir tanım değildir. "Yoruma yer bırakmaz" ve "yeterince basit" gibi ifadeler, bir yöntemin algoritma olduğunu göstermeye yeter, ama bir sorun için hiçbir algoritma bulunmadığını kanıtlamaya yetmez. Olumsuz sonuçlar için kesin bir tanım gerekir. Markov'un yeniden yazma kuralları, Turing'in makineleri ve öteki tanımlar bu ihtiyaçtan doğdu. Bir yöntemi mekanik kılan şey, onun her adımının, uygulayanın ne yaptığını anlamasını değil, yalnızca işaretleri kurallara göre değiştirmesini gerektirmesidir.

Sıfır noktası

Bir öğrenci "algoritma" sözcüğünü duyduğunda, çoğu zaman bir bilgisayar programını düşünür. Ama algoritmalar bilgisayarlardan çok eskidir. Öklid'in en büyük ortak ölçü yöntemi iki bin yılı aşkın bir süredir kullanılmaktadır. "Algoritma" sözcüğünün kendisi de, dokuzuncu yüzyılda Bağdat'ta çalışan matematikçi el-Hârizmî'nin adının Latince biçiminden gelir. Onun Hint rakamlarıyla hesap üzerine yazdığı kitabın Latince çevirisi, bu adla yayılmıştır.

Bir algoritmanın ne olduğunu sezgisel olarak anlamak için, onu benzer şeylerden ayırmak yararlıdır. Bir yemek tarifi de adım adım ilerler. Ama "biraz tuz ekle" ya da "kıvamını bulana kadar pişir" gibi adımlar, uygulayanın yargısına bırakılır. İki aşçı, aynı tarifle farklı yemekler yapabilir. Bir algoritmada ise iki kişi, aynı girdiyle aynı adımları izlediğinde, aynı sonuca ulaşmalıdır.

Algoritmanın bir başka özelliği, bir sorunun tek bir örneğini değil, bütün örneklerini çözmesidir. İki yüz elli iki ile yüz beşin en büyük ortak bölenini bulmak bir hesaptır. Herhangi iki sayının en büyük ortak bölenini bulmanın bir yöntemini vermek ise bir algoritmadır. Algoritma, sonsuz sayıda olası girdiye uygulanabilen sonlu bir talimatlar dizisidir.

Görüşler ve pozisyonlar

Algoritma kavramının ne tür bir kavram olduğu konusunda üç görüş var.

Birinci görüş, sezgisel kavram görüşüdür. Buna göre algoritma, matematikçilerin ve hesap yapanların yüzyıllardır kullandığı sezgisel bir kavramdır. Bir yöntemin algoritma olduğunu görmek için bir tanıma ihtiyaç yoktur; Öklid'in yöntemine bakmak yeter.

İkinci görüş, kesin tanım görüşüdür. Buna göre algoritma kavramı ancak kesin bir tanımla, örneğin Turing makineleriyle ya da yeniden yazma kurallarıyla, anlam kazanır. Sezgisel kavram belirsizdir ve bir sorunun çözümsüz olduğunu kanıtlamak için yetersizdir.

Üçüncü görüş, çözümleme görüşüdür. Buna göre sezgisel kavram belirli bir içeriğe sahiptir ve kesin tanımlar, bu içeriği çözümleme girişimleridir. Bir kesin tanımın doğru olup olmadığı, sezgisel kavramı ne ölçüde yakaladığına bağlıdır.

Bu ders üçüncü görüşü temel alır ve birinci görüşün, sezgisel kavramın bir yöntemi tanımak için yeterli olduğu gözlemini kabul eder. Birinci görüş, Öklid'in yönteminin bir algoritma olduğunu bilmek için bir tanıma gerek olmadığını doğru görür. Ama bir sorun için hiçbir algoritma bulunmadığını göstermek istendiğinde, bütün olası algoritmalar hakkında bir şey söylemek gerekir ve bu, kesin bir tanım olmadan yapılamaz. İkinci görüş, bu ihtiyacı doğru teşhis eder. Ama kesin tanımın neden doğru tanım olduğu sorusunu açık bırakır. Üçüncü görüş, bu soruyu sezgisel kavram ile kesin tanım arasındaki ilişkiye bağlar.

Argümanın yapısı

Bir yöntemin algoritma olup olmadığını sınamak için dört adım izlenebilir.

Birinci adım, yöntemin adımlarını açıkça yazmaktır. Sınayan, yöntemin başladığı girdiyi, her adımda ne yapılacağını ve sonucun nasıl okunacağını sonlu bir metinle yazar.

İkinci adım, her adımın yoruma yer bırakıp bırakmadığını denetlemektir. Sınayan, her adımı farklı kişilerin aynı biçimde uygulayıp uygulamayacağını sorar. Farklı uygulamalara izin veren bir adım, yöntemi algoritma olmaktan çıkarır.

Üçüncü adım, yöntemin her girdi için sonlu sayıda adımda bitip bitmediğini sormaktır. Sınayan, yöntemin bazı girdiler için sonsuza kadar sürüp sürmeyeceğini denetler ve bitişi bir argümanla gösterir.

Dördüncü adım, adımların yargı değil yalnızca kurala uymayı gerektirip gerektirmediğini belirlemektir. Sınayan, her adımın, uygulayanın ne yaptığını anlamasını mı, yoksa yalnızca işaretleri kurallara göre değiştirmesini mi gerektirdiğini sorar.

En güçlü itiraz

Bu yaklaşıma üç yönden ciddi itiraz yapılabilir.

Algoritma kavramını ciddiye alan düşünce şu cevabı verebilir. Bir algoritma, belirli bir sorun sınıfının her örneğine uygulanabilen, sonlu uzunlukta bir talimatlar dizisidir ve sonluluk, belirlilik, etkinlik ve genellik özelliklerini taşır. Kerem'in formalarında görüldüğü gibi, Öklid'in yöntemi bu özelliklerin hepsini taşır ve bitişi, sayıların her adımda küçülmesiyle ayrıca kanıtlanır. Tolga'nın tarifinde görüldüğü gibi, belirlilik, herkesin aynı biçimde sahip olduğu en basit yeteneklere indirgenmektir. Selin'in bitmeyen aramasında görüldüğü gibi, her adımı belirli olan ama her zaman bitmeyen bir yöntem, Knuth'un ayrımıyla, bir algoritma değil bir hesaplama yöntemidir. Lina'nın iki işi ve Defne'nin akış şeması, kurala indirgenebilen adımlarla yargı gerektiren adımlar arasındaki sınırı gösterdi. Barış'ın kurası ise rastlantının dışarıdan gelen bir girdi olarak algoritmaya alınabildiğini gösterdi. Knuth, sezgisel kavramı beş özellikle sistemleştirdi. Ama bu özellikler, bir sorunun çözümsüz olduğunu kanıtlamaya yetmeyen sözcüklere dayanır. Markov'un yeniden yazma kuralları gibi kesin tanımlar, bu ihtiyaçtan doğdu. Bir yöntemi mekanik kılan şey, onun her adımının, uygulayanın ne yaptığını anlamasını değil, yalnızca işaretleri kurallara göre değiştirmesini gerektirmesidir.

Açık kalan sorular

Selin'in bitmeyen araması, her adımı belirli olan bir yöntemin her zaman bitmeyebileceğini gösterdi. Bir yöntemin her girdi için bitip bitmediğini her zaman önceden bilebilir miyiz? Bilemiyorsak, bir yöntemin algoritma olup olmadığı her zaman karar verilebilir bir soru mudur?

Lina'nın iki işi, çevirinin bugün kurallara indirgenemediğini, ama bir gün indirgenebileceğini düşündürdü. Bir işin algoritma olup olmadığı, o işin kendisinin bir özelliği midir, yoksa bizim o iş hakkındaki bilgimizin mi? Bugün yargı gerektiren her iş, ilke olarak bir algoritmayla yapılabilir mi?

Barış'ın kurası, rastlantının bir algoritmaya dışarıdan gelen bir girdi olarak alınabildiğini gösterdi. Rastlantı içeren yöntemler, belirli yöntemlerin yapamadığı bir şeyi yapabilir mi? Yoksa her rastlantılı yöntem, yeterince uzun bir belirli yöntemle taklit edilebilir mi?

Yaygın hatalar

Kendin dene

Aklında kalsın

Beş cümlede dersin iskeleti.

Bir algoritma, belirli bir sorun sınıfının her örneğine uygulanabilen, sonlu uzunlukta bir talimatlar dizisidir ve sonluluk, belirlilik, etkinlik ve genellik özelliklerini taşır; onu bir tariften ayıran, her adımının yargı değil yalnızca kurala uymayı gerektirmesidir.

Öklid'in Elemanlar'ının yedinci kitabı yazılı olarak bilinen en eski algoritmalardan birini verdi, Markov'un Algoritmalar Kuramı kitabı algoritma kavramını dizileri yeniden yazan kurallarla kesinleştirdi, Knuth'un Bilgisayar Programlama Sanatı'nın ilk cildi ise sezgisel kavramı beş özellikle sistemleştirdi ve her zaman bitmeyen yöntemleri hesaplama yöntemi olarak ayırdı.

Bir yöntemin algoritma olup olmadığı dört adımla sınanır: adımlarını açıkça yazmak, her adımın yoruma yer bırakıp bırakmadığını denetlemek, her girdi için bitip bitmediğini sormak ve adımların yargı değil yalnızca kurala uymayı gerektirip gerektirmediğini belirlemek.

Algoritmanın bilgisayarların yaptığı şey olduğu, belirsiz sözcüklere dayandığı ve önemli yöntemlerin çoğunun algoritma olmadığı itirazları, kavramın bilgisayarlardan önce var olduğunu ve onların sınırını belirlediğini, sezgisel kavramın farklı kesin tanımların örtüştüğü sağlam bir çekirdeğe sahip olduğunu ve kavramın değerinin kurala indirgenebilen ile yargı gerektiren arasındaki sınırı çizmekte yattığını gördüğümüzde cevaplanabilir.

Bu yüzden algoritma kavramı, bir yöntemin algoritma olduğunu tanımak için yeterince açıktır, ama bir sorun için hiçbir algoritma bulunmadığını kanıtlamak için kesin bir tanıma ihtiyaç duyar.

Sonraki derse köprü

Bu dersin bütün örnekleri, bir yöntemin algoritma olduğunu gösteriyordu. Ama Selin, daha önce gördükleri bir sonucu hatırlıyor: yüklemler mantığında geçerlilik için hiçbir algoritma yoktu. Bunu göstermek için, olası bütün algoritmalar hakkında bir şey söylemek gerekiyordu. Knuth'un beş özelliği, bir yöntemin bu özellikleri taşıdığını görmeye yetiyordu, ama olası bütün yöntemlerin bir listesini vermiyordu.

Kerem, Öklid'in yöntemini uygularken kalem ve kâğıtla ne yaptığını adım adım yazıyor: sayıları kâğıda yazdı, bir kısmını sildi, yerine başka sayılar yazdı, her adımda yalnızca birkaç rakama baktı. Tolga, her algoritmanın bu kadar basit işlemlere indirgenip indirgenemeyeceğini soruyor: bir işaret okumak, bir işaret yazmak, bir sonraki işarete geçmek. Lina, Markov'un kurallarının da yalnızca işaret dizilerini değiştirdiğini hatırlatıyor.

Bir sonraki ders bu soruya dönüyor. Turing makinesi dersi, Turing'in kalem ve kâğıtla hesap yapan bir insanın ne yaptığını hangi en basit işlemlere indirgediğini, bu işlemlerle kurulan soyut makinenin nasıl çalıştığını ve bütün öteki makineleri taklit edebilen evrensel bir makinenin varlığının ne anlama geldiğini soruyor.