matematik - Kriptarium
İleri Bilişim Matematiği
Pazartesi / 09:15 - 12:00
Online Dersler - (link)
Bu ders, bilgisayar bilimi ve mühendisliğine yönelik ayrık matematik için interaktif bir giriş sunmaktadır. Konu kapsamı kabaca üç kısma bölünebilir:
Matematiğin temel kavramları: Tanımlar, ispatlar, kümeler, fonksiyonlar, ilişkiler.
Ayrık yapılar: graflar, durum makineleri, modüler aritmetik, sayma.
Ayrık olasılık teorisi.
Bu dersi tamamlayan öğrenciler, ayrık matematiğin temel yöntemlerini bilgisayar bilimlerindeki araştırmalarında kullanabilecek ve uygulayabilecektir. Bu yöntemler özellikle algoritmalar, hesaplanabilirlik teorisi, yazılım mühendisliği ve bilgisayar sistemlerinin tasarımı ve analizinde kullanılabilecektir. Dersin sonunda ulaşılacak hedefler:
Bilgisayar algoritmalarında ve sistemlerinde kullanılan temel veri türleri ve yapıları (sayılar, kümeler, graflar ve ağaçlar gibi) hakkında matematiksel olarak gerekçeleri kazanılacaktır.
Analitik ve kombinasyonel yöntemleri kullanarak hesaplama süreçlerini modelleyip analiz edebileceksiniz.
Basit rasgele süreçlerin olasılıklarını ve beklentilerini hesaplamak için ayrık olasılık ilkelerini uygulayabileceksiniz.
Kümeler, ilişkiler, fonksiyonlar ve tamsayılar gibi temel matematiksel kavramları tanımlamak ve mantıksal notasyonu kullanmak.
Temel matematiksel argümanları değerlendirin ve hatalı akıl yürütmeyi tanımlayın (sadece yanıltıcı sonuçlar değil).
Tümevarım hipotezlerini ve basit tümevarım provalarını sentezleyin.
Modüler aritmetiğin temel özelliklerini kanıtlayabilir ve bilgisayar bilimlerindeki uygulamalarını örneğin kriptografi ve karma algoritmalarında açıklayabilir.
Bağlantı ve kısıtlılık tatmini (örn. Planlama) sorunlarını çözmek için veri yapılarının ve durum makinelerinin graf-teorik modellerini uygulayın.
İşlemlerin ve durum makinelerinin doğruluğunu ve feshini ispatlamak için değişmeyenlerin metodunu ve iyi kurulmuş sipariş yöntemlerini uygulayın.
Süreçlerin büyüme oranları için seri ve tekrarlamalardan kapalı ve asimtotik ifadeler türetin.
Permütasyon ve kombinasyon gibi temel kombinasyon işlemlerinin olası sonuçlarının sayısını hesaplayın.
Basit kombinasyon süreçleri için olasılıkları ve ayrık dağılımları hesaplayın; Beklentileri hesapla.
Ayrık Matematik ve Uygulamaları Kenneth H. Rosen (Palme Yayınevi)
Bilişim Matematiği - Uygulamalı Ayrık Matematik, Toros Rifat ÇÖLKESEN (Papatya Yayıncılık)
MIT Ders Notları: (pdf)
Ayrık matematiğe giriş;
Bilim ve mühendislikteki rolü;
​Önermeler, Doğruluk Tabloları ve Uygulamaları
Video 1.1 (izle)
Video 1.2 (izle)
Önermeler ne işe yarar
Problemlerin matematiksel mantıkla ifade edilmesi
"Olmak yada Olmamak" sözünün ayrık matematik yorumu
Bir mühendisin alet çantasında bulunması gereken iki önemli kavram Geçerlilik - Sağlanabilirlik
İspat Tekniklerinin Önemine Giriş
Video 2.1 (izle)
Video 2.2 (izle)
Önermelerden kümelere geçiş sürecini tamamlamak
Küme kuramının kısa özeti tekrar etmek
Kümelerin bilgisayar bilimlerinde nerelerde kullanıyoruz.
Fonksiyonlar ve bilgisayar bilimindeki önemi
Video 3.1 (izle)
Video 3.2 (izle)
Algoritmalar. Problem çözmenin ilk adımı bir matematiksel model oluşturmaktır. Ancak oluşturulan teorik modelin pratiğe geçirilebilmesi için bir emirler listesine ihtiyaç duyulmaktadır. Bu derste bu emirler listesinin nasıl oluşturulabileceği sistematik bir şekilde gösterilmektedir.
Video 4.1 (izle)
Video 4.2 (izle)
Büyük O notasyonu ne işe yarar
Çözmeye çalıştığımız problemin ne kadar kolay veya ne kadar zor olduğunu kullanılan teknolojiden bağımsız olarak ifade etmenin bir yolu olan Büyük-O notasyonu bu videoda gerçek dünya örnekleri üzerinden tartışılmıştır. Videoda kriptanaliz ile asimptotik karmaşıklık arasındaki ilişki açıklanarak gerçek dünya uygulamalarında Büyük - O notasyonunun nasıl kullanılabileceği gösterilmiştir.
Video 4.3 (izle)
Fonksiyon Bileşimleri, Büyük Teta ve Büyük Omega
Çözmeye çalıştığınız problem birçok farklı parçadan oluştuğu zaman her bir alt parçanın ayrı ayrı analiz edilerek asimptotik karmaşıklığının belirlenmesi ve ardından tüm sistemi temsil edecek karmaşıklık ifadesinin belirlenmesi gerekmektedir. Bu derste öncelikle fonksiyon bileşimlerinin karmaşıklık analizinin nasıl gerçekleştirileceği açıklanmıştır. Dersin geri kalan kısmında diğer karmaşıklık gösterimleri olan Büyük Teta ve Büyük Omega gösterimlerinin kullanım amaçları tartışılmıştır.
Video 4.4 (izle) -
Algoritma Paradigmaları, Tractable, Intractable, P, NP
Algoritmaları analiz etmenin bir diğer yolu problemi çözmek için gerekli algoritma paradigmalarını incelemektir. Bu derste öncelikle kısaca algoritma paradigmalarına değinilmiş ardından çözülebilir, çözülemez, P, NP gibi kavramlar kısaca açıklanmıştır.
Video 4.5 (izle)
Ödev 2 Açıklama: Ders 4 sonrasında ödev 2 olarak sizden istenen (i) incelediğiniz algoritmaların matematiksel modelini önermeler, aksiyonlar ve teoremler kullanarak matematiksel olarak ifade etmek (ii) Bu matematiksel modele karşılık gelen algoritmayı ortaya koymak (iii) Algoritmanın karmaşıklığını ifade etmek (iv) Matematiksel modele denk ifadeler araştırılarak algoritmalardaki olası zayıflıkları tartışmak
Sayı Teorisine giriş. Sayıların bilgisayar bilimindeki önemi, bölme kuralı, modüler aritmetik, asal sayılar ve uygulamları
Video 2 (izle)
Video 3 (izle)
Problemi matematiksel mantık ile ifade ettikten sonra en önemli adımlardan biri o problem için gerekli iş yükünü hesaplamaktır. Bu derste çarpma ve toplama kuralı tanıtılarak birbiri ile bağımlı ve bağımsız olayları gerçekleştirmek için gerekli iş yükünün nasıl hesaplanabileceği incelenmiştir. Ayrıca hem toplama hemde çarpma kuralını birlikte kullanan örneklere değinilmiştir. Derste son olarak güvercin yuvası prensibi tartışılmıştır. Fonksiyonlar problem çözme aşamasında tanımlarındaki kesinlikten dolayı birçok kolaylık sunmaktadır. Çünkü bir ilişkinin fonksiyon olabilmesi için tanım kümesindeki her elemanın değer kümesindeki sadece bir eleman ile eşleşmesi gerekmektedir. Birçok problem doğası gereği fonksiyonlara ve bu fonksiyonların terslerine ihtiyaç duyar. Güvercin yuvası teoremi aslında bir fonksiyonun birebir ve örten olup olmadığının ispat edilmesinin en güzel yollarından birini sunmaktadır. Bu derste güvercin yuvası prensibi tanıtılmış ve çeşitli uygulamalarına değinilmiştir.
Ödev 3: İncelemeniz için verilen algoritmalardaki anahtar planlama algoritmasının ürettiği anahtar sayısını sayma kurallarına göre belirleyiniz. Algoritmaların tanımı ile sizin hesaplamalarınız arasında fark olup olmadığını tartışınız veya doğruluğunu ispatlayınız. Daha sonra bu anahtarlar içerisinde güvercin yuvası prensibinden hareketle problemli durumların olup olmadığını analiz ediniz. Ayrıca literatürde incelediğiniz algoritmaların kriptanalizlerini inceleyerek bu analizlerin ders 5 ve ders 6'da işlenen konularla bağlantı olup olmadığını tartışan bir rapor hazırlayınız.