Kuvvet Kümesi Hesaplama

Eleman sayısı n olan bir kümenin boş küme ve kendisi dahil 2ⁿ alt kümesini ve öz alt küme sayısını hesaplar.

Nasıl hesaplanır?

n elemanlı bir kümenin 2n alt kümesi vardır: her eleman bir alt kümede ya vardır ya yoktur, yani eleman başına iki seçenek bulunur. Araç bu toplamı (boş küme ve kümenin kendisi dahil) ve kümenin kendisini saymayan öz alt küme sayısını, yani 2n − 1 değerini verir. n, 0 ile 62 arasında bir tam sayı olmalıdır; daha büyük, negatif ya da kesirli değerler sonuç vermez. n = 0 (boş küme) için 1 alt küme ve 0 öz alt küme vardır. Sonuçlar binlik ayraçlı tam sayılardır ve aracın tam gösterebildiği en büyük 2 kuvveti olan n = 62'de bile (4.611.686.018.427.387.904) her basamak kesindir.

Örnek hesaplama

Bir kümenin 5 elemanı olsun, örneğin {a, b, c, d, e}. Her eleman içeride ya da dışarıda olabilir; alt küme sayısı 2 × 2 × 2 × 2 × 2 = 25 = 32'dir. Öz alt kümeler kümenin kendisini saymaz: 32 − 1 = 31. Hesaplayıcı 32 alt küme ve 31 öz alt küme gösterir. 32'ye boş küme ile {a, b, c, d, e} kümesi de dahildir.

Bu örneği deneyin →

Sık yapılan hatalar

  • 2n yerine 2 × n hesaplamak. Her yeni elemanla sayı iki katına çıkar.
  • Boş kümenin de alt küme olduğunu unutmak. 3 elemanlı kümenin 7 değil 8 alt kümesi vardır.
  • Alt küme ile öz alt kümeyi karıştırmak. Öz alt kümeler kümenin kendisini dışarıda bırakır, sayı bir eksiktir.
  • Boş kümenin öz alt kümelerden çıkarıldığını sanmak. Burada yalnızca kümenin kendisi çıkarılır.
  • Eleman sayısı yerine alt küme sayısını girmek ya da 62'nin üstünde bir değer yazmak; araç bunu hesaplamaz.

Kaynaklar

Bu hesaplama hakkında

n elemanlı bir kümenin kuvvet kümesi, boş küme ve kümenin kendisi dahil olmak üzere tüm olası alt kümelerinin koleksiyonudur ve boyutu her zaman tam olarak 2 üzeri n’dir — bu sonuç, n elemanın her birinin bağımsız olarak belirli bir alt kümeye dahil edilip edilmeyeceğine, yani her eleman için iki seçenek olmasına dayanır. Kümenin kendisini hariç tutan öz alt küme sayısı ise bundan bir eksiktir: 2^n − 1.

Bu sonuç kümeler teorisi ve kombinatoriğin temelini oluşturur ve bilgisayar biliminde sürekli karşımıza çıkar: bir öğe kümesinin tüm alt kümelerini numaralandıran algoritmalar (sırt çantası veya alt küme toplamı problemlerinin kaba kuvvet çözümlerinde olduğu gibi), her bitin bir elemanın dahil olup olmadığını temsil ettiği 0’dan 2^n − 1’e kadar bir bit maskesi kullanır.

Bu faydalı oldu mu?

En fazla 3 tepki seçebilirsiniz.

Yorumlar

  • İlk yorumu siz yazın.

Popüler hesaplayıcılar

Tüm Hesaplayıcılar