Çıkarıcı (matematik) - Extractor (mathematics)

Bir -ekstraktör bir iki parçalı grafik ile soldaki düğümler ve sağdaki düğümler öyle ki soldaki her düğümde komşular (sağda), herhangi bir alt küme için ek özelliğe sahiptir en az boyuttaki sol köşelerin , sağ köşelerde rastgele bir düğüm seçilerek elde edilen dağılım ve sonra rasgele kenar sağ tarafta bir x düğümü elde etmek -a yakın üniforma dağıtımı açısından toplam varyasyon mesafesi.

Bir dağıtıcı ilgili bir grafiktir.

Bir çıkarıcıyı görüntülemenin eşdeğer bir yolu, iki değişkenli bir işlevdir

doğal bir şekilde. Bu bakış açısıyla, çıkarıcı özelliğinin şuna eşdeğer olduğu ortaya çıkıyor: herhangi bir rastlantısallık kaynağı için bu verir bitler ile min-entropi , dağıtım dır-dir -yakın , nerede tekdüze dağılımı gösterir .

Ekstraktörler, küçük parçalarla yapılabildiklerinde ilginçtir. göre ve yakın (giriş kaynaklarındaki toplam rastgelelik) mümkün olduğunca.

Çıkarıcı işlevleri başlangıçta bir yol olarak araştırıldı Ayıkla rastgelelik zayıf rasgele kaynaklardan. Görmek rastgelelik çıkarıcı.

Kullanmak olasılık yöntemi gerçekten iyi parametrelere sahip çıkarıcı grafiklerin var olduğunu göstermek kolaydır. Buradaki zorluk, açık veya net bulmaktır. polinom zamanı iyi parametrelere sahip bu tür grafiklerin hesaplanabilir örnekleri. Çıkarıcı (ve dağıtıcı) grafiklerini hesaplayan algoritmalar, bilgisayar Bilimi.

Referanslar