Yazan: Şadi Evren ŞEKER

Bilgisayar bilimlerinde, karmaşıklık teoremi (complexity theory) ve kuantum işleme (quantum computing) gibi konularda sıkça geçen bir problemdir.

Problem basitçe, bir fonksiyonun 1’e 1 veya n’e 1 olup olmadığını sorgular.

Örneğin f: {1 … n } à { 1 … n } bir fonksiyon olsun. Yani n sayıdan n sayıya tanımlı bir fonksiyon. Bu fonksiyonun örneğin 2’ye 1 olduğunu anlayabilmek için, en kötü ihtimalle, n/2 +1 elemanın sınanması gerekir. Şayet fonksiyon 2’ye bir fonksiyon değilse n/2+1 denemenin sonunda hep farklı sonuçlar çıkacaktır. Şayet fonksiyon 2’ye 1 fonksiyonsa ve şanslıysak, 2. denemede iki farklı sayı için aynı sonucu bulur ve fonksiyonun 1’e 1 olmadığını söyleyebiliriz, ancak şanssızsak n/2+1 deneme yapmamız gerekir.

Benzer problem, 3’e 1 olduğunun sınanması için n/3 +1 deneme gerektirir ve r’ye 1 için n/r +1 deneme gerekir.

Bu problem güvercin yuvası problemi (pigeon hole principle) olarak da ele alınabilir.

Tagged:

Yorumlar

  1. mehmet

    hocam merhaba,birşey sormak istiyorum ben c veya c++ ile bir sınav programı yapacagım alttan ve bir üsten ders alabilecek sekilde,derslerin cakısmadıgı,acaba nasıl bir yol izleyebilirim ,hangi yontemleri kullanabilirim,yardımcı olursanız sevinirim,tesekkürler

mehmet için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir