01
Algoritma Tasarım Yaklaşımları
Kaba kuvvetin kâhin rolü, böl–yönet bağıntısı, açgözlü seçimin yanıldığı sistemler, not almanın örtüşme koşulu, budamanın kestiği arama alanı ve rastgeleleştirmenin beklenen başarımı.
- 01 Kaba Kuvvet ve Sınırları Kaba kuvvetin bu kurstaki rolü bir yavaş seçenek değil bir kâhindir: tam sayım 40 girdide 2640 adım harcıyor, erken çıkan eleme 866 adımla aynı yanıtı veriyor, ilk altı konuma bakan örnekleme ise 406 adımla 14 girdide kâhinden ayrılıyor.
- 02 Böl ve Yönet Bölme ile birleştirmenin ayrı hesaplar olduğu: aynı bölme üzerinde doğrusal birleştirme kâhinin 1,16 katı az adım harcayıp 40 girdide de doğru kalırken, karesel birleştirme kâhinden 1,71 kat yavaşlıyor ve sınırı geçen çözümü atlayan eksik birleştirme 920 adımla 40 girdinin 40'ında yanlış yanıt veriyor.
- 03 Açgözlü Algoritmalar Açgözlü seçimin kanıtlanmadıkça yordam olmadığı: dört değerli 969 para sisteminin 827'sinde açgözlü gerekenden fazla para veriyor, oran 0,8535 ve en büyük fazlalık 16 para; aynı yanılgı 50 yerine 10 tutara kadar sınandığında sistemlerin yalnız 85'inde görülüyor.
- 04 Dinamik Programlama Not almanın iki koşulu ve ikisinin de sayılması: örtüşen alt problemde çağrı 21.891'den 39'a inerken örtüşmeyende ikisi de 39 kalıyor ve defter 19 girişi boşa tutuyor, defterin anahtarı durumun tamamını taşımadığında ise kalıp 40 girdinin 39'unda kâhinden ayrılıyor.
- 05 Geri İzleme Budamanın doğruluğu koruyan tek kısaltma olduğu ve ölçütü bozulduğunda ne olduğu: yedi vezirlik tahtada budamalı arama 552, budamasız arama 960.800 düğüm geziyor, ama komşu sütunu da kesen aşırı budama 82 düğümde bitip çözümlerin tamamını kaybediyor.
- 06 Rastgeleleştirilmiş Algoritmalar Rastgeleliğin iki ayrı yerde kullanılabileceği ve ikisinin ayrı ölçüldüğü: doğrulamasız örnekleme çoğunluğu olmayan 40 dizinin 40'ında yanlış değer döndürürken doğrulamalı örnekleme aynı dizilerde hiç yanılmıyor, ve on altı vezirlik tahtada rastgele sütun sırası 10.053 düğümlük belirlenimci aramayı ortalama 360 düğüme indiriyor.