Konu özeti

  • 6.046J / 18.410J Algoritmalara Giriş (SMA 5503) Sonbahar 2005





    Seviye: 
    Lisans

    Öğretim Üyeleri: 
    Prof. Charles Leiserson
    Prof. Erik Demaine

    Çevirmenler:
    Prof. Dr. Ali Yazıcı
    Haluk Ar
    6.046J ders kitabının kapağı, Algoritmalara Giriş, İkinci Basım, Cormen, Leiserson, Rivest ve Stein.




    Ders Özellikleri


    Ders Videoları

    		Transkriptler
    Seçilmiş ders notları

    		Ödevler ve Çözümleri
    Sınavlar ve Çözümleri





    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 5503 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 Saatleri
      Ders : 2 oturum / hafta, 1.5 saat / oturum
      Ek ders: 1 oturum / hafta, 1 saat / oturum

      Dersin 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 
      Dersin Sonuçları
      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 1.5 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: 0262032937. 

      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

        Aşağıdaki takvimde, kursun dersleri (L), etütleri (R) ve ara sınavları (Q) ile ilgili bilgiler yer alır.
        SEANS#KONULARANAHTAR 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ı
        R1Algoritmaların Doğrulanması

        Horner Kuralı        		 
        L2Asimptotik Simgelem

        Yinelemeler

        Yerine Koyma, Ana Metot        		 
        L3Böl ve Fethet: Strassen, Fibonacci, Polinomsal Çarpım 
        R2Yinelemeler, Özensizlik (Dağınıklık) 
        L4Çabuk-sıralama, Rastgele sıralanmış AlgoritmalarProblem seti 1'in toplanması

        Problem seti 2'nin dağıtımı
        R3Yığın Sıralaması, Dinamik Setler, Öncelikli Kuyruklar 
        L5Doğrusal-zaman Sıralaması: Alt sınırlar, Sayma Sıralaması, Taban Sıralaması 
        L6Düzen istatistikleri, ortanca 
        R4Ortanca Uygulamaları 

        Sepet sıralaması        		 
        L7Kıyımlama, Kıyım FonksiyonlarıProblem seti 2'nin toplanması

        Problem seti 3'ün dağıtımı
        L8Evrensel Kıyımlama, Mükemmel KıyımlamaLaboratuvar ödevi gecesi
        R5Ara Sınav 1 gözden geçirmeProblem seti 3'ün toplanması
        Q1Ara 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ümlemesi        		Problem seti 4'ün dağıtımı
        L10Kırmızı-siyah ağaçlar, Rotasyon(Döndürme), Araya yerleştirme, Silme 
        R72-3 Ağaçları, B-ağaçları 
        L11Veri 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ı
        L12Atlama Listeleri 
        R8Menzil Ağaçları 
        L13Amortize Algoritmalar, Tablo İkileme, Potansiyel MetotProblem set 5'in toplanması

        Problem seti 6'nın dağıtımı
        L14Rekabetçi çözümlemeler: Kendi kendine organize edilmiş listeler 
        R9Rekabetçi çözümlemeler: Kayak kiralama, Rastgele Rekabetçi Çözümlemeler 
        L15Dinamik Programlama, En Uzun Ortak AltdiziProblem seti 6'nın toplanması

        Problem seti 7'nin dağıtımı
        L16Açgözlü Algoritmalar,Minimum Kapsayan Ağaçlar 
        L17En kısa yollar I: Özellikler, Dijkstra' nın Algoritması, Enine AramaProblem seti 7'nin toplanması

        Problem seti 8'in dağıtımı
        L18En kısa yollar II: Bellman-Ford, Doğrusal- Programlama, Fark Kısıtları 
        R10Grafik Arama: Derinliğine Arama, Topolojik Sıralama, DAG En kısa yollar 
        L19En kısa yollar III: Tüm-ikili en kısa yollar, Matris Çarpımı, Floyd-Warshall, JohnsonProblem seti 8'in toplanması
        L20Sınav 2 gözden geçirme 
        L21Etik, Problem Çözme (Zorunlu Katılım)Ev sınavı 2’ nin dağıtımı
        Q2Ara Sınav 2 (sınıfta)Ev sınavı 2’ nin toplanması (Ara sınav 2’den iki gün sonra)
        L22Gelişmiş KonularProblem seti 9'un dağıtımı
        L23Gelişmiş Konular (devam)Laboratuvar ödevi gecesi
        R11Gelişmiş KonularProblem seti 9'un toplanması
        L24Gelişmiş Konular (devam) 
        L25Gelişmiş Konular (devam)

        İleri düzey dersleri konusunda tartışma        		 
         Final Sınavı 

        • Okumalar

          Aşağıdaki Tablo Ders kitabında olan dersin okuma ödevlerini göstermektedir:

          Amazon logo Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. 2nd ed. Cambridge, MA: MIT Press. ISBN: 0262032937.

          Dersin belirtilen okuma ödevlerine ek olarak Yararlı Başvuru Kaynaklarına da bakınız

           
          SEANS#KONULAROKUMALAR
          L1İdari Konular

          Giriş

          Algoritmaların Çözümlenmesi, Araya Yerleştirme Sıralaması, Birleştirme Sıralaması          		Bölüm 1-2
          R1Algoritmaların Doğrulanması

          Horner Kuralı          		 
          L2Asimptotik Simgelem

          Yinelemeler

          Yerine Koyma, Ana Metot          		Bölüm 3-4, hesaba katılmayan kısım 4.4
          L3Böl ve Fethet: Strassen, Fibonacci, Polinomsal ÇarpımKısımlar 28.2 ve 30.1
          R2Yinelemeler, Özensizlik (Dağınıklık) 
          L4Çabuk-sıralama, Rastgele sıralanmış AlgoritmalarKısımlar 5.1-5.3 

          Bölüm 7
          R3Yığın Sıralaması, Dinamik Setler, Öncelikli KuyruklarBölüm 6
          L5Doğrusal-zaman Sıralaması: Alt sınırlar, Sayma Sıralaması, Taban SıralamasıKısımlar 8.1-8.3
          L6Düzen istatistikleri, ortancaBölüm 9
          R4Ortanca Uygulamaları 

          Sepet sıralaması          		Kısım 8.4
          L7Kıyımlama, Kıyım FonksiyonlarıKısımlar 11.1-11.3
          L8Evrensel Kıyımlama, Mükemmel KıyımlamaKısım 11.5
          R5Ara Sınav 1 gözden geçirme 
          Q1Ara Sınav 1 (sınıfta) 
          R6İkili Arama Ağaçları, Ağaç yürüyüşleriKısımlar 12.1-12.3
          L9İkili Arama Ağaçları’nın Çabuk Sıralama ile ilişkisi

          Rastgele İkili Arama Ağaçları’nın çözümlemesi          		Kısım 12.4
          L10Kırmızı-siyah ağaçlar, Rotasyon(Döndürme), Araya yerleştirme, SilmeBölüm 13
          R72-3 Ağaçları, B-ağaçları 
          L11Veri Yapılarını genişletme , Dinamik Sıra İstatistikleri, Aralık ağaçlarıBölüm 14
          L12Atlama ListeleriAtlama Listesi çıktısı (PDF)
          R8Menzil Ağaçları 
          L13Amortize Algoritmalar, Tablo İkileme, Potansiyel MetotBölüm 17
          L14Rekabetçi çözümlemeler: Kendi kendine organize edilmiş listelerSleator, Daniel D., and Robert E. Tarjan. "Amortized efficiency of list update and paging rules." Communications of the ACM 28, no. 2 (February 1985): 202-208.
          R9Rekabetçi çözümlemeler: Kayak kiralama, Rastgele Rekabetçi Çözümlemeler 
          L15Dinamik Programlama, En Uzun Ortak AltdiziBölüm 15
          L16Açgözlü Algoritmalar,Minimum Kapsayan AğaçlarKısımlar 16.1-16.3 and 22.1

          Bölüm 23
          L17En kısa yollar I: Özellikler, Dijkstra' nın Algoritması, Enine AramaKısım 22.2

          Bölüm 24
          L18En kısa yollar II: Bellman-Ford, Doğrusal- Programlama, Fark Kısıtları 
          R10Grafik Arama: Derinliğine Arama, Topolojik Sıralama, DAG En kısa yollarKısımlar 22.3-22.4
          L19En kısa yollar III: Tüm-ikili en kısa yollar, Matris Çarpımı, Floyd-Warshall, JohnsonBölüm 25
          L20Sınav 2 gözden geçirme 
          L21Etik, Problem Çözme (Zorunlu Katılım) 
          Q2Ara Sınav 2 (sınıfta) 
          L22Gelişmiş KonularDinamik Çoklu-dizilim Algoritması çıktısı (PDF)
          L23Gelişmiş Konular (devam) 
          R11Gelişmiş Konular 
          L24Geliş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.
          L25Gelişmiş Konular (devam)

          İleri düzey dersleri konusunda tartışma          		 
           Final 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, 1974. ISBN: 0201000296. 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, 1983. ISBN: 0201000237. 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, 1988. ISBN: 0201060353. General reference, although the exposition is sometimes terse or sketchy. 

          Bentley, Jon Louis. Programming Pearls. Reading, MA: Addison-Wesley, 1986. ISBN: 0201103311. Applications of algorithm design techniques to software engineering. 

          ———. More Programming Pearls: Confessions of a Coder. Reading, MA: Addison-Wesley, 1988. ISBN: 0201118890. More applications of algorithm design techniques to software engineering. 

          ———. Writing Efficient Programs. Englewood Cliffs, NJ: Prentice-Hall, 1982. ISBN: 0139702512. Performance hacking extraordinaire. 

          Brassard, Gilles, and Paul Bratley. Algorithmics: Theory and Practice. Englewood Cliffs, NJ: Prentice-Hall, 1988. ISBN: 0130232432. 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, 1974. ISBN: 0387900969. Intuitive introduction to probability. 

          Even, Shimon. Graph Algorithms. Rockville, MD: Computer Science Press, 1979. ISBN: 0914894218. 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, 1968, 1971. ISBN: 0471257087. ISBN: 0471257095. 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., 1979. ISBN: 0716710447. 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, 1984. ISBN: 020114218X. 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, 1997. ISBN: 0521585198. 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, 1978. ISBN: 0914894226. 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., 1991. ISBN: 0201417057. 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, 1997. ISBN: 0201896834. ISBN: 0201896842. ISBN: 0201896850. 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, 1976. ISBN: 0030848660. 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, 1968. ISBN: 0070381240. Combinatorial mathematics relevant to computer science. Excellent problems. 

          Manber, Udi. Introduction to Algorithms: A Creative Approach. Reading, MA: Addison-Wesley, 1989. ISBN: 0201120372. Elementary text with an emphasis on creativity. 

          Mehlhorn, Kurt. Data Structures and Algorithms. 3 vols. New York, NY: Springer-Verlag, 1984. ISBN: 038713302X. ISBN: 354013641X. ISBN: 0387136428. 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, 1980. ISBN: 0471028517. Readable introduction to number theory. 

          Papadimitriou, Christos H., and Kenneth Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Englewood Cliffs, NJ: Prentice-Hall, 1982. ISBN: 0131524623. 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, 1988. ISBN: 052135465X. Code for numerical algorithms. 

          Reingold, Edwin M., Jurg Nievergelt, and Narsingh Deo. Combinatorial Algorithms: Theory and Practice. Englewood Cliffs, NJ: Prentice-Hall, 1977. ISBN: 013152447X. Good on recurrence relations and binary search trees. 

          Sedgewick, Robert. Algorithms. 2nd ed. Reading, MA: Addison-Wesley, 1988. ISBN: 0201066734. 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, 1997. ISBN: 053494728X. A good text on computability and complexity theory. 

          Tarjan, Robert Endre. Data Structures and Network Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 1983. ISBN: 0898711878. Advanced book with tons of good stuff.

          • Ö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, model.txt (TXT) 
            Model Çıktı, samplesol.txt (TXT) 
            Girdi 1, girdi1.txt (TXT) 
            Girdi 2, girdi2.txt (TXT) 
            Girdi 3, girdi3.txt (TXT) 
            		(PDF)

            Kaynak Kodu, editDistance.java (JAVA) 
            Kaynak Kodu, editDistance.c (C) 
            Problem Seti 8 (PDF)(PDF)
            Problem Seti 9 (PDF)(PDF)

            • 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.

              SINAVLARÇÖZÜMLERİ
              Pratik Ara sınav 1 (PDF)(PDF)#
              Pratik Ara sınav 2 (PDF)(PDF)#
              Pratik Final Sınavı (PDF)(PDF)
              Ara sınav 1 (PDF)(PDF)
              Ara sınav 2 (PDF)(PDF)
              Final Sınavı (PDF)(PDF)