|
İÇİNDEKİLER
İçindekiler
Önsöz 7
Teşekkürler 11
1. Kitap
ALGORİTMALARIN TEMELLERİ
Bölüm 1:
Temeller: Algoritmalar = Programlama + Matematik
BİLGİSAYARLAR 31
Bilgisayarın Gelişim Tarihi 31
HESAP, PROGRAMLAMA DİLLERİ VE ALGORİTMALAR 41
Programlama Dilleri 43
Algoritmalar 46
Problem Çözümleme 47
Algoritmik Karmaşıklık 48
Notasyonlar 49
Büyük O Notasyonu 49
Teta Notasyonu 51
Omega Notasyonu 51
Algoritma Analizi 54
Temel Teorem (Master Theorem) 57
Algoritmaların Gösterimi 60
SAYI SİSTEMLERİ 61
İlk Algoritmalar. Çarpma Algoritmaları 62
Karatsuba’nın Çarpım Algoritması 66
Roma Rakamları ile İlgili Algoritmalar 68
Özdeş Dönüşümler 71
İkili Sayı Sistemi. Sayı Sistemlerinin Problem Çözümünde Kullanımı 73
Tartı Problemi 79
Bölüm 2:
Temeller
TEMEL VERİ YAPILARI 87
Diziler 87
Listeler 88
Yığınlar ve Kuyruklar 90
Ağaçlar 93
İkili Ağaç Yapıları ve Ağaçlarda Dolaşma Yöntemleri 94
ÖZYİNELEMELER 97
Fibonacci Sayılarının Özyinelemeli Hesaplanması 101
Özyinelemeli Programlamaya İlişkin Örnekler 105
RASTGELE SAYILAR 119
Rastgele Sayı Üretimi Algoritmaları 121
Kayıt Değişikliği (Shift–Register) Algoritmaları 126
Engel Algoritması 127
Blum Blum Shub Algoritması 128
Belirli Bir (Üssel) Kurala Göre Dağılım Gösteren Rastgele Sayıların Üretimi 131
Bir Rastgele Sayı Üretimi Örneği: Zarlar 134
ÜRETİM FONKSİYONLARI 139
Bölüm 3:
Kümeleme Algoritmaları
KÜME TEORİSİNİN TEMELLERİ 149
Küme İşlemleri ve Kartezyen Çarpım 150
EKLEME–ÇIKARMA İLKESİNE İLİŞKİN ÖRNEKLER 155
KALE POLİNOMLARI 156
KÜMELENDİRME İŞLEMLERİ. GRUPLAŞTIRMA 160
Küme Elemanlarının Düzenlenmesi 160
Tekrarlı Düzenlemeler 161
Permutasyon 162
Tekrarlı Permutasyonlar 166
KOMBİNASYONLAR 167
Tekrarlı Kombinasyonlar 168
NESNELERİN KUTUYA KONULMASI 173
KOMBİNASYONLARIN OLUŞTURULMASI 176
YER DEĞİŞMELER. 181
TERS ARDIŞIKLIĞA GÖRE PERMUTASYONUN OLUŞTURULMASI 185
K– ELEMANLI ALTKÜMELERİN OLUŞTURULMASI 186
KÜMELERİN ALT KÜMELERE PARÇALANMASI 193
2. Türden Stirling ve Bell Sayıları. 193
Catalan Sayıları 196
Catalan Sayılarının Çözümlerin Sayımında Kullanımı 197
n – SIRALI NESNENİN DÜZENSİZLEŞTİRİLMESİ 201
GÜVERCİN YUVASI İLKESİ 204
AKIL USTASI (MASTERMIND) PROBLEMİNİN ÇÖZÜM ALGORİTMASI 207
Bölüm 4:
Sayı Teorisi ve Sayılarla İlgili Algoritmalar
SAYI TEORİSİ 219
MODÜLER ARİTMETİK 219
(ab mod n)‘nin Hesaplanması Algoritmaları 222
Çinlilerin Kalan Teoremi 223
EN BÜYÜK ORTAK BÖLEN – EBOB 226
Bölünürlük 226
EBOB’un Belirlenmesi Algoritmaları 227
SAYILARIN BÖLÜNEBİLME KURALLARI 230
n Haneli Sayı Problemi 234
ASAL SAYILAR 239
Mersenne Sayıları 244
Asallık Testi ve Asal Sayı Bulma Yöntemleri 245
Asallık Testi 245
Asalların Bulunması 247
Eratosthenes Eleği 249
Sezgisel Yöntem 251
Asal Sayı Bulma Yöntemlerinin Karşılaştırılması 253
KRİPTOLOJİ. 255
Klasik Şifreleme Teknikleri 256
Caesar Şifresi 256
Polybius Şifresi 257
Vigenere Şifresi 257
Makineli Şifrelemeler 259
Simetrik Algoritmalar 260
Genel Anahtar Algoritmalar 261
DOĞRUSAL VEYA AFİN ŞİFRELEME 263
RSA GENEL ANAHTAR KRİPTOSİSTEMİ 266
STEGANOGRAFİ 269
SIR PAYLAŞMA 272
Shamir’in Sır Paylaşma Şeması 272
Shamir Yöntemi ile Gizli Görüntü Paylaşımı 274
GÖRSEL ŞİFRELEME 276
LUHN ALGORİTMASI. KART NUMARASININ DOĞRULANMASI 277
ÖZEL SAYILAR VE SAYILARLA İLGİLİ ALGORİTMİK PROBLEMLER 279
Mükemmel Sayılar 285
Kaprekar Sayıları 288
(3n+1) Problemi (Collatz Problemi) 289
Steinhaus Çevrimi 290
196–Problemi 290
1089 Sayısı 292
Armstrong Sayıları 292
2997 Sayısı 294
Tam Değerli (Diophantine) Denklemler ve Erdös–Straus Varsayımı 294
Bölüm 5:
Altın Kesit ve Fibonacci Sayıları
ALTIN KESİT VE FİBONACCİ SAYILARI 299
ALTIN ORAN 299
FİBONACCİ ALGORİTMASI VE FİBONACCİ SAYILARI 303
FİBONACCİ SAYILARI 304
ALTIN ORANLA FİBONACCİ SAYILARI ARASINDAKİ BENZERLİK 309
ALTIN DİKDÖRTGEN 310
FİBONACCİ SAYILARININ BİLGİSAYARLI HESAPLANMASI 310
LİNEER HOMOJEN YİNELEMELİ İLİŞKİLERİN SABİT KATSAYILARIYLA ÇÖZÜMÜ. FİBONACCİ SAYILARI İÇİN GENEL İFADENİN BULUNMASI 314
LUCAS SAYILARI 316
ALTIN DİZİ 316
FİBONACCİ SAYILARININ UYGULANMASINA İLİŞKİN ÖRNEKLER 323
THUE–MORSE ARDIŞIKLIĞI 327
Bölüm 6:
Graf Teorisi ve Graflarla İlgili Algoritmalar
GRAFLAR VE GRAFLARLA İLGİLİ PROBLEMLER 331
GRAFLARIN BİLGİSAYARDA GÖSTERİMİ 334
GRAFLARIN SAYIMI 338
VERİLEN DERECELERE UYGUN GRAFLARIN ÇİZİLMESİ 346
GRAFLARDA ARAMA ALGORİTMALARI 348
Derinine Arama Algoritması 348
Enine Arama Algoritması 350
EULER YOLLARI 353
MİNİMUM YOL PROBLEMİ 359
GEZGİN SATICI PROBLEMİ VEYA HAMİLTON DÖNGÜLERİ 364
Açgöz Algoritmalarla Gezgin Satıcı Probleminin Çözümü 367
En Yakın Komşu Algoritmasına Göre Gezgin Satıcı Probleminin Çözülmesi 368
GRAFLARDA DÖNGÜLER. MİNİMUM AÇILIM AĞAÇLARI. 371
1. Kruskal Algoritması 376
2. Prim Algoritması 377
3. Boruvka (Sollin) Algoritması 379
4. Tersine Çıkarma (Reverse–Delete) Algoritması 381
STEİNER NOKTASI VE STEİNER AĞAÇLARI 382
GRAFLARDA KÜMELENDİRME ALGORİTMALARI 385
Boş Altgrafların Bulunulması Algoritması 387
RENKLEME PROBLEMİ 391
Welch–Powel Renkleme Algoritması 392
Renklendirme Problemi İçin Sezgisel Algoritma 393
İKİ PARÇALI GRAFLAR VE BU GRAFLARIN EŞLEŞTİRİLMESİ 398
Maksimum Eşleştirme Algoritması Veya Evlenme Problemi 401
MODERN ÜRETİM ZİNCİRİNDE İŞLERİN YAPILMA SIRASI 408
DEDİKODU PROBLEMİ 411
MEYVE BAHÇESİ PROBLEMİ 414
ÜÇ KAP PROBLEMİ 418
KÜPLER PROBLEMİ 421
Bölüm 7:
Sıralama Algoritmaları
SIRALAMA ALGORİTMALARI 427
Sıralama (Sortıng) 427
Yerleştirmeli Sıralama (Insertıon Sort) 429
Direkt Yerleştirmeli Sıralama (Straight Insertion Sort) 429
İkili Yerleştirmeli Sıralama (BINARY ınsertıon sort) 430
Seçmeli Sıralama (Selectıon Sort) 431
Kabarcık Sıralaması (Bubble Sort) 432
Hızlı Sıralama (Quıck Sort) 433
Geliştirilmiş Hızlı Sıralama (Enhanced Quick Sort) 435
Özyinelemeli Olmayan Hızlı Sıralama (Non–Recursıve Quıck Sort) 437
Birleştirme (Merge) İşlemi 439
Birleştirmeli Sıralama (Merge Sort) 440
Yerleşik Birleştirmeli Sıralama (In Place Stable Merge Sort) 441
Bağlı Listeyle Birleştirme (Lınked–Lıst Merge) 444
Bağlı Listeyle Birleştirme Sıralaması (Lınked–Lıst Merge Sort) 444
Aşağıdan Yukarıya Birleştirme Sıralaması (Merge Bottom–Up) 445
İkili Ağaç Sıralaması (BINARY TREE SORT) 447
Kümeleme Kullanarak Sıralama (Heap Sort) 449
Direkt Basamaklı Sıralama (Straight Radix Sort) 450
Basamaklı Yer Değiştirme Sıralaması (Radix Exchange Sort) 451
Dağıtmalı Sıralama (Distribution Sort) 452
Güvercin Yuvası Sıralaması (Pigeon Hole Sort) 453
İki Yönlü Kabarcık Sıralaması (Shaker Sort) 454
İki Yönlü Kabarcık Sıralaması – 2 (Shaker2 Sort) 455
Asansör Sıralaması (Elevator Sort) 456
Tek–Çift Yer Değiştirmeli Sıralama (Odd–Even Transposıtıon) 457
Shell Sıralaması (Shell Sort) 458
Topolojik Sıralama 459
SIRALAMA ALGORİTMALARININ ANALİZİ 460
Bölüm 8:
Matematiksel Uygulamalar
HORNER ŞEMASI İLE POLİNOMLARIN HESAPLANMASI 465
KÖKÜN GEOMETRİK OLARAK BULUNMASI 467
KÖKÜN ANALİTİK YOLLA BULUNMASI 469
Kübik Denklemlerin Köklerinin Hesaplanması 470
4. dereceden denklemlerin çözümü 472
KÖKÜN SAYISAL YÖNTEMLERLE BULUNMASI 475
Yarıya Bölme Yöntemi 476
BABİL KAREKÖK BULMA YÖNTEMİ 477
Tekrarlamalı Yöntem 477
Karekökün Sayısal Olarak Hesaplanması 479
RASYONEL SAYILARIN SÜREKLİ KESİRLERLE GÖSTERİLMESİ 482
SERİLER. SONLU VE SONSUZ SERİ TOPLAMLARININ HESAPLANMASI 486
2. Kitap
KOMBİNATOR ALGORİTMALAR
Bölüm 9:
Labirentlerle İlgili Algoritmalar
LABİRENTTE YOLUN BULUNMASI PROBLEMİ 495
LABİRENTTE YOLUN BULUNMASINA İLİŞKİN YAKLAŞIMLAR 496
Derinine Arama 496
Dalga Algoritması 497
Sezgisel Yaklaşım 499
TEK YOLLU LABİRENTİN ÇİZİLMESİ 500
İKİ NOKTA ARASINDAKİ KESİŞMEYEN YOLLARIN BULUNULMASI 504
LABİRENTTE SİHİRLİ SAYILAR 514
Bölüm 10:
Geometrik Algoritmalar
GEOMETRİK ALGORİTMALAR 517
NOKTALAR, DOĞRULAR VE POLİGONLAR 517
Basit Kapalı Yolun Bulunması 521
Koordinatlarına Göre Üçgenin Alanının Hesaplanması 523
VORONOİ VE DELAUNAY GRAFLARI 524
Voronoi Diyagramı 524
Delaunay Poligonları 525
Voronoi Diyagramının Böl ve Yen Algoritmasına Göre Çizimi 526
NOKTANIN BÖLGEYE AİT OLMASININ BELİRLENMESİ. İZ SÜRME ALGORİTMASI 530
VERİLEN TÜM NOKTALARI İÇİNE ALAN EN KÜÇÜK YARIÇAPLI ÇEMBERİN BULUNMASI 532
Sırlı Çemberler 532
MİNİMUM KUŞATMA ÇEMBERİ 534
Minimum Kuşatma Çemberi Algoritması 536
EN KÜÇÜK KAPALI ÇEVRİMİN BULUNMASI ALGORİTMASI 539
RAMER–DOUGLAS–PEUCKER ALGORİTMASI 543
FRAKTAL GEOMETRİ 545
1. Geometrik Fraktallar 548
1.1. Koch Fraktalı 548
1.2. Ejderha Eğrisi 551
1.3. Sierpinski Üçgeni 554
2. Cebirsel Fraktallar 555
Mandelbrot Fraktalı 555
Julia Fraktalı 556
3. Stokastik Fraktallar 557
L–SİSTEM 558
KAOS OYUNU 559
KUTUPSAL KOORDİNATLAR 560
1. Kardiod (Cardiod) 563
2. Episikloid (Epicycloid) 563
3. Epitrokoid (Epitrochoid) ve Hipotrokoid (Hypotrochoid) 564
BEZİER EĞRİLERİ 566
KÜRESEL KOORDİNAT SİSTEMİ. UV HARİTALAMA 570
GÜZEL SANATLAR GALERİSİ PROBLEMİ 572
İŞBİRLİKÇİ BEKÇİLER PROBLEMİ 575
MONGE,MORLEY, MALFATTİ TEOREMLERİ 577
Monge’nin Çember Teoremi 577
Morley Teoremi ve Malfatti çemberleri 577
Bölüm 11:
Paketleme Problemleri
PAKETLEME PROBLEMLERİ 581
KARE PAKETLEMESİ 582
ÜÇGEN KAPLAMA 584
ÇEMBER PAKETLEME 585
GİYOTİN PROBLEMİ 590
KARE KARELEME VEYA MÜKEMMEL KARELER 595
Bölüm 12:
Aralık Sorgulaması ve kD–Ağaçlar
ARALIK SORGULAMASI VE KD–AĞAÇLAR 613
Tek Boyutlu Aralık Sorgulamaları. 613
Sayı Bulmaca Problemi 614
kD Ağaçları 617
NOKTALARIN ARALIKLARA DENGELİ DAĞILIMI 620
N ARALIKLI PARÇAYA N SAYININ DENGELİ YERLEŞTİRİLMESİ PROBLEMİ 623
NOKTA RANKININ VE MAKSİMUM NOKTALARIN BULUNMASI PROBLEMİ 624
DÜZLEMDE KAPALI ÇİFTLER PROBLEMİ 627
Bölüm 13:
Parçalanma Problemleri
SAYILARIN PARÇALANMASI 631
Problem Tanımı ve Grafiksel Gösterim. 631
Parçalanma Problemi Çeşitleri 633
SAYI PARÇALANMASI İLE İLGİLİ ALGORİTMALAR. 636
PARA PROBLEMLERİ VE ALGORİTMA DEĞERLENDİRİLMESİ 642
n–Para Problemi ile Algoritma Sınıflandırılması 651
8 Para Problemi 657
PARA PROBLEMİ 659
J.STEİNER’İN PASTA PROBLEMİ VEYA ÇEMBERİN BÖLGELERE AYRILMASI 660
Bölüm 14:
Boole Cebriyle İlgili Algoritmik Problemler
BOOLE CEBRİNİN TEMELLERİ 667
AYRIK SİSTEMLER İÇİN METRİK SINIFLANDIRMA 668
Metrik Özellik Vektörü 674
NP KARAKTERLİ PROBLEMLERİN ÇÖZÜMÜNDE GORBATOV’UN KARAKTERİSTİK ANALİZİNİN KULLANIMI 678
Semantik Eşitleme Yardımıyla Problem Çözümü 679
Bölüm 15:
Problem Analizi
PROBLEM ANALİZİ 687
DOMİLO 687
Durum Araştırması veya Domino Kaplama 689
Problemin Modellenmesi 691
SÖZCÜK YAKALAMA 696
ÇOK PARAMETRELİ PARÇALANMA VEYA LİG PROBLEMİ 699
TURNUVA ÇİZELGESİNİN DÜZENLENMESİ 699
Problem Tanımı 705
Lig Problemine Genel Bakış 706
Problem Doğrulama 708
Bölüm 16:
Kombinator Algoritmalar
KOMBİNATOR ALGORİTMALAR 719
POLİOMİNOLAR VEYA KARE HAYVANLAR 719
Problemler 726
LATİN KARELERİ 728
LATİN DİKDÖRTGENLERİ 730
36 Subay Problemi 734
Milli Takım Problemi 734
ŞEBEKE PROBLEMLERİ 734
Şebeke İncelenmesi 734
Matematiksel Tümevarım İlkesi 737
Dikdörtgen Kaplama 739
SUDOKU SAYISAL BULMACASI VE FUTOSHIKI 742
Futoshiki 745
SİHİRLİ KARELER 747
Tek Dereceli Karelerin Yazılması 749
Çift Dereceli Sihirli Karelerin Yazılması 752
SİHİRLİ KARE ÇEŞİTLERİ 753
Asal Sihirli Kareler 755
Sihirli Çarpma Kareler 755
Şeytani Kareler veya Dürer’in Sihirli Kareleri (1514). 756
Sihirli Küpler 757
Sihirli Çemberler. 758
Sihirli Graflar. 759
8 Vezir Problemi ve Sihirli Kareler. 759
SİHİRLİ MATRİSLER 761
EBEDİ TAKVİM ALGORİTMALARI 766
Ebedi Takvim: Algoritma 1. 767
Ebedi Takvim: Algoritma 2. 768
Ebedi Takvim: Algoritma 3. 770
Bölüm 17:
Optimizasyon Algoritmaları
LİNEER PROGRAMLAMA. SİMPLEKS YÖNTEMİ 775
TAŞIMACILIK PROBLEMİ 780
DİNAMİK PROGRAMLAMA 783
Süreç Planlama 784
Dinamik Programlama Yardımıyla Matrisler Zinciri Çarpımı Probleminin Çözümü 786
En Uzun Ortak Altdizinin Bulunması Problemi 795
Uzaklık Ayarlanması 799
Sırt Çantası (Knapsack) Problemi 803
Bölüm 18:
Oyunlar ve Oyunlarda Arama Algoritmaları
OYUNLARDA ARAMA ALGORİTMALARI 811
Minimaks Yöntemi 814
Alfa–Beta (Algoritması 815
n–TAŞ PROBLEMİ VE A* ALGORİTMASI 817
JOSEPHUS PROBLEMİ 824
Probleme Genel Bakış 828
LAMBALARIN YAKILMASI PROBLEMİ 831
Problem Tanımı 832
Çözüm Stratejisi 833
OYLAMA VE OY SAYMA YÖNTEMLERİ 837
Oylama Yöntemleri 838
Basit Çoğunluk Yöntemi 838
Çoğunluk Yöntemi 839
Borda Sayısı Yöntemi 840
Condorcet Kriteri 840
Hare Yöntemi 842
Onaylamalı Yöntem 842
Sıralı Çiftler Halinde Karşılaştırma Yöntemi (Eleme Usulü) 843
Sonsöz 845
EKLER 847
EK–1: Programlama Dillerinin Kısa Kronolojisi 847
EK–2: Tam ve Kesir Kısımlar. Bazı Önemli Bağıntılar 849
EK–3: Seriler 850
EK–4: Bazı Önemli Tarihler 853
Kaynaklar 855
Kavramlar Dizini 865
Kapaktaki Simgelerle İlgili Kısa Bilgi 871 |
Bilgisayar, Teknoloji Kitapları 
