9. Sınıf Matematik · 5. Ünite: Algoritma ve Bilişim
Şifreleme, Çizge ve Arama Algoritmaları
Telefonuna yazdığın mesaj bilgisayar için yalnızca 0 ve 1 dizisidir. Haritada iki adres arasındaki en kısa yol, bir arkadaş ağındaki bağlantılar ya da bir sayıyı en az soruyla tahmin etme oyunu da aynı düşünce biçimiyle çözülür: problemi uygun bir gösterime çevirip adım adım algoritma uygulamak. Bu konuda metni ve sayıları ikili sisteme dönüştüreceksin, düğüm ve ayrıtlarla çizgeler üzerinde yol bulacak, farklı kütleli parayı en az tartımla ve bir sayıyı en az evet/hayır sorusuyla bulacaksın.
Kazanımlar
- MAT.9.5.1.a. Metni harf numaralarına, numaraları ikili sisteme çeviren şifreleme adımlarını (girdi, işlem, çıktı) belirler.
- MAT.9.5.1.b. Bir doğal sayıyı ikili sistemde yazar; ikili yazılmış sayıyı doğal sayıya çevirir; $n$ bit ile kaç farklı kod yazılabileceğini bulur.
- MAT.9.5.1.c. Şifreli (ikili) bir mesajı çözerek metne dönüştürür ve çözme adımlarını algoritma olarak ifade eder.
- MAT.9.5.1.ç. Bir problem durumunu düğüm ve ayrıtlarla gösterir; iki düğüm arasındaki en az ayrıtlı yolu katman katman tarayarak bulur.
- MAT.9.5.1.d-f. Farklı kütleli parayı en az tartımla bulma ve evet/hayır soruları ile sayı bulma stratejilerini kurar, uygular ve kontrol eder.
- MAT.9.5.1.g-h. Aday sayısını her adımda en çok bölen stratejinin tek tek denemeden neden daha az adım gerektirdiğini değerlendirir.
Konu anlatımı
1. Şifreleme: metni sayıya, sayıyı ikiliye çevirmek
2. Kaç bit gerekir? Kodu çözmek
3. Çizge: düğümler ve ayrıtlar
4. En az ayrıtlı yolu bulma algoritması
5. Arama problemi 1: Farklı kütleli parayı en az tartımla bulma
6. Arama problemi 2: Evet/hayır soruları ile sayı bulma
7. Strateji değerlendirme ve sık yapılan hatalar
Anahtar terimler
- Şifreleme (ikili kodlama)
- Metni harf numaralarına, numaraları ikili sistemde kodlara çevirme işlemi; çözme bunun tersidir.
- İkili sistem
- 2 tabanında sayı yazımı; basamak değerleri 1, 2, 4, 8, 16, … ve rakamlar yalnızca 0 ile 1.
- Bit
- İkili kodun bir basamağı; 0 ya da 1 değerini alır.
- n bitlik kod
- 2ⁿ farklı kod yazılabilen n basamaklı ikili dizi.
- Çizge
- Düğümler ve onları birleştiren ayrıtlardan oluşan gösterim.
- Düğüm ve ayrıt
- Düğüm çizgedeki nokta, ayrıt iki düğümü birleştiren çizgidir.
- Yol
- Ardışık ayrıtlarla bir düğümden başka bir düğüme gidiş; uzunluğu ayrıt sayısıdır.
- En az ayrıtlı yol
- İki düğüm arasındaki en az sayıda ayrıt kullanan yol; komşuları katman katman tarayarak bulunur.
- Hafif parayı bulma
- Terazinin üç sonuçlu tartımıyla adayları üçe bölerek en az tartımda sahte parayı bulma stratejisi.
- Evet/hayır ile sayı bulma
- Aralığı her soruda yarıya bölerek en az soruyla tutulan sayıyı bulma stratejisi.
Örnek soru
Türk alfabesinin 29 harfi A = 1, B = 2, C = 3, Ç = 4, … sırasıyla numaralanıyor ve her numara 5 bitlik ikili kodla yazılıyor. S harfinin numarası 22 olduğuna göre S harfinin kodu aşağıdakilerden hangisidir?
- 10101
- 10110
- 11010
- 01101
- 10011
Doğru cevap: B
Çözüm
1. 22'yi 2'ye bölerek kalanları yazalım: $22 \div 2 = 11$ kalan 0; $11 \div 2 = 5$ kalan 1; $5 \div 2 = 2$ kalan 1; $2 \div 2 = 1$ kalan 0; $1 \div 2 = 0$ kalan 1.
2. Kalanları sondan başa okuruz: 1, 0, 1, 1, 0 → $10110_2$.
3. Kontrol: $16 + 4 + 2 = 22$.
Doğru cevap: B. 01101, kalanları baştan sona (ters sırada) okumanın sonucudur ve 13'ü gösterir; 10101 ise 21'dir.