Diskrit programlama problemlerinde tümleme prensipleri üzerine

Abstract

V ÖZET DİSKRİT PROGRAMLAMA PROBLEMLERİNDE TÜMLEME PRENSİBLERİ ÜZERİNE VARGÖR, Duygu Yüksek Lisans Tezi, Matematik Bölümü Tez Yöneticisi: Doç. Dr. Urfat G. NURÎYEV Ocak 2005, 65 sayfa Diskrit Programlama problemleri 60'lı yıllardan itibaren araştırılmaya başlanmıştır. Bu problemler ekonomide, teknolojide karşılaşılan birçok pratik problemin matematiksel modeli olarak ele alınmaktadır. Algoritmaların karmaşıklığı teorisinin gelişmesi ile Diskrit Programlama problemlerinin çoğunun NP-tam sınırından olduğu bilinmektir. Buna göre bu tür problemler için heuristik algoritmalar geliştirilmiştir. Heuristik algoritmaların kalitesi genellikle, problemin özelliklerini göz önüne alma derecesi ile ilişkilidir. Bunun için ise Tümleyici problemler çok önemlidir. Bu nedenle Tezde Yükleme Problemlerinden birkaçının, Kutu Paketleme Probleminin ve Tepe Örtüsü Probleminin Tümleyicileri incelenmiş, heuristik algoritmalardan biri olan Greedy algoritmasını gerçekleştiren TKnap Paket programı hazırlanmış, hesaplama denemeleri yapılmış, elde edilen hesaplamaların hataları incelenmiştir. Anahtar Sözcükler: Diskrit (Kombinatoryal) Optimizasyon Problemleri, Yükleme Problemleri, Klik Problemi, Tepe Örtüsü Problemi, Bağımsız Küme Problemi, Kutu Paketleme Problemleri, Tümleyici Problemler, Heuristik Algoritma, Greedy Algoritması.

vn ABSTRACT ON COMPLEMENT PRINCIBALS OF DISCRETE PROGRAMMING PROBLEMS VARGÖR, Duygu Master Thesis, Mathematics Department Supervisor: Associate Professors Urfat G. NURİYEV January 2005, 65 Pages Discrete Optimization Problems have been started to investigate since 1960's. These problem are mathematics models of lots of practical problems which are used in economical and technological area. With the complexity theory of algorithms, many of Discrete Programming problems are known that they are Np-Complete. According to this, heuristic algorithms have been developed for these problems. Quality of heuristic algorithms are usually about investigation degree of problems' qualifications. As a result fo this, Complements of these problems are very important. So, in this thesis complements of some of Knapsack Problems, Bin-Packing Problem and Vertex Cover have been investigated, Tknap Packet Program has been prepared which verifies Greedy Algorithm that is one of heuristic algorithms, and then calculation tests have been done and errors of these calculations have been examined. Key Words: Discrete (Combinatorial) Optimization Problems, Clique Problem, Knapsack Problems, Vertex Cover Problem, Independent Set Problem, Bin-Packing Problem, Complement Problems, Heuristic Algorithm, Greedy Algorithm.