Dönem Ödevi - Dr. Aybars UĞUR

EGE ÜNİVERSİTESİ
MÜHENDİSLİK FAKÜLTESİ
BİLGİSAYAR MÜHENDİSLİĞİ BÖLÜMÜ
BIM106 ALGORİTMA ve PROGRAMLAMA – II (3+2)
2005-2006 BAHAR YARIYILI
DÖNEM ÖDEVİ : ARAŞTIRMA ve ALGORİTMA GELİŞTİRME
Hazırlayan : Y. Doç. Dr. Aybars UĞUR
Veriliş Tarihi
Teslim Tarihi
: 01.05.2006
: 22.05.2006
Rapor 10 sayfayı geçmemelidir. Raporun yazıcı çıktısı dersin öğretim üyesine teslim
edilecektir. Word belgesi de [email protected] e-posta adresine gönderilecektir. 3 kişi
ortak rapor teslim edilebilir.
Kaynaklardan Bazıları :
http://en.wikipedia.org/wiki/List_of_algorithms
İnternet (google, …)
Dersin sayfasındaki kaynaklar.
Ortak ödevde, aşağıdaki araştırma konularından sadece birisi seçilerek araştırılacak ve
geliştirilecek algoritmalar bölümünden 3 adet seçilip yazılacaktır.
ARAŞTIRMA ÖDEVİ
Aşağıdaki konulardan sadece birisi tercih edilecektir.
1) Sınırların İçini Doldurma (Floodfill veya Boundary Fill) Algoritması (Bilgisayar
Grafikleri)
2) Derinlik Arabelleği (Depth-Buffer veya z-buffer) Algoritması (Bilgisayar Grafikleri)
3) Işın İzleme (Ray Tracing) Algoritması (Bilgisayar Grafikleri)
4) Bresenham'ın Çizgi Algoritması (Bilgisayar Grafikleri)
5) Genetik Algoritmalar (Genetic Algorithms)
6) Karınca Kolonisi (Ant Colony Optimization) Algoritmaları
7) Yapay Sinir Ağları (Neural Networks) : YSA Modelleri, Öğrenme Algoritmaları vb.
8) İşletim Sistemleri (Operating Systems) Algoritmaları
9) Bilgisayar Ağları (Networks) Algoritmaları (Yönlendirme – Routing vs.)
10) A* Algoritması (Yapay Zeka)
11) Sıkıştırma (Compression) Algoritmaları
12) Güvenlik ve Şifreleme (Cryptography) Algoritmaları
13) CRC Algoritmaları (Yazılım Mühendisliği)
14) Robotbilim (Robotics) Algoritmaları
15) Paralel İşleme (Paralel Processing) Algoritmaları
16) Diğer (istediğiniz veya bulacağınız herhangi bir konunun uygunluğu için danışınız)
GELİŞTİRİLECEK ALGORİTMALAR
Aşağıdaki sorulardan sadece üç tanesi seçilerek algoritması yazılacaktır. C#/Java/C/C++
benzeri bir algoritma gösterimi, SPARKS veya sözdekod (pseudo code) gösterimleri de kabul
edilebilir.
1) N x N’lik bir bulmacada, bir dizide verilen kelimeleri 8 yönde arayarak bulan algoritmayı
yazınız. Sınırlamalarınızı kendiniz belirtiniz.
2) N x N’lik bir matriste tutulan amiral battı oyunu için, rasgele (random) atama ile ama
birbirini kesmeyecek şekilde, 4 düz yönde gemileri yerleştiren algoritmayı yazınız. Gemiler :
1 tane N-1’lik, 2 tane N-2’lik ve N tane 1 karelik olmak üzere toplam N+3 tane.
3) Sekiz Vezir (Eight Queen) problemini, Kaba-kuvvet (Brute-Force) ile yani tüm olasılıkları
deneyerek çözen algoritmayı yazınız. İşlem sayısını azaltmak için yapılması gerekenler
hakkında önerilerde bulununuz. Sekiz Vezir Problemi, bir satranç tahtasına 8 tane vezirin
birbirini alamayacak şekilde yerleştirilmesini içerir.
4) Gezgin Satıcı Problemini Kaba-kuvvet (Brute-Force) ile yani tüm olasılıkları deneyerek
çözen algoritmayı yazınız. “ TSP (Traveling Salesman Problem) : Given a number of cities
and the costs of traveling from any city to any other city, what is the cheapest round-trip route
that visits each city exactly once and then returns to the starting city? An equivalent
formulation in terms of graph theory is: Given a complete weighted graph (where the
vertices would represent the cities, the edges would represent the roads, and the weights
would be the cost or distance of that road), find a (Hamiltonian Cycle) with the least weight.
(Wikipedia)
5) Verilen bir sayıyı, yazı ile ifade eden algoritmayı yazınız. 19 -> on dokuz gibi.
6) En fazla 5 harfli bir şifre için, bulana kadar tüm şifreleri deneyen algoritmayı yazınız.
7) Simetrik bir matrisi, yarı boyutu ile bir dizide tutan algoritmayı yazınız. Bu yapı üzerinde,
verilen iki matrisi çarpımını yaptırınız.
8) 500x500’lük bir alana, random (x,y) koordinatlarına sahip, random(0-100) yarıçapa sahip n
tane daire şeklinde engeller koyduğunuzu düşünün. Verilen bir konumun engele rastlayıp
rastlamadığını bulan algoritmayı yazınız.
9) Verilen bir metni şifreleyen herhangi bir algoritma yazınız.
10) Verilen bir dosyayı sıkıştıran basit bir algoritma yazınız.
11) Bir yazı, her harfi yerine alfabedeki sıraya göre n harf sonrasındaki harf konularak
şifrelenmiştir. N değeri bilinmemektedir. Şifreyi çözen algoritmayı yazınız.
12) 8 vezir problemini çözen bir genetik algoritma yazınız.
13) İki boyutlu 800x600’lük 256 gri tonlu bir resimde, her gri tonundan kaçar tane olduğunu
bulduran ve histogramını çizdiren algoritmayı yazınız.
14) Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., “Introduction to Algorithms”,
Second Edition, MIT Press, McGraw-Hill, 2001 benzeri kitaplar elinde olanlar (veya
kütüphaneden alıp) konu sonu sorularından da tercih edebilirler.
15) Diğer