Ayrık yapıların tümleyen problemler yardımıyla incelenmesi
A study of discrete structures by means of complementary problems
- Tez No: 342649
- Danışmanlar: PROF. DR. URFAT NURIYEV
- Tez Türü: Doktora
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2013
- Dil: Türkçe
- Üniversite: Ege Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Bilimleri Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 116
Özet
Ayrık problemler, değişkenlerinin 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 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 incelenmesi 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.
Özet (Çeviri)
Discrete problems are problems whose variables are defined as discontinuous and they search for solutions for frequently encountered situations in daily life. With the development of the theory of algorithm complexity, it is seen that most of these problems are in NP-complete class. There is little hope to find algorithms that give exact solutions for these problems in polynomial time unless P=NP. Consequently, other methods which give results more easily are considered. One of these methods is complementary method. In this thesis, discrete problems such as knapsack problems, change-making problem, subset-sum problem and some graph problems have been considered, then several algorithms for these problems have been analysed. It has been aimed to study the given problems in a better way by means of the complementary method. Complementary problems which have been formerly created for some of the problems mentioned above, and proposed algorithms for these problems with their guarantee values have been analysed. Moreover, complementary problem for the bounded knapsack problem has been constituted and some theorems have been proved. Similarly, complementary problems for change-making problem and subset-sum problems have been created as well. Finally, mental mathematics, Bachet?s game and calculation of the squares of numbers have been considered.
Benzer Tezler
- Baskınlık sayısı parametreleri ve sezgisel algoritmalar
Parameters of domination number and heuristic algorithms
TUFAN TURACI
- Bazı graf yapılarında zedelenebilirlik kavramı üzerine
On the vulnerability concept of some graph structures
BETÜL ATAY
- Doğrusal-fazlı keskin FIR sayısal süzgeç tasarımı için FRM yaklaşımı ve eşzamanlı optimizasyon tekniği
FRM approach and simultaneous optimization technique for sharp linear-phase FIR digital filter design
MURAT KAPAR
Yüksek Lisans
Türkçe
2006
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. AHMET HAMDİ KAYRAN
- Processing wh-dependencies in L2 English: The role of L1 and working memory capacity
İkinci dil olarak İngilizce?de Wh-soru bağımlılıklarını işleme: Birinci dil ve işler-bellek kapasitesinin rolü
FİLİZ ÇELE
Doktora
İngilizce
2010
DilbilimBoğaziçi Üniversitesiİngiliz Dili Eğitimi Ana Bilim Dalı
DOÇ. DR. AYŞE GÜREL
- Türkçe'de ayrık yapılar
Cleft constructions in Turkish
ÖZGE CAN
Yüksek Lisans
Türkçe
2005
DilbilimDokuz Eylül ÜniversitesiGenel Dilbilim Ana Bilim Dalı
PROF.DR. LÜTFİYE OKTAR