Bir Venn şeması çizin ve küme ifadesine hangi bölgelerin ait olduğuna bölge bölge karar verin.
Sayma sorularında bölgeleri ortadan dışa doğru doldurun: önce tüm kümelerin kesişimi, sonra ikili kesişimler, sonra tek kümeler, en son dış bölge.
Kontrol için dahil etme–dışarıda bırakma ilkesini kullanın: |A ∪ B| = |A| + |B| − |A ∩ B|.
Bir bağıntı için her özelliği tüm çiftlerde sınayın; özellik sağlanmıyorsa bir karşı örnek verin.
Bir fonksiyon için B’nin her elemanına gelen okları sayın: en çok bir ok varsa birebirdir, en az bir ok varsa örtendir.
Graf kuramı
El sıkışma lemması
Σ deg(v) = 2|E|
Tam graflar
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
Düzgün (regüler) graf
|E| = n·k/2
Ağaç ve orman
|E| = n − 1, |E| = n − c
Ağacın yaprakları
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Euler
devre: tüm derecelerin çift olması; yol: tam olarak 2 tek derece
Kn içindeki Hamilton devreleri
(n − 1)!/2
Dijkstra güncellemesi
d(v) = min(d(v), d(u) + w(u, v))
L uzunluğundaki gezintiler
(Mᴸ)ij
Yöntem
Her köşenin derecesini yazın; dereceler toplamı kenar sayısının iki katıdır.
Euler sorularında grafın bağlantılı olduğunu denetleyin ve derecesi tek olan köşeleri sayın.
Ağaçlarda n − 1 kenarı ve el sıkışma lemmasını kullanın.
Dijkstra için geçici uzaklıkların bir tablosunu tutun ve her turda henüz kesinleşmemiş köşelerden en küçük uzaklığa sahip olanı kesinleştirin.
En küçük kapsayan ağaç için kenarları ağırlığa göre sıralayın ve bir döngü kapatan her kenarı atlayın (Kruskal) ya da bir başlangıç köşesinden tek bir ağaç büyütün (Prim).
Sayılar kuramı ve modüler aritmetik
Kalanlı bölme
a = q·n + r, 0 ≤ r < n
Öklid
gcd(a, b) = gcd(b, a mod b)
En küçük ortak kat
lcm(a, b) = a·b/gcd(a, b)
Ters
a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
Doğrusal denklik
a·x ≡ b → x ≡ a⁻¹·b (mod n)
Euler’in φ fonksiyonu
φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
Fermat
aᵖ⁻¹ ≡ 1 (mod p)
RSA
n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n
Yöntem
Önce her sayıyı n modunda indirgeyin; kalanlar 0 ile n − 1 arasındadır.
EBOB için Öklid algoritmasıyla art arda bölün; sıfırdan farklı son kalan EBOB’dur.
Bir ters için genişletilmiş algoritmayı çalıştırın ve a’nın katsayısını alın; negatifse n ekleyin.
a·x ≡ b denkliğini a⁻¹ ile çarparak çözün; iki denkliği x = r₁ + m₁k yazarak birleştirin.
Kuvvetler için üssü ikilik tabanda yazın ve art arda kare alın; RSA’da d = e⁻¹ mod φ(n) ve φ(n) = (p − 1)(q − 1)’dir.
2Alıştırma soruları
1.Önermeler mantığı ve ispatlarOrta
Hangi formül (b ∨ c) → a formülüne mantıksal olarak denktir? Üzerine tıklayın.
(b ∨ c) → a
1(b → a) ∧ (c → a)
2(b → a) ∨ (c → a)
3b ∨ (c → a)
4(b ∧ c) → a
2.Önermeler mantığı ve ispatlarZor
Öncülleri b → c; a → c ve sonucu b → a olan argüman geçersizdir. Doğruluk tablosunda karşı örnek olan satıra tıklayın.
b → ca → c∴ b → a
1a = 1, b = 1, c = 1
2a = 1, b = 1, c = 0
3a = 1, b = 0, c = 1
4a = 1, b = 0, c = 0
5a = 0, b = 1, c = 1
6a = 0, b = 1, c = 0
7a = 0, b = 0, c = 1
8a = 0, b = 0, c = 0
3.Kümeler, bağıntılar ve fonksiyonlarOrta
{1, 2, 3, 4} kümesi üzerindeki R bağıntısı yönlü bir graf olarak çizilmiştir (bir döngü (x, x) ∈ R demektir). Dört özellikten tam biri sağlanır. Ona tıklayın.
Ok şeması, A = {1, 2} ve B = {a, b, c, d, e} olan bir f: A → B fonksiyonunu gösterir. f’ye uyan tanıma tıklayın.
f = {(1, d), (2, a)}
1birebir, örten değil
2örten, birebir değil
3eşleme (birebir ve örten)
4hiçbiri
5.Graf kuramıOrta
Bağlantılı grafın bir Euler devresi mi, devre olmayan bir Euler yolu mu var, yoksa hiçbiri mi? Cevabınıza tıklayın.
|V| = 6|E| = 6
1Euler devresi
2Euler yolu, devre yok
3hiçbiri
6.Graf kuramıZor
Kruskal algoritması en küçük kapsayan ağacı kurar. 5. kenar olarak eklediği kenara tıklayın; atlanan kenarlar sayılmaz.
k = 5
1kenar AB
2kenar AC
3kenar BC
4kenar BD
5kenar CE
6kenar DF
7kenar GB
8kenar GC
9kenar GD
10kenar GE
7.Sayılar kuramı ve modüler aritmetikOrta
x ≡ 4 (mod 5) ve x ≡ 0 (mod 7) sağlayan en küçük pozitif tam sayı x değerini bulun.
x ≡ 4 (mod 5)x ≡ 0 (mod 7)
x =
8.Sayılar kuramı ve modüler aritmetikZor
3170 mod 25 değerini bulmak için tekrarlı kare almayı kullanın.
a = 3k = 170n = 25
3170 mod 25 =
3Çözeltiler
1.Önermeler mantığı ve ispatlar
Cevap: (b → a) ∧ (c → a)
Mantıksal denklik: doğruluk tablosunun her satırında aynı değere sahip iki formül denktir (≡). Totoloji her satırda 1, çelişki her satırda 0’dır; olumsallık ikisi de değildir. Yararlı kurallar: De Morgan, ¬(a ∧ b) ≡ ¬a ∨ ¬b ve ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (karşıt değil); ¬(a → b) ≡ a ∧ ¬b; ve dağılma kuralları, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).
Kural
(a ∨ b) → c, a ya da b doğru olduğunda c’yi gerektirir: (a → c) ∧ (b → c).
(b ∨ c) → a ≡ (b → a) ∧ (c → a)
Doğruluk tablosuyla denetleyin
a = 1, b = 1, c = 1: 1 | 1 1 1 1
a = 1, b = 1, c = 0: 1 | 1 1 1 1
a = 1, b = 0, c = 1: 1 | 1 1 1 1
a = 1, b = 0, c = 0: 1 | 1 1 1 1
a = 0, b = 1, c = 1: 0 | 0 0 1 0
a = 0, b = 1, c = 0: 0 | 0 1 1 1
a = 0, b = 0, c = 1: 0 | 0 1 0 1
a = 0, b = 0, c = 0: 1 | 1 1 1 1
Cevap
(b → a) ∧ (c → a)
Çubuktan sonraki sütunlar, gösterilen sırayla seçeneklerdir.
2.Önermeler mantığı ve ispatlar
Cevap: a = 0, b = 1, c = 1
Niceleyiciler ve argümanlar: ¬∀x P(x) ≡ ∃x ¬P(x) ve ¬∃x P(x) ≡ ∀x ¬P(x). Değili içeri taşıyın, geçtiği her niceleyiciyi değiştirin ve iç formülün değilini ¬(a → b) ≡ a ∧ ¬b gibi önermeler mantığı kurallarıyla alın. Tüm öncüllerin 1 olduğu her satırda sonuç da 1 ise bir argüman geçerlidir. Öncüllerin doğru, sonucun yanlış olduğu tek bir satır bir karşı örnektir ve argümanın geçersiz olduğunu gösterir.
Öncüller ve sonuç satır satır
a = 1, b = 1, c = 1: 1 1 | 1
a = 1, b = 1, c = 0: 0 0 | 1
a = 1, b = 0, c = 1: 1 1 | 1
a = 1, b = 0, c = 0: 1 0 | 1
a = 0, b = 1, c = 1: 1 1 | 0
a = 0, b = 1, c = 0: 0 1 | 0
a = 0, b = 0, c = 1: 1 1 | 1
a = 0, b = 0, c = 0: 1 1 | 1
Karşı örnek
a = 0, b = 1, c = 1
Cevap
a = 0, b = 1, c = 1
Bu biçimdeki bir argüman geçerli bir kurala benzer, ama geçerli olmadığını göstermek için tek bir satır yeter.
3.Kümeler, bağıntılar ve fonksiyonlar
Cevap: yansıyan
Bağıntılar: bir X kümesi üzerindeki bir R bağıntısı, sıralı (x, y) çiftlerinin kümesidir. X’teki her x için (x, x) ∈ R ise R yansıyandır; (x, y) ∈ R her zaman (y, x) ∈ R ile birlikte geliyorsa simetriktir; (x, y) ve (y, x) yalnızca x = y ise birlikte R’deyse ters simetriktir; R’deki (x, y) ve (y, z) (x, z) ∈ R’yi zorunlu kılıyorsa geçişlidir. Denklik bağıntısı yansıyan, simetrik ve geçişlidir ve X’i ayrık sınıflara böler.
yansıyan
sağlanır
simetrik
sağlanmaz: (2, 3) ∈ R, (3, 2) ∉ R
ters simetrik
sağlanmaz: (1, 3), (3, 1) ∈ R
geçişli
sağlanmaz: (2, 3), (3, 1) ∈ R, (2, 1) ∉ R
Cevap
yansıyan
4.Kümeler, bağıntılar ve fonksiyonlar
Cevap: birebir, örten değil
Fonksiyonlar ve sayma: bir f: A → B fonksiyonu A’nın her elemanına B’de tam olarak bir görüntü verir. Farklı elemanların görüntüleri farklıysa f birebirdir, B’nin her elemanı bir görüntüyse örtendir, ikisi de sağlanıyorsa eşlemedir (birebir ve örten). |A| = m ve |B| = n iken nᵐ fonksiyon, n!/(n − m)! birebir fonksiyon (m ≤ n) ve dahil etme–dışarıda bırakma ile Σ (−1)ᵏ·C(n, k)·(n − k)ᵐ örten fonksiyon vardır. |𝒫(A)| = 2ᵐ ve |A × B| = m·n.
Birebir mi?
B’nin her elemanına en çok bir kez ulaşılıyor → birebir
Örten mi?
b, c, e ok almaz → örten değil
Cevap
birebir, örten değil
Cevap
birebir, örten değil
5.Graf kuramı
Cevap: Euler yolu, devre yok
Euler, Hamilton ve ağaçlar: bağlantılı bir grafın tüm köşelerinin derecesi çiftse bir Euler devresi (her kenar bir kez, başlangıca dönüş), tam olarak iki köşenin derecesi tekse devre olmayan bir Euler yolu vardır; yol bir tek dereceli köşeden ötekine gider. Bir Hamilton devresi her köşeyi bir kez ziyaret eder; Kn grafında bunlardan (n − 1)!/2 tane vardır. n köşeli bir ağacın n − 1 kenarı vardır ve m kenarlı bağlantılı bir graf m − n + 1 kenar kaldırıldıktan sonra bir kapsayan ağaç bırakır.
Euler yolu bir tek dereceli köşeden başlar ve ötekinde biter.
6.Graf kuramı
Cevap: kenar GC
En kısa yollar ve kapsayan ağaçlar: Dijkstra algoritması her turda bir köşeyi kesinleştirir: geçici uzaklığı en küçük olan, henüz kesinleşmemiş köşeyi. Uzaklığı artık kesindir ve her komşu v için d(v) = min(d(v), d(u) + w(u, v)) alınır. Kruskal algoritması en küçük kapsayan ağacı, kenarları hafiften ağıra alıp bir döngü kapatacak kenarları atlayarak kurar; Prim algoritması bir başlangıç köşesinden tek bir ağaç büyütür ve her seferinde ağaçtan çıkan en hafif kenarı ekler. n köşeli bir kapsayan ağacın n − 1 kenarı vardır.
Kruskal algoritması
1. AC (1)
2. BD (2)
3. GB (4)
4. CE (7)
5. GC (9)
6. DF (17)
kenar numarası 5
GC
Cevap
kenar GC
7.Sayılar kuramı ve modüler aritmetik
Cevap: x = 14
Tersler ve denklikler: a’nın n modunda tersi, tam olarak ebob(a, n) = 1 olduğunda vardır. Genişletilmiş Öklid algoritması 1 = s·n + t·a yazar ve sonra a⁻¹ ≡ t (mod n) olur. ebob(a, n) = 1 olan a·x ≡ b (mod n) denkliğinin çözümü x ≡ a⁻¹·b’dir. Modülleri aralarında asal olan x ≡ r₁ (mod m₁) ve x ≡ r₂ (mod m₂) denkliklerinin m₁·m₂ modunda bir çözümü vardır (Çin kalan teoremi). Euler’in φ(n) fonksiyonu 1’den n’ye kadar n ile aralarında asal olan sayıları sayar: φ(n) = n·∏(1 − 1/p).
Birinci denklik
x = 4 + 5k
İkinci denklik
4 + 5k ≡ 0 (mod 7) → 5k ≡ 3 (mod 7)
k ≡ 3·3 ≡ 2 (mod 7)
Sonuç
x = 4 + 5·2 = 14
x = 14
kontrol: 14 mod 5 = 4, 14 mod 7 = 0
Cevap
x = 14
8.Sayılar kuramı ve modüler aritmetik
Cevap: 3170 mod 25 = 24
Modüler kuvvetler ve RSA: aᵏ mod n değerini tekrarlı kare almayla hesaplayın: k’yi ikilik tabanda yazın, kare alın, her adımdan sonra indirgeyin ve biti 1 olan kuvvetleri çarpın. Fermat: a’yı bölmeyen bir p asalı için aᵖ⁻¹ ≡ 1 (mod p); dolayısıyla üs p − 1 modunda indirgenebilir. RSA: p ve q asallarını seçin, n = p·q ve φ(n) = (p − 1)(q − 1); genel üs e, φ(n) ile aralarında asaldır ve özel üs d = e⁻¹ mod φ(n)’dir. c = mᵉ mod n ile şifreleyin ve m = cᵈ mod n ile çözün.