Hesaplama ve Hesaplamalı Düşünme

1.1Hesaplama

“Hesaplama” sözcüğü çoğu kişiye okul yıllarındaki dört işlemi hatırlatır: toplama, çıkarma, çarpma ve bölme. Bilgisayar biliminde kavramın kapsamı çok daha geniştir. Bir sözlükte kelime aramak, sınıf listesini soyadına göre sıralamak, bir trafik ışığının ne zaman yeşile döneceğine karar vermek de hesaplamadır. Bu kesim hesaplamanın ortak yapısını ve hesaplamayı mümkün kılan parçaları tanıtır.

1.1.1Hesaplama nedir?

Bir öğrencinin dört sınav notunun ortalamasını bulmak, hesaplamanın en yalın örneklerinden biridir. Elde notlar vardır: 70, 85, 60 ve 75. Bu sayılar işlenecek malzemedir. Malzemeye uygulanacak kurallar da bellidir: önce notlar toplanır, sonra toplam 4'e bölünür. Kurallar uygulanınca bir sonuç çıkar: 72,5. Hesaplamanın her örneğinde bu üç parça bulunur: işlenecek veri, uygulanacak kurallar ve üretilen sonuç.

Tanımda iki sözcük özellikle önemlidir. Birincisi “kurallar”dır. Hesaplama keyfe göre yapılmaz; aynı girdiye aynı kurallar uygulanınca her seferinde aynı çıktı elde edilir. Ortalamayı bugün hesaplayan da, yarın hesaplayan da 72,5 bulur. İkincisi “işlenmesi”dir. Veriyi yalnızca saklamak ya da göstermek hesaplama sayılmaz; verinin bir kurala göre dönüştürülmesi gerekir.

Şekil 1.1 bu yapıyı gösterir. Kesik çizgili kutudaki kaynaklar ilk bakışta gözden kaçar ama her hesaplama onlara muhtaçtır. İşlem zaman alır: dört sayıyı toplamak bir an sürer, milyonlarca kaydı sıralamak dakikalar sürebilir. İşlem bellek ister: notlar ve ara toplam bir yerde tutulmalıdır. Her adım enerji harcar: telefonun pili de, veri merkezinin elektrik faturası da bunun sonucudur. Veri başka bir yerden geliyor ya da başka bir yere gidiyorsa iletişim gerekir: notlar öğrenci bilgi sisteminden ağ üzerinden okunur. Kaynaklar sonsuz değildir; bu yüzden aynı işi daha az zaman, bellek ve enerjiyle yapan yöntem daha değerlidir.

Örnekteki son gözlem önemlidir. Notların sayısı arttıkça yapılan toplama sayısı da artar; 40 not için 40 toplama gerekir. İşin süresinin girdinin büyüklüğüyle nasıl büyüdüğü, bir yöntemin iyi olup olmadığını belirleyen ölçütlerden biridir.

1.1.2Hesaplama yalnız aritmetik değildir

Ortalama bulmak sayılarla yapılan bir iştir. Bilgisayarların günlük işlerinin çoğu ise sayılarla doğrudan ilgili görünmez. Bir e-posta programı gelen iletileri tarihe göre dizer, istenmeyen iletileri ayrı bir klasöre taşır. Bir harita uygulaması iki nokta arasındaki en kısa yolu bulur. Bir çeviri programı bir dildeki cümleyi başka bir dile aktarır. Bu işlerin hepsi verinin kurallara göre işlenmesidir; dolayısıyla hepsi hesaplamadır.

Tablo 1.1 beş farklı hesaplama türünü yan yana koyar. Hiçbirinde dört işlem ön planda değildir ama hepsinde aynı üç parça vardır. Arama işleminde girdi bir sözlük ve aranan kelimedir; kural, alfabetik sırayı kullanarak doğru sayfaya gitmektir. Karar verme işleminde kural bir karşılaştırmadır: 47 < 50 doğru olduğu için çıktı “kaldı” olur. Dönüştürme işleminde bir fotoğrafın her pikseli aynı kurala göre değiştirilir. İletişimde bile kurallar vardır: mesaj belirli büyüklükte parçalara bölünür ve her parçanın başına adres yazılır.

Bu genişlik bilgisayarın neden bu kadar çok alanda kullanıldığını da açıklar. Bilgisayar özünde kurallara göre veri işleyen bir makinedir. Bir iş açık kurallarla anlatılabiliyorsa ve veri sayıya çevrilebiliyorsa, o iş bilgisayara yaptırılabilir. Metin, görüntü ve ses bilgisayarda zaten sayı dizileri olarak tutulur; bu yüzden onlar üzerindeki işlemler de hesaplamadır.

1.1.3Hesaplamanın yapı taşları

Bir hesaplamanın kâğıt üzerinde tasarlanıp bir makinede çalıştırılabilmesi için birkaç farklı parçanın bir araya gelmesi gerekir. Bu parçalar altı başlık altında toplanabilir.

Matematik

Nicelikler ve ilişkiler üzerinde işlem yapmayı sağlar. Toplama, bölme ve karşılaştırma gibi işlemler matematiğin araçlarıdır.

Mantık

Bir koşulun doğru mu yanlış mı olduğuna karar verir. “Not 50'den küçük mü?” sorusunun cevabı mantıksal bir değerdir: doğru ya da yanlış.

Veri

Problemi temsil eden girdiler ve hesaplama sırasında oluşan ara sonuçlardır. Ortalama örneğindeki notlar ve ara toplam veridir.

Algoritma

İşlemlerin sonlu ve düzenli sırasıdır. “Toplamı 0 yap, her notu ekle, sonunda not sayısına böl” bir algoritmadır.

Donanım

Adımları fiziksel olarak yürüten sistemdir: işlemci, bellek, kablolar. Algoritma ne kadar iyi olursa olsun, onu çalıştıracak bir makine olmadan sonuç elde edilmez.

Programlama dili

Algoritmayı bilgisayarın anlayacağı biçimde yazmanın aracıdır. Aynı algoritma Java, Python ya da C ile yazılabilir.

Bu parçalar birbirinin yerini tutmaz, birbirini tamamlar. Matematik ve mantık hangi işlemlerin yapılabileceğini, veri neyin işleneceğini, algoritma işlemlerin sırasını belirler. Programlama dili algoritmayı makinenin anlayacağı biçime getirir, donanım da onu çalıştırır. Bir yemek tarifi benzetmesi bu ilişkiyi somutlaştırır: malzemeler veridir, tarif algoritmadır, tarifin yazıldığı dil programlama dilidir, ocak ve tencere donanımdır. Ölçüler ve “kıvam geldi mi?” gibi kontroller de matematik ve mantığın payıdır.

1.2Bilgisayar bilimi

Bilgisayar kullanmayı bilmek ile bilgisayar bilimini bilmek farklı şeylerdir. Bir kelime işlemcide belge hazırlayan kişi bilgisayar kullanır. Bilgisayar bilimi ise o kelime işlemcinin metni nasıl sakladığı, yazım denetiminin hangi yöntemle çalıştığı, belge büyüdükçe programın neden yavaşladığı gibi soruları sorar. Bu kesim bilgisayar biliminin temel ilgi alanlarını ve bu alanın topluma karşı sorumluluklarını tanıtır.

1.2.1Bilgisayar bilimi neyi inceler?

Bilgisayar biliminin geniş alanı dört temel ilgi başlığı altında toplanabilir.

Soyutlama. Gereksiz ayrıntıları gizleyip önemli yapıya odaklanmaktır. Bir dosyayı kaydeden kullanıcı, verinin diskte hangi manyetik bölgeye ya da hangi bellek hücresine yazıldığını bilmez; yalnızca “kaydet” düğmesini görür. Diskin ayrıntıları bir soyutlama katmanının arkasına gizlenmiştir. Bilgisayar sistemleri üst üste binmiş çok sayıda böyle katmandan oluşur. Soyutlama, hesaplamalı düşünmenin de bileşenlerinden biridir.

Algoritmalar. Çözüm adımlarını tasarlamak ve bu adımları analiz etmektir. Analiz, bir algoritmanın doğru sonuç verip vermediğini ve ne kadar zaman ile bellek harcadığını sorar. Aynı problemi çözen iki algoritmadan biri bir saniyede, öteki bir saatte bitebilir.

Sistemler. Donanım ile yazılımın birlikte nasıl çalıştığını anlamaktır. İşletim sistemi, ağlar, veri tabanları ve derleyiciler bu başlığın konularıdır. Bir programın neden yavaş çalıştığı çoğu zaman algoritmaya değil, sistemin bir parçasına bağlıdır; örneğin verinin ağdan gelmesini beklemek.

İnsan ve toplum. Teknolojinin insanlar üzerindeki etkilerini, güvenliğini ve etiğini değerlendirmektir. Bir yazılım teknik olarak kusursuz çalışıp yine de insanlara zarar verebilir.

1.2.2Teknoloji ve sorumluluk

Bilgisayarlar artık bankacılıktan sağlığa, eğitimden işe alıma kadar insan hayatını doğrudan etkileyen kararlarda kullanılıyor. Bu yüzden bir yazılımın yalnızca doğru çalışması yetmez; adil, güvenli ve herkes için kullanılabilir olması da gerekir. Dört sorumluluk alanı öne çıkar.

Erişilebilirlik (accessibility)

Farklı kullanıcıların teknolojiye eşit biçimde erişebilmesidir. Görme engelli bir kullanıcı ekran okuyucuyla bir web sayfasını dinleyebilmelidir. Bunun için sayfadaki her görselin metin açıklaması bulunmalıdır. Renk körü bir kullanıcı yalnızca kırmızı ve yeşille ayrılmış bir grafiği okuyamaz; bilgi renge ek olarak şekil ya da yazıyla da verilmelidir.

Mahremiyet (privacy)

Kişisel verilerin amaçla sınırlı ve güvenli kullanılmasıdır. Bir alışveriş uygulaması teslimat için adres ister; aynı adresi kullanıcının haberi olmadan reklam şirketlerine satması amacın dışına çıkmaktır. Türkiye'de 6698 sayılı Kişisel Verilerin Korunması Kanunu bu konuda kurallar koyar.

Adalet (fairness)

Veri ve algoritmaların ayrımcı sonuç üretmemesidir. Bir algoritma geçmiş verilerden öğreniyorsa, geçmişteki önyargıları da öğrenebilir. Algoritmanın kendisi tarafsız görünse bile sonuçları belirli gruplar aleyhine olabilir.

Sürdürülebilirlik (sustainability)

Enerji tüketiminin, donanım ömrünün ve elektronik atığın dikkate alınmasıdır. Veri merkezleri büyük miktarda elektrik harcar. Kısa sürede eskiyen cihazlar elektronik atığa dönüşür ve bu atığın içinde doğaya zararlı metaller bulunur.

1.3Hesaplamanın tarihi

Bugünün bilgisayarları birkaç kuşak boyunca biriken fikirlerin ürünüdür. Bu fikirlerin çoğu, onları uygulayacak teknoloji ortaya çıkmadan çok önce düşünülmüştü. Bu kesim hesaplama tarihindeki başlıca dönüm noktalarını ve bunlar arasında belki de en önemlisini, depolanan program fikrini anlatır.

1.3.1Dönüm noktaları

Şekil 1.2 beş dönemi bir zaman çizgisi üzerinde gösterir. Her dönem bir öncekinin fikirlerini alıp daha hızlı, daha küçük ve daha ucuz bir teknolojiyle uygular.

1800'ler: mekanik tasarımlar. İngiliz matematikçi Charles Babbage, 1830'larda Analitik Makine (Analytical Engine) adını verdiği mekanik bir hesaplama makinesi tasarladı. Makine dişlilerle çalışacaktı. Ayrı bir hesaplama birimi ve sayıları tutan bir bellek birimi olacaktı. Komutları da delikli kartlardan okuyacaktı. Delikli kart fikri, desenleri kartlardaki deliklerle belirlenen Jacquard dokuma tezgâhından alınmıştı. Babbage'ın makinesi o dönemin işçilik olanaklarıyla tamamlanamadı. Yine de tasarımı, bugünkü bilgisayarların temel parçalarını ilk kez bir arada içeriyordu. Matematikçi Ada Lovelace, 1843'te makine üzerine yazdığı notlarda Bernoulli sayılarını hesaplayan adım adım bir yöntem verdi. Bu yöntem, bir makinede çalıştırılmak üzere yazılmış ilk algoritmalardan biri sayılır. Lovelace, makinenin yalnızca sayılarla değil, sembollerle ifade edilebilen her şeyle, örneğin müzik notalarıyla da işlem yapabileceğini öngördü.

1930'lar: kuramsal temel. Alan Turing 1936'da yayımladığı makalede hesaplamanın soyut bir modelini tanımladı. Bugün Turing makinesi adıyla bilinen bu model, “bir hesaplama tam olarak nedir?” sorusuna matematiksel bir cevap verdi. Aynı makale, bazı problemlerin hiçbir makineyle çözülemeyeceğini de gösterdi. Bu yıllarda elektronik devrelerle sayısal hesap yapan ilk deneysel makineler de kurulmaya başladı.

1940'lar: elektronik makineler. İkinci Dünya Savaşı yıllarında İngiltere'de şifreli mesajları çözmek için Colossus makineleri kuruldu. ABD'de top mermilerinin yörünge tablolarını hesaplamak için ENIAC geliştirildi. Bu makineler binlerce vakum tüpüyle çalışıyor ve bir oda dolusu yer kaplıyordu. Mekanik makinelerden binlerce kat hızlıydılar. Ancak yeni bir işe geçmek için kabloların ve anahtarların elle yeniden düzenlenmesi gerekiyordu.

1950'ler: depolanan program ve ilk yüksek seviyeli diller. Komutları da bellekte saklayan bilgisayarlar yaygınlaştı. Programcılar artık makinenin kablolarıyla değil, bellekteki komutlarla uğraşıyordu. 1957'de IBM'in geliştirdiği Fortran, bilimsel hesapları matematik formüllerine benzeyen bir dille yazmayı mümkün kıldı. Fortran ilk yaygın yüksek seviyeli programlama dili oldu.

Günümüz: her yerde hesaplama. Transistör, tümleşik devre ve mikroişlemci sayesinde bilgisayarlar cebe sığacak kadar küçüldü. Bugün telefonlar, bulut hizmetleri, yapay zekâ uygulamaları ve birbirine bağlı binlerce makineden oluşan dağıtık sistemler aynı temel fikirlerle çalışır.

Bu kısa tarihten çıkan ders şudur: donanım hızlanıp küçüldükçe, algoritma ve depolanan program gibi temel fikirler daha geniş alanlarda uygulanabilir hâle geldi. Fikirler değişmedi; onları taşıyan teknoloji değişti. Babbage'ın dişlileri, ENIAC'ın vakum tüpleri ve bugünün transistörleri aynı işi yapar: kurallara göre veri işler.

1.3.2Sabit ve depolanan program

Erken dönem makinelerin büyük çoğunluğu tek bir işi yapmak için kurulurdu. Bir masa hesap makinesi yalnızca dört işlem yapar. Eski bir çamaşır makinesinin döner düğmesi, dişlilerle belirlenmiş birkaç sabit programdan birini seçer. Bu makinelerde “program”, makinenin fiziksel yapısının kendisidir. Makineye yeni bir iş yaptırmak için onu yeniden kurmak gerekir.

Şekil 1.3 iki yaklaşımı yan yana koyar. Sağdaki bellekte beş hücre vardır. Üstteki üç hücrede komutlar, alttaki iki hücrede veriler durur. Bellek açısından bu hücreler arasında hiçbir fark yoktur; hepsi bit dizileridir. Bir hücrenin içeriğini komut yapan, işlemcinin onu komut olarak okumasıdır. Merkezi işlem birimi (central processing unit, CPU) bellekten bir komut getirir, onu çözer ve uygular, sonra sıradaki komuta geçer. Komut gereken veriyi yine aynı bellekten okur.

Bu basit fikrin sonucu büyüktür. Makineye yeni bir iş yaptırmak için kablolara dokunmak gerekmez; belleğe yeni komutlar yüklemek yeter. Aynı bilgisayar sabah bir kelime işlemci, öğleden sonra bir oyun, akşam bir video oynatıcı olur. Fiziksel olarak hiçbir şey değişmez; yalnızca bellekteki komutlar değişir. ENIAC'ta yeni bir işe geçmek kabloları yeniden bağlamak için günler sürebiliyordu. Depolanan programlı bir makinede aynı geçiş, yeni bir programı belleğe yükleme süresi kadardır.

Depolanan program fikri, 1945'te John von Neumann'ın EDVAC adlı makine için yazdığı raporla geniş bir çevreye yayıldı. Komutların ve verilerin aynı bellekte durduğu bu yapıya bugün von Neumann mimarisi (von Neumann architecture) denir. Bellekte saklanan bir programı çalıştıran ilk elektronik bilgisayar, 1948'de İngiltere'de Manchester Üniversitesinde çalıştırılan küçük deneysel bir makinedir. Bugünkü bilgisayarların hemen hepsi bu mimarinin bir türevidir.

Tablo 1.4 üçüncü bir satır da içerir: genel amaçlı (general purpose) bilgisayar. Depolanan program fikri genel amaçlı bilgisayarın ön koşuludur. Komutları değiştirilebilen bir makine, uygun komutlarla hemen her hesaplamayı yapabilir. Kişisel bilgisayarlar ve akıllı telefonlar genel amaçlıdır. Bunun karşıtı, tek bir iş için tasarlanmış özel amaçlı cihazlardır.

1.4Hesaplama modelleri

Bir bilgisayarın neleri hesaplayabileceğini, neleri hesaplayamayacağını sormak için önce “hesaplama” kavramını kesin biçimde tanımlamak gerekir. Gerçek bilgisayarlar bu iş için fazla karmaşıktır: işlemci türleri, bellek boyutları ve programlama dilleri birbirinden çok farklıdır. Bu yüzden bilgisayar bilimi, ayrıntılardan arındırılmış basit makine modelleri kullanır. Bu modellerin en ünlüsü Turing makinesidir. Bu kesim Turing makinesinin parçalarını tanıtır, bir makineyi adım adım çalıştırır ve bu modelin bilgisayarların sınırları hakkında ne söylediğini anlatır.

1.4.1Turing makinesi

Turing, modelini bir insanın kâğıt kalemle hesap yapışını gözleyerek kurdu. Hesap yapan kişi kâğıda simgeler yazar, yazdıklarını okur, bir sonraki adımda ne yapacağına o an aklında tuttuğu bilgiye ve gördüğü simgeye bakarak karar verir. Turing bu davranışı en yalın parçalarına ayırdı.

Şekil 1.4 makinenin bir anlık görüntüsüdür. Bantta ikili 1011 sayısı yazılıdır; geri kalan hücreler boştur. Başlığın altındaki üçgen, okunacak hücreyi gösterir. Başlığın altındaki kutuda makinenin durumu yazar: q0.

Modelin gücü basitliğinden gelir. Makinenin bir adımı her zaman aynı biçimdedir:

1. Başlığın altındaki simge okunur.
2. Geçiş kuralları tablosunda (şu anki durum, okunan simge) çiftine uyan satır bulunur.
3. O satırın söylediği simge hücreye yazılır.
4. Başlık satırın söylediği yöne bir hücre kayar ya da yerinde kalır.
5. Makine satırın söylediği yeni duruma geçer. Yeni durum DUR ise makine durur; değilse ilk adıma dönülür.

Makinenin “zekâsı” yalnızca kural tablosundadır. Makine tabloya bakar ve söyleneni yapar; geçmiş adımları hatırlamaz, ileriyi planlamaz. Hatırlaması gereken bir şey varsa bunu ya bantta bir simge olarak ya da durumunda taşır. Sonsuz uzunluktaki bant, makinenin belleğidir. Gerçek bilgisayarların belleği sonludur; model ise bellek sıkıntısını bir kenara bırakıp yalnızca “bu iş kurallarla yapılabilir mi?” sorusuna odaklanır.

1.4.2Geçiş kuralları

Bir Turing makinesinin ne yapacağını yalnızca kural tablosu belirler. İlk örnek, bantta yazılı ikili bir sayıya 1 ekleyen makinedir. İkili sistemde 1 eklemek onluk sistemdekine benzer. En sağdaki basamaktan başlanır. Basamak 0 ise 1 yapılır ve iş biter. Basamak 1 ise 0 yapılır ve elde bir soldaki basamağa aktarılır; aynı işlem orada tekrarlanır. Sayının solunda basamak kalmamışsa, oraya 1 yazılır.

Tablo 1.5 üç kuraldan oluşur. Makinenin tek bir çalışma durumu vardır, q0. Bu durumda okunabilecek üç simge vardır: 1, 0 ve □. Her biri için tabloda tam olarak bir kural bulunur. Bu yüzden makine hiçbir adımda ne yapacağı konusunda kararsız kalmaz. Kural 1, elde taşıma işini yapar ve makineyi yine q0'da bırakır; böylece aynı kural, art arda gelen bütün 1'lere uygulanabilir. Kural 2 ve 3 makineyi durdurur.

Bu tablo, ikili toplama bilgisini yalnızca üç satıra sığdırır. Makine “ikili sayı” ya da “elde” kavramlarını bilmez; yalnızca simgeleri okur ve yazar. Kuralların anlamını veren, tabloyu tasarlayan insandır.

1.4.3Adım adım: 111 + 1

Makineyi bantta 111 yazılıyken çalıştıralım. 111₂ onluk sistemde 4 + 2 + 1 = 7'dir; beklenen sonuç 8, yani 1000₂'dir. Başlık en sağdaki basamağın üzerindedir ve durum q0'dır.

Şekil 1.5'teki başlangıç durumundan sonra makine şu adımları izler:

1. Adım 1. Okunan 1, durum q0. Uyan kural 1'dir: 0 yazılır, başlık sola kayar, durum q0 kalır. Bant □□110□ olur. En sağdaki basamakta 1 + 1 = 10 hesaplandı: basamağa 0 yazıldı, elde 1 bir sola taşındı.
2. Adım 2. Başlık 4. hücrede, okunan yine 1. Kural 1 yeniden uygulanır. Bant □□100□ olur; elde hâlâ sürüyor.
3. Adım 3. Başlık 3. hücrede, okunan 1. Kural 1 üçüncü kez uygulanır. Bant □□000□ olur. Sayının bütün basamakları 0'a döndü ama elde henüz yazılmadı.
4. Adım 4. Başlık 2. hücrede, okunan □. Uyan kural 3'tür: 1 yazılır ve makine DUR durumuna geçer. Bant □1000□ olur.

Şekil 1.6 son iki adımın görüntüsünü verir. Bütün çalışma aşağıdaki izleme tablosunda özetlenmiştir. Tablonun her satırı, bir kural uygulanmadan önceki durumu ve uygulandıktan sonraki bandı gösterir.

Makine dört adımda durdu ve bantta 1000 kaldı: 1000₂ = 8 = 7 + 1. Sonuç doğrudur. Tablo 1.6 önemli bir gözlemi de içerir: her satırda yapılacak işi yalnızca “Durum” ve “Okunan” sütunları belirledi. Makinenin önceki adımları, bandın geri kalanı ya da sayının kaç basamaklı olduğu hiçbir kararı etkilemedi.

Adım sayısı da girdiye bağlıdır. Makine sağdan itibaren art arda gelen her 1 için bir adım, elde nerede biterse orada bir adım daha harcar. Sağında k tane 1 bulunan bir sayı için makine k + 1 adımda durur. 111'in sağında üç tane 1 vardır; adım sayısı 3 + 1 = 4'tür.

1.4.4Durumun belleği: eşlik denetimi

1 ekleyen makinenin tek bir çalışma durumu vardı. Bazı işlerde makinenin, okuduğu simgelerle ilgili bir bilgiyi aklında tutması gerekir. Bu bilgi durumda saklanır. Bir bit dizisindeki 1'lerin sayısının çift mi tek mi olduğunu bulan makine bunu açıkça gösterir. Simülatördeki hazır makinelerden biri olan bu makinenin iki çalışma durumu vardır: “çift” ve “tek”. Başlık dizinin en solundaki simgede başlar ve sağa doğru ilerler.

Tablo 1.7'deki makine bantta hiçbir şeyi değiştirmeden ilerler; her hücreye okuduğu simgeyi geri yazar. Değişen tek şey durumdur. Makine bir 1 okuduğunda durum çiftten teke ya da tekten çifte döner, 0 okuduğunda durum aynı kalır. Dizinin sonundaki boş hücreye gelindiğinde durum, o ana kadar okunan 1'lerin sayısının çift mi tek mi olduğunu söyler. Makine bu cevabı boş hücreye Ç ya da T olarak yazar ve durur.

Bu makine, Turing makinesindeki durumun bir tür küçük bellek olduğunu gösterir. Makine 1'lerin tam sayısını bilmez; yalnızca işin gerektirdiği kadarını, yani sayının çift mi tek mi olduğunu bilir. Aynı fikir gerçek bilgisayarlarda da kullanılır: verinin iletim sırasında bozulup bozulmadığını anlamak için gönderilen eşlik biti, tam olarak bu hesapla bulunur.

1.4.5Evrensel Turing makinesi

Şimdiye kadar görülen her Turing makinesi tek bir iş yapıyordu: biri sayıya 1 ekliyordu, öteki eşlik denetliyordu. Yeni bir iş için yeni bir kural tablosu, yani yeni bir makine gerekiyordu. Bu açıdan her Turing makinesi sabit programlı bir makineye benzer. Turing, aynı makalede bu sınırı aşan bir makine de tanımladı.

Evrensel makinenin kendi kural tablosu sabittir ve hiç değişmez. Değişen, bandına yazılan tablodur. Bandına 1 ekleyen makinenin tablosu yazılırsa 1 ekler; eşlik makinesinin tablosu yazılırsa eşlik denetler. Kural tablosu artık makinenin parçası değil, bantta duran bir veridir.

Bu fikir, Tanım 1.3'te tanımlanan depolanan program fikrinin kuramsal temelidir. Evrensel Turing makinesinin bandı bilgisayarın belleğine, banttaki kural tablosu bellekteki programa, evrensel makinenin sabit kuralları da işlemcinin komutları çözüp uygulayan devrelerine karşılık gelir. Turing bu fikri 1936'da kâğıt üzerinde ortaya koydu. Gerçek depolanan programlı bilgisayarlar ise on yıldan fazla bir süre sonra kurulabildi.

Turing makinesi basit görünse de çok güçlüdür. Bugün bilinen her bilgisayarın, yeterli zaman ve bellek verildiğinde yapabildiği her hesabı bir Turing makinesi de yapabilir. Başka bir deyişle, bir Turing makinesinin yapamadığı bir hesabı bugünkü hiçbir bilgisayar yapamaz. Bilgisayarlar Turing makinesinden çok daha hızlıdır ama hesaplayabildikleri şeylerin kümesi aynıdır. Bu yüzden Turing makinesi, “bilgisayar neyi hesaplayabilir?” sorusunu incelemek için yeterli bir modeldir.

1.4.6Bilgisayarların sınırları

Bilgisayarlar çok hızlıdır ama her şeyi yapamaz. Sınırların bir kısmı kaynaklardan, bir kısmı verinin ve modelin doğasından, bir kısmı da hesaplamanın kendisinden gelir. Altı sınır öne çıkar.

Zaman

Büyük girdiler bazı algoritmaları pratik olmaktan çıkarabilir. Bir algoritmanın süresi girdi büyüdükçe çok hızlı artıyorsa, sonuç kullanıcının bekleyebileceği süre içinde gelmez.

Bellek

Veri ve ara sonuçlar sonlu bir depolama alanında tutulur. Turing makinesinin bandı sonsuzdur; gerçek bilgisayarın belleği değildir.

Enerji

Her işlem ve her veri aktarımı enerji tüketir. Telefonun pili, bir veri merkezinin soğutma sistemi ve elektrik faturası bu sınırın günlük yüzleridir.

Hesaplanabilirlik (computability)

Bazı problemler için her girdide doğru sonuç veren bir algoritma yoktur. En bilinen örnek durma problemidir.

Veri kalitesi

Eksik ya da hatalı girdi, doğru bir algoritmayı bile yanlış sonuca götürür.

Model sınırı

Program gerçek dünyanın yalnızca seçilmiş özelliklerini temsil eder. Modelde olmayan bir özellik, sonuçta da hesaba katılmaz.

İlk üç sınır kaynak sınırıdır. Daha hızlı bir işlemci, daha büyük bir bellek ya da daha verimli bir algoritma bu sınırları geriye iter. Hesaplanabilirlik ise başka türden bir sınırdır: donanım ne kadar güçlenirse güçlensin aşılamaz. Son iki sınır hesaplamanın gerçek dünyayla bağından kaynaklanır.

Durma problemi. Hesaplanabilirlik sınırının en bilinen örneği durma problemidir (halting problem). Soru şudur: herhangi bir program ve onun girdisi verildiğinde, programın bir gün durup durmayacağına her durumda doğru karar veren genel bir algoritma yazılabilir mi? Bazı programlar için cevap kolaydır. 1 ekleyen Turing makinesinin her girdide durduğu açıktır. Bazı programlar için ise cevabı bulmak çok zordur. Aşağıdaki kısa program bunun ünlü bir örneğidir:

n = 6
while n ≠ 1
    if n mod 2 = 0
        n = n / 2
    else
        n = 3 * n + 1
yaz("durdu")

Program n = 6 ile çalıştırılırsa n sırasıyla 6, 3, 10, 5, 16, 8, 4, 2, 1 değerlerini alır ve program sekiz turda durur. n = 27 ile çalıştırılırsa 111 tur sürer ve ara değerler 9.232'ye kadar çıkar. Bu programın her pozitif n için durup durmadığı bugün hâlâ bilinmiyor. Bilgisayarlarla çok büyük sayılara kadar denenmiş ve hep durduğu görülmüştür; ama her n için durduğu kanıtlanamamıştır.

Turing 1936'da daha güçlü bir şey gösterdi: her program ve her girdi için durup durmayacağına doğru karar veren genel bir algoritma hiçbir zaman yazılamaz. Gerekçenin ana fikri şöyledir. Böyle bir “kahin” algoritmanın var olduğunu varsayalım. Bu kahini kullanarak ters davranan bir program yazılabilir: program kendisi hakkında kahine sorar; kahin “durur” derse sonsuza kadar döner, “durmaz” derse hemen durur. Bu ters program kendisi üzerinde çalıştırıldığında kahin ne cevap verirse versin yanılmış olur. Demek ki böyle bir kahin var olamaz. Bu sonuç hız ya da bellekle ilgili değildir; mantıksal bir imkânsızlıktır.

Model sınırı. Bir navigasyon uygulaması yolları uzunlukları ve ortalama hızlarıyla modeller. Bir yolun o sabah su baskını yüzünden kapandığı modelde yoksa, uygulama kapalı yolu önermeye devam eder. Program yanlış hesap yapmamıştır; gerçek dünyanın modelde bulunmayan bir özelliğini bilememiştir. Her program bir modelle çalışır ve modelin dışında kalan her şey programın da dışında kalır.

1.5Bilgi ve algoritma

Bir şeyi bilmenin iki farklı yolu vardır. İnsan bir olguyu bilebilir: “Ankara Türkiye'nin başkentidir.” Bir işin nasıl yapıldığını da bilebilir: “Ankara'ya gitmek için şu otobüse binilir, şu durakta inilir.” Bilgisayar biliminin asıl ilgilendiği ikinci türdür, çünkü bilgisayara bir işi yaptırmak için o işin nasıl yapıldığını adım adım anlatmak gerekir. Bu kesim iki bilgi türünü karşılaştırır, algoritmayı tanımlar ve iki klasik algoritmayı, karekök bulmayı ve Öklid algoritmasını, ayrıntılı izler.

1.5.1Bildirimsel ve buyurgan bilgi

Şekil 1.7 iki türü yan yana koyar. “Bir üçgenin iç açıları toplamı 180°'dir” cümlesi doğru bir bilgi verir ama bir işi nasıl yapacağımızı söylemez. Bu bilgiyle bir üçgenin eksik açısı bulunabilir; ancak bunun için yine bir yöntem gerekir. Sağdaki adımlar ise doğrudan uygulanabilir. Adımları izleyen kişi ya da makine, karekökün ne olduğunu tam olarak anlamasa bile sonuca ulaşır.

Karekökün tanımı da bildirimsel bir bilgidir: “x'in karekökü, karesi x olan pozitif sayıdır.” Bu tanım bir sayının karekök olup olmadığını denetlemeye yarar. 5'in karesi 25 olduğu için 5, 25'in kareköküdür. Ama tanım, 10'un karekökünün kaç olduğunu bulmanın yolunu göstermez. Bildirimsel bilgi “ne” sorusuna, buyurgan bilgi “nasıl” sorusuna cevap verir.

Tablo 1.9 her satırda aynı konunun iki yüzünü gösterir. Sıralı liste satırı özellikle öğreticidir: bir listenin sıralı olup olmadığını denetlemek kolaydır, ama karışık bir listeyi sıralamak bir yöntem gerektirir. Bilgisayar programları buyurgan bilginin yazılı hâlidir. Bildirimsel bilgi ise programın doğru çalışıp çalışmadığını denetlemekte kullanılır: sıralama programının çıktısının gerçekten sıralı olduğu, bildirimsel tanımla sınanır.

1.5.2Algoritma

Buyurgan bilginin her türü bir makineye verilemez. “Güzel bir yemek yap” bir talimattır ama hangi adımların izleneceğini söylemez. “Tuzu kararınca ekle” bir adımdır ama ne kadar tuz ekleneceği belli değildir. Bir makinenin izleyebileceği talimatların açık, uygulanabilir ve sonlu olması gerekir.

Algoritmalar buyurgan bilgiyi açık, uygulanabilir ve sonlu adımlara dönüştürür. Algoritmayı yazmanın tek bir yolu yoktur. Türkçe cümleler, akış diyagramları ya da bir programlama diline benzeyen ama onun kadar katı olmayan sözde kod (pseudocode) kullanılabilir. Bu notta algoritmalar sunumdaki gibi kısa sözde kodlarla verilir. Sözde kodda while “koşul doğru olduğu sürece altındaki satırları tekrarla”, return “sonucu döndür ve bitir”, yaz “sonucu ekrana yaz” anlamına gelir. İçeri girintili satırlar, üstlerindeki while satırına bağlıdır.

1.5.3Karekökü yaklaşık bulma

Karekök bulmanın eski ve çok etkili bir yöntemi, İskenderiyeli Heron'a atfedilir ve Babil yöntemi adıyla da anılır. Yöntemin fikri şudur: bir tahmin karekökten büyükse, x'in tahmine bölümü karekökten küçük olur; tahmin karekökten küçükse bölüm büyük olur. Gerçek karekök bu iki sayının arasındadır. Bu yüzden ikisinin ortalaması, çoğu zaman tahminin kendisinden daha iyi bir tahmindir.

Bir örnekle görelim. x = 25 ve tahmin 13 olsun. 25 ÷ 13 ≈ 1,92'dir. Gerçek karekök 5, 13 ile 1,92 arasındadır. İki sayının ortalaması (13 + 1,92) ÷ 2 ≈ 7,46'dır; 7,46, 13'ten 5'e çok daha yakındır. Aynı işlem yeni tahminle tekrarlanır.

Sunumdaki sözde kod yöntemi beş satırda yazar:

x = 25
tahmin = 1
while |tahmin * tahmin - x| > 0.01
    tahmin = (tahmin + x / tahmin) / 2
yaz(tahmin)

Satırlar sırasıyla şunu yapar:

1. x = 25: karekökü aranan sayı x değişkenine konur.
2. tahmin = 1: kaba bir başlangıç tahmini seçilir. Pozitif her başlangıç değeri işe yarar; 1 en basit seçimdir.
3. while |tahmin * tahmin - x| > 0.01: tahminin karesi ile x arasındaki fark, yani hata, hesaplanır. Dikey çizgiler mutlak değeri gösterir: farkın işareti atılır, yalnızca büyüklüğü kalır. Hata 0,01'den büyükse döngünün içindeki satır çalışır; değilse döngü biter. 0,01 değeri “yeterince yakın” sınırıdır; bu tür sınırlara eşik (tolerance) denir.
4. tahmin = (tahmin + x / tahmin) / 2: tahmin ile x/tahmin'in ortalaması yeni tahmin olur. Sonra 3. satıra dönülür ve hata yeniden denetlenir.
5. yaz(tahmin): döngü bittiğinde son tahmin ekrana yazılır.

Döngünün her çalışmasına bir tur (iteration) denir. Sunum, algoritmayı x = 25 için tur tur izler. Şekil 1.8 tahminin sayı doğrusundaki yolculuğunu, Tablo 1.10 ise her turdaki değerleri gösterir.

Tabloda dikkat çeken üç nokta vardır. Birincisi, ilk turda hata 24'ten 144'e çıktı. Tahmin 1'den 13'e sıçradı ve 5'i geçti. Bu bir hata değildir. 1 çok küçük bir tahmindi ve x/tahmin = 25 çok büyüktü; ortalamaları karekökün öbür yanına düştü. İkinci turdan sonra tahmin her zaman 5'in üstünde kalır ve her turda ona yaklaşır.

İkincisi, yaklaşma hızı giderek artar. Hata 144'ten 30,67'ye, sonra 4,23'e, 0,15'e ve 0,0002'ye indi. Son turlarda her tur, doğru basamak sayısını yaklaşık iki katına çıkarır. Bu yüzden yöntem yalnızca beş turda dört ondalık basamaklık doğruluğa ulaştı. Son tahmin tam olarak 5 değil, yaklaşık 5,00002'dir; ama hatası eşiğin çok altındadır.

Üçüncüsü, durma koşulu tahminin kendisine değil, karesine bakar. Algoritma karekökün gerçek değerini bilmez; bilseydi hesaplamaya gerek kalmazdı. Bildiği tek şey bildirimsel tanımdır: karekökün karesi x'e eşittir. Durma koşulu bu tanımı kullanır. Buyurgan yöntem ilerler, bildirimsel tanım ne zaman durulacağına karar verir.

1.5.4Öklid algoritması

Bilinen en eski algoritmalardan biri, Yunan matematikçi Öklid'in MÖ 300 dolaylarında yazdığı Elemanlar adlı eserde yer alır. Algoritma iki pozitif tam sayının en büyük ortak bölenini bulur. Yaklaşık 2.300 yıllık olmasına rağmen bugün hâlâ kullanılır; örneğin kesirleri sadeleştirmede ve internet güvenliğini sağlayan şifreleme yöntemlerinde.

Tanımı doğrudan uygulayan bir yöntem düşünülebilir: küçük sayıdan başlayıp aşağı doğru her sayıyı denemek ve iki sayıyı da bölen ilk sayıda durmak. 48 ile 18 için denemeler 18, 17, 16, … diye gider ve 6'da durur; 13 deneme gerekir. Bu yöntem doğrudur ama yavaştır. 1.000.000 ile 999.999 için 999.999 deneme yapar, çünkü bu iki sayının EBOB'u 1'dir. Öklid'in yöntemi aynı soruyu yalnızca iki turda cevaplar.

Öklid algoritmasının sözde kodu şudur:

GCD(a, b)
while b ≠ 0
    r = a mod b
    a = b
    b = r
return a

Algoritma iki değişkenle çalışır: a ve b. Döngünün her turunda önce a'nın b'ye bölümünden kalan hesaplanıp r'ye konur. Sonra eski b, a'nın; kalan r de b'nin yerini alır. Böylece her turda problem daha küçük sayılarla aynı probleme dönüşür. b sıfır olunca döngü biter ve a'daki değer döndürülür.

Mod işlemine kısaca bakalım. 48 mod 18, 48'in 18'e bölümünden kalandır. 18, 48'in içine iki kez sığar: 2 × 18 = 36. Geriye 48 − 36 = 12 kalır. Demek ki 48 mod 18 = 12'dir. Genel olarak a = q × b + r yazılır; burada q bölüm, r kalandır ve 0 ≤ r < b'dir.

Şekil 1.9 algoritmanın gözle görülür bir yorumunu verir. 48 birim uzunluğunda ve 18 birim genişliğinde bir dikdörtgen, eşit karelerle kalansız döşenmek isteniyor. Kullanılabilecek en büyük karenin kenarı, 48 ile 18'in EBOB'udur. Dikdörtgenden kenarı 18 olan kareler kesildikçe geriye daha küçük bir dikdörtgen kalır. Her kesme, algoritmanın bir turuna karşılık gelir. Kalan dikdörtgen bir gün eş karelerle tam dolar; o karelerin kenarı aranan sayıdır.

1.5.5Öklid algoritması adım adım

GCD(48, 18) çağrısını satır satır izleyelim. Başlangıçta a = 48 ve b = 18'dir.

1. 1. tur. b ≠ 0 koşulu doğrudur (18 ≠ 0). r = 48 mod 18 = 12 olur: 48'den 18 uzunluğunda iki parça çıkar, 12 kalır. Sonra a = 18, b = 12 olur. Artık küçük sayı bölünen olmuştur.
2. 2. tur. 12 ≠ 0 doğrudur. r = 18 mod 12 = 6 olur: 18'den 12 uzunluğunda bir parça çıkar, 6 kalır. Sonra a = 12, b = 6 olur.
3. 3. tur. 6 ≠ 0 doğrudur. r = 12 mod 6 = 0 olur: 12'den 6 uzunluğunda iki parça çıkar, hiçbir şey kalmaz. Sonra a = 6, b = 0 olur.
4. Döngü sonu. 0 ≠ 0 koşulu yanlıştır; döngü biter. return a satırı 6'yı döndürür.

Şekil 1.10 her turda a çubuğundan b uzunluğunda kaç parça çıktığını ve geriye ne kaldığını gösterir. Kalan, bir sonraki turda b'nin yerine geçer. Bütün çalışma Tablo 1.11'de özetlenmiştir.

Sonuç: GCD(48, 18) = 6'dır. Denetim kolaydır: 48 = 8 × 6 ve 18 = 3 × 6. 8 ile 3'ün 1'den büyük ortak böleni yoktur; bu yüzden 6'dan büyük bir ortak bölen de yoktur. Algoritma üç turda bitti. Tanımı doğrudan uygulayan yöntem 13 deneme yapmıştı.

1.5.6Öklid algoritması neden doğru sonuç verir ve durur?

Bir algoritmanın birkaç örnekte doğru sonuç vermesi, her girdide doğru çalıştığını göstermez. Öklid algoritması için iki soru sorulur: neden her zaman doğru sonucu bulur ve neden her zaman durur?

Teoremin gerekçesi şöyledir. Bölme işlemi a = q × b + r biçiminde yazılır; buradan r = a − q × b elde edilir. Bir d sayısı hem a'yı hem b'yi bölüyorsa, a − q × b farkını da böler; yani r'yi de böler. Tersine, d hem b'yi hem r'yi bölüyorsa q × b + r toplamını, yani a'yı da böler. Demek ki iki sayı çiftinin ortak bölenleri aynıdır. Ortak bölenleri aynı olan iki çiftin en büyük ortak böleni de aynıdır.

Örnekte bunu sayılarla görmek mümkündür. 48 ile 18'in ortak bölenleri 1, 2, 3 ve 6'dır. 18 ile 12'nin ortak bölenleri de 1, 2, 3 ve 6'dır. Sayılar küçüldü ama ortak bölenler değişmedi. Algoritmanın her turu, EBOB'u koruyarak problemi küçültür. Son turda ikinci sayı 0 olur. Her pozitif sayı 0'ı böldüğü için a ile 0'ın ortak bölenleri a'nın bölenleridir ve bunların en büyüğü a'nın kendisidir. Bu yüzden algoritma a'yı döndürür.

Durma sorusunun cevabı kalanın özelliğinden gelir. Kalan her zaman bölenden küçüktür: 0 ≤ r < b. Her turda b'nin yerine r geçtiği için b her turda kesinlikle küçülür. b, negatif olmayan bir tam sayıdır. Negatif olmayan bir tam sayı sonsuza kadar küçülemez; en geç b kez küçüldükten sonra 0'a ulaşır. Bu yüzden döngü her girdide sonlu sayıda turdan sonra biter. Pratikte tur sayısı b'den çok daha küçüktür. Kalanlar en az her iki turda bir yarıya iner. Bu yüzden bir milyondan küçük sayılar için bile 30 civarından fazla tur gerekmez; en kötü durumdaki 832.040 ile 514.229 çifti 28 turda biter.

1.6Hesaplamalı düşünme

Karekök ve Öklid algoritmaları hazır problemlere hazır çözümlerdi. Gerçek hayattaki problemler ise çoğu zaman dağınık gelir: “Öğrencilerin derse kaydını kolaylaştıran bir sistem lazım.” Böyle bir istekten çalışan programa giden yol birkaç işten geçer. Problem parçalara ayrılır, parçalar arasındaki benzerlikler görülür, önemli olan önemsizden ayrılır ve en sonunda adımlar yazılır. Bu düşünme biçimine hesaplamalı düşünme denir. Bu kesim hesaplamalı düşünmenin dört bileşenini tek tek ele alır ve sonunda hepsini bir örnekte birleştirir.

1.6.1Hesaplamalı düşünme nedir?

Kavram, bilgisayar bilimci Jeannette Wing'in 2006'da yayımladığı kısa bir makaleyle yaygınlaştı. Wing'e göre hesaplamalı düşünme yalnızca programcıların değil, herkesin öğrenmesi gereken temel bir beceridir; tıpkı okuma, yazma ve aritmetik gibi. Hesaplamalı düşünmek bilgisayar gibi düşünmek demek değildir. Bilgisayar yalnızca kendisine söyleneni yapar; hesaplamalı düşünme ise ona ne söyleneceğini bulma becerisidir.

Şekil 1.11 bileşenleri bir sıra içinde numaralandırır ama uygulamada bu sıra katı değildir. Algoritma yazılırken yeni bir alt problem fark edilebilir ve ayrıştırmaya geri dönülür. Bir örüntü, soyutlamanın neye odaklanacağını belirleyebilir. Dört bileşen birlikte ve birbirini besleyerek çalışır.

Hesaplamalı düşünmenin izleri günlük hayatta da görülür. Bir aşçı büyük bir yemeği hazırlık, pişirme ve sunum aşamalarına ayırır; bu ayrıştırmadır. Bir öğretmen her yıl benzer hataları yapan öğrenciler için aynı ek çalışma sayfasını kullanır; bu örüntü tanımadır. Bir şehir haritası binaların renklerini değil, sokakları gösterir; bu soyutlamadır. Bir yemek tarifi de bir algoritmadır.

1.6.2Ayrıştırma

Sunumdaki örnek bir çevrim içi kayıt sistemidir. Kullanıcılar bir web sayfasından kayıt olacak, bilgileri saklanacak ve kendilerine bir onay e-postası gidecektir. Bu sistemi tek parça olarak düşünmek zordur: nereden başlanacağı belli değildir ve bir hata çıktığında nerede olduğu bulunamaz.

Şekil 1.12 ayrıştırmanın iki düzeyini gösterir. Birinci düzeyde sistem dört ana alt göreve bölünür. İkinci düzeyde bazı alt görevler yeniden bölünür. Ağacın en altındaki her yaprak küçük, tek başına yazılıp test edilebilen bir iştir. Örneğin “biçim denetimi” yalnızca e-posta adresinde @ işareti olup olmadığına ve parolanın en az sekiz karakter olup olmadığına bakan küçük bir parça olabilir.

Tablo 1.12 ayrıştırmanın asıl değerini ortaya koyar: alt görevler girdi ve çıktılarıyla birbirine bağlanır. Form doğrulamanın çıktısı, kaydın girdisidir. Kaydın ürettiği kayıt numarası, bildirimin girdisidir. Bu bağlar açıkça yazıldığında üç önemli yarar ortaya çıkar.

• Ayrı geliştirme ve test. Her alt problem ayrı geliştirilebilir ve test edilebilir. Bildirim parçasını yazan kişi, form doğrulamanın nasıl çalıştığını bilmek zorunda değildir; yalnızca kendisine hangi bilgilerin geleceğini bilmelidir.
• Açık arayüzler. Alt problemlerin girdi ve çıktıları açıkça tanımlanır. Bir parça değiştirildiğinde, girdisi ve çıktısı aynı kaldığı sürece öteki parçalar etkilenmez.
• Bağımlılıkların erken görülmesi. Hangi parçanın hangisini beklediği erken fark edilir. Bildirim, kayıt bitmeden çalışamaz; çünkü kayıt numarasına ihtiyaç duyar. Bu bilgi, işlerin hangi sırayla yapılacağını belirler.

1.6.3Örüntü tanıma

Kayıt sistemine geri dönelim. Sistem üç tür kişiyi kaydedecektir: öğrenciler, personel ve ziyaretçiler. Her biri için ayrı bir kayıt formu tasarlanabilir. Ancak formlar yan yana konunca bir şey dikkati çeker.

Şekil 1.13 tekrar eden yapıyı gösterir. Üç formun dört alanından üçü aynıdır. Bu bir örüntüdür. Örüntüyü fark etmenin pratik bir değeri vardır. Ad alanının boş bırakılmadığını, kimlik numarasının 11 haneli olduğunu ve e-posta adresinin doğru biçimde yazıldığını denetleyen kodu üç kez yazmak gerekmez. Bir kez yazılır, üç formda kullanılır. Kimlik numarası denetiminde bir hata bulunduğunda da tek bir yerde düzeltilir.

Örüntüler yalnızca veride değil, işlemlerde de görülür. Ortalama hesabı ve Öklid algoritması farklı işler yapar, ama ikisi de aynı kalıbı izler: bir koşul doğru olduğu sürece bir işlemi tekrarla, koşul yanlış olunca sonucu ver. Karekök algoritması da bu kalıba uyar. Bu kalıp o kadar sık görülür ki her programlama dilinde onun için özel bir yapı, döngü vardır.

1.6.4Soyutlama

Örüntü tanıma tekrar eden yapıyı bulur; soyutlama bu yapıya bir ad verir ve onu ayrıntılardan ayırır. Kayıt örneğinde üç türün ortak alanları tek bir “Kişi” modelinde toplanır.

Şekil 1.14 sonucu gösterir. Kişi modelinde üç alan vardır. Öğrenci kaydında Kişi'nin bütün alanları bulunur; bunlara ek olarak bir öğrenci numarası vardır. Personel bir birim, ziyaretçi bir ziyaret tarihi ekler. Sistemin büyük bölümü, örneğin e-posta gönderen bildirim parçası, yalnızca Kişi modeliyle çalışır. Bildirim parçası, e-posta gönderdiği kişinin öğrenci mi, personel mi olduğunu bilmek zorunda değildir; yalnızca e-posta alanına ihtiyaç duyar. Farklılıklar yalnızca gerektiği yerde, örneğin öğrenci listesini hazırlayan parçada, görülür.

İyi bir soyutlama, önemli farkları kaybetmeden tekrar eden yapıyı ortaklaştırır. Kişi modeline öğrenci numarasını da koymak yanlış olurdu; çünkü ziyaretçinin öğrenci numarası yoktur ve bu alan çoğu kayıtta boş kalırdı. E-posta alanını modelden çıkarmak da yanlış olurdu; çünkü bildirim parçası çalışamazdı. Soyutlamanın ölçüsü amaçtır: amaca hizmet eden ayrıntı kalır, hizmet etmeyen gizlenir.

1.6.5Algoritma tasarımı ve test

Algoritma tasarımı tek seferde biten bir iş değildir; bir döngü içinde ilerler.

Şekil 1.15'teki döngünün beş aşaması vardır.

1. Örnek oluşturma. Kod yazmadan önce birkaç girdi ve bu girdiler için beklenen çıktılar hazırlanır. Ortalama için: 70, 85, 60, 75 girdisinin beklenen çıktısı 72,5'tir. Beklenen çıktı elle hesaplanır; algoritmanın sonucu bununla karşılaştırılacaktır.
2. Adımları yazma. Çözüm sözde kodla yazılır.
3. Elle izleme. Sözde kod, hazırlanan örnek girdiyle kâğıt üzerinde satır satır çalıştırılır. Her adımda değişkenlerin değeri bir izleme tablosuna (trace table) yazılır. Bu notta Turing makinesi, karekök ve Öklid için kullanılan tablolar böyle tablolardır.
4. Sınırları deneme. Normal girdilerin yanında en küçük, en büyük ve geçersiz girdiler de denenir. Bu tür girdilere sınır durumu (edge case) denir. Hataların çoğu bu girdilerde ortaya çıkar.
5. Düzeltme. Bir hata bulunduğunda yalnızca belirti değil, hatanın temel nedeni düzeltilir. Sonra döngü yeniden başlar: düzeltilen algoritma bütün örneklerle tekrar izlenir.

Bu döngüyü bir örnekle izleyelim. Bir not listesinin ortalamasını bulan şu algoritma yazılmış olsun:

toplam = 0
sayac = 0
while okunacak not var
    toplam = toplam + not
    sayac = sayac + 1
yaz(toplam / sayac)

Algoritma, Örnek 1.1'deki hesabın aynısını yapar: toplam ve sayaç 0'dan başlar, her not toplama eklenir ve sayaç bir artar; sonunda toplam sayaca bölünür. Şimdi farklı türden girdilerle test edelim.

Tablo 1.13 son satırda bir hata yakaladı. Hiç not girilmezse döngü hiç çalışmaz; toplam ve sayaç 0'da kalır ve son satırda 0, 0'a bölünür. Program çöker. Normal girdilerle yapılan testler bu hatayı hiçbir zaman göstermezdi.

Hatayı düzeltmenin iki yolu vardır. Birincisi belirtiyi gidermektir: “sayaç 0 ise ortalamayı 0 kabul et.” Program artık çökmez ama yanlış bir şey söyler: notu hiç olmayan bir öğrencinin ortalaması 0 görünür ve öğrenci dersten kalmış sanılır. İkincisi temel nedeni düzeltmektir. Temel neden şudur: boş bir listenin ortalaması tanımsızdır ve algoritma bu durumu hiç düşünmemiştir. Doğru düzeltme, bu durumu ayrıca ele almaktır:

toplam = 0
sayac = 0
while okunacak not var
    toplam = toplam + not
    sayac = sayac + 1
if sayac = 0
    yaz("Hiç not girilmedi")
else
    yaz(toplam / sayac)

Düzeltilmiş algoritmada if satırı bir karar verir: sayaç 0 ise uyarı yazılır, değilse (else) ortalama hesaplanır. Algoritma dört test durumuyla yeniden izlendiğinde ilk üçü yine 72,5, 100 ve 50 verir; dördüncüsü artık beklenen uyarıyı yazar.

1.6.6Dört bileşen bir arada: not hesaplama aracı

Hesaplamalı düşünmenin dört bileşeni bir problemi baştan sona çözerken nasıl birlikte çalışır? Bunu küçük bir problemle görelim. Bir öğretim elemanı, öğrencilerin dönem sonu puanını hesaplayan basit bir araç istiyor. Puan, vize notunun %40'ı ile final notunun %60'ının toplamıdır. Puanı 50 ve üstü olan öğrenci geçer.

Ayrıştırma. Problem dört alt göreve bölünür. Notları okuma: girdi öğrencinin vize ve final notu, çıktı iki sayı. Notları doğrulama: girdi iki sayı, çıktı “geçerli” ya da “geçersiz”. Puan hesaplama: girdi iki geçerli not, çıktı puan. Karar: girdi puan, çıktı “geçti” ya da “kaldı”.

Örüntü tanıma. Vize ve final notları aynı kurallara uyar: ikisi de 0 ile 100 arasında olmalıdır. Doğrulama kuralı bir kez yazılır ve iki nota da uygulanır. Puan hesabı da bir örüntüdür: her not kendi ağırlığıyla çarpılır ve sonuçlar toplanır. İleride ödev notu eklenirse aynı kalıba bir terim daha eklenir.

Soyutlama. Araç için bir öğrenci yalnızca iki sayıdan ibarettir: vize ve final. Öğrencinin adı, bölümü, devam durumu ya da sınav kâğıdındaki cevaplar bu hesabı etkilemez ve modelde yer almaz.

Algoritma tasarımı. Adımlar sözde kodla yazılır:

oku(vize, final)
if vize < 0 or vize > 100 or final < 0 or final > 100
    yaz("Geçersiz not")
else
    puan = (40 * vize + 60 * final) / 100
    if puan >= 50
        yaz(puan, "geçti")
    else
        yaz(puan, "kaldı")

Puan formülünde yüzdeler 0,4 ve 0,6 yerine 40 ve 60 olarak yazılıp sonuç 100'e bölünür. İki yazım matematikte aynıdır. Ancak bilgisayarlar 0,4 gibi ondalık sayıları ikili sistemde tam olarak saklayamaz ve küçük yuvarlama farkları oluşabilir. Örneğin 55 × 0,4 + 72 × 0,6 işlemi bir bilgisayarda 65,2 yerine 65,19999… sonucunu verebilir. Tam sayılarla çarpıp en sonda bölmek bu riski azaltır.

Bu küçük örnekte dört bileşenin her biri bir iş gördü. Ayrıştırma işi parçalara böldü ve hangi parçanın hangisini beklediğini gösterdi. Örüntü tanıma doğrulama kuralının iki kez yazılmasını önledi. Soyutlama gereksiz öğrenci bilgilerini dışarıda bıraktı. Algoritma tasarımı ve test, sınırdaki bir öğrencinin haksız yere kalmasına yol açabilecek bir hatayı daha kod yazılmadan yakaladı.

1.7Özet

• Hesaplama, verinin kurallara göre işlenmesidir; aritmetikle sınırlı değildir. Arama, sıralama, karar verme, dönüştürme ve iletişim de hesaplamadır. Her hesaplamada bir girdi, bir işlem ve bir çıktı vardır; işlem zaman, bellek, enerji ve iletişim kaynaklarını kullanır.
• Hesaplamanın yapı taşları matematik, mantık, veri, algoritma, donanım ve programlama dilidir. Algoritma bir fikirdir; program o fikrin belirli bir dildeki yazılışıdır.
• Bilgisayar bilimi bilginin temsilini, işlenmesini ve problemlerin çözüm yöntemlerini inceler. Başlıca ilgi alanları soyutlama, algoritmalar, sistemler ve insan ile toplumdur. Teknolojinin sorumlulukları erişilebilirlik, mahremiyet, adalet ve sürdürülebilirliktir.
• Babbage ve Lovelace'tan Turing'e, Colossus ve ENIAC'tan bugünkü telefonlara kadar temel fikirler aynı kaldı; donanım hızlanıp küçüldükçe bu fikirler daha geniş alanlara yayıldı.
• Sabit programlı makinede iş, makinenin fiziksel düzeniyle belirlenir. Depolanan programlı makinede komutlar bellekte veri gibi saklanır; yeni bir program yüklemek makineye yeni bir iş verir. Bu fikir genel amaçlı bilgisayarı mümkün kıldı.
• Turing makinesi bant, okuma/yazma başlığı, durum ve geçiş kurallarından oluşan soyut bir hesaplama modelidir. Her adımı yalnızca (durum, okunan simge) çifti belirler. 1 ekleyen makine 111'i dört adımda 1000'e çevirir.
• Evrensel Turing makinesi, bantta verilen başka bir makinenin kurallarını okuyup onu taklit eder. Depolanan program fikrinin kuramsal temeli budur.
• Bilgisayarların sınırları zaman, bellek, enerji, hesaplanabilirlik, veri kalitesi ve modelden gelir. Durma problemi gibi hesaplanabilirlik sınırları hiçbir donanımla aşılamaz.
• Bildirimsel bilgi neyin doğru olduğunu, buyurgan bilgi bir sonuca nasıl ulaşılacağını anlatır. Algoritma, buyurgan bilgiyi açık, uygulanabilir ve sonlu adımlara dönüştürür.
• Karekök yöntemi tahmin ile x/tahmin'in ortalamasını alarak ilerler ve tahminin karesi x'e yeterince yaklaşınca durur; x = 25 için beş turda 5,0000'a ulaşır.
• Öklid algoritması EBOB(a, b) = EBOB(b, a mod b) eşitliğini kullanır; kalan her turda küçüldüğü için her zaman durur. GCD(48, 18) üç turda 6 verir.
• Hesaplamalı düşünme dört bileşeni birleştirir: ayrıştırma (alt problemlere bölme, girdi ve çıktıları tanımlama), örüntü tanıma (tekrarları bulma), soyutlama (önemliye odaklanıp gerisini gizleme) ve algoritma tasarımı (açık ve sıralı adımlar). Tasarım normal, en küçük, uç ve geçersiz girdilerle test edilir; hatanın belirtisi değil, temel nedeni düzeltilir.

1.8Kavram listesi

Terimlerin İngilizce karşılıkları ve öteki sunumlardaki kullanımları terim sözlüğünde bulunur.

• hesaplama computation
• girdi input
• bilgisayar bilimi computer science
• erişilebilirlik accessibility
• mahremiyet privacy
• adalet fairness
• sürdürülebilirlik sustainability
• sabit program fixed program
• depolanan program stored program
• genel amaçlı general purpose
• von Neumann mimarisi von Neumann architecture
• Turing makinesi Turing machine
• bant tape
• simge symbol
• okuma/yazma başlığı read/write head
• durum state
• geçiş kuralı transition rule
• evrensel Turing makinesi universal Turing machine
• hesaplanabilirlik computability
• durma problemi halting problem
• bildirimsel bilgi declarative knowledge
• buyurgan bilgi imperative knowledge
• algoritma algorithm
• sözde kod pseudocode
• tur iteration
• eşik tolerance
• sonsuz döngü infinite loop
• Öklid algoritması Euclid's algorithm
• en büyük ortak bölen (EBOB) greatest common divisor
• kalan remainder
• mod modulo
• hesaplamalı düşünme computational thinking
• ayrıştırma decomposition
• örüntü tanıma pattern recognition
• soyutlama abstraction
• algoritma tasarımı algorithm design
• test testing
• test durumu test case
• sınır durumu edge case
• izleme tablosu trace table

1.9Kendini Dene

1. İkili sayıya 1 ekleyen Turing makinesi bantta 1111 (ikili 15) ile çalıştırılıyor; başlık en sağdaki basamakta. Makine kaç adımda durur, hangi kurallar kullanılır, bantta ne kalır?

   Cevap

   Dört basamağın hepsi 1 olduğu için kural 1 dört kez uygulanır; her seferinde 0 yazılır ve başlık sola kayar. Bant 0000 olur ve başlık sayının solundaki boş hücreye gelir. Beşinci adımda □ okunur; kural 3 ile 1 yazılır ve makine durur. Bantta 10000 kalır: 16 = 15 + 1. Adım sayısı 4 + 1 = 5'tir; kural 2 hiç kullanılmaz.

2. Eşlik denetimi yapan makine bantta 10010 ile çalıştırılıyor. Her simgeden sonra durum ne olur, makine sonunda ne yazar?

   Cevap

   Durum “çift” ile başlar. 1 okunur: tek. 0: tek. 0: tek. 1: çift. 0: çift. Altıncı adımda boş hücre okunur; durum “çift” olduğu için Ç yazılır ve makine durur. Bant 10010Ç olur. Dizide iki tane 1 vardır ve iki çifttir.

3. GCD(105, 75) Öklid algoritmasıyla hesaplanıyor. Her turda a, b ve r ne olur? Kaç tur sürer, sonuç nedir?

   Cevap

   1. tur: 105 = 1 × 75 + 30, r = 30; a = 75, b = 30. 2. tur: 75 = 2 × 30 + 15, r = 15; a = 30, b = 15. 3. tur: 30 = 2 × 15 + 0, r = 0; a = 15, b = 0. Döngü biter; üç turda 15 döndürülür. Denetim: 105 = 7 × 15, 75 = 5 × 15; 7 ile 5'in 1'den büyük ortak böleni yoktur.

4. Karekök algoritması x = 9 ve tahmin = 1 ile çalıştırılıyor. Her turdan sonra tahmin ve hata ne olur? Algoritma kaç turda durur?

   Cevap

   Başlangıçta hata |1 − 9| = 8'dir. 1. tur: (1 + 9) ÷ 2 = 5, hata |25 − 9| = 16. 2. tur: (5 + 1,8) ÷ 2 = 3,4, hata |11,56 − 9| = 2,56. 3. tur: (3,4 + 2,6471) ÷ 2 ≈ 3,0235, hata ≈ 0,1417. 4. tur: (3,0235 + 2,9767) ÷ 2 ≈ 3,0001, hata ≈ 0,0005. Hata 0,01'in altına indiği için algoritma dört turda durur ve yaklaşık 3,0001 yazar.

5. Aşağıdaki bilgilerin her biri bildirimsel mi, buyurgan mıdır? (a) Su deniz seviyesinde 100 °C'de kaynar. (b) Bir sayının 3'e bölünüp bölünmediğini anlamak için rakamları toplanır; toplam 3'e bölünüyorsa sayı da bölünür. (c) Bir dikdörtgenin alanı, kenar uzunluklarının çarpımıdır.

   Cevap

   (a) bildirimseldir; bir olgu bildirir. (b) buyurgandır; bir sonuca ulaşmak için izlenecek adımları söyler: rakamları topla, toplamı denetle. (c) bildirimseldir; alanın ne olduğunu tanımlar. Alan hesaplamak için bu tanım kullanılabilir ama cümle bir yöntem tarif etmez, bir eşitlik bildirir.

6. Silindirindeki çıkıntılarla tek bir şarkı çalan mekanik bir müzik kutusu ile internetten indirilen şarkıları çalan bir akıllı hoparlör, program açısından nasıl ayrılır?

   Cevap

   Müzik kutusu sabit programlıdır: çalacağı şarkı silindirdeki çıkıntıların fiziksel düzenidir; başka bir şarkı için silindiri değiştirmek gerekir. Akıllı hoparlör depolanan programlıdır: içindeki işlemci bellekte saklanan bir yazılımı çalıştırır; yazılım güncellemesiyle yeni özellikler kazanabilir. Akıllı hoparlörün kendisi yine de belirli işler için tasarlanmıştır ve kullanıcı ona kendi programını yükleyemez; bu yüzden genel amaçlı bir bilgisayar sayılmaz.

7. Aşağıdaki durumların her biri bilgisayarların hangi sınırına örnektir? (a) Bir öğrenci, her programın sonsuz döngüye girip girmeyeceğini önceden söyleyen bir araç yazmaya çalışıyor. (b) Saniyede 10⁹ deneme yapan bir program, 50 bitlik bir anahtarın bütün olasılıklarını en kötü durumda yaklaşık 13 günde deneyebiliyor. (c) Bir anket formunda yaş alanına 250 yazılmış ve yaş ortalaması anlamsız çıkmış.

   Cevap

   (a) hesaplanabilirlik sınırıdır; bu durma problemidir ve böyle genel bir araç yazılamaz. (b) zaman sınırıdır: 2⁵⁰ ÷ 10⁹ ≈ 1,13 × 10⁶ saniye, yaklaşık 13 gün eder; daha hızlı donanım süreyi kısaltır ama anahtara eklenen her bit süreyi yeniden iki katına çıkarır. (c) veri kalitesi sınırıdır; algoritma doğru çalışsa bile hatalı girdi yanlış sonuç verir.

8. Bir metindeki kelime sayısını sayan bir algoritma test edilecek. Normal bir cümlenin yanında hangi sınır ve geçersiz durumlar denenmelidir? En az dört durum ve her biri için beklenen sonuç nedir?

   Cevap

   Örnek bir test kümesi: boş metin → 0; tek kelime (“Merhaba”) → 1; kelimeler arasında birden fazla boşluk (“bir␣␣iki”) → 2; metnin başında ve sonunda boşluk (“␣bir iki␣”) → 2; yalnızca boşluklardan oluşan metin → 0. Algoritma her boşlukta sayacı artırıyorsa son üç durumda yanlış sonuç verir. Temel neden boşlukları değil kelimeleri saymamaktır; doğru düzeltme, bir kelimenin başladığı yerleri saymaktır.

1.10İleri okuma

• J. M. Wing, “Computational Thinking”, Communications of the ACM, 49(3), 2006: hesaplamalı düşünmenin neden herkes için temel bir beceri olduğunu üç sayfada anlatan, kavramı yaygınlaştıran kısa makale.
• J. V. Guttag, Introduction to Computation and Programming Using Python (3. baskı, MIT Press, 2021), Bölüm 1: bildirimsel ve buyurgan bilgi ayrımı, karekök bulma yöntemi ve sabit/depolanan programlı makineler bu nottakine çok yakın bir dille anlatılır.
• C. Petzold, The Annotated Turing (Wiley, 2008): Turing'in 1936 makalesini satır satır açıklayarak Turing makinesini, evrensel makineyi ve hesaplanabilirliği matematik ön bilgisi gerektirmeden kurar.
• M. Sipser, Introduction to the Theory of Computation (3. baskı, Cengage, 2012), Bölüm 3–4: Turing makinelerinin ve durma probleminin kesin matematiksel anlatımı; konuya ileri düzeyde devam etmek isteyenler için.

1.11Kaynaklar

1. J. M. Wing, “Computational Thinking”, Communications of the ACM, 2006.
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, MIT Press.
3. A. B. Downey, C. Mayfield, Think Java, Green Tea Press.
4. M. Sipser, Introduction to the Theory of Computation, Cengage.

İlgili sayfalar: Hesaplama ve Hesaplamalı Düşünme sunumu · Çalışma soruları · Turing makinesi simülatörü · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.