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: Belirtilmemiş.
  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ı: 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

  1. Tez No

    143110

    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

    İngilizce

    2003

    Astronomi ve Uzay Bilimleriİstanbul Teknik Üniversitesi

    Astronomi ve Uzay Bilimleri Ana Bilim Dalı

    PROF. DR. ÜLGEN GÜLÇAT

  2. Tez No

    607063

    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

    İngilizce

    2019

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. BERK CANBERK

  3. Tez No

    335005

    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

    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

  4. Tez No

    380983

    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

    İngilizce

    2015

    MatematikOrta Doğu Teknik Üniversitesi

    Bilimsel Hesaplama Ana Bilim Dalı

    PROF. DR. GERHARD WİEHELM WEBER

  5. Tez No

    232703

    Kablosuz haberleşme sistemlerinde FPGA uygulaması

    Implementation FPGA of wireless communication systems

    ŞENER DİKMEŞE

    Yüksek Lisans

    Türkçe

    Türkçe

    2007

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKocaeli Üniversitesi

    Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı

    PROF. DR. HASAN DİNÇER

Geri Dön