Ayrık Matematik
Mantık, ispat teknikleri, kümeler, sayma, bağıntılar ve graflar.
Kaynak kitap: Discrete Mathematics and its Applications, Kenneth H. Rosen, McGraw-Hill Publishing Company.
- 1. haftapropositional logic, predicates and quantifiers
- Önermeler mantığı, yüklemler ve niceleyicilerBağlaçlar, doğruluk tablosu, mantıksal denklik kanunları ve ∀/∃ ile çeviri ve olumsuzlama. Vizenin ilk sorusu neredeyse her zaman buradan gelir.
- 2. haftanested quantifiers and introduction to proofs
- İç içe niceleyiciler ve çıkarım kuralları∀x∃y ile ∃y∀x farkı, iç içe niceleyicilerin doğruluk değeri, olumsuzlaması ve bir argümanın geçerli olup olmadığını kurallarla gösterme.
- İspat yöntemlerine giriş: doğrudan, contrapositive, çelişkiTek/çift, bölünebilme ve rasyonel sayı tanımlarıyla doğrudan ispat, contraposition, çelişki, durum ayırma ve karşı örnek. Vizenin şablon ispat soruları buradan.
- 3. haftaproof techniques and mathematical induction
- Matematiksel tümevarım ve güçlü tümevarımToplam formülü, bölünebilme ve eşitsizlik için tümevarım iskeleti; pul problemleri ve özyinelemeli dizilerde güçlü tümevarım. Vizede neredeyse kesin bir 20 puanlık soru.
- 4. haftasets and functions
- Kümeler: işlemler, kuvvet kümesi ve küme eşitliği ispatıAlt küme, kuvvet kümesi, kartezyen çarpım, küme işlemleri ve küme eşitliğini üyelik tablosu ya da çift yönlü içermeyle ispatlama.
- Fonksiyonlar: birebir, örten, ters, bileşke, floor ve ceilingBir fonksiyonun one-to-one ve onto olduğunu ispatlama şablonu, ters fonksiyon, bileşke ve floor/ceiling. Vizede 1-1/onto ispatı ve floor/ceiling hesabı neredeyse kesin.
- 5. haftasequences and sums, cardinality of sets, intoduction to algorithms
- Diziler, toplamlar, kardinalite ve algoritmalara girişAritmetik/geometrik diziler, Σ toplam formülleri ve çift toplam, sayılabilir ve sayılamaz kümeler (Cantor), sözde kod ile maksimum, doğrusal/ikili arama, bubble sort ve açgözlü algoritma.
- 6. haftagrowth of functions and complexity of algorithms
- Fonksiyonların büyümesi ve algoritma karmaşıklığıBig-O, Big-Omega ve Big-Theta tanımları, tanık (witness) bulma, 'O değildir' ispatı, büyüme sıralaması ve döngü sayma. Vizenin son konusu.
- 7. haftadivisibility, modular arithmetic, primes
- Bölünebilme, modüler aritmetik ve asal sayılara | b, bölme algoritması (div ve mod), kongrüans, asal çarpanlara ayırma, EBOB/EKOK ve Öklid algoritması. Kriptografi haftasının temeli, final konusu.
- 8. haftacryptography
- Kriptografi: Caesar, affine şifre ve RSAKaydırma ve affine şifreler, genişletilmiş Öklid ile mod tersi, hızlı modüler üs alma ve küçük asallarla RSA anahtar üretme, şifreleme, çözme. Final konusu.
- 9. haftaintroduction to counting, the pigeonhole principle
- Saymaya giriş ve güvercin yuvası ilkesiÇarpım ve toplam kuralı, içerme-dışlama, güvercin yuvası (genelleştirilmiş hali dahil), permütasyon P(n,r) ve kombinasyon C(n,r). Final konusu, bu dönem vizede yok.
- 10. haftaadvanced counting
- İleri sayma: tekrarlı seçim, binom teoremi ve yineleme bağıntılarıTekrarlı permütasyon ve kombinasyon (yıldız-çubuk), tekrarlı harfli kelimeler, binom teoremi ve Pascal özdeşliği, sözlük sırasında sonraki permütasyon ve problemlerden yineleme bağıntısı kurma. Final konusu.
- 11. haftaSolving linear recurrences, generating functions
- Doğrusal yinelemeler, üreteç fonksiyonlar ve içerme-dışlamaKarakteristik denklemle yineleme çözmek, özel çözüm eklemek, böl-ve-yönet yinelemeleri, üreteç fonksiyonla sayma ve içerme-dışlama. Finalde tam bir soru buradan gelir.
- 12. haftarelations
- Bağıntılar: özellikler, denklik bağıntıları ve kısmi sıralamalarBir bağıntının yansıyan, simetrik, ters simetrik, geçişken olup olmadığını kontrol etmek, bileşke ve kapanış almak, denklik sınıflarını ve Hasse diyagramlarını çizmek. Final için klasik soru tipleri.
- 13. haftaIntroduction to graphs, graph isomorphisms
- Graflara giriş ve graf izomorfizmiGraf terimleri, derece ve el sıkışma teoremi, özel graflar (K_n, C_n, W_n, Q_n, K_{m,n}), iki parçalı graflar, komşuluk matrisi ve iki grafın izomorf olup olmadığını göstermek.
- 14. hafta"Connectivity, Euler and Hamilton paths,
- Bağlılık, Euler ve Hamilton yollarıYol ve devre tanımları, bileşenler, kesme köşeleri ve köprüler, matris kuvvetleriyle yol sayma, Euler devresi/yolu için derece koşulu, Hamilton devresi için Dirac ve Ore teoremleri ve kısaca Dijkstra algoritması.