Ayrık yapıların tümleyen problemler yardımıyla incelenmesi
Yükleniyor...
Tarih
2013
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Ege Üniversitesi
Erişim Hakkı
info:eu-repo/semantics/openAccess
Özet
Ayrık problemler, değişkenlerin kesikli olarak tanımlandığı problemlerdir ve günlük yaşamda en sık karşılaşılan durumlara çözüm aramaktadır. Algoritmaların karmaşıklığı teorisinin gelişmesi ile bu problemlerin çoğunun NPtam sınıftan olduğu görülmektedir. Bu problemler için P=NP olmadığı sürece polinom zamanda kesin çözüm veren algoritmaların bulunması ümidi yok denecek kadar azdır. Dolayısıyla bu tür problemler için daha kolay sonuç veren yöntemler düşünülmektedir. Bu yöntemlerden biri de tümleyen yöntemdir. Bu tezde sırt çantası problemleri, bozdurma problemi, altküme-toplamı problemi, bazı graf problemleri gibi ayrık problemler ele alınmış ve bu problemler için bazı algoritmalar incelenmiştir. Tümleyen kavramı üzerinde durularak; bu kavram yardımıyla, verilen problemlerin daha iyi ele alınması amaçlanmıştır. Yukarıda bahsedilen problemlerin bazıları için daha önceden oluşturulmuş tümleyen problemler ile bunlar için önerilen algoritmalar ve garanti değerleri incelenmiştir. Ayrıca sınırlı sırt çantası problemi için tümleyen problem oluşturularak bazı teoremler ispatlanmıştır. Benzer şekilde altküme toplamı problemi ve bozdurma problemi için de tümleyen problemler inşa edilmiştir. Son olarak orta öğretim matematiğinde tümleyen yönteminin kullanıldığı mental aritmetik, Bachet oyunu ve karelerin hesaplanması konuları ele alınmıştır.
Açıklama
Anahtar Kelimeler
Ayrık problemler, Tümleyen yöntemi, Kombinatoriyal optimizasyon, Sırt çantası problemi, Bozdurma problemi, Altküme-toplamı problemi, Greedy algoritma, Mental aritmetik, Bachet oyunu., Discrete problems, Complementary method, Combinatorial optimization, Knapsack problem, Change-making problem, Subset-sum problem, Greedy algorithm, Mental mathematics, Bachet's game., Matematik A.B.D.
