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: Algoritmalar, Doğrusal programlama, Hesaplama, Karmarkar, Simpleks yöntemi, Algorithms, Linear programming, Calculation, Karmarkar, Simplex method
- 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ı: Belirtilmemiş.
Ö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
- Efficient estimation of Shrinkage parameters in fuzzy Ridge and fuzzy Liu regression models using α-cut-based methods under multicollinearity
Çoklu bağıntı durumunda bulanık Ridge ve bulanık Liu regresyon modellerinde α-kesim tabanlı yöntemler kullanılarak Shrinkage parametrelerinin etkin tahmini
AMMAR HOMAIDA
- 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
- Nonlinear model based guidance with deep learning based target trajectory prediction against agile attack patterns
Çevik saldırı manevralarına karşı derin öğrenme tabanlı tehdit yörünge tahmini ile doğrusal olmayan model öngörülü kontrol
ABDULLAH SADIK SATIR
Yüksek Lisans
İngilizce
2021
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiUçak ve Uzay Mühendisliği Ana Bilim Dalı
DOÇ. DR. NAZIM KEMAL ÜRE