Bilgisayar Tasarımında Mantıksal ve Kombinatoryal Problemler
Robert McNaughton
Stanford University
Applied Mathematics and Statistics Laboratory
Stanford, Calif.
Büyük ölçekli sayısal bilgisayarlar ve benzeri aygıtlar üzerinde çalışan mühendisler, giderek artan biçimde mantıksal ya da kombinatoryal nitelikte zor problemlerle karşı karşıya kalmaktadır. Bu güçlükler çoğunlukla, belirli malzemelerden oluşan ve kesin olarak tanımlanmış bir amaç için kurulan bir devreyi en aza indirmeye çalışıldığında ortaya çıkar. Bu problemlerin varlığı ve akademik ilgiyi artırma potansiyeli, bilgisayar mantığı alanının genç ve büyüyen bir alan olmasını haklı kılmaktadır. Mantıkçı ve saf matematikçi bu tür problemleri çözebilir ya da çözemeyebilir; ancak her durumda, bunların ne tür problemler olduğunu bilmekle ilgileneceklerdir.
Bu boşluğu kapatmak amacıyla, bu mühendislik problemlerinden bazılarıyla doğrudan ya da dolaylı olarak karşılaşmış olabilecek kişilere başvurmaya karar verdik. Problemler toplamayı arzu ediyoruz. Bu problemlerin büyük bir bölümünü topladıktan sonra, bilgisayar mantığı alanına ilgiyi artırma girişimi olarak, çözümsüz bir rapor halinde yayımlayabiliriz.
Okuyucularınızdan herhangi biri problem sağlamaya ilgi duyarsa, toplamayı hedeflediğim bilgisayar mantığı problemine ilişkin bir fikir vermek isterim. Bu, bilgisayar devreleri ya da benzer şekilde kurulmuş diğer devrelerle ilişkili, mantıksal nitelikte, matematiksel olarak kesin bir problemdir. Bu tanım bazı açıklamalar gerektirir.
(1) Matematiksel Kesinlik
Problem, “gerçek dünya” ile özünde ilişkili olan hiçbir kavram içermeden, soyut olarak formüle edilmelidir. Örneğin, şu problemi ele alalım: yükselteçler, teller, diyotlar, dirençler ve sabit bir gerilim kaynağı ile toprak kullanarak iki adet 16 basamaklı ikili sayının toplanmasını sağlayan mümkün olan en ucuz devreyi kurun. Bu problem, yükselteçler, doğrultucular vb. öğelere atıf içerir; bunlar açıkça soyut matematiksel varlıklar değildir. Bu problemi çözmek için, bir mühendisin bildiği her şeyi bilmek gerekirdi; örneğin dirençlerin nasıl kullanılacağını ve yükselteçlerin doğrultuculara göre göreli maliyetlerinin ne olduğunu.
(2) Mantıksal Nitelik
Bilgisayar devreleri son zamanlarda mantıksal problemlere yol açmıştır; çünkü bilgisayar devresinin herhangi bir parçasının herhangi bir anda iki durumdan birini alabileceğini varsaymak uygundur (örneğin kapalı veya açık, açık veya kapalı, yüksek potansiyel veya düşük potansiyel). Bunlar, doğruluk ve yanlışlık olan iki doğruluk değeri, ya da 0 ve 1 sayıları, ya da Boole evren kümesi ve boş küme gibi kabul edilerek verimli bir şekilde ele alınabilir. Bu varsayımın yapılabildiği bir devreyle ilgili herhangi bir problem, problem başka açılardan mantık kategorisine hiç uymuyor gibi görünse bile, mantıksal bir nitelik taşır. Devrelerle bağlantılı, mantıksal olmayan bir probleme örnek, değişken dirençler ve akımlarla ilgili herhangi bir problemdir. Çok değerli mantıkla bağlantılı problemlerin dışlanması amaçlanmamaktadır.
(3) Problemlerin Kaynağı
Bu problemlerin bilgisayarlardan elde edilmesi zorunlu değildir. Telefon anahtarlama devreleri, mantıksal problemlerin bir kaynağı olarak iyi bir örnek sunar.
İstenilen biçimde formüle edilmiş bir bilgisayar mantığı problemine bir örnek aşağıdaki gibidir. Aşağıdaki koşullara bağlı olarak, en az sayıda kontağa (yani anahtara) sahip tellerle bağlanmış, tek kutuplu çift konumlu anahtarlardan oluşan iki terminalli bir kontak devresi yapılacaktır:
- Her biri herhangi bir anda 1 veya 0 olan n adet giriş değişkeni vardır, (s_1, \ldots, s_n).
- Her anahtar, bu (s_i) değişkenlerinden birine öyle bir şekilde bağlanmıştır ki, (s_i) 1 ise bir yönde, (s_i) 0 ise diğer yönde kapalı olur.
- İki terminal, girişler (s_1, \ldots, s_n) üzerindeki belirli koşullar altında devre tarafından bağlanacak, kalan koşullar altında ise bağlanmayacaktır.
Dikkat edilirse, problem mantıksaldır; çünkü değişkenler ya 0 ya da 1’dir, bir anahtar iki yönden birinde kapalıdır ve iki terminal ya devre tarafından bağlanmıştır ya da bağlanmamıştır.
(devamı sayfa 31’de)
MANTIKSAL PROBLEMLER (sayfa 30’dan devam)
çift konumlu anahtarlar ve teller gibi unsurlar kullanılsa da, problem soyut bir yorumlamaya sahip olacak şekilde formüle edilmiştir. Problemi çözmek için, değişkenlerin anahtarları nasıl kontrol ettiğini ya da ne tür bir tel kullanılması gerektiğini bilmek gerekmez vb. Ayrıca, ne kadar tel ve çift konumlu anahtarın ne kadara mal olduğunu bilmek de gerekli değildir; kişiye yalnızca kontak sayısını en aza indirmesi söylenir. Devrenin maliyeti burada kontak sayısı olarak tanımlanmıştır ve bu noktadan sonra problem, karmaşık mühendislik değerlendirmeleri bu tanıma yol açmış olsa bile, matematiksel olarak kesin bir hâl alır.
(Elbette bundan daha genel problemler de vardır; örneğin ikiden fazla terminalin bulunabileceği durumlar gibi.)
Okuyucularınızdan herhangi birinin tam olarak matematiksel açıdan kesin olmayan bir problemi varsa, yine de lütfen gönderin; çünkü burada bunun, her biri matematiksel olarak kesin olan, belki de birden fazla probleme dönüştürülmesi mümkün olabilir. İstenilen biçimde formüle edilmiş bir problemin ölçütlerini yalnızca ilgilendiğimiz problem türüne dair bir fikir vermek amacıyla ana hatlarıyla belirttim.
—E. F.