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

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