แผนภาพลูกศรแสดงฟังก์ชัน f: A → B โดย A = {1, 2, 3, 4} และ B = {a, b, c, d, e} ให้คลิกคำอธิบายที่ตรงกับ f
f = {(1, e), (2, b), (3, c), (4, a)}
1หนึ่งต่อหนึ่ง แต่ไม่ทั่วถึง
2ทั่วถึง แต่ไม่หนึ่งต่อหนึ่ง
3หนึ่งต่อหนึ่งทั่วถึง
4ไม่ใช่ทั้งสองอย่าง
5.ทฤษฎีกราฟปานกลาง
ต้นไม้มี 2 จุดยอดดีกรี 4 และจุดยอดอื่นทั้งหมดเป็นใบ (ดีกรี 1) มีกี่ใบ L
2 × deg 4
L =
6.ทฤษฎีกราฟยาก
ขั้นตอนวิธีของไดก์สตราเริ่มจาก A ให้คลิกจุดยอดที่ถูกยืนยัน (ทำให้เป็นค่าถาวร) ในรอบที่ 3 โดย A เองคือรอบที่ 1
เริ่มต้น: Aรอบ 3
1A
2B
3C
4D
5E
6F
7.ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ปานกลาง
จงหาจำนวนเต็มบวกที่น้อยที่สุด x ที่ x ≡ 2 (mod 6) และ x ≡ 1 (mod 13)
x ≡ 2 (mod 6)x ≡ 1 (mod 13)
x =
8.ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ยาก
ใช้การยกกำลังสองซ้ำเพื่อหา 41171 mod 68
a = 41k = 171n = 68
41171 mod 68 =
3สารละลาย
1.ตรรกศาสตร์ประพจน์และการพิสูจน์
คำตอบ: (q → p) ∧ (r → p)
ความสมมูลเชิงตรรกะ: สูตรสองสูตรสมมูลกัน (≡) เมื่อมีค่าเท่ากันทุกแถวของตารางค่าความจริง ซ้ำซ้อน (tautology) เป็น 1 ทุกแถว ขัดแย้ง (contradiction) เป็น 0 ทุกแถว และ contingency ไม่ใช่ทั้งสองอย่าง กฎที่มีประโยชน์: กฎของเดอมอร์แกน ¬(a ∧ b) ≡ ¬a ∨ ¬b และ ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (การแย้งสลับที่); ¬(a → b) ≡ a ∧ ¬b; และกฎการแจกแจง a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c)
กฎ
(a ∨ b) → c ต้องการ c เมื่อ a หรือ b ข้อใดข้อหนึ่งเป็นจริง: (a → c) ∧ (b → c)
(q ∨ r) → p ≡ (q → p) ∧ (r → p)
ตรวจสอบด้วยตารางค่าความจริง
p = 1, q = 1, r = 1: 1 | 1 1 1 1
p = 1, q = 1, r = 0: 1 | 1 1 1 1
p = 1, q = 0, r = 1: 1 | 1 1 1 1
p = 1, q = 0, r = 0: 1 | 1 1 1 1
p = 0, q = 1, r = 1: 0 | 1 0 0 0
p = 0, q = 1, r = 0: 0 | 1 0 1 1
p = 0, q = 0, r = 1: 0 | 0 0 1 1
p = 0, q = 0, r = 0: 1 | 1 1 1 1
คำตอบ
(q → p) ∧ (r → p)
คอลัมน์หลังเส้นคั่นคือตัวเลือกตามลำดับที่แสดง
2.ตรรกศาสตร์ประพจน์และการพิสูจน์
คำตอบ: N = 10
ตารางค่าความจริง: สูตรที่มีตัวแปรต่างกัน n ตัวมี 2ⁿ แถว หนึ่งแถวต่อทุกชุดของค่าความจริง (1 = จริง, 0 = เท็จ) ทำจากด้านในออกมาและให้ทุกประพจน์ย่อยมีคอลัมน์ของตัวเอง ¬a กลับค่า a ∧ b เป็น 1 เฉพาะเมื่อทั้งสองเป็น 1 a ∨ b เป็น 0 เฉพาะเมื่อทั้งสองเป็น 0 a → b เป็น 0 เฉพาะเมื่อ a = 1 และ b = 0 a ↔ b เป็น 1 เมื่อทั้งสองข้างเท่ากัน
คอลัมน์
¬a; c → ¬a; ¬(c → ¬a); b → ¬(c → ¬a); b → c; a ∨ d; (b → c) ∨ (a ∨ d); (b → ¬(c → ¬a)) ∧ ((b → c) ∨ (a ∨ d))
แยกตาม a
a = 1: 6
a = 0: 4
N = 6 + 4 = 10
คำตอบ
N = 10
3.เซต ความสัมพันธ์ และฟังก์ชัน
คำตอบ: k = 3
ความสัมพันธ์: ความสัมพันธ์ R บนเซต X คือเซตของคู่อันดับ (x, y) R สะท้อนเมื่อ (x, x) ∈ R สำหรับทุก x ใน X; สมมาตรเมื่อ (x, y) ∈ R มี (y, x) ∈ R มาด้วยเสมอ; ปฏิสมมาตรเมื่อ (x, y) และ (y, x) อยู่ใน R ทั้งคู่เฉพาะเมื่อ x = y; และแพร่ผ่านเมื่อ (x, y) และ (y, z) ใน R บังคับให้ (x, z) ∈ R ความสัมพันธ์สมมูลคือความสัมพันธ์ที่สะท้อน สมมาตร และแพร่ผ่าน และแบ่ง X เป็นคลาสที่ไม่ซ้อนกัน
คู่ที่ต้องเพิ่ม
{(1, 1), (3, 3), (4, 1)}
นับ
k = 3
คำตอบ
k = 3
4.เซต ความสัมพันธ์ และฟังก์ชัน
คำตอบ: หนึ่งต่อหนึ่ง แต่ไม่ทั่วถึง
ฟังก์ชันและการนับ: ฟังก์ชัน f: A → B ให้สมาชิกทุกตัวของ A มีภาพใน B เพียงหนึ่งตัวพอดี f เป็นหนึ่งต่อหนึ่ง (injective) เมื่อสมาชิกต่างกันมีภาพต่างกัน ทั่วถึง (surjective) เมื่อสมาชิกทุกตัวของ B เป็นภาพ และหนึ่งต่อหนึ่งทั่วถึง (bijective) เมื่อเป็นจริงทั้งสองอย่าง เมื่อ |A| = m และ |B| = n มี nᵐ ฟังก์ชัน ฟังก์ชันหนึ่งต่อหนึ่ง n!/(n − m)! ฟังก์ชัน (m ≤ n) และฟังก์ชันทั่วถึง Σ (−1)ᵏ·C(n, k)·(n − k)ᵐ ฟังก์ชันโดยหลักการเพิ่มเข้า–ตัดออก |𝒫(A)| = 2ᵐ และ |A × B| = m·n
หนึ่งต่อหนึ่งหรือไม่
สมาชิกทุกตัวของ B ถูกชี้ไม่เกินหนึ่งครั้ง → หนึ่งต่อหนึ่ง
ทั่วถึงหรือไม่
d ไม่มีลูกศรชี้เข้า → ไม่ทั่วถึง
คำตอบ
หนึ่งต่อหนึ่ง แต่ไม่ทั่วถึง
คำตอบ
หนึ่งต่อหนึ่ง แต่ไม่ทั่วถึง
5.ทฤษฎีกราฟ
คำตอบ: L = 6
ออยเลอร์ แฮมิลตัน และต้นไม้: กราฟเชื่อมโยงมีวงจรออยเลอร์ (ผ่านทุกเส้นเชื่อมครั้งเดียวและกลับจุดเริ่มต้น) เมื่อทุกจุดยอดมีดีกรีคู่ และมีทางเดินออยเลอร์ที่ไม่ใช่วงจรเมื่อมีจุดยอดดีกรีคี่พอดีสองจุด ทางเดินนั้นไปจากจุดยอดคี่จุดหนึ่งถึงอีกจุดหนึ่ง วงจรแฮมิลตันผ่านทุกจุดยอดครั้งเดียว Kn มีวงจรแบบนี้ (n − 1)!/2 วงจร ต้นไม้ที่มี n จุดยอดมี n − 1 เส้นเชื่อม และกราฟเชื่อมโยงที่มี m เส้นเชื่อมจะเหลือต้นไม้ทอดข้ามหลังเอาเส้นเชื่อมออก m − n + 1 เส้น
เล็มมาการจับมือสำหรับต้นไม้
L + 8 = 2(L + 2) − 2
L = 6
คำตอบ
L = 6
ทางลัด: L = 2 + Σ (d − 2) ของจุดยอดที่มีดีกรี d ≥ 3
6.ทฤษฎีกราฟ
คำตอบ: B
เส้นทางที่สั้นที่สุดและต้นไม้ทอดข้าม: ขั้นตอนวิธีของไดก์สตรายืนยันหนึ่งจุดยอดต่อรอบ: จุดยอดที่ยังไม่ยืนยันซึ่งมีระยะทางชั่วคราวน้อยที่สุด ระยะทางของมันเป็นค่าสุดท้ายแล้ว และเพื่อนบ้าน v ทุกจุดได้ d(v) = min(d(v), d(u) + w(u, v)) ขั้นตอนวิธีของครัสคัลสร้างต้นไม้ทอดข้ามค่าน้อยที่สุดโดยเลือกเส้นเชื่อมจากเบาไปหนักและข้ามเส้นที่ทำให้เกิดวัฏจักร ขั้นตอนวิธีของพริมขยายต้นไม้หนึ่งต้นจากจุดยอดเริ่มต้นโดยเพิ่มเส้นเชื่อมที่เบาที่สุดที่ออกจากต้นไม้เสมอ ต้นไม้ทอดข้ามที่มี n จุดยอดมี n − 1 เส้นเชื่อม
ไดก์สตราทีละรอบ
1. A (0): B: 8, C: 6
2. C (6): B: 7
3. B (7): D: 9, E: 16
4. D (9): E: 14, F: 11
5. F (11)
6. E (14)
รอบ 3
B
คำตอบ
B
7.ทฤษฎีจำนวนและเลขคณิตมอดูลาร์
คำตอบ: x = 14
ตัวผกผันและความสอดคล้อง: a มีตัวผกผันมอดูโล n เมื่อ gcd(a, n) = 1 เท่านั้น ขั้นตอนวิธีของยูคลิดแบบขยายเขียน 1 = s·n + t·a แล้ว a⁻¹ ≡ t (mod n) ความสอดคล้อง a·x ≡ b (mod n) ที่ gcd(a, n) = 1 มีคำตอบ x ≡ a⁻¹·b ความสอดคล้องสองข้อ x ≡ r₁ (mod m₁) และ x ≡ r₂ (mod m₂) ที่มอดูลัสเป็นจำนวนเฉพาะสัมพัทธ์กันมีคำตอบเดียวมอดูโล m₁·m₂ (ทฤษฎีบทเศษเหลือของจีน) φ(n) ของออยเลอร์นับจำนวนตั้งแต่ 1 ถึง n ที่เป็นจำนวนเฉพาะสัมพัทธ์กับ n: φ(n) = n·∏(1 − 1/p)
ความสอดคล้องข้อแรก
x = 2 + 6k
ความสอดคล้องข้อที่สอง
2 + 6k ≡ 1 (mod 13) → 6k ≡ 12 (mod 13)
k ≡ 11·12 ≡ 2 (mod 13)
ผลลัพธ์
x = 2 + 6·2 = 14
x = 14
ตรวจสอบ: 14 mod 6 = 2, 14 mod 13 = 1
คำตอบ
x = 14
8.ทฤษฎีจำนวนและเลขคณิตมอดูลาร์
คำตอบ: 41171 mod 68 = 65
เลขยกกำลังมอดูลาร์และ RSA: คำนวณ aᵏ mod n ด้วยการยกกำลังสองซ้ำ: เขียน k เป็นเลขฐานสอง ยกกำลังสอง ลดค่าหลังทุกขั้นตอน และคูณเลขยกกำลังที่บิตเป็น 1 แฟร์มา: aᵖ⁻¹ ≡ 1 (mod p) สำหรับจำนวนเฉพาะ p ที่หาร a ไม่ลงตัว ดังนั้นลดเลขชี้กำลังมอดูโล p − 1 ได้ RSA: เลือกจำนวนเฉพาะ p และ q, n = p·q และ φ(n) = (p − 1)(q − 1) เลขชี้กำลังสาธารณะ e เป็นจำนวนเฉพาะสัมพัทธ์กับ φ(n) และเลขชี้กำลังส่วนตัวคือ d = e⁻¹ mod φ(n) เข้ารหัสด้วย c = mᵉ mod n และถอดรหัสด้วย m = cᵈ mod n