Ay: Nisan 2021

Evet, hayır, bilmiyorum (Çözüm)

Soru

Cevabı evet ya da hayır olan sorularla sayıyı aradığımız bölgeyi her zaman ikiye bölebiliriz. Örneğin aralığın ortasındaki sayıyı seçip, tuttuğun sayı bu sayıdan büyük mi ya da küçük mi diye sorarsak cevaba göre aralığın bir yarısını hemen eleyebiliriz. Eüer üç cevaplı bir yöntem bulabilirsek bu aralığı eşit aralıklı üç bölgeye ayırabiliriz ve her cevapta bu üç bölgenin ikisini eleyebiliriz. Böylece aradığımız sayıyı daha çabuk, yani daha az denemede bulabiliriz.

Peki bilmiyorum cevabını nasıl elde edebiliriz? Bunu yapmanın yolu tabii ki soruyu sorarken bütün bilgileri vermemekten geçiyor. Bütün bilgileri vermeyeceğiz ama yine de elimizdeki aralığı üç eşit parçaya bölmeye çalışacağız. Soracağımız soruda bu bölmeyi bildirmemiz lazım ama bölümlerin birinin cevabı evet ya da hayır olmamalı.

Önce birle yüz arasındaki sayıları üç gruba ayıralım. Birden otuzüçe kadar, otuzdörtten altmışyediye kadar ve altmışsekizden yüze kadar diye. Şimdi bu aralıkların ortada olanını alalım, yani otuzdörtten altmışyediye kadar olanı. Bu aralık için bilmiyorum cevabını elde etmek isteyelim. Bu durumda bu aralıktan küçük aralık için evet, büyük aralık için de hayır cevabını isteyelim mesela. Bu cevaplar kolay: Örneğin tuttuğun sayı otuzdört ile altmışyedi aralığından küçük mü? Tuttuğu sayı bu aralıktan daha küçük aralıktaysa cevap evet ve daha büyük aralıkta ise cevap hayır olacak. Peki tuttuğu sayı bu aralıkta ise cevap ne olacak? Bu sorunun cevabı da bence hayır olacaktır, çünkü soruda hiçbir belirsizlik kullanmadık. O aralıktaki bir sayı da o aralıktan küçük değildir. Demek ki soruda aralıktan bir sayıya doğru gitmek daha iyi bir yöntem olabilir ama bu sayıyı soruda söylemememiz lazım.

O zaman oyunu tersine çevirelim ve şöyle bir soru soralım: Otuzdört ile altmışyedi arasında bir sayı tuttum. Senin tuttuğun sayı bu sayıdan küçük mü? Eğer tutulan sayı bu aralıktan daha küçük aralıktaysa cevap evet, daha büyük aralıktaysa da cevap hayır olacak. Eğer tutulan sayı bu aralıktaysa bu sefer otomatik bir hayır cevabı olmayacak. Evet cevabı da olmayacak. Mecburen bilmiyorum cevabı verilecek.

Buna benzer başka sorular da bulunabilir tabii ki.

Laz tamirci

Evde bir sürü jaluzi var ama bir tanesi sürekli bozuluyordu. Motorlu bir şey de değil. Bildiğimiz mekanik, elle çekilen bir halatı olan basit bir şey. Nedense hep bu bozuluyor ama. Sonunda kapının üzerindeki bölmeyi açtım ve sorun nerede diye bakayım dedim. Halat normalde sarılması gereken diskten çıkmış ve sıkışmış, böylece bütün jaluzinin hareketini de engellemiş.

Tabii ki düğümü çözmek kolay diye düşündüm ve sıkışan halatı çekiştirmeye başladım. Halatın aksın etrafında defalarca dolanmış olması işimi iyice zorlaştırıyordu. Ayrıca bütün işi tek elle yapmam gerekiyordu çünkü olay yerine sadece bir elim sığıyordu.

İlk gece aksa dolanmış düğüm sayısını dörde indirebildim. Ertesi gün, bu sefer kalanı hallederim diyordum ki düğüm sayısının yediye çıktığını gördüm. Anlaşılır gibi değildi. Öncelikle orada bir düğüm oluşmasına bile imkan veremezken düğümlerin sayısının durup dururken artması hiç de hayra alamet değildi. Ertesi gün devam ederim diye işi orada bıraktım.

Ertesi gün çocukların da yardımıyla düğüm sayısını biraz da azalttım ama halatın pozisyonu gördüğüm kadarıyla imkansız bir şekildeydi. Yanı normal sarılmış bir durumdan bu konuma nasıl gelmiş olabileceğini çözemiyordum. Bu sırada yanlı bir hareket sonucunda jaluzinin lamellerini sola doğru kaydırabildiğimi gördüm. Bu da çalışmak için daha çok alan demekti ve halatı biraz daha bollaştırdım, şimdi halatın oluşturduğu halkaları birbirlerinin içinden geçirebiliyordum ama hala bütün düğümü çözmenin yolunu bulamamıştım. Bu sırada jaluzinin aksını yine yanlışlıkla hareket ettirirken olduğu yerden çıktığını da farkettim. Bu sayede halatı dolandığı yerden komple çıkarabildim fakat aksı yerine takarken ne oldu bilmiyorum, diske giren kısım yerinden çıktı. Çıktığıyla da kalmadı kayboldu. Evet, nerede olduğunu bilmiyorum. Bir ihtimal duvardaki bir delikten aşağıya düştü.

Bütün bu yazıdan da fark edileceği üzere jaluzi ve parçaları hakkında hiçbir bilgim yok. Bu nedenle düşen parçanın adını da bilmiyorum. Bilsem internetten sipariş verebilirdim. Şimdi jaluzinin son halinin fotoğraflarını çekip dükkanları gezmekten başka pek şansım kalmadı. Parçalar pek pahalı gözükmüyor ama anladığım kadarıyla standard da değiller. En iyisi pandemi yüzünden sokağa çıkma yasakları başlamadan hemen yarın gidip şansımı deneyeyim.

Bad Character algoritması

Bu yazı ve algoritma dizisinde de metin arama algoritmalarından Boyer-Moore algoritmasını öğrenmeye çalışacağım. Diğer bazı metin arama algoritmalarında olduğu gibi bu algortimada da aranan metin her adımda tek adım kaydırılmıyor, aksine aranan metnin özelliğine göre kaydırma miktarları optimize ediliyor. Boyer-Moore algoritmasının şimdiye kadar öğrendiğim algoritmalara göre iki farklı özelliği var. Birincisi, aranan metin ve ana metin karşılaştırması sağdan sola doğru yapılıyor. İkincisi de kaydırma miktarını bulmak için iki değişik alt algoritma kullanılıyor. Bu yazıda bu iki algoritmadan biri olan Bad Character algoritmasını anlamaya çalışacağım.

Bu algoritma için aşağıdaki animasyonu programlamaya çalıştım.

Bad Character Rule

Bu animasyon başlatıldığında henüz hazırlanmamış bir tablo ve tablonun üzerinde seçilmiş bir aranan metin gösteriliyor. Tabloda normalde bir metinde olabilecek bütün karakterler olmalı (küçük harfler, büyük harfler, rakamlar vb.) ama sadece fikri gösterebilmek için tabloyu küçük tuttum. Animasyonda ana metni kullanmadım çünkü bu algoritma için ana metin değil aranan metne herhangi bir konumda uymayan bir karakter önemli. Bunu da aranan metnin üzerinde hesaplanacak konumda gösterilen bir karakterle göstermeye çalıştım.

Animasyonda aranan metin olarak

 NNAAMAN

dizisini kullandım. Her tablo seçilen aranan metne göre ayrı oluşturulması gerekiyor. Tabloyu şöyle düşünmeye çalıştım. Aranan metinde ana metni sağdan sola doğru karşılaştırdığımızda ana metindeki ilk uyumsuz karakteri en soldaki sütundan buluyoruz. Ardından bu uyumsuzluğun aranan metindeki hangi pozisyonda olduğunu da birinci satırdan okuyoruz. Algoritma bittiğinde bu tablo bize o karakter ve o konum için aranan metni sağa doğru kaç karakter kaydırabileceğimizi söyleyecek.

Bu tabloyu hazırlamak aslında çok kolay ama bu şekliyle tablo oldukça fazla yer tutmakta, çünkü olası her karakter için tabloda yer harcanıyor ama bu ilk versiyon için bu basit yöntemi anlamak yeterliydi benim için. Literatürde bu sorunla ilgili çeşitli çözümler var ve ileride onlara da bakabilirim.

Tablodan sırayla her satırdaki harf için olası her pozisyonu alıyorum ve bu harfi aranan metnin üzerinde o pozisyonda gösteriyorum. Eğer seçtiğim harfler aranan metindeki harf aynı ise tabloda bu noktaya “-” işareti koyuyorum, çünkü bu algoritma sadece uyumsuzluk varken kullanılıyor. Eğer uyumsuzluk varsa aranan metinde sola doğru harfleri tek tek kontrol ediyorum. Seçilen harfle aynı harfi ilk bulduğum konuma kadar aranan metni sağa doğru kaydırabilirim, çünkü aradaki her durumda bir uyumsuzluğun çıkacağı kesin. Eğer bir harfi uyumsuzluğun çıktığı konumdan sonra bir daha bulamazsam da aranan metni uyumsuzluktan bir sonraki konuma kadar kaydırabilirim. Bu şekilde her karakter ve konum için aranan metni ne kadar kaydırmam gerektiğini tabloya işliyorum. Bu şekilde bu basit algoritma da tabloyu oluşturmuş oluyor.