Bir kez düşün,
bin kez çalıştır.
Bir soruyu çözmek başka, o türden bütün soruları çözen bir yol yazmak başka. Bu ünitede matematik işlemlerini adım adım, sırası kesin, her adımı denetlenebilir bir algoritmaya çeviriyoruz — sonra o algoritmayı akış şemasıyla çiziyoruz. Karekök hesaplayan yöntemi 4000 yıl önce Babilliler böyle yazmıştı.
Algoritma, bir problemi çözmek için izlenecek adımların sırası kesin biçimde belirlenmiş listesidir. Önemli olan şu: her adım, bir sonrakine geçmeden önce tam olarak bitmiş olmalıdır. Aynı algoritmayı anlatmanın üç yolu vardır ve üçü de aynı şeyi söyler.
Adımlar numaralanarak Türkçe cümlelerle yazılır. En kolay okunan, en uzun olan biçim.
1. adım: Başla
2. adım: Toplam = 0, sayaç = 1
3. adım: Toplam = Toplam + sayaç
sayaç = sayaç + 1
4. adım: Eğer sayaç < 10 ise 3. adıma git,
değilse döngüyü sonlandır
5. adım: Yazdır “Toplam”
6. adım: Bitir
Programlama diline benzeyen ama hiçbir dilin kurallarına bağlı olmayan kısa yazım.
Kod yazmadan önce düşünmek için kullanılır.
topla ← 0
sayaç ← 1
döngü sayaç 1’den 10’a kadar
topla ← topla + sayaç
döngü sonu
yaz topla
Her adım bir şekle, adımlar arası geçiş bir oka dönüşür. Karar noktalarını en açık
gösteren biçim budur; şemaya bakan biri “buradan iki yol çıkıyor” diye anında görür.
Şekiller keyfî değildir: şeklin kendisi işin türünü
söyler. Bir sonraki bölümde yedisini de tanıyacaksın.
Karmaşık bir cebirsel ifadeyi ya da fonksiyonu klasik yolla çözmek zor ve zaman alıcı olabilir. Algoritma bu işlemleri kısa sürede, sistematik ve hatasız yapar. Asıl kazanç şudur: aynı türden problemlere tekrar tekrar çözüm üretmek yerine bir kez çözüm yolu kurarsın, sonra sayıları değiştirip tekrar tekrar çalıştırırsın. Yapay zekâ uygulamaları, enerji sistemleri ve savunma sanayisi de bu mantık üzerine kuruludur.
Akış şemasında bir kutunun içine ne yazdığın kadar hangi şekli seçtiğin de anlam taşır. Yedi sembolü düğmelere basarak tanı: her birinin ne zaman kullanıldığını ve şemadaki komşularını göreceksin.
Altıgenin içine dört bilgi yazılır ve iki ayrı yazılışı
da aynı anlama gelir:
i = a, N, b
veya
i, a, N, b
i döngü değişkeni ·
a başlangıç değeri ·
N bitiş değeri ·
b artış-azalış değeri.
Artış değeri 1 olan bir işlemin 5 kez tekrarlanması isteniyorsa sembolün içi
i = 1, 5, 1 olur.
Karar tek bir karşılaştırmayla verilir:
Başlangıç değeri bitiş değerinden küçükse artan döngü
(i = 1, 100, 2 → 1, 3, 5, …).
Başlangıç değeri bitiş değerinden büyükse azalan döngü
(i = 10, 1, −1 → 10, 9, 8, …).
Azalan bir döngüde artış değerini pozitif yazmak, döngünün hiç bitmemesine yol açar —
en sık yapılan hata budur.
Bir algoritmadaki karar noktası aslında bir önermedir: doğru ya da yanlış olur, arası yoktur. Günlük dilde uzun uzun anlattığın koşul, mantık bağlaçlarıyla tek satıra iner ve artık bilgisayarın çalıştırabileceği bir şeye dönüşür.
∧ (ve) — iki koşulun ikisi
birden sağlanmalı. Biri bile bozulursa sonuç yanlıştır.
∨ (veya) — en az biri
sağlansa yeter. “Ya da” da aynı bağlaçtır, ayrı bir şey değil.
⇒ (ise) — koşul sağlandığında belirtilen işlemin
yapılmasını sağlar. Algoritmalarda farklı durumları değerlendirmek ve döngü içinde karar
vermek için kullanılır.
⇔ (ancak ve ancak) — iki koşul
aynı anda doğru ya da aynı
anda yanlış olduğunda doğru sonucu verir. İkisi ayrı düşerse yanlıştır.
∀ (her, tüm) — listedeki
istisnasız herkes koşulu sağlıyor demektir. Bir tek
kişi sağlamıyorsa cümle yanlıştır; yani tek bir karşı örnek
onu çürütür.
∃ (bazı, en az bir) — listede
en az bir kişi koşulu sağlıyor demektir. Onu doğrulamak
için bir örnek yeter; çürütmek içinse hepsine tek tek bakman gerekir.
Bu asimetri algoritmada işine yarar: “her” cümlesini denetlerken ilk karşı örnekte
durursun, “bazı” cümlesini denetlerken ilk örnekte durursun.
Okullar dönem sonunda öğrencilere teşekkür ya da takdir belgesi verir. Karar keyfî değil, dört koşula bağlıdır — yani bir algoritmadır. Aşağıdaki öğrenci listesinde düğmeye bastığında algoritma dört koşulu sırayla denetler ve nerede takıldığını gösterir.
1 · Tüm derslerden başarılı olması
2 · Derslerin dönem puanlarının ağırlıklı ortalamasının 70,00’ten aşağı olmaması
3 · Davranış puanının 100 olması
4 · Özürsüz devamsızlık gün sayısının en fazla 5 olması
Bunlar “ve” ile bağlıdır: dördü birden sağlanmalıdır.
Dört koşul sağlandıysa belge türü ortalamaya bakılarak belirlenir:
Ortalama 70,00 – 84,99 arasındaysa
teşekkür belgesi
Ortalama 85,00 ve üzeriyse
takdir belgesi
Bu ikinci basamak “ise” bağlacıyla kurulur: koşul
doğruysa şu işlem yapılır.
1. adım: Başla
2. adım: Öğrencinin ortalamasını, başarısız ders sayısını, davranış puanını ve özürsüz
devamsızlık gün sayısını oku
3. adım: Başarısız ders sayısı 0 değilse “Belge alamaz” yazdır, 8. adıma git
4. adım: Davranış puanı 100 değilse “Belge alamaz” yazdır, 8. adıma git
5. adım: Devamsızlık > 5 ise “Belge alamaz” yazdır, 8. adıma git
6. adım: Ortalama < 70 ise “Belge alamaz” yazdır, 8. adıma git
7. adım: Ortalama ≥ 85 ise “Takdir belgesi” yazdır, değilse “Teşekkür belgesi” yazdır
8. adım: Bitir
Dikkat et: koşullar en ucuz ve en kesin eleyen olandan başlayarak sıralandı. Böylece başarısız dersi olan bir öğrenci için kalan üç denetim hiç çalışmaz. Algoritmalarda koşulların sırası, sonucu değil hızı değiştirir.
Döngü, istenen koşullarda tekrar eden (yinelenen) işlemler için kullanılan yapıdır. 1 ile 100 arasındaki tek sayıların toplamını bulmak için 50 tane toplama satırı yazman gerekmez — bir döngü yeter. Üstelik aynı döngüyü iki farklı yoldan kurabilirsin.
BAŞLA
sayaç = 1, toplam = 0
toplam = toplam + sayaç
sayaç = sayaç + 2
sayaç < 100 ? evet → yukarı dön
hayır → toplam yazdır
BİTİR
Burada tekrarı sağlayan şey koşul sembolüdür. Sayaç elle 2 artırılır, koşul her turda ayrıca denetlenir.
BAŞLA
toplam = 0
i = 1, 100, 2
toplam = toplam + i
(birleştirici → döngüye dön)
toplam yazdır
BİTİR
Burada tekrarı sağlayan şey döngü sembolüdür. Artış, başlangıç ve bitiş tek satırda yazılı; sayacı elle artırmaya gerek yok.
Akış Şeması 1’de başlangıçta toplam 0, sayaç 1 kabul edilir; sayaç 2 artımla artırılır,
koşulda sayacın 100’den küçük olması istenir ve her artımda toplam sayaç kadar büyür.
Akış Şeması 2’de başlangıçta toplam 0 kabul edilir, döngü değişkeni i seçilip 1’den
başlayarak 100’e kadar 2 artım değeriyle artırılır ve her artımda toplama i eklenir.
Buradan çıkan sonuç: bir algoritmanın işleyişi bir ya da
daha fazla akış şemasıyla ifade edilebilir. Doğru şema tek değildir; hangisinin daha
okunaklı olduğuna sen karar verirsin.
İkisinin de bulduğu sayı: 1 + 3 + 5 + … + 99 = 2500
(50 tane tek sayı, 50² = 2500).
Bir fonksiyonun sıfırının (kökünün) iki değer arasında kaldığı biliniyorsa, bu iki değerin ortalaması alınıp köke adım adım yaklaşılabilir. Buna ortalama alarak yineleme yöntemi denir. Her adımda arama aralığı yarıya iner; yani belirsizlik her turda ikiye bölünür.
1. adım: Kökün arasında olduğu tahmin edilen iki sayı belirlenir: x₁ ve x₂
2. adım: f(x₁) ve f(x₂) hesaplanır. Biri sıfırsa fonksiyonun sıfırı o sayıdır
3. adım: İkisi de sıfır değilse ortalama alınır: x₃ = (x₁ + x₂) / 2
4. adım: f(x₃) = 0 ise x₃ köktür, 6. adıma git.
f(x₃) ≠ 0 ise işaretine göre yeni aralık belirlenir:
f(x₃) ile f(x₁) aynı işaretliyse x₁ = x₃ yenilenir
zıt işaretliyse x₂ = x₃ yenilenir
5. adım: f(x₃) sıfıra yaklaşıncaya kadar adımları tekrarla
6. adım: Bitir
a = 2, b = −6 alalım: f(x) = 2x − 6. İlk tahminler x₁ = 1, x₂ = 7.
f(1) = −4 negatif, f(7) = 8
pozitif. Fonksiyon değeri eksiden artıya geçtiğine göre
arada bir yerde sıfırdan geçmek zorunda — kök bu iki
sayının arasındadır. Yöntemin bütün gücü bu tek gözlemde.
Ortalama alınır: (1 + 7)/2 = 4, f(4) = 2 pozitif. Demek kök 1 ile 4 arasında.
(1 + 4)/2 = 2,5, f(2,5) = −1 negatif → kök 2,5 ile 4 arasında. (2,5 + 4)/2 = 3,25,
f(3,25) = 0,5 → kök 2,5 ile 3,25 arasında. (2,5 + 3,25)/2 = 2,875, f(2,875) = −0,25.
Bu işlem sürdürüldüğünde fonksiyonun sıfırı yaklaşık 3
bulunur — zaten 2x − 6 = 0 ⇒ x = 3.
Karekök hesaplama işlemi, sayısal algoritmalar kullanılarak ilk kez Babilliler tarafından yapılmıştır. Babil metodu adı verilen bu yöntem de bir yinelemedir: bir tahminden başlar, her turda tahmini düzeltir ve kısa sürede hesap makinesi kadar hassas bir sonuca ulaşır.
Karekökü alınacak sayı a, başlangıç tahmini x₀ > 0 olmak üzere
xn+1 = ½ · ( xn + a / xn )
n = 0, 1, 2, …
Belirlenen bir hata payına ulaşılana kadar tekrarlanır. Gerçek kök değerine
mümkün olduğunca yakın bir başlangıç tahmini seçmek işlem
adımlarını kısaltır.
8² = 64 ve 9² = 81 olduğundan √70 bu ikisinin arasındadır; 70 sayısı 64’e daha yakın
olduğu için x₀ = 8 alınır.
x₁ = ½ · (8 + 70/8) = ½ · (8 + 8,75) = 8,375
x₂ = ½ · (8,375 + 70/8,375) ≈ ½ · (8,375 + 8,3582) ≈
8,3666
Gerçek değer 8,36660… — iki adımda dört ondalık basamak doğru çıktı.
1. adım: Karekök değeri hesaplanacak sayı belirlenir; bu sayı a olsun
2. adım: Gerçek karekök değerine yakın tahminî bir sayı girilir; bu sayı x₀ olsun
3. adım: xn+1 = ½(xn + a/xn) formülünden x₁ bulunur
4. adım: Yinele. |xn+1 − xn| < 0,001 ise bitir, değilse 3. adıma git
5. adım: Bitir
Durma ölçütü iki ardışık tahminin farkıdır, doğru cevaba uzaklık değil — çünkü doğru cevabı zaten bilmiyoruz. Yinelemeli her algoritmanın böyle bir “ne zaman duracağım” kuralı olmalıdır.
a irrasyonel bir sayının karekökü ve b, a’ya en yakın tam kare sayı olmak üzere
√a ≈ (a + b) / (2 · √b)
√123 için: 121 = 11² sayısı 123’e en yakın tam karedir.
√123 ≈ (123 + 121) / (2 · 11) = 244 / 22 ≈ 11,0909
Gerçek değer 11,09053… — üç basamak doğru.
Bu iki yöntem aslında aynı yöntemdir: (a + b)/(2√b) yazılışında
√b yerine x₀ dersen ½(x₀ + a/x₀) çıkar. Yani tam kare yöntemi, Babil metodunun
tek adımıdır ve başlangıç tahmini olarak en yakın tam
karenin kökünü kullanır.
Bir önceki ünitede n farklı nesnenin n! şekilde sıralandığını öğrendin. Şimdi bunu hesaplayan algoritmayı yazıyoruz. Faktöriyel, döngünün en temiz örneğidir: tek bir çarpma satırı, doğru sayıda tekrar.
oku n
eğer n < 0 ise yaz “geçersiz”, bitir
çarpım ← 1
döngü i = 1, n, 1
çarpım ← çarpım · i
döngü sonu
yaz çarpım
Çarpımın başlangıç değeri 1’dir, 0 değil — sıfırla başlarsan her şey sıfır kalır. Bu, döngü kuran herkesin bir kez düştüğü tuzaktır. Ayrıca n = 0 için döngü hiç çalışmaz ve çarpım 1 olarak yazdırılır; bu da 0! = 1 kabulüyle uyumludur.
oku sayı
basamak ← 0
tekrarla
sayı ← sayı / 10 (tam bölüm)
basamak ← basamak + 1
sayı > 0 olduğu sürece
yaz basamak
48 765 için: 4876 → 487 → 48 → 4 → 0. Bölme beş kez yapıldı, cevap 5 basamak. Burada döngünün kaç kez döneceğini önceden bilmiyoruz; bitiş sayıya bağlı. Bu yüzden döngü sembolü değil koşul sembolü kullanmak daha uygundur.
20 öğrenciden ortalaması 50 ve üzeri olanları saymak:
adet ← 0; i = 1, 20, 1 döngüsünde her not okunur, not ≥ 50 ise adet bir artırılır; döngü
bitince adet yazdırılır. Sayaç döngünün dışında sıfırlanır
— içeride sıfırlarsan her turda sıfıra döner.
Bir sayının pozitif çift olup olmadığını bulmak: sayı
okunur; sayı > 0 ve sayının 2 ile bölümünden kalan 0 ise “pozitif çift sayıdır”
yazdırılır, değilse “değildir” yazdırılır. Tek koşul sembolü yeter, çünkü iki şartı
∧ ile birleştirdik.
Girilen 10 sayıdan negatif olanları saymak: döngüsüz
yazılırsa sayı okuma satırı 10 kez tekrarlanır; döngüyle yazılırsa
i = 1, 10, 1 satırı bunun yerine geçer. İkisi de
doğrudur, ikincisi üç satır kısadır ve sayı 10’dan 1000’e
çıkınca da değişmez.
“Ortalaması 70’ten küçük veya devamsızlığı 5’ten büyük
olanlar” cümlesi belge alamayanları verir; ikisinden birinin bozulması yeter.
Bunu “ve” ile yazarsan yalnızca ikisi birden bozuk olan
öğrencileri elemiş olursun — hepsini değil.
Kısa kural: “ve” daraltır, “veya” genişletir.
toplam = 0 satırı döngünün içine düşerse her turda sıfırlanır ve sonunda yalnızca son terim kalır. Başlangıç değerleri döngüye girmeden önce verilir. Aynı hatanın kardeşi: faktöriyelde çarpımı 0’dan başlatmak.
Koşul hiç bozulmuyorsa döngü sonsuza kadar döner. En sık iki sebebi: sayacı artırmayı unutmak, ya da azalan bir döngüde artış değerini pozitif yazmak (i = 10, 1, +1). Şemanı bitirdiğinde “bu koşul ne zaman yanlış olur” diye bir kez sor.
“Sınıftaki bazı öğrencilerin ortalaması 70’in üzerindedir” cümlesi bir kişi bulununca doğrulanır. “Tüm öğrenciler…” cümlesi ise ortalaması 68 olan tek bir Ömer’le çürür. Soruda niceleyiciyi değiştirip aynı sayıları vermek, en sevilen tuzaklardan biridir.
Ortalaması tam 85,00 olan öğrenci takdir belgesi alır (aralık “85,00 ve daha yukarı”). Devamsızlığı tam 5 gün olan belge alabilir (“en fazla 5”), 5,5 gün olan alamaz. “Küçüktür” ile “küçük eşittir” arasındaki fark bir öğrencinin belgesini götürür.
Ortalama alarak yinelemede yeni aralık, f(x₃)’ün işaretine bakılarak seçilir; f(x₃)’ün büyüklüğüne değil. f(x₃) ile f(x₁) aynı işaretliyse x₁ = x₃, zıt işaretliyse x₂ = x₃ olur. Yanlış tarafı atarsan kök aralığın dışında kalır ve yöntem hiçbir zaman yakınsamaz.
Soru her açılışta karışıyor, şıkların yeri de sabit değil. Yanlış cevap verdiğinde doğrusunu ve gerekçesini birlikte göreceksin.
Adımları sırayla yaptığın, bir yerde karar verip yol ayırdığın ve aynı işi tekrarladığın her durum bir algoritmadır. Farkı, yazılı olması.
“Alarm çaldı → hava yağmurlu mu? evetse şemsiye al, hayırsa alma → çantayı hazırla → çık.” Bu bir koşul sembolüdür. Şemsiyeyi unutmanın sebebi çoğu zaman koşulu hiç denetlememektir.
“i = 1, 12, 1 → i. üniteyi oku, yirmi soru çöz, yanlışları not et.” Bir döngü. Planın işlememe sebebi genelde bitiş değerinin gerçekçi olmaması: 12 ünite, günde bir ünite bile olsa iki hafta.
“Maça gidiyoruz ancak ve ancak hem Deniz hem Elif gelirse.” Bu ⇔ değil aslında ∧. Gerçek ⇔ şudur: “Deniz gelirse Elif de gelir, Elif gelirse Deniz de.” İkisi hep birlikte hareket eder.
8 kişilik turnuvada eşleşmeler kurayla belirleniyor. Kaç farklı sıralama var? 8! = 40 320. Bunu elle saymak imkânsız; faktöriyel döngüsü saniyeden kısa sürede hesaplar. Turnuva uygulamalarının içinde tam olarak bu döngü çalışır.
“Karıştır” düğmesi rastgele değil, bir algoritmadır: listeden bir şarkı seç, çal, listeden çıkar, liste boşalana kadar tekrarla. Aynı şarkının iki kez çalmaması, “çıkar” adımı sayesindedir.
“Ortalama ≥ 80 ve devamsızlık ≤ 10 ve disiplin cezası yok.” Üç koşul da “ve” ile bağlı. Başvurun reddedildiğinde hangi koşulda takıldığını bilmek istersin — iyi yazılmış sistemler sana ilk bozulan koşulu söyler.
“toplam = 0; her hafta: toplam = toplam + 150; toplam < 3000 olduğu sürece devam.” Kaç hafta sürer? Döngü 20 turda biter. Kaydırağı bu bölümde çektiğinde gördüğün şey tam olarak buydu: biriken toplam.
Arkadaşın 1–100 arası bir sayı tuttu, “büyük/küçük” diyerek yönlendiriyor. En iyi stratejin hep ortadan başlamak — bu, ortalama alarak yineleme yönteminin ta kendisi. 100 sayı, en fazla 7 tahminde biter.
Hesap makinesine √70 yazdığında ekranda anında 8,3666 çıkar. İşlemci bu sayıyı bir tablodan okumaz; Babil metodunun modern akrabası olan bir yinelemeyi birkaç tur çalıştırır. 4000 yıllık fikir hâlâ cebinde.
Algoritmik yapı testi · üç anlatım biçimi, yedi sembol, döngünün dört bilgisi, mantık bağlaçları ve niceleyiciler, belge dağıtma algoritması, ortalama alarak yineleme, Babil metodu ve faktöriyel/basamak sayısı algoritmaları
Algoritmik doğal dil — numaralı Türkçe adımlar
Sözde kod — dile bağlı olmayan kısa yazım
Akış şeması — şekiller ve oklar
Bir algoritmanın işleyişi birden fazla akış şemasıyla
ifade edilebilir.
Oval → BAŞLA / BİTİR
Paralelkenar → veri girişi
Dikdörtgen → işlem
Eşkenar dörtgen → koşul (iki çıkış)
Dalgalı taban → sonuç yazdır
Altıgen → döngü
Daire → birleştirici
i = a, N, b veya
i, a, N, b
i döngü değişkeni · a başlangıç · N bitiş · b artış-azalış
a < N ise artan, a > N ise
azalan döngü.
∧ ve — ikisi birden
∨ veya / ya da — en az biri
⇒ ise — koşul sağlanınca işlemi yap
⇔ ancak ve ancak — aynı anda doğru ya da aynı anda yanlış
∀ her/tüm · ∃ bazı/en az bir
Ortalama alarak yineleme: kök iki sayı arasındaysa
ortalamayı al, f(x₃)’ün işaretine göre yarısını at, tekrarla.
Babil metodu:
xn+1 = ½(xn + a/xn)
Tam kare yolu: √a ≈ (a + b) / (2√b), b en yakın tam kare
1 + 3 + … + 99 = 2500
√70: 8 → 8,375 → 8,3666
√123 ≈ 244/22 = 11,0909
2x − 6 = 0 kökü: 4 → 2,5 → 3,25 → 2,875 → 3
48 765 → 5 basamak · 5! = 120 · 8! = 40 320