Ayrık Matematik / Ayrık Yapılar

Neden önemli

Kalkülüs sürekli şeylerle uğraşır, bilgisayar ise ayrık şeylerle: bitler, düğümler, adımlar. Bir algoritmanın doğru olduğunu tümevarımla, kaç adım sürdüğünü saymayla, ağdaki en kısa yolu graf kuramıyla gösterirsin. Bu dersi geçiştirenler algoritmalar dersinde zorlanır.

Bilmen gerekenler

• Önermeler ve yüklemler mantığı; "ve, veya, ise" ile koşul yazmak.
• Doğrudan ispat, çelişkiyle ispat ve özellikle tümevarım.
• Kümeler, fonksiyonlar, bağıntılar; denklik ve sıralama bağıntıları.
• Permütasyon, kombinasyon, güvercin yuvası ilkesi, temel olasılık.
• Graflar: derece, yol, döngü, bağlılık; ağaçlar.
• Özyineli bağıntılar (recurrence): algoritma analizinin temeli.

Alıştırma ve proje

• İspatları ezberleme, kendin yaz; bir arkadaşına okut, ikna oluyor mu bak.
• Graf konularını kodla dene: bir grafı komşuluk listesiyle tut, bağlı mı diye kontrol et.
• Sayma sorularının cevabını küçük bir programla deneyerek doğrula.

Sık yapılan hatalar

• Dersi "sınavdan geçmelik matematik" diye görmek; algoritmalar dersinde geri döner.
• Tümevarımda temel adımı ya da varsayımı atlamak.
• İspatı örneklerle "gösterdim" sanmak; üç örnek bir ispat değildir.