Ayrık yapıların tümleyen problemler yardımıyla incelenmesi

Küçük Resim Yok

Tarih

2014

Dergi Başlığı

Dergi ISSN

Cilt Başlığı

Yayıncı

Ege Üniversitesi

Erişim Hakkı

info:eu-repo/semantics/closedAccess

Ö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 NP-tam 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 projede 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.;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.

Açıklama

Araştırma Projesi -- Ege Üniversitesi, 2014

Anahtar Kelimeler

Kaynak

WoS Q Değeri

Scopus Q Değeri

Cilt

Sayı

Künye