Yükleniyor...

Ana Sayfa / Matematik

Matematiksel Analiz

Formüller, algoritmalar ve kanıtlar

Hanoi Kuleleri, üstel büyüme, rekürsif fonksiyonlar ve kombinatorik analizin en güzel örneklerinden biridir. n disk için minimum hamle sayısı 2n - 1 formülü ile verilir ve bu, matematiksel olarak ispatlanmış optimal çözümdür.

Temel Formül

Hanoi Kuleleri için en temel ve önemli formül, n disk taşınırken gereken minimum hamle sayısını veren formüldür:

Minimum Hamle Sayısı

T(n) = 2n - 1

Burada T(n), n disk için gereken minimum hamle sayısıdır.

Örnek Hesaplamalar

Disk Sayısı (n) 2n 2n - 1 Süre (sn/disk)
1211 sn
2433 sn
3877 sn
4161515 sn
5323131 sn
664631 dk 3 sn
71281272 dk 7 sn
82562554 dk 15 sn
101,0241,02317 dk 3 sn
201,048,5761,048,57512 gün
324,294,967,2964,294,967,295136 yıl
6418,446,744,073,709,551,61618,446,744,073,709,551,615585 milyar yıl

64 Disk Örneği

Efsanedeki 64 disk için gereken hamle sayısı 18,446,744,073,709,551,615'tir. Bu sayı o kadar büyüktür ki, saniyede bir hamle yapan bir makine bile bunu tamamlamak için 585 milyar yıl gerektirir. Evrenin şu anki yaşı yaklaşık 13.8 milyar yıldır!

Rekürsif Çözüm

Hanoi Kuleleri'nin en zarif çözümü rekürsif yaklaşımdır. Bu yaklaşım, problemi daha küçük alt problemlere ayırır ve "böl ve fethet" (divide and conquer) stratejisini kullanır.

Rekürsif Algoritma

function hanoi(n, kaynak, hedef, yardimci):
    // Base case: 1 disk
    if n == 1:
        tasi_disk(kaynak, hedef)
        return
    
    // n-1 diski kaynaktan yardimciya tasi
    hanoi(n-1, kaynak, yardimci, hedef)
    
    // En buyuk diski kaynaktan hedefe tasi
    tasi_disk(kaynak, hedef)
    
    // n-1 diski yardimcidan hedefe tasi
    hanoi(n-1, yardimci, hedef, kaynak)

Matematiksel İndüksiyon Kanıtı

Teorem: n disk için minimum hamle 2n - 1'dir.

Temel Durum (n = 1):

T(1) = 1 = 21 - 1. Tek disk için doğru.

İndüksiyon Varsayımı:

n-1 disk için T(n-1) = 2n-1 - 1 olsun.

İndüksiyon Adımı:

n disk için:

  • n-1 diski kaynaktan yardımcıya tasi: T(n-1) hamle
  • En büyük diski kaynaktan hedefe tasi: 1 hamle
  • n-1 diski yardımcıdan hedefe tasi: T(n-1) hamle
T(n) = T(n-1) + 1 + T(n-1) = 2·T(n-1) + 1

İndüksiyon varsayımını yerine koyalım:

T(n) = 2·(2n-1 - 1) + 1 = 2n - 2 + 1 = 2n - 1

Sonuç: İndüksiyon tamamlandı. Teorem doğrudur. ∎

Karmaşıklık Analizi

Algoritma karmaşıklığı analizi, bir algoritmanın verimliliğini ölçmek için kullanılan matematiksel bir çerçevedir.

Zaman Karmaşıklığı

⏱️ Zaman Karmaşıklığı

O(2n)

Üstel zaman karmaşıklığı. Her disk eklendiğinde süre ikiye katlanır.

💾 Uzay Karmaşıklığı

O(n)

Rekürsif çağrı yığını için gerekli alan.

🎯 Optimallik

Θ(2n)

Alt ve üst sınır aynıdır - daha iyisi mümkün değil.

Büyüme Oranları Karşılaştırması

Büyüme Sınıfı Örnek 220 için süre
O(1)Sabit1 işlem
O(log n)İkili arama20 işlem
O(n)Lineer arama1 milyon işlem
O(n log n)Hızlı sıralama20 milyon işlem
O(n²)Kabarcık sıralama1 trilyon işlem
O(2n)Hanoi Kuleleri1 milyon trilyon işlem

NP-Hard Bağlantısı

Genelleştirilmiş Hanoi Kuleleri problemi (4+ çubuk), NP-hard olarak sınıflandırılır. Bu, büyük örnekler için optimal çözüm bulmanın hesaplama açısından zor olduğu anlamına gelir.

Kapalı Form Çözümü

Rekürsif tanımın yanında, Hanoi Kuleleri için kapalı form (closed-form) çözümler de vardır.

T(n) = 2n - 1 Türetimi

Rekürsif denklem:

T(n) = 2·T(n-1) + 1, T(0) = 0

Her iki tarafa 1 ekleyelim:

T(n) + 1 = 2·T(n-1) + 2 = 2·(T(n-1) + 1)

S(n) = T(n) + 1 dönüşümü yapalım:

S(n) = 2·S(n-1), S(0) = 1

Bu geometrik dizinin çözümü:

S(n) = 2n

Geri dönüşüm:

T(n) = S(n) - 1 = 2n - 1

Alternatif İteratif Formül

Bit Manipülasyonu ile:

T(n) = (1 << n) - 1

Bu, 2n - 1 hesaplamasının bilgisayar bilimindeki ifadesidir.

İkili Gösterim ve Bit Desenleri

Hanoi Kuleleri'nin çözümü, ikili sayı sistemi ile yakından ilişkilidir. Her hamle, ikili sayıların yapısından doğrudan türetilebilir.

Gray Kod Bağlantısı

Hanoi Kuleleri çözümü, Gray kodları ile izomorfiktir. Gray kod, ardışık sayılar arasında sadece bir bit değişen bir sayı sistemidir.

Hamle Binary Gray Kod Hareket Edilen Disk
0000000-
10010011
20100112
30110101
41001103
51011111
61101012
71111001

İkili Hamle Belirleme

Hamle sayısının en sağdaki 1 bit'i hangi diskin hareket edeceğini gösterir:

disk_number = position_of_rightmost_set_bit(move_number)

Örnek: Hamle 5 (1012) → En sağdaki 1, 1. pozisyonda → Disk 1

Genellemeler

Klasik 3 çubuklu problem, çeşitli şekillerde genelleştirilebilir.

4+ Çubuk Problemi (Frame-Stewart Algoritması)

Problem: n disk ve k çubuk (k ≥ 3)

Frame-Stewart Algoritması (1941):

  1. En uygun m diski seç (0 < m < n)
  2. m diski kaynaktan yardımcı çubuğa taşı (k-1 çubuk kullanarak)
  3. Kalan n-m diski kaynaktan hedefe taşı (k çubuk kullanarak)
  4. m diski yardımcıdan hedefe taşı (k-1 çubuk kullanarak)
F(n, k) = min1≤m { 2·F(m, k-1) + F(n-m, k) }

Çoklu Hedef Problemleri

  • Cyclic Hanoi: Diskler sadece bir yönde hareket edebilir. Çözüm: 3n - 1 hamle
  • Directed Graph: Çubuklar arası geçişler kısıtlı. Karmaşıklık geçiş grafiğine bağlıdır.
  • Reve's Puzzle: Farklı boyutlardaki diskler için genelleme.

İstatistiksel Analiz

Rastgele hamlelerle çözüm olasılıkları ve ortalama çözüm süreleri üzerine istatistiksel çalışmalar yapılmıştır.

Rastgele Çözüm Olasılığı

Her hamlede rastgele seçim yapıldığında:

  • Küçük disk sayıları için (n ≤ 5): Makul sürede çözüm bulunabilir
  • Orta disk sayıları için (n = 6-8): Çok uzun süre gerektirir
  • Büyük disk sayıları için (n > 8): Pratik olarak imkansız
P(optimal) = 1 / (tüm olası hamle dizileri) ≈ 0 (n büyüdükçe)

Ortalama Çözüm Süreleri

Disk Optimal (sn) Ortalama (dk) Uzman (sn)
371-210-15
4153-530-45
5318-121-2
66320-303-5
712745-608-12
82552-3 saat20-30

İnsan Performansı

Deneyimli oyuncular, optimal stratejiyi kullanarak disk başına ortalama 1-2 saniyede hamle yapabilirler. Bu, otomatik çözümden sadece 2-3 kat daha yavaştır.

Matematiksel Özet

Hanoi Kuleleri, matematiğin en zarif problemlerinden biridir. Basit kurallarla tanımlanmasına rağmen, derin matematiksel yapılar içerir:

  • Rekürsiyon: Kendini referans eden elegan çözüm
  • Üstel Büyüme: 2n - 1 formülü
  • İkili Sistem: Gray kod ile doğal bağlantı
  • Kombinatorik: Optimal ve suboptimal çözüm uzayı
  • Algoritma: Bilgisayar biliminin temel örneği

Pratik Uygulama

Matematiksel bilgilerinizi test edin:

Oyunu Oyna Stratejiler

Referanslar

  1. Frame, J. S. (1941). Solution to advanced problem 3918. American Mathematical Monthly, 48, 216-217.
  2. Stewart, B. M. (1939). Problem 3918. American Mathematical Monthly, 46, 363.
  3. Hinz, A. M. (1989). An iterative algorithm for the Tower of Hanoi with four or more pegs. The Computer Journal.
  4. Troshkin, A. A. (1989). Analysis of a recursion hierarchy. Computer Science.
  5. Scorer, R. S., Grundy, P. M., & Smith, C. A. B. (1944). Some binary games. Mathematical Gazette.