Adımları
yaz,
makine yapsın.
Algoritma, bir problemi çözmek ya da belirli bir görevi tamamlamak için izlenen açık ve anlaşılır şekilde belirlenmiş kural ve işlemlerin adım adım uygulanmasıdır. Aynı algoritma üç ayrı dilde yazılabilir: algoritmik doğal dil, akış şeması ve sözde kod. Bu ünitede üçünü de yazacak, birinden ötekine çevirecek ve döngü ile karar noktasının ne işe yaradığını göreceksin.
Yolculuk şöyle: algoritma terimi ünlü matematikçi Harizmi’nin adından türemiştir. Harizmi’nin eserleri XII. yüzyılda Latinceye “Algoritmi de numero Indorum” (Hint Sayıları Üzerine Algoritmalar) olarak çevrilmiş; XIII. yüzyılda kelime Arapçada “ondalık sistem” anlamı taşımış (0’dan 9’a kadar olan sayılar ve ondalık sistem kavramı); XIX. yüzyılda Fransızcada “algorithme” olarak yeniden şekillenmiş ve anlamı korunarak İngilizceye “algorithm” olarak geçmiştir.
Algoritma, bir problemi çözmek veya belirli bir görevi
tamamlamak için izlenen açık ve anlaşılır şekilde belirlenmiş kural ve işlemlerin adım adım
uygulanmasını ifade eder.
Tanımdaki iki kelime sınavda da hayatta da her şeyi belirler:
· açık — her adım tek bir anlama gelmeli, “biraz”, “yeterince”
gibi kelimeler algoritmada yer alamaz.
· adım adım — sıra bellidir; adımların yeri değişirse
algoritma değişir.
Bir de şu var: algoritmanın bitmesi gerekir. Sonsuza kadar
dönen bir işlem, problemi çözmediği için algoritma sayılmaz.
Algoritmik yaklaşım; algoritmaların geliştirilmesi,
değerlendirilmesi ve uygulanması için kullanılan kapsamlı bir problem çözme yöntemini
tanımlar. Bu yaklaşım bilgisayar bilimleri,
matematik, mühendislik, ekonomi gibi alanlarda yaygın olduğunu ve temel prensiplerinin
her türlü bilim dalında uygulanabildiğini söylüyor.
Algoritmada kullanılan verilerin düzenli ve anlamlı bir biçimde
gösterilmesine veri yapısı denir.
Nöbet örneğindeki günler listesi
(pazartesi, salı, …, pazar) bir veri yapısıdır: sıralı olduğu için “kaçıncı eleman”
sorusu anlamlıdır.
Algoritmik doğal dil, bir problemi çözme adımlarını günlük dili
kullanarak sıralı ve açık biçimde anlatan bir yöntemdir. Bu yöntem teknik detaylardan uzak,
herkesin anlayabileceği basit ifadelerle algoritmanın nasıl işlediğini gösterir.
Yani üç temsilin en okunaklı olanıdır; karşılığında da en
uzunudur. Kalıp hep aynı: 1. adım Başla,
sonra girdilerin alınması, işlem, koşulun kontrolü, sonucun yazdırılması ve en sonda
Bitir.
Akış şeması, bir problemi çözme adımlarının görsel temsilidir. İşlemleri, karar noktalarını (evet veya hayır) ve akış yönlerini çeşitli geometrik şekiller kullanarak gösterir. Her şeklin sabit bir anlamı vardır; şekli değiştirirsen anlamı da değişir. Aşağıdaki düğmelerle Tablo 5.1’deki altı sembolü tek tek gez.
2. örnek bir doğal sayının tek mi çift mi olduğunu iki
farklı akış şemasıyla buluyor:
· Akış Şeması I: koşul x % 2 = 0
→ “Evet” yolunda “Sayı çifttir”, “Hayır” yolunda
“Sayı tektir”.
· Akış Şeması II: koşul x % 2 = 1
→ “Evet” yolunda “Sayı tektir”, “Hayır” yolunda
“Sayı çifttir”.
Çıkarım: “x % 2 = 0” ve “x % 2 = 1” ifadeleri
birbirlerinin tamamlayıcısıdır. Biri doğruysa öteki yanlıştır.
75 için deneyelim. Şema I’de “75 % 2 = 0” yanlış olduğundan
“Hayır” yolu izlenir ve “Sayı tektir.” çıktısı alınır.
Şema II’de “75 % 2 = 1” doğru olduğundan “Evet” yolu izlenir ve
yine “Sayı tektir.” çıktısı alınır. Aynı sonuca, ters yollardan
gidilir.
Buradan çıkan kural: bir algoritmanın işleyişi bir veya daha fazla
akış şemasıyla ifade edilebilir. Sınavda “hangi şema doğru?” diye sorulmaz, “bu şema hangi
çıktıyı verir?” diye sorulur — Evet/Hayır etiketlerinin hangi kutuya
gittiğine bakmadan cevaplama.
Atama operatörleri, değişkenlere veya veri yapılarına değer atamak için kullanılan simgelerdir. Bir değişkene ilk değerini atamak, güncellemek veya bir hesaplama sonucunu belirlemek için kullanılır. Atama için “←” veya “=” sembolleri kullanılabilir. Örnekte A ← x · y yazıldığında A değişkenine x · y işleminin sonucu atanmıştır.
İki tabloyu yan yana koyunca gözden kaçan bir çakışma çıkar:
“=” hem atama hem karşılaştırma sembolü olarak geçiyor.
· alan = uzun · kısa → burada “=” atamadır;
soldaki kutuya sağdaki sonucu koy demektir.
· x % 2 = 0 ? → burada “=” karşılaştırmadır;
bir soru sorar, cevabı doğru ya da yanlıştır.
Hangisi olduğunu nerede durduğundan anlarsın: karar
baklavasının içindeyse karşılaştırma, işlem dikdörtgeninin içindeyse atamadır. Ders kitabının
“←” sembolünü tercih etmesinin sebebi tam olarak bu karışıklığı
önlemektir.
% operatörü, bir sayının diğerine bölümünden kalanı verir.
Bu ünitedeki örneklerin çoğu bu tek operatörün üstüne kurulu:
· x % 2 → tek mi çift mi (2. örnek)
· x % 10 → birler basamağı (3. örnek)
· (indeks + gün) % 7 → haftanın günü (6. örnek)
· abc % 100, % 10 → basamaklara ayırma
Neden bu kadar işe yarıyor? Çünkü kalan, bir sayıyı sonlu sayıda
kutuya yerleştirir: 2’ye bölünce iki kutu (0 ve 1), 7’ye bölünce yedi kutu (0’dan 6’ya).
Haftanın 7 günü, saatin 12 rakamı, bir yılın 4 mevsimi — hepsi
döngüsel olduğu için kalanla modellenir.
Söz dizimi, bir programlama dilindeki komutların, ifadelerin ve
veri yapılarının nasıl düzenlenmesi gerektiğini tanımlayan kurallar ve yapılar bütünüdür.
Programlama dili, bilgisayarların anlayabileceği ve
işleyebileceği talimatlar dizisini oluşturmak için kullanılan formel bir dildir.
Uyarı: her programlama dilinin kendine özgü bir söz dizimi
vardır. Programcılar, söz dizimleri yardımıyla algoritmaları kod hâline getirir. Söz dizimi doğru
kullanılmadığında program hatalı çalışır veya hiç çalışmaz.
Sözde kod; bir bilgisayar programının nasıl çalışacağını anlatan, insanların okuyup anlayabileceği, sade ve açıklayıcı bir dil kullanılarak yazılan bir dizi talimattır. Vurgu şu: sözde kod, gerçek bir programlama dilinin teknik detaylarını ve karmaşık söz dizimini kullanmaz. Yani noktalı virgül, süslü parantez, kütüphane adı yoktur; mantık vardır.
Girdi: Pozitif bir tam sayı x
Çıktı: x’in 5’e tam bölünüp bölünmediğine dair doğru ya da
yanlış şeklinde bir çıktı
Başla
b ← x % 10 (sayının birler basamağını bul)
b 0 veya 5 ise
Yazdır DOĞRU (x, 5’e tam bölünür.)
b 0 veya 5 değilse
Yazdır YANLIŞ (x, 5’e tam bölünmez.)
Bitir
Test: x = 47 için b = 47 % 10 = 7. 7 ≠ 5 ve 7 ≠ 0 olduğu için “Hayır” yolu izlenir: 47, 5’e tam bölünmez.
Girdi: ilk nöbet günü, nöbet aralığı, hedef nöbet
Çıktı: hedef nöbet günü
Başla
günler ← (pazartesi, salı, çarşamba, perşembe, cuma, cumartesi, pazar)
ilk nöbet indeksi ← [günler] in indeksini bul (ilk nöbet günü)
toplam gün ← (hedef nöbet − 1) * (nöbet aralığı)
hedef gün indeksi ← (ilk nöbet indeksi + toplam gün) % 7
hedef gün ← günler (hedef gün indeksi)
Yazdır …
Bitir
3 günde bir nöbet tutan, ilk nöbeti salı olan doktorun 9. nöbeti: toplam gün = (9 − 1) · 3 = 24; salının indeksi 2; 2 + 24 = 26; 26 = 7 · 3 + 5 ⇒ kalan 5; listenin soldan 5. elemanı cuma.
VKİ, bir kişinin kilosunun (kg) boyunun (m) karesine bölünmesiyle
hesaplanan bir değerdir ve kategoriler yardımıyla genel sağlık durumu hakkında bilgi sunar.
Tablo:
· VKİ ≤ 18,5 → Düşük kilolu
· 18,5 < VKİ ≤ 25 → Normal kilolu
· 25 < VKİ ≤ 30 → Fazla kilolu
· VKİ > 30 → Obezite
Akış şemasında bu, art arda dizilmiş üç karar baklavasıdır:
önce en küçük aralık sorulur, “Hayır” çıkarsa bir sonrakine geçilir. Aralıklar
üst üste binmediği için sıra önemli değildir ama
boşluk da bırakmadığı için her VKİ değeri mutlaka bir
kategoriye düşer.
Üç temsilde imla ve noktalama farklılıkları olmasını
açıkça gerekçelendiriyor: bu ifadelerin kullanımına ilişkin
kurallar yazı dili kurallarından farklıdır. Ayrıca sözde kodun “Yazdır” ile başlayan
satırlarında farklı bir yazım tercih edilmesinin nedeni
metin ile sayısal değeri ayırt etmektir.
Yazdır “Dikdörtgenin alanı”, alan, “birimkaredir.” satırında
tırnak içindekiler aynen basılır, tırnaksız alan
ise içindeki sayıyla değiştirilir. İkinci yazımda aynı iş köşeli
parantezle yapılıyor: “Dikdörtgenin alanı [alan] birimkaredir.”
Son söz: sözde kod yazımında kullanılan yazım tarzlarında
farklılıklar olabilir. Bu farklılıklar, kullanıcının yatkın olduğu programlama diline kolay geçiş
yapmasını sağlar.
Döngü, belirli koşullar sağlandığı sürece tekrar eden (yinelenen) işlemleri yürütmek için kullanılan yapıdır. Akış şemasında döngüyü tanımak kolaydır: bir ok geriye, daha önce geçtiğin bir kutuya döner. Aşağıda 1. örneğin adım adım çalışması var: 13’ün 3’e bölümünden kalanı tekrarlı çıkarmayla bulan algoritma.
Kullanıcı bölünen (a) ve bölen (b) için sırasıyla 13 ve
3 girmiştir. a’nın mevcut değerinden b çıkarılarak yeni bir a
hesaplanır; bu adım döngünün her yinelenişinde tekrarlanır ve
a sürekli azalır.
Yineleme 0: a = 13
Yineleme 1: 13 − 3 = 10
Yineleme 2: 10 − 3 = 7
Yineleme 3: 7 − 3 = 4
Yineleme 4: 4 − 3 = 1
a değeri 1 olduğunda 1 < 3 olduğundan yineleme durur ve
kalan a’ya eşit olur: kalan 1. Eklenen ayrıntı:
yineleme sayısı da bölümü verir — 4 yineleme yapıldı,
13 : 3 işleminin bölümü 4’tür.
Not: koşulun kontrol edildiği “a < b” ifadesi
“a ≥ b” şeklinde de gösterilebilir.
İkisi aynı şemayı verir ama Evet ve Hayır kolları yer
değiştirir:
· a < b ? → Evet: bitir · Hayır: döngüye geri dön
· a ≥ b ? → Evet: döngüye geri dön · Hayır: bitir
Bu, 2. örnekteki “x % 2 = 0” ile “x % 2 = 1” çiftinin aynısıdır:
bir koşulun değilini alırsan iki kolu takas etmen gerekir.
Sınavda en sık yapılan hata, koşulu ters çevirip kolları takas etmeyi unutmaktır — o zaman
algoritma tam ters çalışır ya da hiç durmaz.
Eratosthenes Kalburu, MÖ III. yüzyılda Antik Yunan matematikçisi
Eratosthenes tarafından geliştirilen bir algoritmadır. Belirli bir sayıya kadar olan tüm
asal sayıları bulmak için kullanılır ve bir sayının daha küçük asal sayıların katı olup
olmadığını kontrol ederek asallığını test eder.
1. adım: 2’den belirlenen bir n tam sayı değerine kadar ardışık
tam sayılardan bir liste oluşturun.
2. adım: Başlangıçta en küçük asal sayı olan 2’yi alın ve 2’nin
tüm katlarını (4, 6, 8, …) işaretleyin.
3. adım: İşaretlenmemiş bir sonraki sayıyı alın, örneğin 3 ve
tüm katlarını işaretleyin. Tüm sayılar işaretlenmişse veya bir sonraki işaretlenmemiş sayı
bulunamıyorsa durun.
4. adım: 3. adımı algoritma sonlanana kadar tekrarlayın.
Listede işaretlenmemiş olarak kalan sayılar, n tam sayısına kadar olan tüm asal sayılardır.
Deneme bölme algoritmasında ilk olarak asal çarpanlarına ayrılacak
sayının en küçük asal sayı olan 2 ile bölünebilirliğine bakılır. Sayı 2’ye
bölünebiliyorsa elde edilen bölümün 2 ile bölünebilirliğine bakılır; bu işleme iki ile kalanlı
bölme işlemi yapılıncaya kadar devam edilir. Ardından 3, 5, 7 gibi asal sayılarla bölme işlemine
devam edilir.
75 için tablo:
· Girdi alınır → x = 75, liste { }
· 2’ye tam bölünme → x = 75, liste { }
· y = 3 ile tam bölünme → x = 25, liste {3}
· y = 5 ile tam bölünme → x = 5, liste {3, 5}
· y = 7 ile tam bölünme → x = 5, liste {3, 5}
Durdurma ölçütü: bir sayının asal çarpanları bulunurken
sayının karekök değerine kadar olan asal sayılara bölünüp bölünmediğini kontrol etmek
yeterlidir. 11, 13, 17, … asal sayıları 75’in karekökünün yaklaşık
değeri olan 8,6’dan büyük olduğu için asal çarpanı olamaz. Sonuç: 75’in asal çarpanlar
listesi {3, 5}.
Kriptoloji, bilgileri koruma ve gizleme bilimidir. Sayıların
çarpanlara ayrılması bu alanda önemli bir yere sahiptir. Adını bulucuları
Ron Rivest, Adi Shamir ve Leonard Adleman’ın soy isimlerinin baş
harflerinden alan RSA şifreleme algoritması, büyük sayıların asal
çarpanlarına ayrılmasına dayanır.
Bütün fikir tek bir asimetride: bu algoritmada
iki asal sayının çarpımı kolayca hesaplanabilirken bir sayının asal
çarpanlarına ayrılması son derece zordur. Bir mesajın şifresini çözmek için gerekli özel
anahtar, bu büyük sayıları asal çarpanlarına ayırma işlemine bağlıdır; etkili bir asal çarpanlara
ayırma algoritması olmadan bu tür bir şifrelemeyi kırmak zordur.
Başlıca algoritmalar: deneme bölme algoritması,
Pollard’ın rho algoritması ve kuantum bilgisayarlar için geliştirilen
Shor algoritması.
Sorular karışık sırayla geliyor. Sembolü tanı, koşulu işlet, çıktıyı bul.
Algoritma yazmak için bilgisayara ihtiyacın yok. Aşağıdaki dokuz sahnede her gün, farkında olmadan çalıştırdığın algoritmalar var; bir kısmında döngü, bir kısmında karar noktası, bir kısmında ikisi de.
Telefonun ertele tuşu bir döngüdür: “çal → tuşa bas → 9 dakika
bekle → tekrar çal”. Döngünün durma koşulu senin “kapat”
demendir.
Durma koşulu olmayan bir döngü sonsuz döngüdür ve algoritma
sayılmaz. Bazı alarm uygulamaları erteleme sayısını sınırlar; bu, döngüye
ikinci bir durma koşulu eklemektir: “sayaç > 3 ise durma,
çalmaya devam et.”
1. örnekteki a ← a − b döngüsüyle aynı yapı: her
turda bir değer değişiyor, koşul her turda yeniden kontrol ediliyor.
68 TL’lik bir alışverişe 200 TL verdin, para üstü 132 TL.
Kantinci en az sayıda banknot vermek isterse şu algoritmayı çalıştırır:
kalan tutardan küçük ya da eşit en büyük banknotu seç, düş,
tekrarla.
132 → 100 ver, kalan 32 → 20
ver, kalan 12 → 10 ver, kalan 2 →
1 + 1. Toplam 5 parça.
Kasada 100 TL yoksa aynı döngü 50 + 50 + 20 + 10 + 1 + 1 verir;
algoritma değişmez, sadece veri (kasadaki banknotlar) değişir.
İyi bir algoritmanın işareti budur: girdi değişince kendini
bozmaz.
Sunuma 18 gün var ve 6 slayt hazırlayacaksın. “Günde kaç slayt?” sorusu bir
bölme, “Son slayt hangi güne denk gelir?” sorusu bir
kalan problemidir.
6. örnekteki nöbet algoritmasının aynısını kurabilirsin: bugün
salı ise ve 3 günde bir slayt yapacaksan, 6. slayt
(6 − 1) · 3 = 15 gün sonra;
(2 + 15) % 7 = 17 % 7 = 3 ⇒ listenin 3. günü
çarşamba.
Haftalık planlama yapan bütün uygulamalar bu tek satırı kullanır:
% 7.
Bahçede 14 kişi var, iki takıma ayrılacaksınız. Kaptanların sırayla seçmesi bir
döngüdür: “sıradaki kaptan bir kişi seçsin → seçilmeyenler
listesinden çıkar → liste boşalana kadar tekrarla.”
Kişi sayısı tek olduğunda algoritmanın bir
karar noktasına ihtiyacı olur: “n % 2 = 1 ise bir takım bir
kişi fazla olsun ya da kaleci ortak olsun”.
Algoritmanın her girdi için çalışması gerektiğini anlamanın en
hızlı yolu budur: 14 kişide sorun yokken 15 kişide takılıyorsa, algoritma değil
tarif yazmışsındır.
“Karıştır” düğmesi de bir algoritmadır ve iyi olanı şöyle çalışır:
son şarkıdan başla, rastgele bir öncekiyle yer değiştir, bir geri
git, tekrarla. Liste bittiğinde her sıralama eşit
olasılıkla çıkmış olur.
Kötü bir karıştırma “her şarkıya rastgele bir sayı ver, sırala” der; bu da
çalışır ama daha yavaştır.
Aynı problemi iki algoritma çözebilir ve ikisi de doğru
olabilir; aralarındaki fark verimliliktir. Bu, bir sonraki
ünitenin konusu.
Yemek tarifi ile algoritma arasındaki tek fark kesinliktir.
“Bir tutam tuz at” bir algoritma adımı değildir; “2 gram tuz ekle” adımdır.
Tarifte de karar noktası vardır: “kürdanı batır; temiz çıkıyorsa
fırından al, değilse 5 dakika daha bekle.” Bu tam olarak bir karar baklavasıdır ve
“değilse” kolu geriye döndüğü için döngüdür.
İyi yazılmış bir tarifi bir başkası aynen uygulayıp aynı sonucu alabiliyorsa, o tarif
algoritma olmuştur.
Alfabetik bir sınıf listesinde “Zeynep”i ararken listeyi baştan taramazsın,
sondan açarsın. Bu, sıralı veri üzerinde çalışan bir arama
algoritmasıdır.
Aynı listede sıralama bozuk olsaydı sondan açmanın hiçbir
faydası olmazdı; baştan sona bakman gerekirdi.
Ders: algoritmanın hızı, verinin nasıl düzenlendiğine bağlıdır.
“Veri yapısı” tanımı tam da bunun içindir.
Bir siteye kayıt olurken “en az 8 karakter, bir büyük harf, bir rakam” uyarısını veren şey
küçük bir algoritmadır: üç koşulu da kontrol et, hepsi
sağlanıyorsa kabul et.
Bu, üç karar baklavasının art arda dizilmesidir; herhangi
birinden “Hayır” çıkarsa kayıt reddedilir.
Şifrenin kendisi asla sitede saklanmaz; sayısal bir işlemden
geçirilip özeti saklanır. Bir sonraki ünitede bu özetin
arkasındaki sayı sistemini ve ASCII’yi göreceksin.
Ücretlendirme sistemleri, VKİ örneğiyle aynı yapıdadır:
art arda dizilmiş aralık kontrolleri.
“Aktarma süresi ≤ 45 dakika ise indirimli, değilse tam ücret” bir karar noktasıdır. Sınırın
hangi tarafa dâhil olduğu (≤ mi, < mi) tam 45. dakikada
bindiğinde para farkı yaratır.
VKİ tablosunda da aynı özen vardır: aralıklar 18,5 < VKİ ≤ 25
diye yazılmıştır; bir uç açık, bir uç kapalı. Sınırdaki değerin nereye gittiğini
operatör söyler.
48 soruluk test · algoritmanın tanımı ve kökeni, algoritmik doğal dil, akış şeması sembolleri, atama ve karşılaştırma operatörleri, sözde kod, döngü, kalan bulma, tek-çift ve 5’e bölünme testleri, Eratosthenes Kalburu, deneme bölme ve RSA
Bir problemi çözmek veya belirli bir görevi tamamlamak için izlenen
açık ve anlaşılır kural ve işlemlerin
adım adım uygulanması.
Adı Harizmi’den gelir.
Algoritmik doğal dil: günlük dille, sıralı ve açık.
Akış şeması: adımların görsel temsili.
Sözde kod: koda benzer ama söz dizimi yok.
Oval → başlangıç/bitiş
Paralelkenar → veri girişi/çıktı
Dikdörtgen → işlem
Baklava → karar noktası
Ok → akış yönü
Yazdırma şekli → sonucun yazdırılması
Atama: ← veya =
Karşılaştırma: < > <= >= = !=
Aritmetik: + − * / ^ %
% kalanı verir.
Belirli koşullar sağlandığı sürece tekrar eden (yinelenen)
işlemleri yürütmek için kullanılan yapı.
Şemada işareti: geriye dönen ok.
13 → 10 → 7 → 4 → 1
Kalan 1, yineleme sayısı 4 ⇒
bölüm 4.
“a < b” yerine “a ≥ b” yazılırsa kollar takas olur.
x % 2 = 0 ⇒ çift, x % 2 = 1 ⇒ tek;
ikisi birbirinin tamamlayıcısıdır.
b = x % 10 birler basamağıdır; b = 0 veya 5 ise sayı 5’e tam
bölünür. 47 → b = 7 ⇒ bölünmez.
2’den n’ye listeyi yaz, işaretlenmemiş ilk sayıyı al ve tüm
katlarını işaretle, tekrarla.
Kalanlar asal sayılardır. 100’e kadar
25 asal vardır.
Asal çarpan ararken karekökten büyük asallara bakmak
gereksizdir (75 için sınır ≈ 8,6).
RSA (Rivest, Shamir, Adleman) tam olarak bu işin
zorluğuna dayanır.