Dedikodu (Toplam değiştirme, çoğa çok) Problemi

396

Başlıkta belirttiğim gibi 3 değişik ad ile tanınan bu problemin konusu, n sayıda insanın her biri 1 adet bilgiye sahip olduğu bilinip kaç adet konuşma ile bütün insanların mevcut bilgilere sahip olabileceğidir. n adet insan olduğu için n adet te bilgi olacaktır.

İnsanlar=A,B,C,….N gibi büyük harfler ile temsil edilsin

Bilgiler=a,b,c,….n gibi küçük harfler ile gösterilsin.

Bu problemde bir konuşma esnasında iki taraf ta birbirine bilgi aktarımı yapacağı için yönsüz graf problemi olarak ele alınacaktır. İnsanlar ile sahip oldukları bilgileri de küme olarak gösterirsek A{a}, B{b}, C{c},… şeklinde devam eden bir dizi insan-bilgi ilişkisi üzerine kurulu küme elde ederiz. Basitten karmaşığa doğru problemin çözümünü inceleyelim.

Öncelikle 1 insan olduğunu düşünürsek hiç konuşma olmayacaktır. En az 2 insan olmak durumundadır.

2 insan durumu

2 insanı basitçe A{a} ve B{b} olarak gösterelim.

A ve B insanları bir telefon görüşmesinde sahip oldukları bilgileri birbirleriyle paylaşır ve telefon görüşmesi sonunda küme durumlarımız A{a,b} ve B{b,a} şeklinde güncellenir. Bu durumda 2 insan da bütün bilgilere eriştiği için problem 1 görüşmede çözülmüş olur.

3 insan durumu

3 insanın küme durumları A{a}, B{b} ve C{c} şeklinde gösterilir.

Önce A ve B arasında bir görüşme gerçekleştiğini düşünelim. Görüşme sonunda kümeler A{a,b}, B{b,a} ve C{c} durumunda güncellenir. Şimdi B ve C kişileri görüşsün ve oluşan küme durumu A{a,b}, B{b,a,c} ve C{c,a,b} haline güncellensin. Gördüğünüz üzere tek eksik A kişisinin c bilgisine erişmesi olacaktır bunun için de son olarak A ve C kişileri görüşürse herkes bütün bilgilere erişmiş olur. 3 insanlı sistemin çözümü de 3 görüşmeyle gerçekleştirildi.

4 ve üzeri insan durumu

Tijdeman tarafından kanıtlanan problemde 4 ve üzeri insan için sonuç bir denkleme indirgenebilmiştir. Biz örnek olarak sadece 4 kişi için çözüm aşamalarını yazalım.

A{a}, B{b}, C{c} ve D{d} insan-bilgi ilişkimizi göstersin.

A ve B ve aynı anda C ve D görüşmeleri gerçekleşsin.  Görüşmeler sonunda A{a,b}, B{b,a}, C{c,d} ve D{d,c} durumuna güncellenir. Sonrasında B ve D insanları bir görüşmede bulunursa ve A ve C insanları bir görüşmede bulunursa tüm bilgiler tüm insanlara aktarılmış olur ve sonuç 4 görüşme olarak bulunur.

Genelleme

İnsan Görüşme
0,1 0
2 1
3 3
4 ve 4+ 2n-4

Üstteki problemimizde yönsüz graflar üzerinden işlem yapmıştık fakat yönlü grafların da kullanılabileceği problemler karşımıza çıkabilir. Örneğin dosya paylaşımında bulunan n elemanı düşünelim. Bir dosyayı mail veya başka bir yöntem ile başka bir insana atılan anda diğer insan da size bir dosya atmış sayılmayacaktır. Bu durum da bize yönlü graf kavramını hatırlatır. Yönlü grafların kullanıldığı problemlerde çözüm 1. Kişiden N. Kişiye kadar sıralı iletişim ve ardından tam tersi N. Kişiden 1. Kişiye doğru sıralı iletişim şeklinde gerçeklenir. Ne demek istediğimi tablo olarak inceleyecek olursak,

Paylaşım A B C D
İlk durum a b c d
A->B a a,b c  d
B->C a a,b a,b,c d
C->D a a,b a,b,c a,b,c,d
D->C a a,b a,b,c,d a,b,c,d
C->B a a,b,c,d a,b,c,d a,b,c,d
B->A a,b,c,d a,b,c,d a,b,c,d a,b,c,d

4 insandan oluşan sistemimizde yapılacak işlemler ve sonuçları tek tek yukarıdaki gibi olacaktır. Bu durumda ve diğer bütün durumlarda sadece tek bir formül  bizi çözüme götürecektir.

Formül=2n-2

2 farklı türü anlatılan problemin kullanım alanları olarak haberleşme uygulamaları, paralel hesaplama problemleri gibi alanların büyük kısmında kullanıldığını söyleyebiliriz.

Yorum yaz

Email adresiniz yayınlanmayacaktır.