Dersi Veren Fakülte \ Bölüm
Mühendislik Fakültesi \ Bilgisayar Mühendisliği
Kredi
AKTS
Ders Türü
Öğretim Dili
Bilgisayar Mühendisliği
Yapay Zeka Mühendisliği
Bu ders verimli bilgisayar algoritmaları tasarlamak, bunların doğruluğunu kanıtlamak ve çalışma sürelerini analiz etmek için gerekli teknikleri kapsar.
Konular arasında sıralama ve seçme algoritmaları, algoritma tasarım teknikleri: böl ve yönet, açgözlü algoritmalar, dinamik programlama, ve grafik algoritmaları (minimum kapsayan ağaçlar, en kısa yol) yer alır.
Ders Kitapları ve/veya Kaynaklar
Introduction to Algorithms. Third Edition. By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. McGraw-Hill.
Algorithm Design. By Jon Kleinberg and Eva Tardos. Addison Wesley.
Bu dersin amacı, temel algoritma tasarım paradigmalarını ve bu paradigmaları kullanan örnek problemleri öğretmektir. Derste, algoritmaların doğruluğunun kanıtlanması ve çalışma sürelerinin analiz edilmesi konularına özellikle vurgu yapılmaktadır.
1. Sıralama ve seçme içeren problemleri çözer.
2. Uygun bir problemi çözmek için böl ve yönet algoritması geliştirir.
3. Uygun bir problemi çözmek için açgözlü algoritma geliştirir.
4. Uygun bir problemi çözmek için dinamik programlama kullanarak algoritma geliştirir.
5. Tek kaynaklı ve tüm ikililer arası en kısa yollar, topolojik sıralama ve minimum kapsayan ağaç algoritmaları dahil olmak üzere temel grafik algoritmalarını kullanarak problemleri çözer.
1. Hafta: Asimptotik analiz, toplamlar, özyinelemeli ilişkiler, Insertion Sort
2. Hafta: Böl ve fethet algoritmaları (Mergesort, Inversion Counting, Closest Pair)
3. Hafta: Quicksort, Randomized Quicksort analizi
4. Hafta: Seçme (Selection) algoritması ve analizi
5. Hafta: Lineer zamanlı sıralama, Counting Sort, Radix Sort
6. Hafta: Açgözlü algoritmalar (Exchange Argument, Interval Scheduling, Fractional Knapsack, Minimizing Maximum Lateness, Huffmann Coding)
7. Hafta: Çizge gösterimleri, temel çizge algoritmaları (DFS, BFS)
8. Hafta: DFS uygulamaları (Articulation Points and Bridges, Strongly Connected Components, Topological Sorting)
9. Hafta: En küçük kapsayan ağaç algoritmaları (Kruskal, Prim), Dijkstra'nın en kısa yol algoritması
10. Hafta: Dinamik Programlama I (Weighted Interval Sch., Memoization, Iteration over Subproblems, Longest Common Subsequnce, Matrix Chain Multiplication)
11. Hafta: Dinamik Programlama II (0-1 Knapsack, Floyd-Warshall’ın Tüm-ikililer En Kısa Yol Algoritması)
12. Hafta: NP-Completeness
Referans Değerlendime Ölçütleri
• Vize % 40
• Final % 45
• Ödev % 15
|
Program Çıktısı
*
|
| 1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
|
Ders Çıktısı
|
|---|
| 1 |
C, D
|
A, B
|
|
|
|
C
|
B
|
|
|
|
|
| 2 |
C, D
|
A, B
|
|
|
|
C
|
B
|
|
|
|
|
| 3 |
C, D
|
A, B
|
|
|
|
C
|
B
|
|
|
|
|
| 4 |
C, D
|
A, B
|
|
|
|
C
|
B
|
|
|
|
|
| 5 |
C, D
|
A, B
|
|
|
|
C
|
B
|
|
|
|
|