Algoritmalara Giriş Pdf Indir
Algoritmalar kitabını Türkçe olarak Bilgisayar kitapları Kategorisi altında PDF olarak indirebilirsiniz. Ayrıca seafoodplus.info arşivlerinden PDF, ePUB, Rar ve Zip formatlarında da indirebilir online olarak okuyabilirsiniz.
Sayfa içindekiler
Algoritmalar KİTAP AÇIKLAMASI
“Bilgisayar biliminin bilgisayarlarla bağlantısı, astronominin teleskoplarla bağlantısından fazla değildir.” E. W. Dijkstra
Bilgisayar bilimlerinin özünü oluşturan algoritma analizi, insanlığın tarih boyunca geliştirdiği, bilgisayar donanımından, programlama dillerinden veya yazılım projelerinden bağımsız, bir işin farklı şekillerde nasıl yapılacağını anlatan, bilgi birikimini oluşturmaktadır. Herhangi bir dilde veya ortamda, herhangi bir amaçla program yazmak isteyen birinin, yazdığı programı daha iyi nasıl yazabileceğini veya yazılabilecek en iyi algoritmayı geliştirdiğini anlaması ancak algoritmayı doğru şekilde analiz etmesi ile mümkün olur. Bu kitap, algoritma analizi kavramlarına giriş yapmanın yanında, programlama ile uğraşan herhangi birinin ihtiyaç duyabileceği çok klasik problemler için de çözüm yollarını sunmakta ve hatta bu çözümlerin Java gibi güncel bir dil üzerinden kodlaması ile ilgili örnekler de vermektedir.
Bilgisayar bilimlerinin ve programlamanın en gizemli ve ilgi çekici konusu olan algoritmalara bu kitapla giriş yapan biri için programlama artık çok farklı bir olguya dönüşecektir.
Algoritmalar KİTABINI PDF, EPUB İNDİR OKU
Algoritmalar yayınını online olarak okumak için indirmeniz gerekmektedir. PDF formatındaki dosyaları Adobe programı ile ePUB formatındaki dosyaları Microsoft EDGE ile açabilir yada kindle&#;ınızda okuyabilirsiniz.
İndirme linkine ulaşabilmek için sosyal medya paylaşım yöntemlerini kullanabilir yada 90 saniye beklemelisiniz. Eğer beklemek istemiyorsanız yada indiremiyorsanız lütfen konuya yorum bırakın
Algoritmalar İLE İLGİLİ TÜRDE FARKLI YAYINLAR
Bilgisayar kitapları türleri hakkında diğer yayınları göz atmak için buradan.
Algoritmalar kitabını PDF, ePUB, RAR, ZIP formatlarında indirmeye çalışırken herhangi bir sorun ile karşılaştıysanız lütfen sorunu anlatan yorumunuzu bırakın.
Konu özeti
- J / J Algoritmalara Giriş (SMA ) Sonbahar
J / J Algoritmalara Giriş (SMA ) Sonbahar
Seviye:
Lisans
Öğretim Üyeleri:
Prof. Charles Leiserson
Prof. Erik Demaine
Çevirmenler:
Prof. Dr. Ali Yazıcı
Haluk ArJ ders kitabının kapağı, Algoritmalara Giriş, İkinci Basım, Cormen, Leiserson, Rivest ve Stein. Ders Özellikleri Ders Videoları
Dersin Ana Başlıkları Bu ders bütün ders notları ve ders videolarını içermektedir. Ders kitabı Prof. Leiserson'ın katkısıyla yazılmıştır.
Dersin Tanımı Bu ders, verimli algoritmaların tasarımı ve çözümlemesi ile ilgili teknikleri, pratikteki kullanımlarını vurgulayarak öğretir. Dersin içerdiği konular: Sıralama, arama ağaçları, yığınlar ve kıyım fonksiyonları, böl ve fethet; dinamik programlama, amortize edilmiş çözümleme, grafik algoritmaları, en kısa yollar, ağ akışı, bilişimsel geometri, sayı teorisi algoritmaları, polinom ve matriks hesaplamaları; ön bellekleme ve paralel hesaplamalardır.
Bu ders aynı zamanda Singapur-MIT Ortaklığı (SMA) programı kapsamında SMA sayılı ders olarak da verilmektedir.
(Algoritmaların Tasarımı ve Çözümlenmesi )
Teknik Gereksinimler
Bu dersteki bazı dosyaları çalıştırmak için özel yazılımlar gerekir: .c, .java.
- Ders İzlencesi
Ders İzlencesi
Ders Saatleri
Ders : 2 oturum / hafta, saat / oturum
Ek ders: 1 oturum / hafta, 1 saat / oturumDersin amaçları ve sonuçları
Dersin amaçları
Bu ders, bilgisayar algoritmalarının çözümlenmesi ve tasarımı konularına bir giriş niteliğindedir. Dersin tamamlanması ile öğrenciler şunları kazandıracaktır:- Algoritmaların doğrusal performanslarının çözümlenmesi
- Temel algoritmalara ve veri yapılarına alışıklık
- Önemli algoritmik tasarım paradigmalarının ve çözümleme metodlarının uygulanması
- Genel mühendislik tasarım alanındaki verimli algoritmaların sentezi
Bu dersi tamamlayan öğrenciler şunları yapmış olacaktır:- Döngü değişmezlerini ve tüme varım yöntemlerini kullanarak algoritmaların doğruluklarını tartışmak
- Asimptotik Çözümlemeyi kullanarak algoritmaların en kötü koşma zamanlarını analiz etmek. Polinomsal, üstsel ve logaritmik fonksiyonların asimptotik davranışlarını kıyaslamak. En iyi, ortalama ve en kötü çözümlemelerin bağlantısını keşfetmek.
- Olasılığa dayalı algoritmaların ortalama durum çalışma zamanlarının çözümlemesini yapmak.
- Rastgele algoritmaların temel özelliklerini açıklamak ve bunları çözümlemek için yöntemleri bulmak. Rastgele bir algoritma olasılığa bağlı olarak girişleri değişen algoritmanın farklarını açıklayabilmek.
- Amortize edilmiş çözümlemeyi kullanarak, uygun yerlerde çözümleme yapmak. Hesaplama metodu ve potansiyel metodu da içeren, amortize edilmiş çözümlemenin farklı stratejilerini tanımlamak.
- Böl ve fethet fikrini tanımlamak ve buna uyan bir algoritmik tasarım durumu hazırlamak. Böl ve fethet algoritmalarını sentezlemek. Bu algoritmaların performanslarını ölçmek.
- Dinamik programlama fikrini tanımlamak ve bunun kullanıldığı tasarım durumunu hazırlamak. Dinamik programlama algoritmalarının sentezini ve çözümlemesini yapmak.
- Aç gözlü fikrini açıklamak ve tasarım durumlarını hazırlamak. Aç gözlü algoritmaların sentezini ve çözümlemesini yapmak.
- Sıralama için başlıca algoritmaları açıklamak. Sıralamada kullanılan algoritmaları sentezlemek. Koşma sürelerinin alt sınırlarını ölçmek ve bu sınırların nasıl aşılabileceğini açıklamak.
- Dinamik kümeleri oluşturmak için gerekli temel veri yapılarını tanımlamak. Varolan veri yapılarını kullanarak yeni veri yapılarını sentezlemek. Veri yapılarını anahtar öğe olarak kullanan algoritmaları sentezlemek.
- Hesap Geometrisi, işlem araştırması, güvenlik ve kripto, paralel ve dağıtılmış sistemler, işletim sistemleri ve bilgisayar mimarisi gibi uygulanmış algoritmik ayarlara alışıklık sağlamak.
Ön Koşullar
Programlamanın iyice anlaşılmış olması ve olasılık teorisi ile ayrık matematik konularında sağlam bir bilgi birikimi bu ders için ön koşuldur.Dersler
Dersler Pazartesi ve Çarşamba günleri saatlik sürelerle işlenecektir. Derslerde sunulan konular ile ilgili sorumlusunuz.Ek Dersler
Öğrenciler her hafta bir saat ek derse katılmak durumundadır. Ek derslerde anlatılan konulardan da sorumlusunuz. Ek derslere katılım ile sene sonu notu arasında daha önceki senelerde görülen doğru orantılı bir ilişki var. Ek dersler, size soru sorabilmeniz ve eğitmenler ile etkileşim sağlamanız için ortam yaratacaktır.Kitap
Bu ders için referans kitabı : Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. 2nd ed. Cambridge, MA: MIT Press. ISBN:
Daha önceki senelerde bu kitabın birinci basımı kullanılıyordu. Ancak 2. basım 1. Basımın geliştirilmiş hali olduğundan, ilk basımı referans kitabı olarak kullanmak uygun değildir. - Takvim
Takvim
Aşağıdaki takvimde, kursun dersleri (L), etütleri (R) ve ara sınavları (Q) ile ilgili bilgiler yer alır. SEANS# KONULAR ANAHTAR TARİHLER L1 İdari Konular
Giriş
Algoritmaların Çözümlenmesi, Araya Yerleştirme Sıralaması, Birleştirme SıralamasıProblem seti 1'in dağıtımı R1 Algoritmaların Doğrulanması
Horner KuralıL2 Asimptotik Simgelem
Yinelemeler
Yerine Koyma, Ana MetotL3 Böl ve Fethet: Strassen, Fibonacci, Polinomsal Çarpım R2 Yinelemeler, Özensizlik (Dağınıklık) L4 Çabuk-sıralama, Rastgele sıralanmış Algoritmalar Problem seti 1'in toplanması
Problem seti 2'nin dağıtımıR3 Yığın Sıralaması, Dinamik Setler, Öncelikli Kuyruklar L5 Doğrusal-zaman Sıralaması: Alt sınırlar, Sayma Sıralaması, Taban Sıralaması L6 Düzen istatistikleri, ortanca R4 Ortanca Uygulamaları
Sepet sıralamasıL7 Kıyımlama, Kıyım Fonksiyonları Problem seti 2'nin toplanması
Problem seti 3'ün dağıtımıL8 Evrensel Kıyımlama, Mükemmel Kıyımlama Laboratuvar ödevi gecesi R5 Ara Sınav 1 gözden geçirme Problem seti 3'ün toplanması Q1 Ara Sınav 1 (sınıfta) R6 İkili Arama Ağaçları, Ağaç yürüyüşleri L9 İkili Arama Ağaçları’nın Çabuk Sıralama ile ilişkisi
Rastgele İkili Arama Ağaçları’nın çözümlemesiProblem seti 4'ün dağıtımı L10 Kırmızı-siyah ağaçlar, Rotasyon(Döndürme), Araya yerleştirme, Silme R7 Ağaçları, B-ağaçları L11 Veri Yapılarını genişletme , Dinamik Sıra İstatistikleri, Aralık ağaçları Problem seti 4'ün toplanması
Problem seti 5'in dağıtımıL12 Atlama Listeleri R8 Menzil Ağaçları L13 Amortize Algoritmalar, Tablo İkileme, Potansiyel Metot Problem set 5'in toplanması
Problem seti 6'nın dağıtımıL14 Rekabetçi çözümlemeler: Kendi kendine organize edilmiş listeler R9 Rekabetçi çözümlemeler: Kayak kiralama, Rastgele Rekabetçi Çözümlemeler L15 Dinamik Programlama, En Uzun Ortak Altdizi Problem seti 6'nın toplanması
Problem seti 7'nin dağıtımıL16 Açgözlü Algoritmalar,Minimum Kapsayan Ağaçlar L17 En kısa yollar I: Özellikler, Dijkstra' nın Algoritması, Enine Arama Problem seti 7'nin toplanması
Problem seti 8'in dağıtımıL18 En kısa yollar II: Bellman-Ford, Doğrusal- Programlama, Fark Kısıtları R10 Grafik Arama: Derinliğine Arama, Topolojik Sıralama, DAG En kısa yollar L19 En kısa yollar III: Tüm-ikili en kısa yollar, Matris Çarpımı, Floyd-Warshall, Johnson Problem seti 8'in toplanması L20 Sınav 2 gözden geçirme L21 Etik, Problem Çözme (Zorunlu Katılım) Ev sınavı 2’ nin dağıtımı Q2 Ara Sınav 2 (sınıfta) Ev sınavı 2’ nin toplanması (Ara sınav 2’den iki gün sonra) L22 Gelişmiş Konular Problem seti 9'un dağıtımı L23 Gelişmiş Konular (devam) Laboratuvar ödevi gecesi R11 Gelişmiş Konular Problem seti 9'un toplanması L24 Gelişmiş Konular (devam) L25 Gelişmiş Konular (devam)
İleri düzey dersleri konusunda tartışmaFinal Sınavı - Okumalar
Okumalar
Aşağıdaki Tablo Ders kitabında olan dersin okuma ödevlerini göstermektedir:
Dersin belirtilen okuma ödevlerine ek olarak Yararlı Başvuru Kaynaklarına da bakınız
SEANS# KONULAR OKUMALAR L1 İdari Konular
Giriş
Algoritmaların Çözümlenmesi, Araya Yerleştirme Sıralaması, Birleştirme SıralamasıBölüm R1 Algoritmaların Doğrulanması
Horner KuralıL2 Asimptotik Simgelem
Yinelemeler
Yerine Koyma, Ana MetotBölüm , hesaba katılmayan kısım L3 Böl ve Fethet: Strassen, Fibonacci, Polinomsal Çarpım Kısımlar ve R2 Yinelemeler, Özensizlik (Dağınıklık) L4 Çabuk-sıralama, Rastgele sıralanmış Algoritmalar Kısımlar
Bölüm 7R3 Yığın Sıralaması, Dinamik Setler, Öncelikli Kuyruklar Bölüm 6 L5 Doğrusal-zaman Sıralaması: Alt sınırlar, Sayma Sıralaması, Taban Sıralaması Kısımlar L6 Düzen istatistikleri, ortanca Bölüm 9 R4 Ortanca Uygulamaları
Sepet sıralamasıKısım L7 Kıyımlama, Kıyım Fonksiyonları Kısımlar L8 Evrensel Kıyımlama, Mükemmel Kıyımlama Kısım R5 Ara Sınav 1 gözden geçirme Q1 Ara Sınav 1 (sınıfta) R6 İkili Arama Ağaçları, Ağaç yürüyüşleri Kısımlar L9 İkili Arama Ağaçları’nın Çabuk Sıralama ile ilişkisi
Rastgele İkili Arama Ağaçları’nın çözümlemesiKısım L10 Kırmızı-siyah ağaçlar, Rotasyon(Döndürme), Araya yerleştirme, Silme Bölüm 13 R7 Ağaçları, B-ağaçları L11 Veri Yapılarını genişletme , Dinamik Sıra İstatistikleri, Aralık ağaçları Bölüm 14 L12 Atlama Listeleri Atlama Listesi çıktısı (PDF) R8 Menzil Ağaçları L13 Amortize Algoritmalar, Tablo İkileme, Potansiyel Metot Bölüm 17 L14 Rekabetçi çözümlemeler: Kendi kendine organize edilmiş listeler Sleator, Daniel D., and Robert E. Tarjan. "Amortized efficiency of list update and paging rules." Communications of the ACM 28, no. 2 (February ): R9 Rekabetçi çözümlemeler: Kayak kiralama, Rastgele Rekabetçi Çözümlemeler L15 Dinamik Programlama, En Uzun Ortak Altdizi Bölüm 15 L16 Açgözlü Algoritmalar,Minimum Kapsayan Ağaçlar Kısımlar and
Bölüm 23L17 En kısa yollar I: Özellikler, Dijkstra' nın Algoritması, Enine Arama Kısım
Bölüm 24L18 En kısa yollar II: Bellman-Ford, Doğrusal- Programlama, Fark Kısıtları R10 Grafik Arama: Derinliğine Arama, Topolojik Sıralama, DAG En kısa yollar Kısımlar L19 En kısa yollar III: Tüm-ikili en kısa yollar, Matris Çarpımı, Floyd-Warshall, Johnson Bölüm 25 L20 Sınav 2 gözden geçirme L21 Etik, Problem Çözme (Zorunlu Katılım) Q2 Ara Sınav 2 (sınıfta) L22 Gelişmiş Konular Dinamik Çoklu-dizilim Algoritması çıktısı (PDF) L23 Gelişmiş Konular (devam) R11 Gelişmiş Konular L24 Gelişmiş Konular (devam) Demaine, Erik D. "Cache-Oblivious Algorithms and Data Structures." To appear in Lecture Notes from the EEF Summer School on Massive Data Sets, a volume of Lecture Notes in Computer Science. Berlin, Germany: Springer-Verlag. L25 Gelişmiş Konular (devam)
İleri düzey dersleri konusunda tartışmaFinal Sınavı Yararlı Başvuru Kaynakları
Aho, Alfred V., John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Reading, MA: Addison-Wesley, ISBN: The classic text, but it lacks topics in network flows and linear programming, as well as more recent algorithms.
———. Data Structures and Algorithms. Reading, MA: Addison-Wesley, ISBN: Revised and more elementary version of the first six chapters of The Design and Analysis of Computer Algorithms.
Baase, Sara. Computer Algorithms: Introduction to Design and Analysis. 2nd ed. Reading, MA: Addison-Wesley, ISBN: General reference, although the exposition is sometimes terse or sketchy.
Bentley, Jon Louis. Programming Pearls. Reading, MA: Addison-Wesley, ISBN: Applications of algorithm design techniques to software engineering.
———. More Programming Pearls: Confessions of a Coder. Reading, MA: Addison-Wesley, ISBN: More applications of algorithm design techniques to software engineering.
———. Writing Efficient Programs. Englewood Cliffs, NJ: Prentice-Hall, ISBN: Performance hacking extraordinaire.
Brassard, Gilles, and Paul Bratley. Algorithmics: Theory and Practice. Englewood Cliffs, NJ: Prentice-Hall, ISBN: Good examples and problems. Focus on methods rather than specific problems.
Chung, Kai Lai. Elementary Probability Theory with Stochastic Processes. New York, NY: Springer-Verlag, ISBN: Intuitive introduction to probability.
Even, Shimon. Graph Algorithms. Rockville, MD: Computer Science Press, ISBN: Broad treatment of graph algorithms, including network flow and planarity.
Feller, William. An Introduction to Probability Theory and Its Applications. 3rd ed. 2 vols. New York, NY: John Wiley & Sons, , ISBN: ISBN: Excellent reference for probability theory.
Garey, Michael R., and David S. Johnson. Computers and Intractibility: A Guide to the Theory of NP-Completeness. San Francisco, CA: W. H. Freeman & Co., ISBN: Reference book devoted to NP-completeness. The second half contains an extensive list of NP-complete problems and references to algorithms in the literature for polynomial-time special cases.
Gonnet, Gaston H. Handbook of Algorithms and Data Structures. Reading, MA: Addison-Wesley, ISBN: X. Code in Pascal and C, comparisons of actual running times, and pointers to analysis in research papers.
Gusfield, Dan. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge, UK: Cambridge University Press, ISBN: General treatment of algorithms that operate on character strings and sequences.
Horowitz, Ellis, and Sartaj Sahni. Fundamentals of Computer Algorithms. Potomac, MD: Computer Science Press, ISBN: Good on data structures, dynamic programming, and branch-and-bound algorithms.
Kingston, Jeffrey H. Algorithms and Data Structures: Design, Correctness, Analysis. Reading, MA: Addison-Wesley Publishing Co., ISBN: A nice introductory book on data structures, with a good chapterchapter on algorithm correctness.
Knuth, Donald E. The Art of Computer Programming. 3rd ed. 3 vols. Reading, MA: Addison-Wesley, ISBN: ISBN: ISBN: Encyclopedic work in three volumes: (1) Fundamental Algorithms, (2) Seminumerical Algorithms, and (3) Sorting and Searching.
Lawler, Eugene L. Combinatorial Optimization: Networks and Matroids. New York, NY: Holt, Rinehart, and Winston, ISBN: Graph algorithms (dense graphs), network flows, and linear programming. First few chapters are excellent.
Liu, Chung L. Introduction to Combinatorial Mathematics. New York, NY: McGraw-Hill, ISBN: Combinatorial mathematics relevant to computer science. Excellent problems.
Manber, Udi. Introduction to Algorithms: A Creative Approach. Reading, MA: Addison-Wesley, ISBN: Elementary text with an emphasis on creativity.
Mehlhorn, Kurt. Data Structures and Algorithms. 3 vols. New York, NY: Springer-Verlag, ISBN: X. ISBN: X. ISBN: Three volumes: (1) Sorting and Searching, (2) Graph Algorithms and NP-Completeness, and (3) Multidimensional Searching and Computational Geometry. Lecture notes on basic and advanced topics.
Niven, Ivan, and Herbert S. Zuckerman. An Introduction to the Theory of Numbers. 4th ed. New York, NY: John Wiley & Sons, ISBN: Readable introduction to number theory.
Papadimitriou, Christos H., and Kenneth Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Englewood Cliffs, NJ: Prentice-Hall, ISBN: Linear programming and its variants.
Press, William P., Brian P. Flannery, Saul A. Teukolsky, and William T. Vetterling. Numerical Recipies in C: The Art of Scientific Computing. Cambridge, UK: Cambridge University Press, ISBN: X. Code for numerical algorithms.
Reingold, Edwin M., Jurg Nievergelt, and Narsingh Deo. Combinatorial Algorithms: Theory and Practice. Englewood Cliffs, NJ: Prentice-Hall, ISBN: X. Good on recurrence relations and binary search trees.
Sedgewick, Robert. Algorithms. 2nd ed. Reading, MA: Addison-Wesley, ISBN: Elementary text with an excellent breadth of topics. Light on analysis, but lots of figures.
Sipser, Michael. Introduction to the Theory of Computation. Boston, MA: PWS Publishing Company, ISBN: X. A good text on computability and complexity theory.
Tarjan, Robert Endre. Data Structures and Network Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, ISBN: Advanced book with tons of good stuff. - Ödevler
Ödevler
Bu bölüm, ekran okuyucu yazılımlarıyla kullanılamayan dökümanları içerir. Bir "#" sembolü, bu tip dökümanları belirtir.
Bu bölümdeki bazı dosyalar .c, ve .java gibi özel yazılımları kullanmayı gerektirir.
Derslerin problem setleri, öğrencilerin çözmesi gereken pek çok egzersiz ve problemi içerir. Öğrenciler sadece problemleri çözüm teslim etmek zorundadırlar ama, ders materyallerinde uzmanlaşmalarına yardımcı olmak adına, egzersizleri çözmeleri de önerilir. Egzersiz sorularının çoğu ders kitabından alınmıştır.
ÖDEVLER ÇÖZÜMLERİ Problem Seti 1 (PDF)# (PDF)# Problem Seti 2 (PDF) (PDF) Problem Seti 3 (PDF) (PDF) Problem Seti 4 (PDF) (PDF) Problem Seti 5 (PDF) (PDF)# Problem Seti 6 (PDF) (PDF)# Problem Seti 7 (PDF)
Model Girdi, seafoodplus.info (TXT)
Model Çıktı, seafoodplus.info (TXT)
Girdi 1, seafoodplus.info (TXT)
Girdi 2, seafoodplus.info (TXT)
Girdi 3, seafoodplus.info (TXT)(PDF)
Kaynak Kodu, seafoodplus.info (JAVA)
Kaynak Kodu, editDistance.c (C)Problem Seti 8 (PDF) (PDF) Problem Seti 9 (PDF) (PDF) - Sınavlar
Sınavlar
Bu kısım ekran okuma yazılımıyla kullanılamayacak dökümanlar içerir. "#" sembolü bu tip dökümanları belirtir.
Bu kısım dersin güncel ve pratik sınavlarını içerir.
1 Algoritmalara Giriş J/J DERS 1 Algoritmaların Çözümlemesi Araya yerleştirme sıralaması Asimptotik çözümleme Birleştirme sıralaması Yinelemeler Prof. Charles E. Leiserson
2 Dersle ilgili bilgiler 1. Öğretim kadrosu. Uzaktan eğitim 3. Ön koşullar 4. Dersler 5. Etütler 6. Ders notları. Ders kitabı 8. Dersin WEB sitesi. Ek destek Kayıt. Problem setleri. Algoritmaları tanımlamak. Not verme politikası Ortak çalışma politikası September, 05 Introduction to Algorithms L1.
3 Algoritmaların çözümlemesi Bilgisayar program başarımı ve kaynak kullanımı konusunda teorik çalışmalar Başarımdan daha önemli ne vardır? modülerlik kullanıcı dostluğu doğruluk programcı zamanı bakım kolaylığı basitlik işlevsellik genişletilebilirlik sağlamlık güvenilirlik September, 05 Introduction to Algorithms L
4 Neden algoritmalar ve başarımla uğraşırız? Algoritmalarla ölçeklenebilirlik anlaşılabilir. Başarım genelde yapılabilir olanla imkansızın arasındaki çizgiyi tanımlar. Algoritmik matematik program davranışlarını açıklamak için ortak dil oluşturur. Başarım bilgi işleme&#;nin para birimidir. Program başarımından alınan dersler diğer bilgi işleme kaynaklarına genellenebilir. Hız eğlencelidir! September, 05 Introduction to Algorithms L
5 Sıralama (sorting) problemi Girdi: dizi a 1, a,, a n sayıları. Çıktı: permütasyon a&#; 1, a&#;,, a&#; n öyle ki a&#; 1 a&#; a&#; n. Örnek: Girdi: Çıktı: September, 05 Introduction to Algorithms L
6 Araya yerleştirme sıralaması (Insertion sort) pseudocode ( sözdekod ) INSERTION-SORT (A, n) A[ n] for j to n do key A[ j] i j 1 while i > 0 and A[i] > key do A[i+1] A[i] i i 1 A[i+1] = key (anahtar) September, 05 Introduction to Algorithms L
7 Araya yerleştirme sıralaması (Insertion sort) pseudocode (sözde kod) INSERTION-SORT (A, n) A[ n] for j to n do key A[ j] i j 1 while i > 0 and A[i] > key do A[i+1] A[i] i i 1 A[i+1] = key A: 1 i j n key (anahtar) sorted (sıralı) September, 05 Introduction to Algorithms L1.
8 Araya yerleştirme sıralaması örneği September, 05 Introduction to Algorithms L
9 Araya yerleştirme sıralaması örneği September, 05 Introduction to Algorithms L1.
10 Araya yerleştirme sıralaması örneği September, 05 Introduction to Algorithms L
11 Araya yerleştirme sıralaması örneği September, 05 Introduction to Algorithms L1.
12 Araya yerleştirme sıralaması örneği September, 05 Introduction to Algorithms L1.
13 Araya yerleştirme sıralaması örneği September, 05 Introduction to Algorithms L1.
14 Araya yerleştirme sıralaması örneği September, 05 Introduction to Algorithms L
15 Araya yerleştirme sıralaması örneği September, 05 Introduction to Algorithms L
16 Araya yerleştirme sıralaması örneği September, 05 Introduction to Algorithms L
17 Araya yerleştirme sıralaması örneği September, 05 Introduction to Algorithms L
18 Araya yerleştirme sıralaması örneği (bitti) September, 05 Introduction to Algorithms L
19 Koşma süresi (Running time) Koşma süresi girişe bağımlıdır: Önceden sıralanmış bir diziyi sıralamak daha kolaydır. Koşma süresinin girişin boyutuna göre parametrelenmesi yararlıdır, çünkü kısa dizileri sıralamak uzun dizilere oranla daha kolaydır. Genellikle, koşma süresinde üst sınırları ararız, çünkü herkes garantiden hoşlanır. September, 05 Introduction to Algorithms L
20 Çözümleme türleri En kötü durum (Worst-case): (genellikle) T(n) = n boyutlu bir girişte algoritmanın maksimum süresi Ortalama durum: (bazen) T(n) = n boyutlu her girişte algoritmanın beklenen süresi. Girişlerin istatistiksel dağılımı için varsayım gerekli. En iyi durum: (gerçek dışı) Bir giriş yapısında hızlı çalışan yavaş bir algoritma ile hile yapmak. September, 05 Introduction to Algorithms L1.
21 Makineden-bağımsız zaman Araya yerleştirme sıralamasının en kötü zamanı nedir? Bilgisayarın hızına bağlıdır: bağıl ( rölatif ) zaman ( aynı makinede), mutlak (absolüt ) zaman (farklı makinelerde). BÜYÜK FİKİR: Makineye bağımlı sabitleri görmezden gel. n &#;ayaklaştıkça, T(n)&#;nin büyümesine bak. " Asimptotik Çözümleme" September, 05 Introduction to Algorithms L
22 Θ- simgelemi (notation) Matematik: Θ(g(n)) = { f (n):öyle c 1, c, n 0 pozitif sabit sayıları vardır ki tüm n n0} için 0 c 1 g(n) f (n) c g(n). Mühendislik: Düşük değerli terimleri at; ön sabitleri ihmal et. Örnek: 3n 3 + 0n 5n = Θ(n 3 ) September, 05 Introduction to Algorithms L1.
23 Asimptotik başarım T(n) n yeterince büyürse, Θ(n ) algoritması bir Θ(n 3 ) algoritmasından her zaman daha hızlıdır. n n 0 Öte yandan asimptotik açıdan yavaş algoritmaları ihmal etmemeliyiz. Gerçek dünyada tasarımın mühendislik hedefleriyle dikkatle dengelenmesi gereklidir. Asimptotik çözümleme düşüncemizi yapılandırmada önemli bir araçtır. September, 05 Introduction to Algorithms L
24 Araya yerleştirme sıralaması çözümlemesi En kötü durum: Giriş tersten sıralıysa. T ( n) = n j= Θ( j) = Θ ( n ) Ortalama durum:tüm permutasyonlar eşit olasılıklı. T ( n) = n j= Θ( j / ) = Θ ( n ) [aritmetik seri] Araya yerleştirme sıralaması hızlı bir algoritma mıdır? Küçük n değerleri için olabilir. Büyük n değerleri için asla! September, 05 Introduction to Algorithms L
25 Birleştirme sıralaması BİRLEŞTİRME-SIRALAMASI A[ n] 1. Eğer n = 1 ise, işlem bitti.. A[ n/ ]ve A[ n/ + n ]&#;yi özyinelemeli sırala. 3. sıralanmış listeyi Birleştir. Anahtar altyordam: Birleştirme September, 05 Introduction to Algorithms L
26 Sıralı iki dizilimi birleştirme 1 September, 05 Introduction to Algorithms L
27 Sıralı iki dizilimi birleştirme 1 1 September, 05 Introduction to Algorithms L1.
28 Sıralı iki dizilimi birleştirme 1 1 September, 05 Introduction to Algorithms L
29 Sıralı iki dizilimi birleştirme 1 1 September, 05 Introduction to Algorithms L1.
30 Sıralı iki dizilimi birleştirme 1 1 September, 05 Introduction to Algorithms L
31 Sıralı iki dizilimi birleştirme 1 1 September, 05 Introduction to Algorithms L
32 Sıralı iki dizilimi birleştirme 1 1 September, 05 Introduction to Algorithms L
33 Sıralı iki dizilimi birleştirme 1 1 September, 05 Introduction to Algorithms L
34 Sıralı iki dizilimi birleştirme 1 1 September, 05 Introduction to Algorithms L
35 Sıralı iki dizilimi birleştirme 1 1 September, 05 Introduction to Algorithms L
36 Sıralı iki dizilimi birleştirme 1 1 September, 05 Introduction to Algorithms L
37 Sıralı iki dizilimi birleştirme 1 1 September, 05 Introduction to Algorithms L
38 Sıralı iki dizilimi birleştirme 1 1 Süre = Θ(n), toplam n elemanı birleştirmek için (doğrusal zaman). September, 05 Introduction to Algorithms L
39 Birleştirme sıralamasının çözümlenmesi Suistimal T(n) Θ(1) T(n/) Θ(n) BİRLEŞTİRME-SIRALAMASI A[ n] 1. Eğer n = 1&#;se, bitir.. Yinelemeli olarak A[ n/ ] ve A[ n/ + n ]&#;yi sırala. 3. sıralı listeyi Birleştir Özensizlik: T( n/ ) + T( n/ ) olması gerekir, ama asimptotik açıdan bu önemli değildir. September, 05 Introduction to Algorithms L
40 Birleştirme sıralaması için yineleme T(n) = Θ(1) eğer n = 1ise; T(n/) + Θ(n) eğer n > 1ise. Genellikle n&#;nin küçük değerleri için taban durumu ( base case ) olan T(n) = Θ(1) &#;i hesaplara katmayacağız; ama bunu sadece yinelemenin asimptotik çözümünü etkilemiyorsa yapacağız.. Derste T(n)&#;nin üst sınırını bulmanın birkaç yolunu inceleyeceğiz. September, 05 Introduction to Algorithms L
41 Yineleme ağacı T(n) = T(n/) + cn&#;yi çözün; burada c > 0 bir sabittir. September, 05 Introduction to Algorithms L
42 Yineleme ağacı T(n) = T(n/) + cn&#;i çözün; burada c > 0 bir sabittir. T(n) September, 05 Introduction to Algorithms L
43 Yineleme ağacı T(n) = T(n/) + cn&#;i çözün; burada c > 0 bir sabittir. cn T(n/) T(n/) September, 05 Introduction to Algorithms L
44 Yineleme ağacı T(n) = T(n/) + cn&#;i çözün; burada c > 0 bir sabittir. cn cn/ cn/ T(n/4) T(n/4) T(n/4) T(n/4) September, 05 Introduction to Algorithms L
45 Yineleme ağacı T(n) = T(n/) + cn&#;i çözün; burada c > 0 bir sabittir.&#;i cn cn/ cn/ cn/4 cn/4 cn/4 cn/4 Θ(1) September, 05 Introduction to Algorithms L
46 Yineleme ağacı T(n) = T(n/) + cn&#;i çözün; burada c > 0 bir sabittir. cn cn/ cn/ h = lg n cn/4 cn/4 cn/4 cn/4 Θ(1) September, 05 Introduction to Algorithms L
47 Yineleme ağacı T(n) = T(n/) + cn&#;i çözün; burada c > 0 bir sabittir. cn cn cn/ cn/ h = lg n cn/4 cn/4 cn/4 cn/4 Θ(1) September, 05 Introduction to Algorithms L
48 Yineleme ağacı T(n) = T(n/) + cn&#;i çözün; burada c > 0 bir sabittir. cn cn cn/ cn/ cn h = lg n cn/4 cn/4 cn/4 cn/4 Θ(1) September, 05 Introduction to Algorithms L
49 Yineleme ağacı T(n) = T(n/) + cn&#;i çözün; burada c > 0 bir sabittir. cn cn cn/ cn/ cn h = lg n cn/4 cn/4 cn/4 cn/4 cn Θ(1) September, 05 Introduction to Algorithms L
50 Yineleme ağacı T(n) = T(n/) + cn&#;i çözün; burada c > 0 bir sabittir. cn cn cn/ cn/ cn h = lg n cn/4 cn/4 cn/4 cn/4 cn Θ(1) yaprak sayısı = n Θ(n) September, 05 Introduction to Algorithms L
51 Yineleme ağacı T(n) = T(n/) + cn&#;i çözün; burada c > 0 bir sabittir. cn cn cn/ cn/ cn h = lg n cn/4 cn/4 cn/4 cn/4 cn Θ(1) yaprak sayısı = n Θ(n) Toplam = Θ(n lg n) September, 05 Introduction to Algorithms L
52 Sonuçlar Θ(n lg n), Θ(n )&#;dan daha yavaş büyür. En kötü durumda, birleştirme sıralaması asimptotik olarak araya yerleştirme sıralamasından daha iyidir. Pratikte, birleştirme sıralaması araya yerleştirme sıralamasını n > 30 değerlerinde geçer. Bunu kendiniz deneyin! September, 05 Introduction to Algorithms L
Konu özeti
- J / J Algoritmalara Giriş (SMA ) Fall
J / J Algoritmalara Giriş (SMA ) Fall
Seviye:
Lisans
Öğretim Üyeleri:
Prof. Charles Leiserson
Prof. Erik Demaine
Çevirmenler:
Prof. Dr. Ali Yazıcı
Haluk ArJ ders kitabının kapağı, Algoritmalara Giriş, İkinci Basım, Cormen, Leiserson, Rivest ve Stein. Ders Özellikleri Dersin Ana Başlıkları Bu ders bütün ders notları ve ders videolarını içermektedir. Ders kitabı Prof. Leiserson'ın katkısıyla yazılmıştır.
Dersin Tanımı Bu ders, verimli algoritmaların tasarımı ve çözümlemesi ile ilgili teknikleri, pratikteki kullanımlarını vurgulayarak öğretir. Dersin içerdiği konular: Sıralama, arama ağaçları, yığınlar ve kıyım fonksiyonları, böl ve fethet; dinamik programlama, amortize edilmiş çözümleme, grafik algoritmaları, en kısa yollar, ağ akışı, bilişimsel geometri, sayı teorisi algoritmaları, polinom ve matriks hesaplamaları; ön bellekleme ve paralel hesaplamalardır.
Bu ders aynı zamanda Singapur-MIT Ortaklığı (SMA) programı kapsamında SMA sayılı ders olarak da verilmektedir.
(Algoritmaların Tasarımı ve Çözümlenmesi )
Teknik Gereksinimler
Bu dersteki bazı dosyaları çalıştırmak için özel yazılımlar gerekir: .c, .java.
Bu bölüm, ekran okuyucu yazılımlarıyla kullanılamayan dökümanları içerir. Bir "#" sembolü, bu tip dökümanları belirtir.
Bu bölümdeki bazı dosyalar .c, ve .java gibi özel yazılımları kullanmayı gerektirir.
Derslerin problem setleri, öğrencilerin çözmesi gereken pek çok egzersiz ve problemi içerir. Öğrenciler sadece problemleri çözüm teslim etmek zorundadırlar ama, ders materyallerinde uzmanlaşmalarına yardımcı olmak adına, egzersizleri çözmeleri de önerilir. Egzersiz sorularının çoğu ders kitabından alınmıştır.
- Ders 1: İdari konular; Giriş; Algoritmaların Çözümlenmesi, Araya yerleştirme Sıralaması, Birleştirerek Sıralama
Ders 1: İdari konular; Giriş; Algoritmaların Çözümlenmesi, Araya yerleştirme Sıralaması, Birleştirerek Sıralama
- Ders 2: Asimptotik Simgelem; Yinelemeler; Yerine koyma, Ana Metod
Ders 2: Asimptotik Simgelem; Yinelemeler; Yerine koyma, Ana Metod
- Ders 3: Böl-ve-fethet: Strassen, Fibonacci, Polynomsal Çarpım
Ders 3: Böl-ve-fethet: Strassen, Fibonacci, Polynomsal Çarpım
- Ders 4: Çabuk Sıralama, Rastgele Algoritmalar
Ders 4: Çabuk Sıralama, Rastgele Algoritmalar
- Ders 5: Doğrusal-Zamanlı Sıralama: Alt sınırlar, Sayma Sıralaması, Taban Sıralaması
Ders 5: Doğrusal-Zamanlı Sıralama: Alt sınırlar, Sayma Sıralaması, Taban Sıralaması
- Ders 6: Sıra İstatistikleri, Ortanca
- Ders 7: Kıyım, Kıyım Fonksiyonları
- Ders 8: Evrensel Kıyım, Mükemmel Kıyım
Ders 8: Evrensel Kıyım, Mükemmel Kıyım
- Ders 9: İkili Arama Ağaçları ile Çabuk Aramanın ilişkisi - Rastgele İkili Arama Ağaçlarının Çözümlemesi
Ders 9: İkili Arama Ağaçları ile Çabuk Aramanın ilişkisi - Rastgele İkili Arama Ağaçlarının Çözümlemesi
- Ders Kırmızı-Siyah Ağaçlar, Araya yerleştirlemeler, Eklemeler, Silmeler
Ders Kırmızı-Siyah Ağaçlar, Araya yerleştirlemeler, Eklemeler, Silmeler
- Ders Genişleyen veri yapıları, Dinamik sıra istatistikleri, Aralık Ağaçları
Ders Genişleyen veri yapıları, Dinamik sıra istatistikleri, Aralık Ağaçları
- Ders Atlama Listeleri
- Ders Amortize edilmiş Algoritmalar, Tablo Çiftleme, Potansiyel Metodu
Ders Amortize edilmiş Algoritmalar, Tablo Çiftleme, Potansiyel Metodu
- Ders Yarışmacı Çözümleme: Kendi kendini organize eden Listeler
Ders Yarışmacı Çözümleme: Kendi kendini organize eden Listeler
- Ders Dinamik Programlama, En uzun ortak altdizi
Ders Dinamik Programlama, En uzun ortak altdizi
- Ders Aç gözlü algoritmalar, En az yayılan ağaçlar
Ders Aç gözlü algoritmalar, En az yayılan ağaçlar
- Ders En Kısa Yollar I: Özelllikleri, Dijkstra'nın Algoritması, Önce-enine Arama
Ders En Kısa Yollar I: Özelllikleri, Dijkstra'nın Algoritması, Önce-enine Arama
- Ders En Kısa Yollar II: Bellman-Ford, Doğrusal Programlama, Fark sınırlamaları
Ders En Kısa Yollar II: Bellman-Ford, Doğrusal Programlama, Fark sınırlamaları
- Ders En Kısa Yollar III: Bütün çiftlerin en kısa yolu, Matriks Çarpımı, Floyd-Warshall, Johnson
Ders En Kısa Yollar III: Bütün çiftlerin en kısa yolu, Matriks Çarpımı, Floyd-Warshall, Johnson
- Ders İleri Düzey konuları
Ders İleri Düzey konuları
- Ders İleri Düzey konuları (devamı)
Ders İleri Düzey konuları (devamı)
- Ders İleri Düzey konuları (devamı)
Ders İleri Düzey konuları (devamı)
- Ders İleri Düzey konuları (devamı) – Bu ders sonrası alınacak derslerle ilgili tartışma
Ders İleri Düzey konuları (devamı) – Bu ders sonrası alınacak derslerle ilgili tartışma