Bu proje, dinamik programlama algoritmalarını zaman, bellek ve özellikle enerji karmaşıklığı perspektifinden inceleyen akademik bir analiz çalışmasıdır. Klasik algoritma analizine (Big-O) ek olarak, enerji karmaşıklığı kavramı hem teorik modelleme hem de deneysel ölçümler (CodeCarbon) aracılığıyla ele alınmıştır. Tüm deney süreci ve sonuçlar, Streamlit tabanlı etkileşimli bir arayüz üzerinden görselleştirilmektedir.
Bu çalışma, algoritmaların performansını yalnızca hız (zaman) açısından değil, aynı zamanda enerji tüketimi ve çevresel etki açısından da değerlendirmeyi amaçlamaktadır:
- Teorik Modelleme: Enerji karmaşıklığını, zaman karmaşıklığı T(n) ile ilişkilendirerek teorik olarak modellemek: E(n) ∝ T(n)
- Deneysel Gözlem: CodeCarbon kullanarak algoritmaların gerçek donanım üzerindeki karbon ayak izini ve enerji tüketimini ölçmek
- Karşılaştırmalı Analiz: Farklı girdi boyutlarında algoritmaların zaman, bellek ve enerji davranışlarını karşılaştırmak
- Yaklaşım Farkı: Grafik tabanlı ve tablo tabanlı dinamik programlama yaklaşımlarının enerji tüketim farklarını ortaya koymak
| Algoritma | Tür | Açıklama |
|---|---|---|
| Bellman–Ford | Graf Tabanlı | Tek kaynaklı en kısa yol algoritması. Negatif ağırlıklı kenarları destekler. |
| Floyd–Warshall | Graf Tabanlı | Tüm düğüm çiftleri için en kısa yolları hesaplar. |
| 0-1 Knapsack | Tablo Tabanlı | Bellek erişimi yoğun, klasik dinamik programlama problemi. |
Projede hem teorik hem de donanım tabanlı metrikler kullanılmıştır.
- Çalışma Süresi (T(n))
- CPU Çalışma Süresi
- Bellek Kullanımı (KB)
-
Teorik Enerji Karmaşıklığı
Ortalama güç tüketimi sabit kabul edilerek: E(n) ∝ T(n) -
Deneysel Enerji Tüketimi (CodeCarbon)
Donanım sensörleri üzerinden ölçülen CO₂ emisyonu (kg) -
Energy Impact Score (İkincil Metrik)
Time × Memory
⚠️ Önemli:
Teorik enerji karmaşıklığı ile CodeCarbon'dan elde edilen deneysel ölçümler bilinçli olarak ayrı tutulmuştur.
Teorik model algoritmanın yapısını, deneysel ölçüm ise gerçek sistem üzerindeki maliyeti temsil eder.
- Algoritmalar, arayüz ve dosya işlemlerinden (I/O) izole edilerek ölçülmüştür
- Enerji karmaşıklığı, ders müfredatına ve literatüre uygun şekilde zaman karmaşıklığına orantılı modellenmiştir
- Deney sonuçları, tek seferlik ölçümler yerine tekrarlar üzerinden ortalama alınarak hesaplanmıştır
- 0-1 Knapsack algoritması, grafik tabanlı algoritmalardan farklı bir bellek erişim modeli sunduğu için bonus kapsamda eklenmiştir
- Python 3.x
- Streamlit
- CodeCarbon
- psutil
- Pandas
- Matplotlib
dynamicProgramming/
├── algorithms/
│ ├── bellman_ford.py
│ ├── floyd_warshall.py
│ └── knapsack_01.py
├── experiments/
│ ├── run_bellman.py
│ ├── run_floyd.py
│ └── run_knapsack.py
├── measurements/
│ ├── time_tracker.py
│ ├── energy_tracker.py
│ └── codecarbon_tracker.py
├── results/
│ ├── csv/
│ │ └── results.csv
│ └── plots/
│ └── (otomatik üretilen grafikler)
├── app.py
├── requirements.txt
└── README.md
Projeyi yerel makinenizde çalıştırmak için aşağıdaki adımları izleyin:
Öncelikle projeyi bilgisayarınıza indirin ve proje dizinine gidin:
git clone https://github.com/kullaniciadi/proje-adi.git
cd dynamicProgramming# Sanal ortamı oluşturun
python -m venv venv
# Sanal ortamı aktif edin:
# Windows için:
venv\Scripts\activate
# Mac/Linux için:
source venv/bin/activateProje için gerekli olan kütüphaneleri yükleyin:
pip install -r requirements.txtstreamlit run app.pyTarayıcınızda otomatik olarak http://localhost:8501 adresi açılacaktır.
- Algoritma Seçimi: Menüden analiz etmek istediğiniz algoritmayı seçin
- Girdi Boyutu: Deney için girdi boyutunu belirleyin (örn: düğüm sayısı, kapasite)
- Deneyi Çalıştır: "Run Experiment" butonuna tıklayın
- Sonuçları İnceleyin:
- Zaman, bellek ve enerji grafikleri
- Karbon ayak izi tabloları
- Karşılaştırmalı analizler
Proje, her deney sonucunda otomatik olarak şu verileri üretir:
- CSV Formatında Ham Veri (
results/csv/results.csv) - Görselleştirme Grafikleri (
results/plots/)- Zaman karmaşıklığı grafikleri
- Enerji karmaşıklığı grafikleri
- Bellek kullanım grafikleri
- Enerji tüketimi karşılaştırmaları
Proje çıktıları Streamlit arayüzünde interaktif grafiklere dönüştürülmektedir. Aşağıda Bellman-Ford, Floyd-Warshall ve Knapsack algoritmalarının karşılaştırmalı analizlerinden örnekler yer almaktadır.
Deneyler sonucunda elde edilen ham veriler aşağıda verilmiştir. Veri setinin tamamına ulaşmak için linke tıklayabilirsiniz.|
🔗 Verinin Tamamını İncele: results.csv Dosyasını Görüntüle
Algoritmaların enerji karmaşıklığı, zaman karmaşıklığı ile doğrudan ilişkilidir:
E(n) = P_avg × T(n)
Burada:
- E(n): Enerji karmaşıklığı
- P_avg: Ortalama güç tüketimi (sabit kabul edilir)
- T(n): Zaman karmaşıklığı
Bu model, algoritmanın teorik analizini enerji boyutuna genişletir.
| Algoritma | Zaman Karmaşıklığı | Teorik Enerji | Alan Karmaşıklığı |
|---|---|---|---|
| Bellman-Ford | O(VE) | O(VE) | O(V) |
| Floyd-Warshall | O(V³) | O(V³) | O(V²) |
| 0-1 Knapsack | O(nW) | O(nW) | O(nW) |
- Donanım Bağımlılığı: CodeCarbon ölçümleri, çalıştırılan donanıma göre değişiklik gösterir
- Arka Plan İşlemleri: Deneyler sırasında diğer uygulamaları kapatmanız önerilir
- Küçük Girdi Boyutları: Çok küçük girdilerde enerji ölçümleri gürültülü olabilir
- Platform Desteği: CodeCarbon, tüm işlemcilerde aynı hassasiyette çalışmayabilir
Bu proje sonucunda hazırlanan "Dinamik Programlama Algoritmalarında Zaman ve Enerji Karmaşıklığı Karşılaştırması" başlıklı detaylı akademik rapora aşağıdaki bağlantıdan ulaşabilirsiniz.