Geri Dön

Dizi birleştirme probleminde zaman – bellek ödünleşimi

Time - space tradeoff in array merging problem

PDF İndir

  1. Tez No: 969973
  2. Yazar: SUBHAN GULIYEV
  3. Danışmanlar: PROF. DR. MEHMET EMİN DALKILIÇ
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2025
  8. Dil: Türkçe
  9. Üniversite: Ege Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Uluslararası Bilgisayar Ana Bilim Dalı (disiplinlerarası)
  12. Bilim Dalı: Bilgi Teknolojileri Bilim Dalı
  13. Sayfa Sayısı: Belirtilmemiş.

Özet

Toplam N elemanlı iki farklı sıralı diziyi birleştirmek, fazladan N elemanlık ek bellek kullanılarak çözülmekte olup Birleştirme Sıralaması (Merge Sort) algoritmasında uygulanmaktadır. Ancak bu fazladan bellek kullanımı, ek bellek gerektirmeyen, yerinde birleştirme yapan algoritmalara göre ciddi dezavantaj oluşturmaktadır. Ek bellek kullanmadan verimli bir şekilde birleştirme yapmak, eski zamanlardan itibaren birçok bilgisayar bilimcilerinin üzerinde çalıştığı ancak tam anlamıyla tatmin edici bir çözüme ulaşamadıkları bir problemdir. Bu çalışma kapsamında dizi birleştirme problemine yönelik farklı bir bakış açısı sunulmuştur. Bu alternatif yaklaşım çerçevesinde dizi birleştirme probleminde mevcut zaman-bellek ödünleşimi potansiyeli (biraz bellekten ve biraz çalışma zamanından ödün vermek) kullanılarak yeni bir dizi birleştirme algoritması tasarlanmış ve gerçeklenmiştir. Zaman-bellek ödünleşimi tabanlı bu birleştirme algoritması C++ programlama diliyle gerçeklenmiş olup performans testlerinin yapılması için iki farklı test ortamı oluşturulmuştur. İlk test ortamında, rand () fonksiyonu ile oluşturulan farklı problem uzunlukları (N) ve farklı ek bellek uzunlukları (k) için algoritmanın performansı test edilmiştir. İkinci test ortamı ise bu birleştirme algoritmasının Birleştirme Sıralaması (Merge Sort) algoritmasında kullanılarak farklı girdi tipleri ile performans testlerinin yapıldığı ortamdır. Elde edilen sonuçlar, geliştirilen birleştirme algoritmasının farklı ek bellek kullanımları için bellek arttıkça algoritmanın karmaşıklığının azaldığını ortaya koymuştur.

Özet (Çeviri)

The problem of merging two distinct sorted arrays, comprising a total of N elements, is conventionally addressed by allocating an auxiliary buffer of size N – an approach employed in the Merge Sort algorithm. However, this additional memory requirement constitutes a significant drawback compared to in-place merging algorithms that perform the merge without extra storage. Efficient in-place merging has long been recognized as a challenging problem, studied by numerous researchers, but yet no fully satisfactory solution has emerged. In this thesis, an alternative perspective on the array merging problem is presented. Within this framework, a new merge algorithm is designed and implemented by exploiting the inherent time-space trade-off (trading a modest amount of extra space for reduced execution time). This time-space trade-off-based merging algorithm has been implemented in C++ and evaluated in two distinct test environments. In the first, algorithm's performance is measured across various problem instances of size N generated by the rand () function and auxiliary buffer sizes k. In the second, the merging algorithm is integrated into the Merge Sort procedure and benchmarked on multiple input distributions. The experimental results confirm that, increasing the amount of auxiliary buffer k, decreases the algorithm's overall time complexity.

Benzer Tezler

  1. Tez No

    827860

    Derin öğrenme ve büyük veri analitiği yöntemleriKullanarak Covid-19 yayılımının ileriye dönük tahmini

    Forecasting the spread of covid-19 using deep learning and big data analytics methods

    CYLAS KIGANDA

    Yüksek Lisans

    İngilizce

    İngilizce

    2023

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

    Bilgisayar Bilimleri Ana Bilim Dalı

    PROF. DR. MUHAMMET ALİ AKCAYOL

  2. Tez No

    827867

    Classification of abnormal respiratory sounds using deep learning techniques

    Solunum seslerinin derin öğrenme yöntemleri ile sınıflandırılması

    AHAMADI ABDALLAH IDRISSE

    Yüksek Lisans

    İngilizce

    İngilizce

    2023

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

    Bilgisayar Bilimleri Ana Bilim Dalı

    DOÇ. DR. OKTAY YILDIZ

  3. Tez No

    888651

    Integrating path planning and image processing with UAVs for disease detection and yield estimation in indoor agriculture

    Kapalı alan tarımda hastalık tespiti ve verim tahmini için rota planlama ve görüntü işlemenin İHA'larla entegre edilmesi

    ONAT ERDOĞMUŞ

    Yüksek Lisans

    İngilizce

    İngilizce

    2024

    Mekatronik Mühendisliğiİstanbul Teknik Üniversitesi

    Mekatronik Mühendisliği Ana Bilim Dalı

    PROF. DR. ERDİNÇ ALTUĞ

  4. Tez No

    457163

    Characterization of short tandem repeats using local assembly

    Lokal DNA birleştirme metodu ile mikrosatellitlerin bulunması

    GÜLFEM DEMİR

    Yüksek Lisans

    İngilizce

    İngilizce

    2017

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. CAN ALKAN

  5. Tez No

    397843

    Design and realization of Ku-band microstrip patch antenna with LNA for small satellites

    Küçük uydular için Ku band mikroşerit yama anten dizisi ve düşük gürültülü kuvvetlendirici tasarımı ve gerçeklemesi

    LIDA KOUHALVANDI

    Yüksek Lisans

    İngilizce

    İngilizce

    2015

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

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

    ÖĞR. GÖR. HASAN BÜLENT YAĞCI

Geri Dön