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
((r ∨ q) ∧ r) → ¬q bir totoloji, bir çelişki mi yoksa olumsallık mı? Cevabınıza tıklayın.
((r ∨ q) ∧ r) → ¬q
1totoloji
2çelişki
3olumsallık
2.Önermeler mantığı ve ispatlarZor
Doğruluk tablosunun 16 satırının kaçı (¬(d ∧ a) → a) ∨ ¬((¬b → d) ∧ c) formülünü doğru yapar? Bu sayıya N deyin.
(¬(d ∧ a) → a) ∨ ¬((¬b → d) ∧ c)
N =
3.Kümeler, bağıntılar ve fonksiyonlarOrta
R = {(1, 4), (4, 1), (4, 2)}, {1, 2, 3, 4} kümesi üzerinde bir bağıntıdır. R’yi yansıyan yapmak için ona eklenmesi gereken sıralı çiftlerin en küçük sayısı k kaçtır?
R = {(1, 4), (4, 1), (4, 2)}
k =
4.Kümeler, bağıntılar ve fonksiyonlarZor
|A| = |B| = 3 ise kaç tane f: A → B eşlemesi vardır? Sayıya N deyin.
|A| = 3|B| = 3
N =
5.Graf kuramıOrta
K8 tam grafının kaç farklı Hamilton devresi (H) vardır? Yalnızca başlangıç köşesi ya da yönü farklı olan devreler aynı sayılır.
K8
H =
6.Graf kuramıZor
C köşesinde başlayıp biten 3 uzunluğunda kaç kapalı gezinti vardır? Bir gezinti köşeleri ve kenarları tekrar edebilir. Sayıya N deyin.
M = komşuluk matrisiL = 3
N =
7.Sayılar kuramı ve modüler aritmetikOrta
11 sayısının 59 modundaki tersini bulun: 0 < x < 59 olan ve 11·x ≡ 1 (mod 59) sağlayan x sayısı.
a = 11n = 59
11−1 mod 59 =
8.Sayılar kuramı ve modüler aritmetikZor
Bir RSA anahtarı p = 17 ve q = 19 asallarını ve e = 13 genel üssünü kullanıyor. Özel üssü, d, bulun (0 < d < φ(n)).
p = 17q = 19e = 13
d =
3Çözeltiler
1.Önermeler mantığı ve ispatlar
Cevap: olumsallık
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).
Doğruluk tablosu satır satır
q = 1, r = 1: r ∨ q = 1, (r ∨ q) ∧ r = 1, ¬q = 0, ((r ∨ q) ∧ r) → ¬q = 0
q = 1, r = 0: r ∨ q = 1, (r ∨ q) ∧ r = 0, ¬q = 0, ((r ∨ q) ∧ r) → ¬q = 1
q = 0, r = 1: r ∨ q = 1, (r ∨ q) ∧ r = 1, ¬q = 1, ((r ∨ q) ∧ r) → ¬q = 1
q = 0, r = 0: r ∨ q = 0, (r ∨ q) ∧ r = 0, ¬q = 1, ((r ∨ q) ∧ r) → ¬q = 1
Sınıflandırın
((r ∨ q) ∧ r) → ¬q: 0, 1, 1, 1
4 satırın 3 tanesinde 1, diğerlerinde 0: bir olumsallık.
Cevap
olumsallık
2.Önermeler mantığı ve ispatlar
Cevap: N = 13
Doğruluk tabloları: n farklı değişkenli bir formülün 2ⁿ satırı vardır; her satır doğruluk değerlerinin bir birleşimidir (1 = doğru, 0 = yanlış). İçten dışa doğru çalışın ve her alt formüle kendi sütununu verin. ¬a değeri tersine çevirir; a ∧ b yalnızca ikisi de 1 olduğunda 1’dir; a ∨ b yalnızca ikisi de 0 olduğunda 0’dır; a → b yalnızca a = 1 ve b = 0 olduğunda 0’dır; a ↔ b iki taraf eşit olduğunda 1’dir.
Sütunlar
d ∧ a; ¬(d ∧ a); ¬(d ∧ a) → a; ¬b; ¬b → d; (¬b → d) ∧ c; ¬((¬b → d) ∧ c); (¬(d ∧ a) → a) ∨ ¬((¬b → d) ∧ c)
a üzerinden bölün
a = 1: 8
a = 0: 5
N = 8 + 5 = 13
Cevap
N = 13
3.Kümeler, bağıntılar ve fonksiyonlar
Cevap: k = 4
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.
Eklenecek çiftler
{(1, 1), (2, 2), (3, 3), (4, 4)}
Sayın
k = 4
Cevap
k = 4
4.Kümeler, bağıntılar ve fonksiyonlar
Cevap: N = 6
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.
Sayın
N = 3!/(3 − 3)! = 6
Cevap
N = 6
5.Graf kuramı
Cevap: H = 2520
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.
Sayın
H = (8 − 1)!/2 = 5040/2 = 2520
Cevap
H = 2520
6.Graf kuramı
Cevap: N = 2
Dereceler: bir köşenin derecesi ona değen kenar sayısıdır. Her kenarın iki ucu vardır; bu yüzden dereceler kenar sayısının iki katını verecek şekilde toplanır: Σ deg(v) = 2|E| (el sıkışma lemması). Dolayısıyla derecesi tek olan köşelerin sayısı çifttir. Kn grafının n(n − 1)/2 kenarı vardır, n köşeli k-düzgün bir grafın nk/2 kenarı vardır ve n köşeli bir ağacın n − 1 kenarı vardır.
Komşuluk matrisi
A: 0 1 1 0 0 0
B: 1 0 1 1 0 0
C: 1 1 0 0 1 0
D: 0 1 0 0 1 1
E: 0 0 1 1 0 1
F: 0 0 0 1 1 0
Bir adım daha
(M³)CC = 1·1 + 1·1 + 3·0 + 2·0 + 0·1 + 1·0 = 2
Cevap
N = 2
7.Sayılar kuramı ve modüler aritmetik
Cevap: 11−1 mod 59 = 43
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).
Genişletilmiş Öklid algoritması
Her r kalanı r ≡ t·11 (mod 59) olarak yazılır.
r = 59, t = 0
r = 11, q = 5, t = 1
r = 4, q = 2, t = −5
r = 3, q = 1, t = 11
r = 1, q = 3, t = −16
Ters
1 ≡ −16·11 (mod 59)
x = 43
kontrol: 11·43 = 473 = 8·59 + 1
Cevap
11−1 mod 59 = 43
8.Sayılar kuramı ve modüler aritmetik
Cevap: d = 133
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.