Bölüm 1.2: Hesaplama ve Hesaplamalı Düşünme

1.2.1Programlama ve hesaplama

Bilgisayar çok hızlı çalışan ama hiçbir şeyi kendiliğinden bilmeyen bir yardımcıdır. Saniyede milyarlarca işlem yapar, yine de hangi işlemi hangi sırayla yapacağına kendisi karar veremez. Bu kararı ona yazılı bir talimat listesi verir. O listeye program, listeyi yazma işine programlama denir. Programın yaptırdığı iş ise çoğu zaman bir hesaplamadır: veri alınır, işlenir ve bir sonuç üretilir. Bu kesim iki kavramı ayrı ayrı tanımlar ve küçük bir Java programında ikisinin nasıl birleştiğini gösterir.

1.2.1.1Programlama

Programlama dili, insan ile makine arasında bir köprüdür. İnsan için okunaklı, makine için de kesin olmalıdır. Günlük konuşmada “biraz bekle” ya da “uygun bir sayı seç” demek yeterlidir; dinleyen kişi boşlukları kendi yorumuyla doldurur. Bilgisayar böyle bir yorum yapmaz. Ne kadar bekleyeceği, hangi sayıyı seçeceği açıkça yazılmamışsa ya hata verir ya da yanlış bir şey yapar. Bu yüzden programlama dillerinin kuralları sıkıdır: bir noktalı virgül eksikse Java programı derlenmez.

Programlanan bir bilgisayar karmaşık görevleri yerine getirebilir. Akıllı telefon, tablet, dizüstü bilgisayar, çamaşır makinesi ve otomobil, içlerinde çalışan programlar sayesinde iş görür. İnternet üzerinden alışveriş, haber, iletişim ve eğitim de programların ürünüdür. Bilgisayarlar evden iş yerine, eğlenceden eğitime her alana girmiştir.

Programlama öğrenmenin bir yararı da düşünme biçimine yansır. Bir işi bilgisayara yaptırabilmek için önce o işi tam olarak anlamak gerekir. “Ortalama al” gibi kısa bir isteğin arkasında kaç sayı olduğu, sayıların nereden geldiği ve sonucun nasıl yazılacağı gibi sorular yatar. Bu soruları sormayı ve yanıtlamayı öğrenen kişi, problem çözmede de daha düzenli düşünür.

1.2.1.2Programlamanın rolü

Programlama, bilgisayarların istediğimiz görevleri yerine getirmesi için kullanılan bir araçtır. Programcılar bilgisayarları hayatın her alanında daha kullanışlı ve verimli hâle getirir. Üç alan bu rolü iyi örnekler:

• Otomasyon: Akıllı termostatlar sıcaklığı ölçüp ısıtıcıyı açar ya da kapatır. Aydınlatma ve güvenlik sistemleri belirli koşullarda kendiliğinden devreye girer. Fabrikalardaki robotlar aynı kaynağı ya da montajı binlerce kez aynı doğrulukla yapar.
• Sağlık: Kalp pili kalbin ritmini sürekli ölçer ve gerektiğinde uyarı verir. MR cihazı ölçülen sinyallerden görüntü üretir; bu dönüşüm baştan sona bir hesaplamadır. Hastane bilgi sistemleri ve randevu sistemleri de programlarla çalışır.
• Eğitim: Çevrim içi ders platformları, öğretim yazılımları, sınav ve not sistemleri programlanmış bilgisayarların ürünüdür.

Elektrik-elektronik mühendisliği bu alanların hepsine dokunur. Bir mikrodenetleyiciye yüklenen gömülü yazılım, bir sensörden gelen sinyali süzen sayısal filtre ya da bir motorun hızını ayarlayan kontrol döngüsü programlamayla yazılır. Devre tasarımı ile yazılım arasındaki sınır, bu tür sistemlerde giderek incelir.

1.2.1.3Hesaplama

Hesaplama bilgisayarların temel işlevidir. Ekranda bir harfin çizilmesi bile hesaplamadır: harfin biçimi, boyutu ve konumu sayılara çevrilir, bu sayılardan hangi piksellerin hangi renge boyanacağı hesaplanır. Hesaplama üç tür iş içerir. Matematiksel işlemler toplama ve çarpma gibi işlemlerdir. Mantıksal kararlar bir koşulun doğru olup olmadığına bakar. Veri işleme ise veriyi sıralamak, aramak ve biçimlendirmek gibi genel işleri kapsar.

Şekil 1.2.1'de görülen düzen bütün hesaplamalarda aynıdır. Değişen, verinin türü ve işlemin karmaşıklığıdır. Birkaç örnek:

• Veri analizi: Bir sıcaklık sensöründen bir gün boyunca alınan ölçümlerden ortalama, en büyük değer ve eğilim hesaplanır; sonuç bir grafik olarak çizilir.
• Benzetim (simülasyon): Bir devrenin ya da hava durumunun matematiksel modeli kurulur. Bilgisayar modeli küçük zaman adımlarıyla ilerletir ve sistemin nasıl davranacağını öngörür.
• Oyun geliştirme: Her karede nesnelerin konumları fizik kurallarıyla güncellenir, çarpışmalar denetlenir, bilgisayarın yönettiği karakterler karar verir.

Programlama ile hesaplama arasındaki ilişki şöyle özetlenebilir: hesaplama yapılan iştir, programlama o işin tarifini yazmaktır. İyi yazılmış bir program, aynı hesaplamayı daha az adımla, daha az bellekle ve daha az hatayla yaptırır. Bu yüzden programlama hesaplamayı daha etkili ve verimli hâle getirir.

1.2.1.4Hesaplamanın yapı taşları

Hesaplamanın iki temel yapı taşı vardır. Birincisi matematiktir: toplama, çıkarma, çarpma ve bölme gibi işlemler. İkincisi mantıktır: kararlar, mantıksal ifadelerin değerlendirilmesiyle alınır. “Eğer hava güneşliyse dışarı çık” cümlesi bir mantık işlemidir. Önce “hava güneşli mi?” sorusunun yanıtı bulunur; yanıt doğru ya da yanlıştır. Ardından bu yanıta göre bir eylem seçilir.

Aşağıdaki Java programı iki yapı taşını birlikte kullanır. İki sayının toplamını ve çarpımını hesaplar, sonra bir koşula göre karar verir.

public class Hesaplama {
    public static void main(String[] args) {
        int a = 7, b = 3;
        int toplam = a + b;     // matematik
        int carpim = a * b;     // matematik
        boolean gunesli = true; // mantık
        System.out.println("Toplam: " + toplam);
        System.out.println("Çarpım: " + carpim);
        if (gunesli) {          // karar
            System.out.println("Dışarı çık");
        }
    }
}

Program çalıştırıldığında şu çıktıyı üretir:

Toplam: 10
Çarpım: 21
Dışarı çık

Program satır satır şöyle çalışır:

• public class Hesaplama satırı programın sınıfını tanımlar. Java'da her kod bir sınıfın içinde yazılır ve dosyanın adı sınıfın adıyla aynı olmalıdır: Hesaplama.java.
• main metodu programın giriş noktasıdır. Java sanal makinesi programı başlatınca ilk bu metodu çağırır.
• int a = 7, b = 3; satırı iki tam sayı değişkeni tanımlar ve onlara ilk değerlerini verir. Bunlar hesaplamanın girdileridir.
• toplam ve carpim satırları matematik yapı taşını kullanır. Sağ taraftaki ifade hesaplanır, sonuç soldaki değişkene yazılır.
• boolean gunesli = true; satırı mantık yapı taşının verisini hazırlar. boolean tipindeki bir değişken yalnız iki değerden birini alabilir: true ya da false.
• İki println satırı sonuçları yazdırır. "Toplam: " + toplam ifadesinde + işareti sayıyı metne ekler; buna dizgi birleştirme denir.
• if (gunesli) satırı kararı verir. Koşul true olduğu için süslü parantezlerin içindeki blok çalışır ve “Dışarı çık” yazılır. Koşul false olsaydı blok atlanır, programın çıktısı yalnız iki satır olurdu.

1.2.1.5Kod izleme: Hesaplama programı

Bir programın ne yaptığını anlamanın en güvenilir yolu onu elle izlemektir. Kod izleme, programı satır satır yürütür gibi okuyup her adımda değişkenlerin değerini ve ekrana yazılanları kaydetmektir. Tablo 1.2.1 Hesaplama programının izlemesidir. Satır numaraları kodun ilk satırından sayılır: 1. satır sınıf başlığı, 3. satır int a = 7, b = 3; satırıdır.

İzlemede iki ayrıntı dikkat çeker. Birincisi, bir değişken değer aldıktan sonra yeni bir atama gelmedikçe o değeri korur; tabloda a ve b baştan sona değişmez. İkincisi, 9. satırda ekrana bir şey yazılmaz. Bu satırda yalnız koşul değerlendirilir ve hangi yolun izleneceği belirlenir. Kararın sonucu bir sonraki satırda görünür. Program böylece hesaplamanın üç aşamasını sırayla gösterir: veri alındı, işlendi, sonuç üretildi.

1.2.2Bilgisayar bilimi

“Bilgisayar bilimi” adı yanıltıcı olabilir. Ad, alanın bilgisayar denen makineyle ilgili olduğunu düşündürür. Oysa alanın asıl konusu makine değil, makinenin çözdüğü problemler ve bu problemleri çözme yollarıdır.

1.2.2.1Teknolojiden fazlası

Bilgisayar bilimi yalnız bilgisayarlarla ilgili teknik bilgiden oluşmaz; aynı zamanda problem çözme becerileriyle ilgili bir disiplindir. Teknoloji bu disiplinde bir araçtır. Temel amaç sorunları çözmek ve bilgiyi daha iyi anlamaktır. Sık anılan bir benzetme bunu açıkça anlatır: astronomi teleskoplarla ne kadar ilgiliyse, bilgisayar bilimi de bilgisayarlarla o kadar ilgilidir. Teleskop gökyüzünü incelemenin aracıdır; bilgisayar da problem çözmenin.

Bu bakışın pratik bir sonucu vardır. Bir programlama dilinin ya da bir geliştirme ortamının ayrıntıları birkaç yılda değişir. Bir problemi parçalara ayırma, doğru veri yapısını seçme ve çözümün doğruluğunu sınama becerisi ise değişmez. Bu derste Java öğrenilir, ama Java'nın arkasındaki düşünme biçimi başka dillere de taşınır.

1.2.2.2Üç dayanak: mantık, problem çözme, yaratıcılık

Bilgisayar bilimi üç beceriye dayanır:

• Mantık: Verileri değerlendirip doğru sonuçlar çıkarma yeteneğidir. Program yazma sürecinin temelini oluşturur. Bir if deyiminin koşulu, bir döngünün ne zaman duracağı, iki koşulun && ile mi || ile mi bağlanacağı hep mantık sorularıdır.
• Problem çözme: Karmaşık problemleri tanımlama ve çözme becerisidir. Her problem, mantıklı bir adım sırasıyla çözülür. Bu adım sırasını bulmak programlamanın en zor ve en öğretici kısmıdır.
• Yaratıcılık: Yeni ve yenilikçi çözümlerin doğmasını sağlar. Aynı problemin birçok farklı çözümü olabilir. İki sayının EBOB'u bütün sayıları tek tek deneyerek de, Öklid algoritmasıyla da bulunur; ikisi aynı sonucu verir, ama büyük sayılarda biri diğerinden çok daha hızlıdır.

Bu üç beceri ayrı ayrı öğretilmez; programlama yaptıkça birlikte gelişir. Bir programdaki hata ayıklanırken mantık, programın parçaları tasarlanırken problem çözme, takılınan bir noktada başka bir yol aranırken yaratıcılık kullanılır.

1.2.2.3Teknoloji ve sosyal sorumluluk

Bilgisayar bilimi, teknolojinin insanlara nasıl yardımcı olabileceğini ve toplumsal sorunların çözümüne nasıl katkı sağlayabileceğini düşünmeye yöneltir. Dünyayı daha iyi anlamaya ve geliştirmeye yardımcı olur. Teknolojiyi insanlığın hizmetine sunma sorumluluğunu da vurgular. Bu yüzden alan, yalnız teknolojiyle ilgilenenler için değil, problem çözme ve düşünme becerilerini geliştirmek isteyen herkes için ilginçtir.

Uygulama alanları çok geniştir: tıp, ekonomi, astronomi, biyoloji, enerji, ulaşım ve afet yönetimi bunlardan yalnız birkaçıdır. Bir deprem sonrasında hasar tespiti, uydu görüntülerini işleyen programlarla hızlanır. Bir elektrik şebekesinde yük dengelemesi, tüketimi öngören modellerle yapılır.

Bu genişliğin bir bedeli de vardır: yazılan programlar gerçek insanları etkiler. Bir hastane yazılımındaki hata yanlış ilaç dozuna, kişisel verilerin korunmaması da ciddi mağduriyetlere yol açabilir. Programcının sorumluluğu, kodun derlenmesiyle bitmez; kodun doğru çalıştığından ve kullanıcılarına zarar vermediğinden emin olmayı da kapsar.

1.2.2.4Bilgisayar biliminin konuları

Bilgisayar bilimi gerçekliği anlamayı, modellemeyi ve analiz etmeyi amaçlar. Problemleri çözmek için algoritmalar ve kod kullanılır. Alanın içinde üç geniş başlık öne çıkar:

• Soyutlama (abstraction): Karmaşık bir sistemin gereksiz ayrıntılarını gizleyip özünü bırakmak. Metro haritası iyi bir örnektir. Harita sokakları, binaları ve gerçek uzaklıkları göstermez; yalnız durakları ve hatları gösterir. Yolcunun bilmesi gereken de budur: hangi duraktan binileceği, nerede aktarma yapılacağı.
• Problem çözme: Problemi parçalara ayırmak, her parçayı adım adım çözmek ve çözümleri birleştirmek.
• Sanat ve tasarım: Bilgisayar bilimi mantık ve analitik düşünceyle sınırlı değildir. Dijital medya, elektronik müzik, oyunlar ve animasyon da bu alanın ürünleridir.

Soyutlama ile problem çözme, hesaplamalı düşünmenin de iki ayağıdır. Örüntü tanıma ve algoritma tasarımı bu ikisini tamamlar ve dört beceri birlikte bir çalışma yöntemi oluşturur.

1.2.3Hesaplamalı düşünme

Bir program yazmanın en zor kısmı çoğu zaman Java'nın kurallarını hatırlamak değildir. Asıl zorluk, kodun ilk satırı yazılmadan önce gelir. Problem ne istiyor ve hangi parçalardan oluşuyor? Hangi bilgi gerekli, hangisi gereksiz? Parçalar hangi sırayla çözülecek? Bu sorulara düzenli biçimde yanıt arama alışkanlığına hesaplamalı düşünme denir.

1.2.3.1Tanım

Terim 2006'da Jeannette Wing'in kısa bir makalesiyle yaygınlaştı. Wing, bu düşünme biçiminin yalnız bilgisayar bilimcilerine değil herkese gerekli olduğunu savundu ve onu okuma, yazma ve aritmetik gibi temel bir beceri saydı. Dört becerili ayrım, bu fikri öğretmek için okullarda ve üniversitelerde yaygın olarak kullanılan bir çerçevedir.

Hesaplamalı düşünme “bilgisayar gibi düşünmek” demek değildir. Bilgisayar düşünmez; yalnız talimatları yürütür. Hesaplamalı düşünme, insanın bir problemi bilgisayara anlatılabilir hâle getirme becerisidir. Aynı beceri bilgisayar olmadan da işe yarar. Bir yemek tarifi yazmak, bir devreyi sınamak için ölçüm sırası belirlemek ya da bir sınava çalışma planı yapmak da aynı dört adımla düzenlenebilir.

Dört beceriyi tek bir problem üzerinde görmek, onları ayrı ayrı tanımlamaktan daha öğreticidir. Bu kesim boyunca örnek problem şudur: bir sınıftaki öğrencilerin not ortalamasını bulmak.

1.2.3.2Ayrıştırma

“Not ortalamasını bul” isteği tek bir adım gibi görünür, ama bilgisayar için dört ayrı işten oluşur:

1. Notları oku.
2. Notları topla.
3. Toplamı not sayısına böl.
4. Sonucu yaz.

Her alt problem tek başına kolaydır. Okuma için bir giriş komutu, toplama için bir döngü, bölme için tek bir işlem, yazma için println yeterlidir. Ayrıştırmanın gücü buradan gelir: zor bir problem, kolay problemlerin birleşimine dönüşür.

Ayrıştırma bir kez yapılıp bırakılmaz. Bir alt problem hâlâ büyükse o da bölünür. “Notları oku” adımı, notların klavyeden mi, bir dosyadan mı, bir veri tabanından mı geleceğine göre yeniden parçalanabilir. Java'da her alt problem çoğu zaman ayrı bir metoda karşılık gelir. Büyük programlar da böyle kurulur: sınıflar ve metotlar, ayrıştırmanın koddaki izleridir.

Ayrıştırmanın elektronikteki karşılığı blok diyagramdır. Bir ses yükselteci tasarlanırken önce ön yükselteç, ton denetimi ve güç katı gibi bloklar ayrılır; her blok ayrı tasarlanıp sınanır, sonra birleştirilir. Bir programdaki metotlar da aynı mantıkla ayrı ayrı yazılıp denenebilir.

1.2.3.3Örüntü tanıma

Not ortalaması örneğinde örüntü açıktır. Birinci notu okuyup toplama eklemek ile ikinci notu okuyup toplama eklemek aynı iştir; yalnız not değişir. Otuz öğrencilik bir sınıf için bu adımı otuz kez ayrı ayrı yazmak gerekmez. Tekrar eden adım bir kez yazılır ve bir döngüye konur. Örüntü tanıma, programlamada çoğu zaman “burada bir döngü var” fikrine götürür.

Örüntü yalnız tek problemin içinde aranmaz; problemler arasında da aranır. Not ortalaması ile bir sensörün bir günlük sıcaklık ortalaması aynı problemdir: bir sayı listesinin toplamını alıp eleman sayısına bölmek. Biri için yazılan çözüm, küçük bir değişiklikle öbürüne de uyar. Babil yöntemi ve Öklid algoritmasında da tekrar eden bir adım vardır: biri tahmini iyileştirir, öbürü kalanı hesaplar. Her ikisi de bu adımı belirli bir koşul sağlanana kadar yineler.

Örüntü tanıma tecrübeyle güçlenir. Çok sayıda problem çözmüş bir programcı, yeni bir problemde “bu, en büyüğü bulma problemi” ya da “bu, iki listeyi birleştirme problemi” diyebilir. Problemi tanınan bir kalıba indirgemek, çözümü sıfırdan bulmaktan çok daha hızlıdır.

1.2.3.4Soyutlama

Bir öğrenciyle ilgili çok sayıda bilgi vardır: adı, numarası, doğum tarihi, memleketi, devamsızlığı, notları. Ortalama hesabı için bunların çoğu gereksizdir. Öğrencinin adı ya da numarası ortalamayı etkilemez. Gerekli olan yalnız iki bilgidir: notlar ve not sayısı. Soyutlama yapıldıktan sonra problem “otuz öğrencinin ortalaması” olmaktan çıkar, “bir sayı listesinin ortalaması” olur. Bu daha genel bir problemdir ve çözümü başka yerlerde de kullanılabilir.

Metro haritası örneği aynı fikri gösterir: harita gerçek şehrin küçültülmüş bir fotoğrafı değildir; yolcuya gereken bilgi dışındaki her şey atılmıştır. İyi bir soyutlama, atılan ayrıntının gerçekten gereksiz olduğundan emin olmayı gerektirir. Notların ağırlıkları farklıysa, örneğin vize %40 ve final %60 ise, “yalnız notlar yeterli” soyutlaması yanlış olur; ağırlıklar da modele girmelidir.

Soyutlama nesne yönelimli programlamanın da temelidir. Java'da bir Ogrenci sınıfı tasarlanırken gerçek bir öğrencinin bütün özellikleri değil, programın ihtiyaç duyduğu özellikler sınıfa alan olarak konur. Bir kayıt sisteminde ad ve numara gerekir, bir not sisteminde notlar gerekir. Aynı gerçek varlık, farklı programlarda farklı biçimde soyutlanır.

1.2.3.5Algoritma tasarımı

Önceki üç beceri problemi hazırlar; algoritma tasarımı çözümü yazar. Not ortalaması için algoritma, sunumdaki sözde kod biçimiyle şöyledir:

set toplam to 0
for each not in notlar do
    set toplam to toplam + not
set ort to toplam / n
print ort

Bu adımlar ayrıştırmanın dört alt problemini, örüntü tanımanın bulduğu döngüyü ve soyutlamanın bıraktığı iki bilgiyi (notlar ve n) bir araya getirir. Her adım açıktır: ne yapılacağı konusunda yoruma yer yoktur. Adım sayısı sonludur: döngü listedeki her not için bir kez çalışır ve liste bitince durur.

Algoritma yazılırken bazı ayrıntılar da kararlaştırılır. Toplam neden 0'dan başlar? Çünkü hiç not eklenmemişken toplam sıfırdır ve her not bu değere eklenir. Liste boşsa ne olur? n = 0 olur ve bölme tanımsız kalır. İyi tasarlanmış bir algoritma bu durumu da düşünür; örneğin “liste boşsa ‘not yok’ yaz” diye bir adım ekler.

1.2.3.6Dört beceri bir arada: not ortalaması

Tablo 1.2.2 dört becerinin örnek problemde neye karşılık geldiğini özetler.

Algoritma hazır olunca Java'ya çevirmek kolaydır. Aşağıdaki program, notları bir dizide tutar ve ortalamayı hesaplar. Notlar sunumun örnek problemlerindeki 40, 75 ve 90'dır.

public class Ortalama {
    public static void main(String[] args) {
        int[] notlar = {40, 75, 90};   // girdi: yalnız notlar
        int toplam = 0;
        for (int not : notlar) {        // her not için aynı adım
            toplam = toplam + not;
        }
        double ort = (double) toplam / notlar.length;
        System.out.println("Ortalama: " + ort);
    }
}

Program “Ortalama: 68.33333333333333” yazar. Kodun her parçası bir beceriye karşılık gelir. notlar dizisi soyutlamanın sonucudur: öğrenciler değil, yalnız notlar tutulur. for döngüsü örüntü tanımanın bulduğu tekrar eden adımdır. Toplama ve bölme satırları ayrıştırmanın alt problemleridir. Bütün kod da algoritmanın Java'daki karşılığıdır.

Bölme satırındaki (double) dönüşümü önemlidir. toplam ve notlar.length ikisi de int tipindedir. Java iki int değeri bölerken sonucu da int verir ve kesirli kısmı atar: 205 / 3 = 68. (double) toplam yazılınca bölünen ondalıklı sayıya çevrilir ve gerçek bölme yapılır. Bu ayrıntı soyutlamanın gözden kaçırabileceği türden bir şeydir: algoritma kâğıt üzerinde doğrudur, ama Java'nın sayı tipleri hesaba katılmazsa program yanlış sonuç verir.

1.2.4Bilgisayarın tarihi

Bugünkü bilgisayar tek bir buluşun değil, birkaç yüzyıl süren bir gelişmenin ürünüdür. Bu gelişme iki fikrin etrafında döner. Birincisi hesabı makineye yaptırmaktır: dişli çarklardan vakum tüplerine, oradan transistörlere uzanan çizgi bu fikrin ürünüdür. İkincisi makinenin ne yapacağını değiştirebilmektir: sabit programlı makinelerden depolanan programlı makinelere geçiş bu fikrin ürünüdür. Tarihin ayrıntıları bu iki çizgiye yerleştirilince akılda daha kolay kalır.

1.2.4.1Bilgisayar nedir?

Günümüz bilgisayarları elektronik devrelerle çalışır ve sayıları dijital olarak temsil eder. Dört ana bileşenden oluşurlar:

• İşlemci (CPU, central processing unit, merkezî işlem birimi): Talimatları yürütür, hesapları yapar.
• Bellek (RAM, random access memory, rastgele erişimli bellek): Çalışan programı ve verisini tutar. Elektrik kesilince içeriği silinir.
• Depolama: Disk ve SSD gibi birimler veriyi kalıcı olarak saklar. Bilgisayar kapansa da veri kaybolmaz.
• Giriş/çıkış birimleri: Klavye, fare, ekran, yazıcı ve ağ bağlantısı bilgisayarın dış dünyayla iletişimini sağlar.

Bir Java programı çalışırken bu bileşenlerin hepsi devrededir. .java ve .class dosyaları diskte durur. Program başlatılınca belleğe yüklenir. İşlemci talimatları birer birer yürütür. println ise sonucu ekrana, yani bir çıkış birimine gönderir. Bellek ile depolama arasındaki fark programcı için de önemlidir: bir değişkende tutulan değer program bitince kaybolur, kalıcı olması gereken veri bir dosyaya yazılmalıdır.

1.2.4.2Elektronik ve dijital

Bugünkü bilgisayarı tanımlayan iki sıfat vardır: elektronik ve dijital. İkisi farklı şeyler anlatır.

• Elektronik: Bilgisayar verileri elektrik akımıyla işler. Mekanik dişliler yerine transistörler anahtarlama yapar. Anahtarlamada hareketli parça olmadığı için işlemler çok hızlıdır.
• Dijital (sayısal): Veriler 0 ve 1 ile temsil edilir. Her 0 ya da 1 bir bittir; 8 bit bir bayt eder. Bir bayt 2⁸ = 256 farklı değer alabilir.

Dijital temsilin neden tercih edildiği Şekil 1.2.4'te görülür. Analog bir sinyalde her gerilim değeri farklı bir bilgi taşır. Bu yüzden sinyale karışan küçük bir gürültü bilgiyi değiştirir. Dijital sinyalde ise yalnız iki düzey vardır. 5 V'luk bir sistemde 3,9 V da 4,8 V da “1” sayılır. Gürültü sinyali biraz oynatsa da hangi düzeyde olduğu kolayca ayırt edilir. Dijital sistemlerin güvenilirliği buradan gelir. Elektronik dersinden tanıdık olan lojik kapılar, bu iki düzeyli sinyallerle çalışan devrelerdir.

1.2.4.3Sabit programlı bilgisayar

Sabit programlı makinelerin kökleri çok eskilere dayanır:

• Abaküs ve Antikythera Mekanizması (MÖ 2. yüzyıl). Antikythera Mekanizması, gök cisimlerinin konumlarını dişli çarklarla hesaplayan antik bir Yunan aletidir.
• Pascaline (Blaise Pascal, 1642) ve Leibniz'in basamaklı hesap makinesi (1673).
• Babbage'ın Fark Makinesi (1822) ve Hollerith'in elektrikli çizelgeleme makinesi (1890). Hollerith'in makinesi ABD nüfus sayımının sonuçlarını delikli kartlardan saymak için yapıldı.
• Atanasoff–Berry Bilgisayarı (ABC) ve Turing Bombası. Bomba, İkinci Dünya Savaşı'nda Alman Enigma şifresini çözmek için kuruldu.

Şekil 1.2.5'teki Pascaline sabit programlı makinenin tipik bir örneğidir. Çarkları toplama yapacak biçimde dizilmiştir; başka bir hesap, örneğin karekök, bu makineye yaptırılamaz. Bugün de sabit programlı cihazlar vardır: basit bir cep hesap makinesi ya da bir çamaşır makinesinin eski tip mekanik programlayıcısı aynı mantıkla çalışır. Sabit programlı makineler bilgisayar biliminin temellerini attı, teknolojik gelişmelere ilham verdi ve modern bilgisayarların öncüsü oldu.

1.2.4.4Babbage ve Analitik Makine

Charles Babbage (1791–1871) İngiliz bir matematikçi ve mucitti. Fark Makinesi, çok terimli ifadelerin değer tablolarını hesaplamak için tasarlanmış sabit programlı bir makineydi. Babbage daha sonra çok daha iddialı bir tasarıma yöneldi. 1837'de Analitik Makine'yi (Analytical Engine) tasarladı. Bu, ilk genel amaçlı ve programlanabilir bilgisayar tasarımıdır.

Analitik Makine matematiksel hesaplama yapabilir ve sonuçları saklayabilirdi. Asıl yeniliği, farklı hesaplamalar için programlanabilmesiydi. Bugünkü bilgisayarın parçaları bu tasarımda vardı:

• store (depo): sayıları tutan bellek;
• mill (değirmen): işlemleri yapan, bugünkü işlemcinin karşılığı olan birim;
• delikli kartlarla giriş ve yazıcıyla çıkış.

Delikli kart fikri, dokuma tezgâhından alındı. Joseph Marie Jacquard 1804'te desenleri delikli kartlarla belirlenen bir dokuma tezgâhı geliştirmişti. Kart değiştirilince desen değişiyordu. Babbage aynı fikri hesaba uyguladı: kart değiştirilince hesap değişecekti. Makinenin ne yapacağını değiştirmek için makineyi değil, kartları değiştirmek yetiyordu.

Makine Babbage'ın yaşamında tamamlanamadı. Dönemin metal işleme olanakları binlerce hassas parçayı üretmeye yetmiyordu, para da bulunamadı. Bugün yalnız Şekil 1.2.6'daki gibi deneme modelleri vardır. Yine de Analitik Makine modern bilgisayarların öncüsü kabul edilir; çünkü genel amaçlı bir makinenin hangi parçalardan oluşması gerektiğini ilk kez açıkça tanımladı.

1.2.4.5Ada Lovelace ve ilk program

Ada Lovelace (1815–1852) İngiliz bir matematikçi ve yazardı. 1843'te İtalyan mühendis Luigi Menabrea'nın Analitik Makine üzerine yazdığı Fransızca bir makaleyi İngilizceye çevirdi ve çeviriye kendi notlarını ekledi. Notlar makalenin kendisinden uzundu.

Notların en ünlüsü “Not G”dir. Lovelace bu notta makinenin Bernoulli sayılarını hesaplaması için adım adım bir yöntem verdi. Yöntem, hangi değerin hangi bellek hücresine yazılacağını ve hangi işlemin hangi sırayla yapılacağını gösteren bir tablodur. Bu tablo ilk bilgisayar programı kabul edilir ve Lovelace bilgisayar tarihinin ilk programcısı sayılır. Lovelace matematiksel düşünceyi programlamayla bilimsel bir yaklaşımla birleştirdi.

Lovelace'ın öngörüsü programdan da ileri gider. Makinenin yalnız sayılarla değil, sembollerle de çalışabileceğini ilk fark edenlerdendir. Ona göre müzik notaları da sembollerle temsil edilirse makine müzik besteleyebilirdi. Bugünkü bilgisayarların metin, ses ve görüntü işlemesi bu fikrin gerçekleşmesidir. Lovelace'ın mirası bir programlama diline de adını verdi: 1980'de tanıtılan Ada dili onun adını taşır.

Bu öykünün bir dersi vardır: Lovelace'ın programı, makine henüz yokken yazıldı. Algoritma bir makineye bağlı değildir; kâğıt üzerinde tasarlanabilir ve elle izlenebilir. Bu not boyunca yapılan kod izlemeleri de aynı fikre dayanır.

1.2.4.6Zaman çizelgesi ve depolanan program

Babbage ile ilk elektronik bilgisayarlar arasında yaklaşık bir yüzyıl vardır. Şekil 1.2.7 bu dönemin önemli tarihlerini bir arada gösterir.

Çizelge üç döneme ayrılır:

• Mekanik dönem: Dişliler ve kartlar. Pascaline, Fark Makinesi ve Analitik Makine bu döneme aittir.
• Kuramsal temel: Alan Turing 1936'da “hesaplanabilir” kavramının ne demek olduğunu kesin olarak tanımladı ve evrensel makine fikrini ortaya koydu. Bu çalışma hiçbir makine yapmadı; bir makinenin neyi yapıp neyi yapamayacağını belirledi.
• Elektronik dönem: Vakum tüplü ABC, Colossus ve ENIAC; ardından depolanan programlı EDVAC.

Elektronik dönemin en önemli adımı depolanan program fikridir.

Fikrin 1945'teki önemi şuradadır: program ve veri aynı bellekte durduğu için program da bir veridir. Bir program, başka bir programı girdi olarak okuyabilir, değiştirebilir ya da üretebilir. Derleyiciler tam olarak bunu yapar: javac, girdi olarak bir Java kaynak dosyasını okur ve çıktı olarak başka bir program üretir. Java sanal makinesi de .class dosyasındaki programı veri gibi okuyup çalıştırır.

Bugün kullanılan dizüstü bilgisayarlar, telefonlar ve sunucular temelde bu mimariyle çalışır. İşlemci bir döngü içinde sıradaki komutu bellekten getirir, çözer ve yürütür; sonra bir sonraki komuta geçer. Bir koşullu atlama komutu bu sırayı değiştirebilir. Java'daki if ve while deyimleri, derlendikten sonra sonunda bu tür atlama komutlarına dönüşür.

1.2.4.7İlk elektronik bilgisayarlar: ABC ve Colossus

Atanasoff–Berry Bilgisayarı (ABC), John Atanasoff ve Clifford Berry'nin 1937–1942 yılları arasında Iowa State Üniversitesi'nde geliştirdiği makinedir. İlk elektronik dijital bilgisayar kabul edilir. ABC'nin özellikleri şunlardır:

• Mantık devrelerini vakum tüpleriyle kurdu.
• Sayıları ikili (0/1) sistemde işledi.
• Belleği, dönen tamburlar üzerindeki kondansatörlerden oluşuyordu. Bir kondansatörün yüklü ya da boş olması bir biti temsil ediyordu.
• Programlanamazdı. Yalnız doğrusal denklem sistemlerini çözüyordu; yani sabit programlı bir makineydi.

Colossus Mark 1, Tommy Flowers ve ekibinin 1944'te İngiltere'deki Bletchley Park'ta kurduğu makinedir. İlk programlanabilir elektronik dijital bilgisayar kabul edilir; anahtar ve fişlerle programlanıyordu. İkinci Dünya Savaşı'nda düşmanın şifreli mesajlarını çözmek için kullanıldı. Yaklaşık 1600 vakum tüpü içeriyordu ve mekanik cihazlardan çok daha hızlı ve esnekti. Colossus, bilgisayar teknolojisinin ilerlemesine büyük katkı sağladı; ancak savaştan sonra uzun yıllar gizli tutulduğu için etkisi geç anlaşıldı.

İki makine arasındaki fark, tarihin ana çizgisini özetler. ABC elektronik ve ikiliydi, ama tek bir işe bağlıydı. Colossus programlanabiliyordu, ama programı değiştirmek anahtarları ve fişleri elle değiştirmek demekti. Programın bellekte durması için birkaç yıl daha beklemek gerekti.

1.2.4.8Vakum tüpü ve transistör

İlk elektronik bilgisayarların ortak parçası vakum tüpüdür. Vakum tüpü, havası boşaltılmış bir cam tüptür. İçinde üç ana eleman bulunur:

• Katot: Isıtılınca elektron yayar.
• Anot (plaka): Katodun yaydığı elektronları toplar.
• Izgara: Katot ile anot arasında durur. Izgaraya uygulanan küçük bir gerilim, elektron akışını açar ya da keser.

Izgara gerilimiyle akımın açılıp kapanabilmesi, tüpü bir elektronik anahtar yapar: akım geçiyorsa 1, geçmiyorsa 0. Bu anahtarlama hareketli parça içermediği için mekanik rölelerden binlerce kat hızlıdır. Bir röle milisaniyeler içinde açılıp kapanırken bir tüp mikrosaniyeler düzeyinde anahtarlama yapar.

Vakum tüpünün sakıncaları da büyüktü. Tüpler çok ısınır, çok enerji harcar ve sık arızalanır. Binlerce tüplü bir makinede her gün birkaç tüpün yanması olağandı. Çözüm 1947'de icat edilen transistör oldu. Transistör aynı anahtarlama işini çok daha küçük, serin ve güvenilir biçimde yapar. Elektronik derslerinde incelenen MOSFET'ler de bu işi görür. Bugünkü işlemcilerde milyarlarca transistör vardır.

1.2.4.9ENIAC ve EDVAC

ENIAC (1946), John Mauchly ve J. Presper Eckert'in Pennsylvania Üniversitesi'nde (ABD) kurduğu makinedir. Genel amaçlı ilk büyük ölçekli elektronik bilgisayar kabul edilir. Mekanik parçalar yerine yaklaşık 17 500 vakum tüpü kullanıyordu; bu yüzden önceki makinelerden çok daha hızlı ve güvenilirdi. Saniyede yaklaşık 5000 toplama yapabiliyordu. Topçu atış tabloları gibi büyük hesaplar için kullanıldı.

ENIAC'ın iki zayıf yanı vardı. Sayıları onlu sistemde tutuyordu; bu, devreleri karmaşıklaştırıyordu. Daha önemlisi, programı değiştirmek için kablolar elle yeniden takılıyordu. Yeni bir problem için makineyi hazırlamak günler sürebilirdi.

EDVAC (1949–1951) bu iki sorunu çözdü. Tasarımı, John von Neumann'ın 1945'te yazdığı bir raporda tanımlandı; makine 1951'de tam olarak çalıştı. EDVAC'ın yenilikleri şunlardır:

• ENIAC'tan farklı olarak ikili sayı sistemini kullandı.
• Programı ve veriyi aynı bellekte sakladı. Bu, depolanan program fikrinin uygulamasıdır.
• Komutlar sırayla çalışıyordu; koşula bağlı atlama yapılabiliyordu.

Bu tasarım, bugünkü bilgisayarların temeli olan von Neumann mimarisidir. ENIAC ile EDVAC'ı ayıran şey hız değil, programın nerede durduğudur. ENIAC'ta program kablolarda, EDVAC'ta bellekteydi.

1.2.4.10Genel amaçlı bilgisayar

Genel amaçlı bilgisayar iş, eğitim ve eğlence gibi birçok alanda kullanılır. Program değiştirilerek farklı görevlere uyarlanır: aynı dizüstü bilgisayar bir dakika önce müzik çalar, bir dakika sonra Java derler. Sabit programlı makineyle farkı budur. Genel amaçlı bilgisayarlar iş süreçlerini otomatikleştirir, bilimsel hesaplamaları hızlandırır ve iletişimi kolaylaştırır.

1.2.4.11İlk programlar ve Fortran

İlk programlar çoğunlukla matematiksel hesaplamalar içindi. Kullanımlar bilimsel ve askerî uygulamalara odaklanıyordu: atış tabloları, nükleer fizik hesapları, hava durumu tahmini. Programlar ve veriler delikli kartlarla girilirdi. Bir kartın her sütunundaki delik düzeni bir karakteri kodlardı.

Şekil 1.2.9'daki gibi bir kart 80 karakter tutardı. Yüz satırlık bir program yüz kartlık bir desteydi. Deste düşüp kartlar karışırsa program bozulurdu. Bugün bazı kod düzenleyicilerinde görülen 80 karakterlik satır sınırı bu dönemden kalmadır.

İlk programlar makine diliyle ya da makine diline çok yakın biçimde yazılıyordu. Her işlemcinin komutları farklı olduğu için bir makinede yazılan program başka bir makinede çalışmazdı. İlk yaygın yüksek seviyeli programlama dili olan Fortran (Formula Translation) bu sorunu hafifletti. Fortran, John Backus önderliğinde IBM'de geliştirildi ve 1957'de kullanıma sunuldu. Bilimsel hesaplamalarda yaygın olarak kullanıldı ve bugün de bu alanda kullanılır.

Yüksek seviyeli dil, programcının K = I + J gibi matematiğe yakın ifadeler yazmasını sağlar. Bir derleyici bu ifadeyi makine komutlarına çevirir. Programcı artık bellek adresleriyle değil, değişken adlarıyla düşünür. Java da (1995) yüksek seviyeli bir dildir; int toplam = a + b; satırı bu geleneğin devamıdır.

1.2.5Turing makineleri

“Hesaplama” sözcüğü günlük dilde bulanık bir anlam taşır. Bir problem için “bilgisayarla çözülebilir” demek ne anlama gelir? Hangi bilgisayarla, ne kadar bellekle, hangi dille? Alan Turing 1936'da bu soruyu bütün makinelerden bağımsız olarak yanıtlamak için son derece basit bir soyut makine tanımladı. Bu makine gerçek bir bilgisayar gibi hızlı ya da kullanışlı değildir. Değeri, hesaplamanın ne olduğunu kesin olarak tanımlamasından gelir.

1.2.5.1Evrensel Turing makinesi

Alan Turing'in 1936'da tanımladığı bu model, soyut ve genel amaçlı bir bilgisayar modelidir ve bilgisayar biliminin en temel modellerinden biridir. Evrensel makine, kendisine verilen her Turing makinesinin yaptığını yapabilir. Bu yüzden hesaplanabilir her problemi çözebilir.

Evrensel makine fikri, depolanan program fikrinin kuramsal karşılığıdır. Şekil 1.2.10'da taklit edilecek makinenin tanımı, bant üzerindeki öteki veriler gibi okunur. Bugünkü bilgisayarlar da aynı biçimde çalışır: tek bir donanım, bellekteki programa göre metin düzenleyici, oyun ya da derleyici olur. Modern bilgisayarların evrensel olarak programlanabilmesinin kuramsal temeli budur. Depolanan programlı bilgisayar ve evrensel Turing makinesi, bilgisayar teknolojisinin iki önemli dönüm noktasıdır: biri makinenin nasıl yapılacağını, öbürü ne yapabileceğini belirledi.

1.2.5.2Turing makinesinin parçaları

Kural biçimi şöyledir:

(durum, okunan) → (yazılacak, yön, yeni durum)

Örneğin (q0, 0) → (1, sağ, q0) kuralının anlamı şudur: makine q0 durumundayken başlığın altında 0 varsa o hücreye 1 yazılır, başlık bir sağa gider ve makine q0 durumunda kalır. Şekil 1.2.11'deki anlık görüntüde bu kural uygulanırsa 1 numaralı hücre 1 olur ve başlık 2 numaralı hücreye geçer.

Makinenin her adımı bu kadar basittir: bir sembol oku, bir sembol yaz, bir hücre git, durumu değiştir. Toplama, çarpma, karşılaştırma gibi bütün işlemler bu basit adımların uzun dizilerinden kurulur. Bant sonsuz olduğu için bellek sınırı yoktur. Gerçek bilgisayarlardan farkı da budur: gerçek bir bilgisayarın belleği sonludur.

Turing makinesinin bileşenleri bir Java programının bileşenlerine benzetilebilir. Bant, verinin tutulduğu bellektir; başlık, o an üzerinde çalışılan değişkeni gösterir; kural tablosu programdır; durum da programın o an hangi satırda olduğudur. Benzetme kusursuz değildir, ama bir Turing makinesinin de bir program yürüttüğünü görmeye yardım eder.

1.2.5.3Örnek: bitleri ters çeviren makine

En basit Turing makinelerinden biri, banttaki her 0'ı 1, her 1'i 0 yapan makinedir. Makinenin yalnız bir çalışma durumu (q0) ve üç kuralı vardır. Kurallar Tablo 1.2.5'te verilmiştir.

Kurallara göre 0 okunursa 1, 1 okunursa 0 yazılır ve her iki durumda başlık bir sağa gider. Boş hücreye gelince makine durur. Bantta 0110 yazılıyken makineyi çalıştıralım. Başlangıçta durum q0'dır ve başlık 0 numaralı hücrededir. Tablo 1.2.6 her adımı gösterir.

Makine dört yazma adımı ve bir durma adımı, toplam beş adım çalışır. Bantta 1001 kalır. Adım sayısı girdinin uzunluğuna bağlıdır: n bitlik bir girdi için makine n yazma ve bir durma adımı, yani n + 1 adım çalışır.

Bu küçük kural tablosu makinenin programıdır. Evrensel makine böyle bir tabloyu bantta okuyup çalıştırabilir. Aynı fikir Java'da bir döngüyle de yazılabilir: bir dizinin her öğesi için öğe 0 ise 1, 1 ise 0 yap ve bir sonraki öğeye geç. Turing makinesindeki “sağa git” adımı, döngüdeki indis artırımına karşılık gelir; boş hücrede durmak da dizinin sonuna gelince döngüden çıkmaya karşılık gelir.

1.2.5.4Hesaplanabilirlik ve durma problemi

Turing makinesi hesaplamanın ne olduğunu ve sınırlarını kesin olarak tanımlar. Bu tanımın kabul görmesini sağlayan iddia, Church–Turing tezidir.

Teorem kutusunda verilse de Church–Turing tezi kanıtlanmış bir matematik teoremi değildir. “Adım adım bir yöntem” sezgisel bir kavramdır ve kesin bir matematiksel tanımı yoktur. Tez, bu sezgisel kavramın Turing makinesiyle tam olarak yakalandığını ileri sürer. Bugüne kadar önerilen bütün hesaplama modelleri, Turing makinesinden daha güçlü çıkmamıştır; tezin genel kabul görmesinin nedeni budur.

Turing'in 1936 makalesinin asıl şaşırtıcı sonucu, her problemin hesaplanabilir olmadığıdır. Bunun en ünlü örneği durma problemidir (halting problem): verilen bir program, verilen bir girdiyle çalıştırılınca bir gün durur mu, yoksa sonsuza dek mi çalışır? Turing bu soruyu her program için doğru yanıtlayan bir algoritmanın olamayacağını kanıtladı.

Kanıtın fikri, bir karşı örnek kurmaya dayanır ve birkaç cümleyle anlatılabilir. Varsayalım ki durur(p, g) adlı bir metot yazılabilsin. Bu metot, p programı g girdisiyle çalışınca durursa true, durmazsa false döndürsün ve kendisi her zaman dursun. Bu metodu kullanarak yeni bir program, ters(p), yazılır. ters, durur(p, p) sorusunu sorar: yanıt true ise sonsuz bir döngüye girer, false ise hemen durur. Şimdi ters programı kendi kaynak koduyla çalıştırılsın. ters(ters) durursa, durur(ters, ters) true döner ve ters sonsuz döngüye girer; yani durmaz. Durmazsa, durur false döner ve ters hemen durur; yani durur. İki durum da çelişkiye varır. Çelişkinin tek kaynağı, durur metodunun yazılabileceği varsayımıdır; demek ki böyle bir metot yazılamaz.

Bu sonucun pratik bir anlamı vardır. Java derleyicisi bazı açık sonsuz döngüleri fark eder, ama her sonsuz döngüyü bulan bir derleyici yazılamaz. Bir programın her girdide durduğunu otomatik olarak gösteren genel bir araç da yoktur. Sınır, hızdan ya da bellekten gelmez; mantıksal bir sınırdır. Daha hızlı bir bilgisayar bu sınırı aşamaz. Bu sonuçlar 20. yüzyılın en önemli bilimsel sonuçlarından biri kabul edilir.

1.2.5.5Turing-tamlık ve Java

Java, Python ve C gibi diller Turing-tamdır. Bir Turing makinesinin yapabildiği her hesabı yapabilirler. Bunun için bir dilde koşullu dallanma ve sınırsız tekrar (döngü ya da özyineleme) ile istenen kadar veri tutma olanağının bulunması yeterlidir. Diller hız ve kolaylık bakımından birbirinden farklıdır, güç bakımından değil. Java'da yazılabilen her hesap Python'da da yazılabilir; yalnız biri daha kısa, öbürü daha hızlı olabilir.

Bu eşdeğerliğin bir sonucu da dil seçiminin bir “güç” sorunu olmamasıdır. Bir projeye Java'nın seçilmesinin nedenleri tip denetimi, taşınabilirlik ve kütüphanelerin zenginliği gibi mühendislik gerekçeleridir. Durma problemi de Turing-tam bütün diller için geçerlidir: Java'da da her programın durup durmadığına karar veren bir program yazılamaz.

1.2.6Bilgisayarların sınırları

Durma problemi, hesaplamanın mantıksal sınırıdır: hiçbir bilgisayar onu aşamaz. Bunun yanında daha gündelik sınırlar da vardır. Hesaplanabilir bir problem bile, gereken zaman ya da bellek eldekinden fazlaysa pratikte çözülemez. Bu kesim fiziksel kaynakların sınırlarını ve bu sınırların bir Java programında nasıl göründüğünü ele alır.

1.2.6.1Kaynak sınırları

Bilgisayarlar karmaşık hesaplamaları çok hızlı yapar; bu güç teknolojik gelişmelere dayanır. Yine de her kaynak sınırlıdır:

• İşlemci hızı: Hesapların ne kadar hızlı yapılacağını belirler. Bugünkü işlemciler saniyede milyarlarca işlem yapar, ama bu sayı da sonludur. Adım sayısı girdiyle çok hızlı büyüyen bir algoritma, en hızlı işlemcide bile yıllarca sürebilir.
• Bellek: Veri saklama kapasitesidir. Daha fazla bellek daha karmaşık görevler demektir, ama bellek de sınırlıdır. Turing makinesinin bandı sonsuzdur; gerçek bir bilgisayarın belleği değildir.
• Veri işleme kapasitesi: Büyük veri kümelerini işlemek zaman ve kaynak ister. Milyonlarca kaydı okumak bile diskin hızıyla sınırlıdır.
• Enerji: Bilgisayarlar sınırlı bir kaynak olan enerjiyi tüketir. Daha güçlü bilgisayar daha fazla enerji demektir. Büyük veri merkezleri küçük bir kentin tükettiği kadar elektrik harcayabilir.

Programcılar bu sınırları kaynakları etkin kullanarak aşmaya çalışır: aynı işi daha az adımda ve daha az bellekle yapan algoritmalar seçerler. EBOB'u bulmak için bütün sayıları tek tek denemek ile Öklid algoritmasını kullanmak arasındaki fark, bu seçimin iyi bir örneğidir.

1.2.6.2Sınırlar Java'da da görünür

Bilgisayarın belleği sonlu olduğu için her sayı tipi de sonlu sayıda bitle saklanır. Bu sınır bazen beklenmedik sonuçlara yol açar. Aşağıdaki program üç tipik durumu gösterir.

public class Sinirlar {
    public static void main(String[] args) {
        int enBuyuk = Integer.MAX_VALUE;
        System.out.println(enBuyuk);
        System.out.println(enBuyuk + 1);  // taşma
        System.out.println(0.1 + 0.2);    // duyarlık
        System.out.println(5 / 2);        // tamsayı bölmesi
    }
}

Program şu çıktıyı üretir:

2147483647
-2147483648
0.30000000000000004
2

Dört satırı ayrı ayrı açıklamak gerekir.

Birinci ve ikinci satır: taşma. Java'da int tipi 32 bitlik bellek kullanır. Bitlerden biri işaret için ayrıldığı için en büyük değer 2³¹ − 1 = 2 147 483 647'dir; bu değer Integer.MAX_VALUE sabitinde tutulur. Bu sayıya 1 eklenince sonuç 32 bite sığmaz. Java bu durumda hata vermez; sonuç sessizce en küçük değere, −2 147 483 648'e döner. Bu olaya taşma (overflow) denir.

Sararak dönmenin nedeni, negatif sayıların ikiye tümleyen (two's complement) biçiminde saklanmasıdır. 2 147 483 647 ikili tabanda 0111…1 (bir 0 ve otuz bir 1) olarak yazılır. Buna 1 eklenince elde zinciri bütün 1'leri 0 yapar ve en soldaki bit 1 olur: 1000…0. İkiye tümleyende en soldaki bit işaret bitidir; bu bit örüntüsü −2³¹ = −2 147 483 648'i gösterir. Arabaların eski mekanik kilometre sayaçları da benzer davranır: 99 999'dan sonra 00 000'a döner.

Taşma, gerçek programlarda sinsi hatalara yol açar. 100000 * 100000 ifadesinin matematiksel değeri 10¹⁰'dur, ama Java bu çarpımı int olarak yapar ve 1 410 065 408 sonucunu verir. İşlenenlerden biri long yapılırsa (100000L * 100000) sonuç doğru çıkar: 10 000 000 000. long 64 bittir ve en büyük değeri yaklaşık 9,2 · 10¹⁸'dir. Taşmanın sessizce geçmesi istenmiyorsa Math.addExact ve Math.multiplyExact gibi metotlar kullanılır; bu metotlar taşma olduğunda ArithmeticException fırlatır ve “integer overflow” iletisini verir.

Üçüncü satır: duyarlık. double tipi ondalıklı sayıları ikili tabanda yaklaşık 15–16 anlamlı basamak duyarlıkla saklar. 0,1 sayısı ikili tabanda tam yazılamaz; tıpkı 1/3'ün onlu tabanda 0,333… diye sonsuza dek sürmesi gibi, 0,1 de ikili tabanda sonsuz bir kesirdir. Bilgisayar bu kesri bir yerde keser ve en yakın değeri saklar. 0,1 ile 0,2'nin yaklaşık değerleri toplanınca küçük hatalar birikir ve sonuç 0.30000000000000004 çıkar. Bu yüzden 0.1 + 0.2 == 0.3 ifadesi false verir. Ondalıklı sayılar == ile değil, aralarındaki farkın çok küçük olup olmadığına bakılarak karşılaştırılmalıdır: Math.abs(a - b) < 1e-9. Babil yöntemindeki döngü koşulu da bu fikirle yazılmıştır.

Dördüncü satır: tam sayı bölmesi. İki int değerin bölümü yine int'tir; kesirli kısım atılır. 5 / 2 ifadesi 2,5 değil 2 verir. Atma işlemi sıfıra doğru yapılır: -7 / 2 ifadesi −3,5 değil −3 verir. Ondalıklı sonuç için işlenenlerden en az biri double olmalıdır: 5 / 2.0 ya da 5.0 / 2 ifadesi 2.5 verir.

Sıfıra bölme de iki tipte farklı davranır. 5 / 0 tam sayı bölmesidir ve ArithmeticException: / by zero fırlatır. 1.0 / 0 ise hata vermez; sonuç Infinity olur. 0.0 / 0 ifadesinin sonucu da “sayı değil” anlamına gelen NaN'dır.

1.2.6.3Makineler ve teknoloji

Teknoloji insanların yaşamını etkileyen bir güçtür; makineler bu gelişmenin önemli bir parçasıdır. Makineler işleri hızlı ve verimli yapar. Bu güç sanayi devriminden bugüne sürekli arttı. Yine de inşa edilebilecek makinelerin sınırları vardır:

• Fiziksel sınırlar: Boyut, ağırlık ve dayanıklılık fizik yasalarına bağlıdır. Bir transistör birkaç atomdan küçük yapılamaz. Sinyal ışıktan hızlı gidemez; 3 GHz'lik bir işlemcide bir saat çevrimi sırasında ışık yalnız yaklaşık 10 cm yol alır. Yonganın boyutu bu yüzden hızı da sınırlar.
• Enerji sınırları: Makineler enerjiye ihtiyaç duyar ve enerji kaynakları sınırlıdır. Daha güçlü makine daha fazla enerji ve daha fazla soğutma ister. Harcanan elektrik enerjisinin büyük bölümü ısıya dönüşür; bu ısı uzaklaştırılamazsa yonga zarar görür.
• Teknolojik sınırlar: Yeni malzemeler, yeni tasarım fikirleri ve yeni algoritmalar sınırları zorlayabilir. Vakum tüpünden transistöre geçiş böyle bir sınırın aşılmasıydı.

Sınırları anlamak, daha iyi ve verimli makineler tasarlamayı sağlar. Yazılımda bunun karşılığı, problemi daha az kaynakla çözen algoritmalardır. Donanım belirli bir hızın ötesine geçemiyorsa, aynı işi daha az adımda yapan bir algoritma çoğu zaman daha hızlı bir makineden daha büyük kazanç sağlar.

1.2.7Bildirimsel ve buyurusal bilgi

Bir şeyi bilmenin iki yolu vardır. Bir karekökün ne olduğunu bilmek ile bir sayının karekökünü bulabilmek aynı şey değildir. Birincisi tanımı bilmek, ikincisi yöntemi bilmektir. Bilgisayara bir iş yaptırmak için ikinci tür bilgi gerekir. Bu kesim iki bilgi türünü ayırır ve her ikisini iki klasik problem üzerinde gösterir: karekök ve en büyük ortak bölen.

1.2.7.1İki bilgi türü

Bilgi, insanların ya da makinelerin dünyayı anlamasına ve sorunları çözmesine yardım eden bilinçli kavrayıştır. İki biçimde ifade edilebilir: bildirimsel ve buyurusal. Tablo 1.2.8 iki türü karşılaştırır.

Bilgisayara buyurusal bilgi gerekir: programlar “nasıl yapılır” bilgisini yazar. Kek tanımını bilen bir aşçı yamağı kek yapamaz; tarife ihtiyacı vardır. Bilgisayar da tanımdan yola çıkarak bir şey üretemez, ona adımlar verilmelidir. Bildirimsel bilgi ise boşa gitmez: sonucun doğru olup olmadığını sınamaya yarar. Tarifle yapılan şeyin gerçekten kek olup olmadığına tanıma bakılarak karar verilir.

1.2.7.2Bildirimsel bilgi

“Su deniz seviyesinde 100 °C'de kaynar” bir gerçektir; bildirimsel bir bilgidir. Karekökün tanımı da bildirimseldir:

y, x'in kareköküdür ⇔ y · y = x ve y ≥ 0.

Bu tanımla bir tahmin sınanabilir. 4 · 4 = 16 ve 4 ≥ 0 olduğundan 4, 16'nın kareköküdür. 5 · 5 = 25 ≠ 16 olduğundan 5 değildir. Tanımdaki y ≥ 0 koşulu da gereklidir: (−4) · (−4) = 16 olsa da −4, 16'nın karekökü sayılmaz.

Ama tanım, karekökün nasıl hesaplanacağını söylemez. √2'yi bu tanımdan doğrudan bulmak mümkün değildir. Tanıma göre √2, kendisiyle çarpılınca 2 eden sayıdır; bu sayının ne olduğunu bulmak için bir yöntem gerekir. Tanımın yapabildiği tek şey, önerilen bir adayı sınamaktır: 1,4 · 1,4 = 1,96 olduğu için 1,4 √2 değildir, ama ona yakındır.

1.2.7.3Buyurusal bilgi: Babil yöntemi

Karekök için buyurusal bilgiye bir örnek Babil yöntemidir. Yöntem, bir sayının karekökünü adım adım bulur:

1. x değerini al.
2. Bir başlangıç tahmini y₀ seç (ör. y₀ = 1).
3. y_n² ≈ x ise dur; cevap y_n'dir.
4. Değilse yeni tahmini hesapla: y_n+1 = (y_n + x / y_n) / 2.
5. Adım 3'e dön.

Yöntemin neden çalıştığı basit bir gözlemle açıklanır. y gerçek kökten büyükse x / y ondan küçüktür; y küçükse x / y büyüktür. Çünkü y · (x / y) = x'tir ve iki çarpanın ikisi birden kökten büyük ya da küçük olamaz. Gerçek kök her zaman y ile x / y arasındadır. İkisinin ortalaması bu aralığın ortasıdır ve köke iki uçtan da daha yakındır. Her tekrarda tahmin köke yaklaşır.

Yakınsama çok hızlıdır. İlk tahmin köke yeterince yakınsa, her adımda doğru basamak sayısı yaklaşık iki katına çıkar. Bunun nedeni, yeni tahminin hatasının eski hatanın karesiyle orantılı olmasıdır: hata 0,01 ise bir sonraki adımda yaklaşık 0,0001 düzeyine iner. Tablo 1.2.9 x = 16 ve y₀ = 1 için ilk beş tekrarı gösterir.

Tablonun ilk satırları yöntemin bir özelliğini gösterir. Başlangıç tahmini 1, gerçek kökün (4) çok altındadır; bu yüzden x / y = 16 çok büyüktür ve ilk ortalama 8,5 olur. Tahmin bir anda kökün üstüne sıçrar. Bundan sonra bütün tahminler kökün üstünde kalır ve her adımda ona yaklaşır. Yakınsama ilk adımlarda yavaştır, köke yaklaştıkça hızlanır: 3. adımda hata yaklaşık 0,14, 4. adımda 0,002, 5. adımda 0,0000006'dır. Beş tekrarda 4'e çok yakın bir değer bulunur.

1.2.7.4Babil yöntemi Java ile

Babil yönteminin adımları doğrudan Java'ya çevrilebilir. “y² ≈ x ise dur” adımı, |y · y − x| farkı küçük bir eşikten (burada 0,001) büyük olduğu sürece devam eden bir while döngüsüne dönüşür.

double x = 16;   // karekökü aranan sayı
double y = 1;    // başlangıç tahmini y0
while (Math.abs(y * y - x) > 0.001) {
    y = (y + x / y) / 2;   // yeni tahmin
    System.out.println(y);
}
System.out.println("Karekök ≈ " + y);

Kodun satırları algoritmanın adımlarına şöyle karşılık gelir:

• double x = 16; adım 1'dir. x ondalıklı tiptedir; Java 16 tam sayısını otomatik olarak 16.0'a çevirir.
• double y = 1; adım 2'dir: başlangıç tahmini.
• while (Math.abs(y * y - x) > 0.001) adım 3'ün tersidir. “Yaklaşık eşitse dur” yerine “yaklaşık eşit değilse devam et” yazılır. Math.abs mutlak değeri verir; fark negatif de olabileceği için gereklidir.
• y = (y + x / y) / 2; adım 4'tür. Eski y değeri sağ tarafta kullanılır, yenisi aynı değişkene yazılır.
• Döngünün sonuna gelince denetim yeniden while satırına döner; bu da adım 5'tir.

Program tam 4 değil, 4'e çok yakın bir yaklaşık değer yazar. Bunun iki nedeni vardır. Birincisi, döngü fark 0,001'in altına inince durur; kesin eşitlik beklenmez. İkincisi, double zaten sonlu duyarlıklıdır. Eşik daha küçük seçilirse (ör. 1e-12) sonuç daha da yakın olur ve döngü yalnız bir iki tur daha döner.

1.2.7.5EBOB: iki tanım

Örneğin 12'nin bölenleri 1, 2, 3, 4, 6, 12; 18'in bölenleri 1, 2, 3, 6, 9, 18'dir. Ortak bölenler 1, 2, 3 ve 6'dır; en büyüğü 6 olduğu için EBOB(12, 18) = 6'dır.

EBOB'un da iki tanımı vardır. Bildirimsel tanım EBOB'un ne olduğunu söyler. d, a ile b'nin ortak bölenidir; yani bir x, y tam sayısı için a = d · x ve b = d · y'dir. Ayrıca bu koşulu sağlayan sayıların en büyüğüdür. Bu tanım bir adayı sınamaya yarar: 6, 12'yi de 18'i de böler ve daha büyük ortak bölen yoktur. Ama tanım EBOB'u bulma yolunu vermez. Şekil 1.2.15'teki gibi bütün bölenleri listelemek küçük sayılarda işe yarar, büyük sayılarda çok yavaştır.

Buyurusal tanım ise EBOB'u nasıl bulacağımızı söyler: Öklid algoritması. Bölme ve kalan almayı, kalan 0 olana kadar tekrarlar. Yaklaşık MÖ 300'de Öklid'in Elemanlar kitabında yer alan bu yöntem, bilinen en eski algoritmalardan biridir.

1.2.7.6Öklid algoritması

Algoritmanın adımları şöyledir:

1. İki pozitif tam sayı a ve b'yi al (a ≥ b).
2. a'yı b'ye böl, kalana r de: r = a mod b.
3. r = 0 ise dur: EBOB = b.
4. Değilse a'ya b'yi, b'ye r'yi ata.
5. Adım 2'ye dön.

Algoritmanın doğruluğu tek bir gözleme dayanır.

Teorem, algoritmanın her adımda neyi koruduğunu söyler: sayılar küçülür ama EBOB değişmez. Kalan her zaman bölenden küçük olduğu için (r < b) sayılar her adımda kesin olarak küçülür ve bir gün kalan 0 olur. Kalan 0 olduğunda b, a'yı tam böler; bu durumda EBOB(a, b) = b'dir. Teorem sayesinde bu sonuç baştaki sayıların da EBOB'udur.

Üç bölmeden sonra kalan 0 olur ve EBOB(48, 18) = 6 bulunur. Bölenleri listeleme yöntemiyle aynı sonuç, 48'in on, 18'in altı böleni yazılarak bulunurdu. Fark büyük sayılarda belirginleşir. Öklid algoritmasında ilk sayı en geç iki adımda bir yarıya iner. b ≤ a/2 ise kalan b'den, dolayısıyla a/2'den küçüktür. b > a/2 ise kalan a − b'dir ve bu da a/2'den küçüktür. Bu yüzden milyarlık sayılarda bile adım sayısı birkaç düzineyi geçmez.

1.2.7.7Öklid algoritması Java ile

int a = 48, b = 18;   // a >= b
int r = a % b;        // kalan
while (r != 0) {
    a = b;
    b = r;
    r = a % b;
}
System.out.println("EBOB = " + b);

Java'daki % işleci kalanı verir; algoritmadaki “mod” işlemine karşılık gelir. Kod, algoritmanın adımlarını şöyle izler:

• İlk iki satır adım 1 ve 2'dir: sayılar alınır ve ilk kalan hesaplanır.
• while (r != 0) adım 3'ün tersidir: kalan 0 değilse devam edilir.
• Döngü gövdesindeki ilk iki satır adım 4'tür. Sıra önemlidir: önce a = b, sonra b = r yazılır. Ters sırada yazılsaydı b'nin eski değeri kaybolurdu.
• r = a % b; satırı adım 2'nin tekrarıdır; denetim yeniden while satırına döner.
• Döngü bittiğinde son bölen b'dedir ve sonuç olarak yazdırılır.

Program “EBOB = 6” yazar. İzlemede 4. ve 8. adımlarda a ile b'nin bir an aynı değeri taşıdığı görülür (18 ve 18, 12 ve 12). Bu bir hata değildir; atamalar sırayla yapıldığı için ara bir durumdur ve bir sonraki satırda b güncellenir.

Kod a ≥ b koşulunu varsayar, ama bu koşul sağlanmasa da doğru çalışır. a = 18, b = 48 ile başlanırsa ilk kalan 18 % 48 = 18 olur. İlk tur yalnız iki sayının yerini değiştirir (a = 48, b = 18) ve algoritma bir bölme fazlasıyla aynı sonucu bulur: dört bölme, EBOB = 6.

1.2.8Algoritma ve problem

Babil yöntemi ve Öklid algoritması, buyurusal bilginin iki örneğidir. İkisinin ortak özelliği, bir problemi kesin adımlarla çözmeleridir. Bu tür adım dizilerine algoritma denir. Algoritma kavramı bilgisayar biliminin merkezindedir; programlama da büyük ölçüde algoritmaları bir dille ifade etmektir.

1.2.8.1Algoritma

Algoritma bir görevin nasıl yapılacağını belirler ve karmaşık problemleri basitleştirmeye yarar. Bilgisayar programlarının temelidir: programlama, algoritmaları bir programlama diliyle ifade etme sürecidir. Bilgisayar bilimi de büyük ölçüde algoritmaların tasarımı ve analizinden oluşur. İyi bir programcı, problem için uygun algoritmayı seçip uygulayabilen kişidir.

Tanımdaki dört özellik birer birer önemlidir.

• Açıklık: Her adım tek bir biçimde anlaşılmalıdır. “Sayıyı biraz büyüt” açık bir adım değildir; “sayıya 1 ekle” açıktır. Bilgisayar yorum yapmadığı için açık olmayan bir adımı yürütemez.
• Sıra: Adımların sırası sonucu değiştirir. Öklid algoritmasında a = b ile b = r atamalarının sırası değişirse algoritma yanlış sonuç verir. Kek tarifinde de pişirmeden önce un eklenir.
• Sonluluk: Algoritma her girdi için bir gün durmalıdır. “1 ekle ve yazdır; bunu hiç durmadan tekrarla” talimatı açık ve sıralıdır, ama bitmediği için algoritma değildir. Babil yönteminin durduğunu fark eşiği, Öklid algoritmasının durduğunu da kalanın her adımda küçülmesi güvence altına alır.
• Amaç: Algoritma belirli bir problemi çözmek için yazılır ve doğru sonucu vermelidir.

İyi tasarlanmış bir algoritma hem doğru hem verimli olmalıdır. Doğruluk, her geçerli girdi için doğru sonucu vermesidir. Verimlilik ise bu sonucu makul bir zamanda ve makul bir bellekle bulmasıdır. EBOB için bölenleri listeleme yöntemi doğrudur ama verimsizdir; Öklid algoritması hem doğru hem verimlidir.

“Algoritma” sözcüğünün kökeni 9. yüzyılda Bağdat'ta yaşamış matematikçi el-Hârizmî'dir. Onun hint-arap rakamlarıyla hesap yapmayı anlatan kitabının Latince çevirisinde adı “Algoritmi” diye yazıldı. Sözcük zamanla, kuralları belli bir hesap yöntemi anlamını kazandı.

Algoritmalar çoğu zaman bir programlama dilinde değil, sözde kodla (pseudocode) yazılır. Sözde kod, algoritmayı belirli bir dile bağlı kalmadan, yarı doğal dille anlatma biçimidir. Noktalı virgül, tip bildirimi gibi ayrıntılarla uğraşmaz; adımların mantığına odaklanır. Bu notta kullanılan while … do, set … to, repeat … until gibi kalıplar sözde kodun yaygın biçimleridir.

1.2.8.2Girdi, işlem, çıktı

Bir algoritma yazılmadan önce problemin kendisi açıkça tanımlanmalıdır. Programın ya da algoritmanın ne yapması gerektiği belirlenir; gerekli adımlar ve çıktı ortaya konur. Problem belirlemenin iki bileşeni vardır:

• Girdi (input): Problemin çözülmesi için gereken bilgi ya da veri.
• Çıktı (output): Problemin sonucu ya da istenen bilgi.

Şekil 1.2.17'deki düzen, hesaplamanın üç aşamasının problem tanımına uygulanmış biçimidir. Girdi ve çıktı belirlenince işlem, ikisini bağlayan algoritma olur. Öklid algoritması için girdi iki pozitif tam sayı, çıktı onların EBOB'udur. Babil yöntemi için girdi bir pozitif sayı ve bir başlangıç tahmini, çıktı karekökün yaklaşık değeridir.

Şekildeki geri dönüş oku geri bildirimi (feedback) gösterir: çıktıya bakarak girdiyi ya da işlemi düzeltmek. Termostat iyi bir örnektir. Sıcaklığı ölçer (girdi), istenen değerle karşılaştırır (işlem), ısıtıcıyı açar ya da kapatır (çıktı). Isıtıcının açılması odanın sıcaklığını, yani bir sonraki girdiyi değiştirir. Elektrik-elektronik mühendisliğindeki kapalı çevrim kontrol sistemleri de bu düzenle çalışır. Babil yöntemi de bir tür geri bildirimdir: her tahminin karesi x ile karşılaştırılır ve sonuç bir sonraki tahmini belirler.

1.2.8.3Belirsiz bir isteği netleştirmek

Problemi tanımlarken altı soru yardımcı olur: Ne? Kim? Nerede? Ne zaman? Nasıl? Neden? Bu sorular özellikle günlük dille verilmiş belirsiz istekleri netleştirmeye yarar.

“Not ortalaması hesapla” isteği belirsizdir. Program yazılmadan önce en az üç sorunun yanıtı bilinmelidir:

• Kaç not var? Sayı sabit mi (üç not), yoksa kullanıcı mı girecek?
• Notların ağırlıkları eşit mi? Vize %40, final %60 ise basit ortalama yanlış sonuç verir.
• Sonuç tam sayı mı, ondalıklı mı olacak? Yuvarlama yapılacak mı?

Bu sorular yanıtlanmadan yazılan program yanlış problemi çözebilir. Program hatasız derlenir, hatasız çalışır, ama istenen şeyi yapmaz. Bu tür hataları bulmak, derleme hatalarını bulmaktan çok daha zordur; çünkü derleyici hiçbir uyarı vermez.

1.2.9Algoritmik işlemler

Babil yöntemi, Öklid algoritması ve not ortalaması farklı problemleri çözer, ama hepsi aynı üç tür işlemden kurulur. Bu üç tür her programlama dilinde bulunur ve algoritmaların temel yapısını oluşturur.

1.2.9.1Üç işlem türü

• Sıralı işlem (sequential): Her işlem bir öncekinden sonra, sırayla çalışır. Örneğin veriyi oku, işle, sonucu üret.
• Koşullu işlem (conditional): Koşul sağlanıyorsa bir işlem, sağlanmıyorsa başka bir işlem yapılır. Örneğin sayı pozitif mi?
• Döngülü işlem (iterative): Bir işlem, koşul sağlandığı sürece tekrarlanır. Örneğin bir listedeki bütün sayıları toplamak.

Şekil 1.2.18'deki üç yapı birbirinin içine yerleştirilerek bütün algoritmalar kurulabilir. Öklid algoritmasının gövdesi sıralı üç atamadır; bu gövde bir döngünün içindedir; döngünün devam edip etmeyeceğine bir koşul karar verir. Java'da sıralı işlem deyimleri alt alta yazmakla, koşullu işlem if/else ile, döngülü işlem while, do-while ve for ile yazılır.

Bu üç türün “karmaşıklığı denetlemeye yarar” olması da önemlidir. Bir programın akışı yalnız bu üç yapıyla kurulursa her parçanın tek bir girişi ve tek bir çıkışı olur. Program yukarıdan aşağıya okunabilir ve izlenebilir. Bu fikir, yapısal programlama adıyla 1960'lı ve 1970'li yıllarda yerleşti ve Java dahil bugünkü dillerin hepsini etkiledi.

1.2.9.2while: önce koşul

Döngülü işlem, devam koşulu yanlış olana kadar belirli eylemleri tekrar eder. Listeleri gezmek ve verileri işlemek için kullanışlıdır. Döngünün iki parçası vardır: devam koşulu ve gövde. Koşulun gövdeden önce mi sonra mı sınandığı, iki farklı döngü türü ortaya çıkarır.

İlk türde koşul önce sınanır. Sözde kodda bu yapı while … do ile yazılır. Aşağıdaki örnek, i > 0 olduğu sürece s'yi 1 artırır ve i'yi 1 azaltır.

while i > 0 do
    set s to s + 1
    set i to i - 1

Java karşılığı neredeyse birebirdir:

int s = 0, i = 3;
while (i > 0) {
    s = s + 1;
    i = i - 1;
}

Döngü üç tur döner ve sonunda s = 3, i = 0 olur. Koşul dört kez sınanır: üçünde doğru, sonuncusunda yanlış çıkar. Genel olarak i, n ile başlarsa döngü n tur döner ve s sonunda n olur. Koşul önce sınandığı için i baştan 0 ise gövde hiç çalışmaz.

1.2.9.3repeat … until ve do … while

İkinci türde gövde önce çalışır, koşul sonra sınanır. Sözde kodda bu yapı repeat … until ile yazılır. Aşağıdaki örnek, k değeri n'den büyük olana kadar k'yi yazdırır ve 1 artırır.

repeat
    print k
    set k to k + 1
until k > n

Java'da repeat … until yoktur. Karşılığı do … while'dır, ama koşul tersine çevrilir. until, koşul doğru olunca durur; while ise koşul doğru oldukça devam eder. “k > n olana kadar” ifadesi, “k ≤ n olduğu sürece” ifadesiyle aynı anlama gelir.

int k = 1, n = 3;
do {
    System.out.println(k);
    k = k + 1;
} while (k <= n);

k = 1, n = 3 için program 1, 2 ve 3'ü alt alta yazar. Gövde üç kez çalışır; üçüncü turun sonunda k = 4 olur, 4 <= 3 yanlış çıkar ve döngü biter.

İki yapının farkı, koşulun baştan yanlış olduğu durumda görülür. k = 5, n = 3 ile başlanırsa do … while döngüsü 5'i bir kez yazar, sonra koşulu sınar ve durur. Aynı koşulla yazılmış bir while (k <= n) döngüsü ise gövdeyi hiç çalıştırmaz ve hiçbir şey yazmaz. Gövdenin en az bir kez çalışması gereken durumlarda do … while doğal bir seçimdir. Kullanıcıdan geçerli bir değer girene kadar giriş istemek bunun tipik örneğidir: değer en az bir kez okunmalıdır.

1.2.9.4Sonsuz döngü

Bir döngünün bitmesi için gövdenin koşulu etkileyen değişkeni değiştirmesi ve bu değişikliğin koşulu sonunda yanlış yapması gerekir. while örneğinde i = i - 1; satırı unutulursa i hep 3 kalır, 3 > 0 hep doğru olur ve döngü hiç bitmez. Benzer biçimde i = i + 1; yazılırsa i büyür ve koşul yine hep doğru kalır. Bu ikinci durumda i sonunda int'in sınırına ulaşıp taşar ve negatif olur; döngü belki biter ama çok uzun bir süre sonra ve yanlış bir sonuçla.

Derleyici sonsuz döngüleri genel olarak yakalayamaz. Durma probleminin bir sonucu da budur: bir döngünün her girdide biteceğini otomatik olarak gösteren genel bir yöntem yoktur. Takılan bir program, geliştirme ortamındaki (IDE) durdur düğmesiyle ya da konsolda Ctrl+C ile durdurulur.

Bir döngüyü yazarken üç soru sormak sonsuz döngüleri büyük ölçüde önler. Koşuldaki değişken döngüden önce doğru bir değer alıyor mu? Gövde bu değişkeni değiştiriyor mu? Değişiklik koşulu sonunda yanlış yapacak yönde mi? Üç sorunun yanıtı da “evet” ise döngü biter.

1.2.10Sık yapılan hatalar

Sözde koddan Java'ya geçerken bazı hatalar çok sık yapılır. Bir kısmını derleyici yakalar ve bir hata iletisi verir; bir kısmı ise derlenir ama yanlış çalışır. Aşağıdaki iletiler JDK 21'in javac derleyicisiyle elde edilmiştir.

1.2.11Özet

• Programlama bilgisayara yapacağı işi adım adım bildiren talimatları yazmaktır. Hesaplama veriyi matematik ve mantıkla işleyip bir sonuç üretme sürecidir. Hesaplama yapılan iştir, programlama o işin tarifidir.
• Bilgisayar bilimi mantık, problem çözme ve yaratıcılığa dayanır; teknoloji bu bilimde yalnız bir araçtır. Yazılan programlar gerçek insanları etkiler ve bu da bir sorumluluk getirir.
• Hesaplamalı düşünme dört beceriden oluşur. Ayrıştırma problemi alt problemlere böler, örüntü tanıma tekrar eden işi görür. Soyutlama gereksiz ayrıntıyı atar, algoritma tasarımı çözümü sonlu ve açık adımlarla yazar.
• Sabit programlı makinede program donanıma gömülüdür. Depolanan programlı makinede program da veri gibi bellekte durur ve değiştirilebilir. EDVAC ve von Neumann mimarisi bugünkü bilgisayarların temelidir.
• Tarihin ana çizgisi: Babbage'ın Analitik Makinesi (1837) ve Lovelace'ın programı (1843); Turing'in kuramsal modeli (1936); vakum tüplü ABC, Colossus ve ENIAC; depolanan programlı EDVAC; transistör (1947) ve Fortran (1957).
• Turing makinesi bant, bant başlığı ve kural tablosundan oluşur. Evrensel Turing makinesi başka bir makinenin tanımını okuyup onu taklit eder. Church–Turing tezine göre adım adım hesaplanabilen her şey bir Turing makinesiyle hesaplanabilir.
• Her problem hesaplanabilir değildir: durma problemini her program için çözen bir algoritma yoktur. Java gibi Turing-tam diller güç bakımından eşittir; hız ve kolaylık bakımından farklıdır.
• Kaynaklar sınırlıdır ve bu sınırlar Java'da da görünür: int taşar, double yaklaşık değer tutar, iki int'in bölümü int'tir.
• Bildirimsel bilgi bir şeyin ne olduğunu söyler ve sınamaya yarar. Buyurusal bilgi nasıl yapılacağını söyler ve bilgisayara gereken budur. Babil yöntemi karekökü, Öklid algoritması EBOB'u buyurusal olarak bulur.
• Algoritma açık, sıralı, sonlu ve amaçlı adımlardan oluşur. Algoritma yazılmadan önce problemin girdisi ve çıktısı belirlenir; belirsiz istekler sorularla netleştirilir.
• Her algoritma sıralı, koşullu ve döngülü işlemlerden kurulur. while koşulu önce, do … while sonra sınar. Sözde koddaki repeat … until Java'da do … while ile ve koşul değillenerek yazılır. Gövde koşulu sonunda yanlış yapmazsa döngü sonsuza dek sürer.

1.2.12Kavram listesi

• hesaplama computation
• hesaplamalı düşünme computational thinking
• problemi parçalama (ayrıştırma) decomposition
• soyutlama abstraction
• algoritma algorithm
• sözde kod pseudocode
• bit bit
• bayt byte
• depolanan programlı bilgisayar stored-program computer
• von Neumann mimarisi von Neumann architecture
• derleyici compiler
• Turing makinesi Turing machine
• hesaplanabilirlik computability
• taşma overflow
• kayan noktalı sayı floating-point number
• tam sayı bölmesi integer division
• bildirimsel / buyurusal bilgi declarative / imperative knowledge
• en büyük ortak bölen (EBOB) greatest common divisor (GCD)
• Öklid algoritması Euclidean algorithm
• girdi / çıktı input / output
• sıralı akış sequential flow
• koşullu akış conditional flow
• while döngüsü while loop
• do-while döngüsü do-while loop
• sonsuz döngü infinite loop

1.2.13Kendini Dene

1. Bir otoparkın gün içindeki en yoğun saatini bulan bir program yazılacak. Giriş ve çıkış kapılarındaki sayaçlar her araç geçişinde saati kaydediyor. Aşağıdaki kararlardan her biri hesaplamalı düşünmenin hangi becerisine karşılık gelir? (a) Araçların plakası ve rengi göz ardı edilir. (b) Problem “kayıtları oku, her saat için içerideki araç sayısını hesapla, en büyüğü bul, yaz” diye bölünür. (c) “En büyüğü bulma” işinin not ortalamasındaki döngüye benzediği fark edilir.

   Cevap

   (a) Soyutlama: sonuç için yalnız geçiş saatleri ve yönü (giriş ya da çıkış) gerekir. (b) Ayrıştırma: büyük problem dört alt probleme bölünmüştür. (c) Örüntü tanıma: her kayıt için tekrar eden aynı adım bir döngüyle yazılabilir. Bu üç adımdan sonra algoritma tasarımı, alt problemleri sıralı adımlar olarak yazar.

2. ENIAC ile EDVAC arasındaki temel fark nedir? Hangisi depolanan programlı bir bilgisayardır?

   Cevap

   ENIAC'ta program kablo bağlantılarıyla kuruluyordu; yeni bir iş için kablolar elle yeniden takılıyordu. Sayıları da onlu sistemde tutuyordu. EDVAC ise programı ve veriyi aynı bellekte saklıyordu ve ikili sistemi kullanıyordu. Depolanan programlı bilgisayar EDVAC'tır; tasarımı von Neumann mimarisinin temelidir.

3. Bitleri ters çeviren Turing makinesi 111000 bandında kaç adım çalışır? Makine durduğunda bantta ne kalır?

   Cevap

   Her hücre için bir yazma adımı vardır: 6 yazma adımı. Yedinci adımda □ okunur ve makine durur. Toplam 7 adım çalışır; bantta 000111 kalır. Genel olarak n bitlik bir bant için n + 1 adım gerekir.

4. Babil yöntemiyle √9, y₀ = 1 alınarak üç adım hesaplansın. Tahminler kökün hangi tarafında kalır?

   Cevap

   y₁ = (1 + 9) / 2 = 5; y₂ = (5 + 9/5) / 2 = 3,4; y₃ = (3,4 + 9/3,4) / 2 ≈ 3,023529. Başlangıç tahmini kökün altındadır; ilk adımda tahmin kökün üstüne çıkar ve sonra hep üstte kalarak 3'e yaklaşır.

5. Öklid algoritmasıyla EBOB(252, 105) bulunsun. Kaç bölme yapılır? Sonucun sağlaması nasıl yapılır?

   Cevap

   252 = 2 · 105 + 42; 105 = 2 · 42 + 21; 42 = 2 · 21 + 0. Üç bölmeden sonra kalan 0 olur ve EBOB = 21 bulunur. Sağlama: 252 = 21 · 12 ve 105 = 21 · 5'tir; 12 ile 5'in 1'den büyük ortak böleni yoktur.

6. Aşağıdaki iki satır ne yazdırır?
   System.out.println(Integer.MAX_VALUE + 1 == Integer.MIN_VALUE);
System.out.println(7 / 2 * 2.0);

   Cevap

   Birinci satır true yazar: en büyük int değere 1 eklenince taşma olur ve sonuç en küçük değere sarar. İkinci satır 6.0 yazar: işlemler soldan sağa yapılır, önce 7 / 2 tam sayı bölmesiyle 3 olur, sonra 3 · 2.0 = 6.0 bulunur.

7. k = 0 ile başlayan iki döngü veriliyor. Her birinin sonunda k kaçtır?
   do { k = k - 3; } while (k > 0);
while (k > 0) { k = k - 3; }

   Cevap

   do … while gövdeyi koşuldan önce bir kez çalıştırır: k = −3 olur, -3 > 0 yanlış çıkar ve döngü biter; sonuç −3. while ise koşulu önce sınar: 0 > 0 yanlış olduğu için gövde hiç çalışmaz; sonuç 0.

8. Ortalama programında bölme satırı double ort = toplam / notlar.length; biçiminde, yani (double) dönüşümü olmadan yazılsa, 40, 75 ve 90 notları için ne yazdırılır? Neden?

   Cevap

   “Ortalama: 68.0” yazdırılır. toplam (205) ve notlar.length (3) ikisi de int'tir; bölme tam sayı bölmesi olarak yapılır ve 68 bulunur. Bu değer ancak atamada double'a çevrilir; kaybolan kesir geri gelmez.

9. “Bir sayı, 1'den ve kendisinden başka pozitif böleni olmayan, 1'den büyük bir tam sayıysa asaldır” cümlesi hangi tür bilgidir? Aynı konuda öbür türe bir örnek verilsin.

   Cevap

   Bildirimseldir: asal sayının ne olduğunu tanımlar ve bir adayı sınamaya yarar. Buyurusal bir karşılığı şöyle olabilir: “n > 1 olsun. 2'den başlayarak √n'ye kadar her d için n mod d'ye bak; kalan 0 olan bir d bulunursa ‘asal değil’, bulunmazsa ‘asal’ yaz.” Bu tarif, kararın nasıl verileceğini adım adım söyler.

1.2.14İleri okuma

• J. M. Wing, “Computational Thinking”, Communications of the ACM 49(3), 2006: hesaplamalı düşünme terimini yaygınlaştıran üç sayfalık makale. Bu düşünme biçiminin neden herkese gerekli olduğunu tartışır.
• J. V. Guttag, Introduction to Computation and Programming Using Python (3. baskı, 2021), Bölüm 1: bildirimsel ve buyurusal bilgi ayrımını ve karekök için tahmin et-iyileştir yöntemini bu notla aynı örnekler üzerinden anlatır.
• C. Petzold, Code: The Hidden Language of Computer Hardware and Software (2. baskı, 2022): rölelerden ve anahtarlardan başlayarak bir bilgisayarın parça parça nasıl kurulduğunu, ikili sayıları ve depolanan program fikrini teknik olmayan bir dille açıklar.
• R. Sedgewick ve K. Wayne, Computer Science: An Interdisciplinary Approach (2016), Turing makineleri ve hesaplanabilirlik bölümleri: Turing makinesi örneklerini, evrensel makineyi ve durma probleminin kanıtını Java programlarıyla ilişkilendirerek verir.

1.2.15Kaynaklar

1. H. M. Deitel, P. J. Deitel, Java: How to Program, 11. baskı, Pearson, 2017.
2. A. B. Downey, C. Mayfield, Think Java, 2. baskı, O'Reilly, 2019.
3. J. V. Guttag, Introduction to Computation and Programming Using Python, 3. baskı, MIT Press, 2021.
4. Oracle, The Java Tutorials: “Language Basics”, docs.oracle.com/javase/tutorial.
5. C. Petzold, Code: The Hidden Language of Computer Hardware and Software, 2. baskı, 2022.
6. R. Sedgewick, K. Wayne, Computer Science: An Interdisciplinary Approach, Addison-Wesley, 2016.
7. A. M. Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem”, Proceedings of the London Mathematical Society, 1936.
8. J. M. Wing, “Computational Thinking”, Communications of the ACM 49(3), 33–35, 2006.

İlgili sayfalar: Bölüm 1.2 sunumu · Çalışma soruları · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.