Veri Yapıları ve Algoritmalar

Veri yapıları ve algoritmalar, program tasarımında, çoğu zaman eksikliği hissedilen önemli bir konu; yalnız başına bir programlama dili veya aracı bilmek etkin bir program geliştirmeye yetmemektedir denilebilir. Bu çeşitli veri yapıları veveri modelleri ele alınmakta, onlara ait algoritmik ifadeler incelenmekte ve uygulama örnekleri verilmektedir. Bu dersi tamamladıktan sonra,

Bilgisayar yazılım dünyasına ait bazı kavramlar, terimler ve sözcükleri
Bilgilerin bilgisayar belleğinde tutulması yöntemlerini
Bağlantılı liste, ağaç, graf gibi çeşitli veri modellerini
Programların bellek gereksinimi ve çalışma hızlarının hesabını
Temel yazılım nesnelerinin tasarımını
Arama ve sıralama algoritmalarını
Durum makinaları ve gramer çözümlemeyi

öğrenmiş olacağız.

Kısacası Veri yapıları ve algoritmalar, hazır program geliştirme araçları kullanılıyor olsa bile, üzerinde durulması gereken önemli bir konudur. Algoritmik düşünce sistemine geçilmediği sürece ciddi program tasarımları yapılması oldukça güçtür denilebilir. Program tasarımı ve algoritmik düşünce tarzı bir yaşam biçimi olmaktadır.

BÖLÜM 1 – Veri Yapıları ve Algoritmalarına Giriş

1.1 Yazılım ve Program
1.2 Donanım ve Bellek
1.3 İşletim Sistemi
1.4 Veri Yapısı ve Veri Modeli
1.5 Algoritma
1.6 Programın Bellek Gereksinimi ve Çalışma Hızı
1.7 İşlemci, Makina Kodu ve Assembly Dili
1.8 Programlama Dilleri
1.9 Veritabanı ve SQL
1.10 Böl ve Yönet Yaklaşımı
1.11 Network Yazılımı/Programlaması
1.12 Kıyaslama (Benchmarking)
Bölüm Özeti
Değerlandirme Soruları

BÖLÜM 2 – Veri Yapıları (Data Structures)

2.1 Ham Veriden Bilgiye Dönüşüm
2.2 Veri Yapılarının Sınıflandırılması
2.3 Bilgisayarın İç Belleği
2.4 Temel Veri Yapıları
2.4.1 Karakter (ASCII, Ünikod)
2.4.1.1 Ünikod (Unicode)
2.4.2 Tamsayı (Dogal, 1’e Tümleyen, 2’ye Tümleyen, BCD)
2.4.2.1 İşaretsiz (Unsigned Integer) ve İşaretli Tamsayı (Signed Integer)
2.4.2.2 Tamsayıların Uzunluğu ve Boyları
2.4.3 Kesirli Sayı (Kayan Noktalı-IEEE 754)
2.4.3.1 Kayan Noktalı Sayı Formatı & IEEE 754
2.4.4 Karakter Katarı/Sözcük
2.4.5 Dizi/Matris
2.5 Tanımlamalı Veri Yapıları
2.5.1 Topluluk (Struct) Oluşturma
2.5.2 Ortaklık (union) Oluşturma
2.5.3 bit Düzeyinde Erişim

Değerlendirme Soruları

BÖLÜM 3 – Veri Modelleri

3.1 Veri Modelleri
3.1.1 En Çok Bilinen Veri Modelleri
3.2 Liste ve Bağlantılı Liste Veri Modeli
3.3 Ağaç Veri Modeli
3.4 Graf Veri Modeli
3.5 Durum Makinası Veri Modeli
3.6 Veritabanında İlişkisel Veri Modeli
3.7 Ağ (Network) Veri Modeli
Değerlendirme Soruları

BÖLÜM 4 – Algoritmik Program Tasarımı

4.1 Program Tasarımı
4.1.1 Program Tasarım Şemaları
4.2 Algoritma Tasarımı
4.2.1 Kaba-kod (PseudoCode) ve Gerçek Kod
4.3 Akış Şemaları
4.3.1 Algoritma ve İlişki Tanımlamasi için Çeşitli Yöntemler
4.3.1.1 Koşullu Dallanma Simgesi
4.3.1.2 Döngü Simgesi
4.3.1.3 İçiçe Döngü Kullanılması
4.3.2 N-S (Nassi-Schnederman) Şemaları
4.3.3 W-O (Warnier-Orr) Diyagramları
4.4 Çeşitli Akış Şeması Örnekleri
4.4.1 Faktöriyel Hesabı
4.4.2 Para Getirisi Hesabı
4.4.3 İkinci Dereceden Denklemin Kökleri
4.4.4 N Adet Sayının Aritmetik Ortalaması
4.4.5 Dizinin En Küçük (Veya En Büyük) Elemanını Bulma

Değerlendirme Soruları

BÖLÜM 5 – Program Çalışma Hızı ve Bellek Gereksinimi

5.1 Temel Kavramlar
5.2 Program Çalışma Hızı ve Karmaşıklık: Kıyaslama ve Algoritma Analizi
5.2.1 Yürütme Zamanı (Running Time)
5.2.1.1. Aritmetik Ortalama için T(n) Hesabı
5.2.1.2. En Küçük Eleman Bulma için T(n) Hesabı
5.2.1.3. Matris Toplama için T(n) Hesabı
5.2.2. Karmaşıklık (Complexity)
5.2.2.1 Yürütme Zamanı ve Karmaşıklık Hesabı
5.3. Programın Bellek Gereksinimi
5.3.1. Program Büyüklüğü
5.3.2. Veri Alanı
5.3.3. Yığın Bellek Gereksinimi
Örnek: Bellek Miktarı Hesabı
5.4. Asimtotik Notasyonlar
Örnek: Büyük O Notasyonu Hesabı
Bölüm Özeti
Değerlendirme Soruları

BÖLÜM 6 – Bağlantılı Listeler

6.1. Bağlantılı Liste (Linked List)
6.1.1. Bağlantılı Liste ile İlgili Kavramlar
6.1.2. İşaretçi Değişkenler ve Bağlantılı Liste
6.2. Bağlantılı Listelerin Bellekte Tutulma Biçimleri
6.3. Ayrık Alanlarda Bağlantılı Liste Uygulaması
6.3.1. Ekleme İşlemi
6.3.2. Listeleme İşlemi
6.3.3. Arama İşlemi
6.3.4. Silme İşlemi
6.4. Tek Yönlü Bağlantılı Liste Uygulaması
6.5. Dizi Üzerinde Bağlantılı Liste
6.5.1. Dizi Üzerinde Bağlantılı Listeye Ekleme
6.6. İki Yönlü Bağlantılı Liste Uygulaması (double linked list)
6.6.1. İki-Yönlü Listeye Ekleme İşlemi
6.6.2. İki-Yönlü Listede Listeleme İşlemi
6.6.3. İki-Yönlü Listede Arama İşlemi
6.6.4. İki Yönlü Listede Silme/Listeden Çıkarma İşlemi
6.7. Listeyi Dosyada Saklamak
Proje Çalışması
Bölüm Özeti
Çalışma Soruları
Değerlendirme Soruları

BÖLÜM 7 – Ağaç Veri Modeli

7.1. Ağaç Veri Modeli Temel Kavramları
7.1.1. Ağaç Veri Modeline İlişkin Tanımlar
7.2. Ağaç Türleri
7.3. Ağaç Üzerinde Yapılan İşlemler
7.4. Ağaçların Bellekte Tutulması
7.4.1. Düğüm Bağıntısıyla Ağaç Kurulması/Veri Yapısı
7.4.2. İndis Bağıntısıyla Ağaç Kurulması/Veri Yapısı
7.4.2.1 İndis Bağıntısı Yönteminin Olumlu/Olumsuz Yanları
7.5. Dengeli Ağaç ve AVL Ağaç Yapısı
7.6. Kümeleme Ağacı (Heap Tree)
7.7 Trie Ağacı/Sözcük Ağacı
7.8. Kodlama ve Kodlama Ağaçları
7.8.1 Kodlama Ağaçları Üzerine Teoremler
7.8.2. Huffman Kodlama Ağacı
7.8.3. Shanno-Fano Kodlama Ağacı
7.9. Çeşitli Ağaç Şekilleri
7.9.1. Aile İşaretçisi Ağacı (Parent Pointer Tree)
7.9.2. Komut Çözme Ağacı
Bölüm Özeti
Çalışma Soruları
Değerlendirme Soruları

BÖLÜM 8 – İkili Ağaçlar (Binary Trees)

8.1. İkili Ağaç Yapıları
8.2. İkili Ağaç Üzerinde Dolaşma/Düğümlere Erişim
8.2.1. İkili Ağaç Üzerinde Dolaşma/Düğümlere Erişim – 2
8.2.2. İkili Ağaç Üzerinde Dolaşma/Düğümlere Erişim – 3
8.3. Bağıntı Ağaçları (Expression Trees)
8.3.1. İç-Takı, Ön-Takı ve Son-Takı
8.4. İkili Arama Ağaçları için Algoritmalar
8.4.1. İkili Arama Ağacına Ekleme Algoritması
8.4.2. İkili Arama Ağacında Dolaşma Algoritmaları
8.4.3. İkili Arama Ağacında Arama Algoritması
8.4.4. İkili Arama Ağacından Düğüm Silme Algoritması
Bölüm Özeti
Çalışma Soruları
Değerlendirme Soruları

BÖLÜM 9 – Yığın ve Kuyruk Yapısı

9.1. Yığın ve Kuyruk Veri Modellerine Giriş
9.1.1. Yığın ve Kuyruk İşlevleri
9.2. Yığın Tasarımı
9.2.1. Dizi Üzerinde Yığın Tasarımı
9.2.1.1. Dizi Üzerinde Yığın Uygulama Örneği
9.2.2. Bağlantılı Listeyle Yığın Tasarımı
9.2.2.1. Bağlantılı Listeyle Yığın Uygulama Örneği
9.3. Kuyruk Tasarımı
9.3.1. Dizi Üzerinde Kaydırmalı Kuyruk
9.3.2. Dizi Üzerinde Çevrimsel Kuyruk
9.3.2.1. Dizi Üzerinde Çevrimsel Kuyruk Uygulaması
9.3.3. Bağlantılı Listeyle Kuyruk Tasarımı
9.4. Öncelikli Kuyruk Çözümleri
9.4.1. Kümeleme Ağacıyla Öncelikli Kuyruk
Bölüm Özeti
Çalışma Soruları
Değerlendirme Soruları

BÖLÜM 10 – Sıralama Algoritmaları

10.1. Sıralama Algoritmalarına Giriş
10.2. Sıralama Algoritmaları Temel Kavramları
10.2.1. Dizinli Dosya Yapısı
10.3. Araya Sokma (Insertion) Sıralaması
10.3.1. Araya Sokma Sıralaması Uygulaması
10.4. Seçmeli Sıralama (Selection Sort)
10.5. Kabarcık Sıralaması (Bubble Sort)
10.5.1. Kabarcık Sıralaması Uygulaması
10.6. Birleşmeli Sıralama (Merge Sort)
10.7. Kümeleme Sıralaması (Heap Sort)
10.8. Hızlı Sıralama (Quick Sort)
10.8.1. Hızlı Sıralama Uygulaması

Çalışma Soruları
Değerlendirme Soruları

BÖLÜM 11 – Arama Algoritmaları

11.1. Arama Üzerine Temel Kavramlar
11.1.1. Dahili ve Harici Aramalar
11.1.2. Aramalarda Anahtar Sözcükler
11.2. Ardışık veya Doğrusal Arama
11.2.1. Dizi Üzerinde Ardışık Arama Yapma
11.2.2. Ardışık Aramada Yürütme Zamanı Hesabı
11.3. İkili Arama
11.3.1. Sıralı Dizide İkili Arama
11.3.1.1. Sıralı Dizide İkili Arama Fonksiyonu
11.3.2. İkili Ağaç Üzerinde İkili Arama
11.3.2.1. İkili Ağaç Üzerinde İkili Arama Fonksiyonu
11.4. Çırpı Fonksiyonu
11.4.1. Çırpı Fonksiyonu Örneği
11.4.2. Çırpı Fonksiyonda Çatışmaların Çözümlemesi
11.4.2. Çatışma ve Yükleme Faktörü

BÖLÜM 12 – Graf Veri Modeli

12.1. Graf Veri Modeline Giriş
12.2. Graflar Üzerine Temel Tanımlar
12.2.1. Graflar Üzerine Temel Tanımlar – 1
12.2.2. Graflar Üzerine Temel Tanımlar – 2
12.2.3. Graflar Üzerine Temel Tanımlar – 3
12.2.4. Graflar Üzerine Temel Tanımlar – 4
12.2.5. Graflar Üzerine Temel Tanımlar – 5
12.2.6. Graflar Üzerine Temel Tanımlar – 6
12.3. Grafların Bellek Üzerinde Tutulması
12.3.1. Grafların Bellek Üzerinde Tutulması Örneği
12.4. Greedy Yaklaşımı
12.4.1 Greedy Yaklaşımı Uygulaması Kaba-kodu
12.5. Graf Üzerinde Dolaşma
12.5.1. DFS Yöntemi
12.5.2. BFS Yöntemi
12.6. Graf Renklendirme
12.6.1. Graf Renklendirme Örneği
12.7. Çeşitli Graf Algoritmaları
12.7.1. Dijkstra’nın Algoritması
12.7.1.1. Dijkstra’nın Algoritması Davranışı
12.7.2. Kruskal’ın Algoritması
12.7.2.1. Kruskal Algoritmasının Kaba-Kodu

Çalışma Soruları

Hazırlayan: Alper ÖZÇELİK Ahmet Yesevi Üniversitesi – Emeği geçen hazırlayan kişilere teşekkürler

Not: Flash programının fişi çekildi artık geliştirilmiyor ve desteklenmiyor. Dosyada görsel anlatımlarda flash animasyonları kullanılıyor index.html dosyasını ücretsiz ve kurulumsuz “Basilisk” tarayıcı ile açıp animasyonları görüntüleyebilirsiniz. Basilisk tarayıcısını indirmek için Tıklayınız.