Geri Dön

Lineer programlama algoritmalarında hesaplama karmaşıklığı ve karmarkar algoritması

Computational complexity in lineer programming algorithms and Karmarkar's algorithm

  1. Tez No: 84484
  2. Yazar: NESRİN ESEN
  3. Danışmanlar: YRD. DOÇ. DR. N. KEMAL ERDOĞAN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Matematik, Mathematics
  6. Anahtar Kelimeler: Algoritmalar, Doğrusal programlama, Hesaplama, Karmarkar, Simpleks yöntemi, Algorithms, Linear programming, Calculation, Karmarkar, Simplex method
  7. Yıl: 1999
  8. Dil: Türkçe
  9. Üniversite: Eskişehir Osmangazi Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Matematik Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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.

Geri Dön