Lineer programlama algoritmalarında hesaplama karmaşıklığı ve karmarkar algoritması
Computational complexity in lineer programming algorithms and Karmarkar's algorithm
- Tez No: 84484
- Danışmanlar: YRD. DOÇ. DR. N. KEMAL ERDOĞAN
- Tez Türü: Yüksek Lisans
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 1999
- Dil: Türkçe
- Üniversite: Eskişehir Osmangazi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Matematik Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 145
Özet
ÖZET Hesaplama karmaşıklığının amacı, spesifik bir algoritmanın kullanılmasıyla belirli bir problemin çözülmesi için gereken aritmetik ya da diğer hesaplamalı işlemlerin sayısını belirlemektir. Bunu bir problemin çözülmesinin maliyeti olarak adlandırırız. Bir algoritmanın maliyeti birkaç yolla ölçülebilmektedir. Bunlardan ikisi, bir algoritmanın en-kötü durum ve ortalama-durum maliyetleridir. Bir algoritmanın maliyetine 0(f(L)) denirse, C bir pozitif sabit, L probleme ait girdi verisinin uzunluğunun ölçümü ve / bir fonksiyon olmak üzere, yeterince büyük bir L için aritmetik işlemlerin sayısın Cf(L) olmaktadır. Bu tez dört bölümden oluşmaktadır ve özellikle lineer programlama algoritmalarının karmaşıklığıyla ilgilidir. Birinci bölümde, algoritma ve hesaplama karmaşıklığı kavramlarının tanımları ve bunlarla ilgili temel kavramlar yer almaktadır. İkinci bölümde, bir girdi verisinin büyüklüğünün tanımı verilmektedir ve bir algoritmanın etkinliğini nasıl ölçebileceğimiz açıklanmaktadır. Üçüncü bölümde, lineer programlamanın geometrisi ve simpleks ve elipsoid algoritmaların karmaşıklıkları yer almaktadır. Dördüncü ve son bölümde, teori ve uygulamada diğer lineer programlama algoritmalarından daha etkin olan Karmarkar'ın lineer programlama için olan algoritmasının karmaşıklık ve yakınsaklık özellikleri ele alınmıştır. iv
Özet (Çeviri)
SUMMARY The purpose of computational complexity is to determine the number of arithmetic or other computational operations required to solve a particular problem using a specific algorithm. We refer to this as the cost of solving a problem. The cost of an algorithm can be measured in several ways. Two of them are the worst-case cost and average-case cost of an algorithm. If it is said that the cost of an algorithm is 0(/(X)) it is meant for sufficiently large L number of arithmetic operations^ Cf(L) where C is some positive constant, L is a measure of the length of the input data for the problem and/is some function. This thesis consists of four chapters and it especially deals with the complexity of lineer programming algorithms. In chapter 1, we summarize the definitions and background metarials of an algorithm and computational complexity. In chapter 2, we give the definition of size of an input data and explain that how we can measure of an algorithm's efficiency. In chapter 3, we mention about the geometry of lineer programming problems and computational complexities of simplex and ellipsoid algorithms. In chapter 4, we give the complexity and convergence characteristics of Karmarkar' s algorithm for lineer programming which is more efficient than other lineer programming algorithms in theory and practice.
Benzer Tezler
- Parallel solution of unsteady, incompressible three-dimensional Navier-Stokes equations with a new implicit method
Zamana bağlı, sıkıştırılamaz, üç boyutlu Navier-Stokes denklemlerinin yeni bir kapalı metodlar paralel çözümü
VİLDAN ÜSTOĞLU ÜNAL
Doktora
İngilizce
2003
Astronomi ve Uzay Bilimleriİstanbul Teknik ÜniversitesiAstronomi ve Uzay Bilimleri Ana Bilim Dalı
PROF. DR. ÜLGEN GÜLÇAT
- Energy aware endurance framework for mission critical aerial networks
Güdümlü havasal ağlar için enerji farkında endürans modeli
YUSUF ÖZÇEVİK
Doktora
İngilizce
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. BERK CANBERK
- Bulanık çok modlu kaynak kısıtlı proje çizelgeleme problemlerinin çözümü için matematiksel bir model
A mathematical model for the solution of the fuzzy multi mode resource-constrained project scheduling problems
ÖMER ATLI
Doktora
Türkçe
2012
Endüstri ve Endüstri MühendisliğiHava Harp Okulu KomutanlığıEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. CENGİZ KAHRAMAN
- Advances in robust identification of spline models and networks by robust conic optimization, with applications to different sectors
Değişik sektörlere uygulamalarıyla birlikte sağlam konik optimizasyon ile eğri modelleri ve ağların sağlam tanımlanmasındaki gelişimler
AYŞE ÖZMEN
Doktora
İngilizce
2015
MatematikOrta Doğu Teknik ÜniversitesiBilimsel Hesaplama Ana Bilim Dalı
PROF. DR. GERHARD WİEHELM WEBER
- Kablosuz haberleşme sistemlerinde FPGA uygulaması
Implementation FPGA of wireless communication systems
ŞENER DİKMEŞE
Yüksek Lisans
Türkçe
2007
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKocaeli ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. HASAN DİNÇER