Algoritma Nedir? Girdi, Karar ve Döngülerle Problem Çözme

Bir algoritmayı başlatan üç soru: Girdi, işlem ve çıktı

Birçok problemi açıklamak için algoritma girdi, işlem ve çıktı bileşenleriyle incelenebilir. Bu bileşenler probleme göre değişebilir:

• Girdi: Algoritmanın başlangıçta aldığı veri veya veriler. Örneğin bir sayı listesi, kontrol edilecek $n$ sayısı ya da öğrencinin notudur.
• İşlem: Girdiye uygulanan karşılaştırma, toplama, bölme, sıralama veya karar adımlarıdır.
• Çıktı: İşlemler tamamlandıktan sonra elde edilen sonuçtur. Bu sonuç bir sayı, bir liste veya "asal değildir" gibi bir karar olabilir.

Bu ayrım, algoritmanın eksik kurulmasını önler. Örneğin "en büyük sayıyı bul" ifadesi tek başına yeterli değildir. Hangi sayılar arasında arama yapılacağı girdi, karşılaştırma yöntemi işlem, bulunan en büyük değer ise çıktıdır.

Bir algoritmanın adımları mantıksal sırada olmalıdır. Ayrıca hedeflenen geçerli girdiler için sonlu sayıda adımda tamamlanması, her adımın açık ve uygulanabilir olması beklenir. Bir adımın "gerekirse sayıları karşılaştır" biçiminde bırakılması belirsizlik oluşturur; hangi sayıların, hangi koşulda ve hangi sırayla karşılaştırılacağı yazılmalıdır.

Bir büyüklüğü tanımlamak da tek başına yeterli değildir. Örneğin bir algoritmada "en büyük" adlı değişken tutuluyorsa, her yeni değer bu değişkenle karşılaştırılır. Yeni değer daha büyükse değişken güncellenir; değilse mevcut değer korunur. Böylece değişkenin hangi kurala göre değiştiği anlaşılır.

Sıralı adımların içine karar ve tekrar yerleştirmek

Algoritmalar yalnızca düz bir işlem sırası değildir. Problem gerektirdiğinde iki temel yapı kullanılır:

Karar yapısı: Bir koşulun doğru veya yanlış olmasına göre farklı yol izlenir. Örneğin "Eğer $n<2$ ise asal değildir sonucunu ver" bir karardır. Burada eşitsizlik sağlanıyorsa algoritma bir yoldan, sağlanmıyorsa başka bir yoldan ilerler.

Tekrar yapısı: Bir veya daha fazla işlemin belirli bir koşula ya da yineleme sayısına bağlı olarak tekrar çalıştırılmasıdır. Bir listedeki tüm değerleri kontrol etmek için listedeki her eleman sırayla incelenir. Sayaç, tekrarın hangi konumda olduğunu takip etmek için kullanılabilir. Sayaç her adımda artırılır ve belirlenen sınır aşıldığında döngü sonlandırılır.

Bir döngünün güvenilir olması için üç nokta açıkça belirtilmelidir: başlangıç değeri, her turda yapılan değişiklik ve bitiş koşulu. Örneğin sayaç $1$'den başlar; sayaç $10$'dan küçük veya eşit olduğu sürece işlem yapılır, ardından sayaç $1$ artırılır. Sayaç değişmiyorsa veya bitiş koşuluna ulaşamıyorsa algoritma hedeflenen geçerli girdi için sonlanmayabilir.

Karar ile tekrar birlikte de kullanılabilir. En büyük değeri bulma işleminde her yeni eleman döngüyle incelenir; her eleman için "yeni değer mevcut en büyükten büyük mü?" kararı verilir. Bu iki yapı, birçok algoritmik problemde çözümün ana iskeletini oluşturur.

Liste içinden en büyük değeri bulma mantığı

Bir listedeki en büyük değeri bulmak için başlangıçta listenin ilk elemanı geçici olarak en büyük kabul edilir. Bu seçim önemlidir; çünkü henüz hiçbir karşılaştırma yapılmadan rastgele bir sayı seçmek yanlış sonuç verebilir.

Daha sonra listedeki sonraki elemanlar sırayla kontrol edilir. Her eleman için şu karar uygulanır: Yeni değer, mevcut en büyük değerden büyükse en büyük değişkeni güncelle; değilse değiştirme. Liste bittiğinde değişkende kalan değer, incelenen listenin en büyük elemanıdır.

Bu yöntemde algoritmanın çıktısı yalnızca son değerdir; ara aşamalardaki güncellemeler ise çözümün nasıl ilerlediğini gösterir. Örneğin $[8, 3, 11, 6]$ listesinde başlangıçta en büyük $8$ seçilir. $3$, $8$'den büyük olmadığı için değer değişmez. $11$, $8$'den büyük olduğu için yeni en büyük değer olur. $6$, $11$'den büyük değildir. Sonuç $11$'dir.

Sınır durumu da dikkate alınmalıdır: Liste boşsa ilk elemanı seçme adımı uygulanamaz. Bu nedenle algoritmanın girdisinin en az bir eleman içerdiği belirtilmeli veya boş liste için ayrıca bir çıktı tanımlanmalıdır. Bu, algoritma yazarken girdinin koşullarını belirtmenin neden gerekli olduğunu gösterir.

Asallık kontrolünde eşik koşullarını doğru kurmak

Asal sayı, $1$ ve kendisi dışında pozitif böleni bulunmayan, $1$'den büyük pozitif tam sayıdır. Bu tanımda iki sınır özellikle önemlidir: $1$ asal değildir; $n<2$ olan sayılar da bu algoritmanın asal kabul ettiği kümenin dışındadır.

Bir sayının asal olup olmadığını kontrol etmek için önce $n<2$ koşulu incelenir. Koşul doğruysa sonuç doğrudan "asal değildir" olur. Değilse $k=2$ başlanır ve $k$'nin $n$'yi bölüp bölmediği kontrol edilir. Bölünüyorsa $n$, 1 ve kendisi dışında bir bölen bulduğu için asal değildir. Bölünmüyorsa sayaç $1$ artırılır ve kontrol, belirlenen sınır içinde sürdürülür.

Bu algoritmada karar kuralı "bölünüyor mu?" sorusudur. Döngü bitene kadar hiçbir uygun bölen bulunmazsa sonuç "asaldır" biçiminde verilir. Buradaki "uygun" ifadesi, algoritmada kontrol edilmesi tanımlanan değerleri anlatır; döngünün hangi değerde sona ereceği açıkça yazılmalıdır.

Örneğin $n=7$ için $k=2,3,4,5,6$ değerleri kontrol edilebilir. Bu değerlerin hiçbiri 7'yi bölmediği için algoritma 7'nin asal olduğunu bildirir. Buna karşılık $n=9$ için $k=2$ başarısız olur, $k=3$ olduğunda 9'un 3'e bölündüğü görülür ve sonuç asal değildir. Böylece algoritma hem tekrar hem de erken sonuçlandıran karar yapısını içerir.

Algoritmanın doğruluğunu test etmek: tek örnekle yetinmemek

Bir algoritmanın doğru olduğunu değerlendirmek için yalnızca beklenen sonucu veren bir örneğe bakmak yeterli değildir. Farklı türde girdiler seçilmelidir. En azından normal bir örnek, sınır değeri ve kararın iki farklı sonucunu veren örnek denenmelidir.

Asallık algoritması için $7$ normal bir örnek, $1$ sınır durum, $9$ ise bölünebilir bir örnek olabilir. $1$ üzerinde ilk koşulun çalışıp "asal değildir" sonucunu vermesi gerekir. $9$ üzerinde döngünün uygun böleni bulduğunda gereksiz kontrolleri sürdürmeden bitmesi beklenir.

En büyük değeri bulma algoritmasında da listenin ilk elemanının en büyük olması, en büyük değerin son eleman olması ve negatif değerlerin bulunması gibi durumlar kontrol edilebilir. Örneğin $[-4,-2,-9]$ listesinde başlangıç değerinin ilk eleman alınması, karşılaştırmalar sonunda $-2$ sonucuna ulaşılmasını sağlar. Bu örnek, "en büyük" kavramının sayısal olarak en yüksek değeri ifade ettiğini; tüm değerlerin pozitif olmasının gerekmediğini gösterir.

Test sırasında şu sorular sorulmalıdır: Her girdi için bir çıktı tanımlı mı? Her adım uygulanabilir mi? Döngü sonlanıyor mu? Karar koşulu yanlış yönde kurulmuş olabilir mi? Algoritmanın adımları bu sorulara cevap verecek açıklıkta değilse, çözüm henüz tamamlanmış sayılmaz.

Çözümlü örnekler: yazılı bir problemi algoritmaya dönüştürme

Örnek 1 — Bir listedeki en büyük değeri bulma

Verilenler: $[8,3,11,6]$ listesi.

İstenen: Listedeki en büyük değeri bulmak.

Çözüm adımları:

1. Girdi listesinin ilk elemanını geçici en büyük değer seç: en büyük $=8$.
2. İkinci elemanı kontrol et: $3>8$ yanlış, bu yüzden en büyük değişmez.
3. Üçüncü elemanı kontrol et: $11>8$ doğru, bu yüzden en büyük $=11$ yapılır.
4. Dördüncü elemanı kontrol et: $6>11$ yanlış, değişiklik yapılmaz.
5. Liste bittiği için mevcut en büyük değeri çıktı olarak ver.

Sonuç: En büyük değer $11$'dir.

Bu çözümde girdi liste, çıktı $11$, tekrar yapısı listedeki elemanları sırayla inceleme, karar yapısı ise her eleman için yapılan büyüklük karşılaştırmasıdır.

Örnek 2 — 9 sayısının asal olup olmadığını kontrol etme

Verilen: $n=9$.

İstenen: 9'un asal olup olmadığını belirlemek.

Çözüm adımları:

1. $n<2$ kontrol edilir. $9<2$ yanlış olduğu için devam edilir.
2. $k=2$ seçilir.
3. 9'un 2'ye bölünüp bölünmediği kontrol edilir. Bölünmediği için $k=3$ yapılır.
4. 9'un 3'e bölündüğü görülür.
5. 1 ve kendisi dışında bir bölen bulunduğundan sonuç "asal değildir" olarak verilir.

Sonuç: 9 asal değildir.

Bu örnekte algoritma, tüm olası kontrolleri tamamlamadan da doğru sonuca ulaşabilir; çünkü asal olmadığını göstermek için uygun bir bölen bulmak yeterlidir. Buna karşılık asal sonucuna ulaşmak için algoritmada belirlenen kontrol aralığının tamamlanması gerekir.