พื้นฐานวิทยาการคอมพิวเตอร์: ชุดสรุปเร่งรัด

สรุปสูตร ขั้นตอนวิธีทำที่สำคัญของทุกหัวข้อ และโจทย์ฝึก 20 ข้อ พร้อมเฉลยละเอียดไว้ท้ายเล่ม

โจทย์ใหม่กลับไปที่รายวิชา

ในหน้าต่างพิมพ์ ให้เลือก “บันทึกเป็น PDF” เพื่อเก็บสำเนาไว้ในอุปกรณ์ของคุณ

1สูตรและวิธีทำ

ระบบเลข

ค่าประจำตำแหน่ง
ฐานสอง 2k, ฐานแปด 8k, ฐานสิบหก 16k
เป็นเลขฐานสิบ
Σ dk·bk
จากเลขฐานสิบ
หารด้วยฐาน อ่านเศษจากล่างขึ้นบน
ฐานสิบหก ↔ ฐานสอง
เลขฐานสิบหกหนึ่งหลัก = 4 บิต
two’s complement
กลับบิตแล้วบวก 1

ตรรกศาสตร์ประพจน์และการพิสูจน์

แถวของตารางค่าความจริง
2ⁿ
นัยสำคัญ (ถ้า–แล้ว)
p → q ≡ ¬p ∨ q ≡ ¬q → ¬p
นิเสธของนัย
¬(p → q) ≡ p ∧ ¬q
เงื่อนไขสองทาง
p ↔ q ≡ (p → q) ∧ (q → p)
กฎของเดอมอร์แกน
¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q
กฎการแจกแจง
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
นิเสธของตัวบ่งปริมาณ
¬∀x P(x) ≡ ∃x ¬P(x), ¬∃x P(x) ≡ ∀x ¬P(x)
โมดัสโพเนนส์ โมดัสโทลเลนส์
p → q, p ⊢ q; p → q, ¬q ⊢ ¬p

วิธีการ

  1. นับจำนวนตัวแปรที่ต่างกัน ตารางค่าความจริงมี 2ⁿ แถว โดยเริ่มจากแถวที่ทุกตัวเป็น 1
  2. ให้ทุกประพจน์ย่อยมีคอลัมน์ของตัวเอง และเติมคอลัมน์จากด้านในออกมาด้านนอก
  3. ใช้กฎของตัวเชื่อมแต่ละตัว: → เป็น 0 เฉพาะเมื่อ 1 → 0 และ ↔ เป็น 1 เมื่อทั้งสองข้างมีค่าเท่ากัน
  4. สำหรับความสมมูล ให้เปรียบเทียบคอลัมน์สุดท้ายทีละแถว สำหรับการอ้างเหตุผล ให้ดูเฉพาะแถวที่ทุกสมมติฐานเป็น 1
  5. การหานิเสธของข้อความที่มีตัวบ่งปริมาณ ให้ย้าย ¬ เข้าไปด้านใน สลับ ∀ กับ ∃ และใส่นิเสธให้สูตรด้านใน

ตรรกะดิจิทัล: เกต แผนที่คาร์โนห์ และฟลิปฟล็อป

เกตพื้นฐาน
A·B, A + B, A′, (A·B)′, (A + B)′, A ⊕ B
กฎของพีชคณิตแบบบูล
X + X′ = 1, X·X′ = 0, X + XY = X, XY + XY′ = X
กฎของเดอมอร์แกน
(X·Y)′ = X′ + Y′, (X + Y)′ = X′·Y′
ลำดับของแผนที่คาร์โนห์
00, 01, 11, 10 (Gray code)
กลุ่มของ 2ᵏ เซลล์
สูญเสีย k ตัวแปร
มัลติเพล็กเซอร์ 4 ต่อ 1
F = A′B′I0 + A′BI1 + AB′I2 + ABI3
ฟลิปฟล็อป
D: Q⁺ = D, T: Q⁺ = T ⊕ Q, JK: Q⁺ = JQ′ + K′Q
ตัวนับ
n บิต: 2ⁿ สถานะ; มอด N: n ที่น้อยที่สุดที่ 2ⁿ ≥ N; fout = fclk/N
ตัวนับริปเปิล
fmax = 1/(n·tpd)
ตัวนับริงและตัวนับจอห์นสัน
n และ 2n สถานะ

วิธีการ

  1. สำหรับวงจร ให้ทำจากอินพุตไปถึงเอาต์พุตทีละเกตและเขียนค่าบนทุกเส้น หรือเขียนนิพจน์ของมันแล้วเติมตารางค่าความจริง
  2. สำหรับการทำให้ง่าย ให้ใส่ 1 (และค่าไม่สนใจเป็น X) ลงในแผนที่คาร์โนห์ที่มีแถวและคอลัมน์เรียงตามรหัสเกรย์: 00, 01, 11, 10
  3. ครอบคลุม 1 ด้วยกลุ่ม 1, 2, 4, 8 หรือ 16 เซลล์ให้น้อยที่สุดและใหญ่ที่สุดเท่าที่เป็นไปได้ โดยพันข้ามขอบ แต่ละกลุ่มคือหนึ่งพจน์ผลคูณที่ประกอบด้วยตัวแปรที่คงที่ จัดกลุ่ม 0 สำหรับรูป POS
  4. สำหรับฟลิปฟล็อปและตัวนับ ให้อ่านอินพุตที่ขอบแอ็กทีฟของสัญญาณนาฬิกาแต่ละขอบ เขียนสถานะหลังทุกขอบ และจำไว้ว่าตัวนับ n บิตวนกลับหลัง 2ⁿ สถานะ

ทฤษฎีจำนวนและเลขคณิตมอดูลาร์

การหารที่มีเศษ
a = q·n + r, 0 ≤ r < n
ยูคลิด
gcd(a, b) = gcd(b, a mod b)
ตัวคูณร่วมน้อย
lcm(a, b) = a·b/gcd(a, b)
อินเวอร์ส
a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
ความสอดคล้องเชิงเส้น
a·x ≡ b → x ≡ a⁻¹·b (mod n)
ฟังก์ชันโทเทียนต์ของออยเลอร์
φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
แฟร์มา
aᵖ⁻¹ ≡ 1 (mod p)
RSA
n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n

วิธีการ

  1. ลดทุกจำนวนมอดูโล n ก่อน เศษจะอยู่ระหว่าง 0 ถึง n − 1
  2. สำหรับ ห.ร.ม. ให้หารซ้ำด้วยขั้นตอนวิธีของยูคลิด เศษที่ไม่เป็นศูนย์ตัวสุดท้ายคือ ห.ร.ม.
  3. สำหรับตัวผกผัน ให้ทำขั้นตอนวิธีแบบขยาย และเก็บสัมประสิทธิ์ของ a ถ้าเป็นลบให้บวก n
  4. แก้ a·x ≡ b โดยคูณด้วย a⁻¹ รวมสองความสอดคล้องโดยเขียน x = r₁ + m₁k
  5. สำหรับเลขยกกำลัง ให้เขียนเลขชี้กำลังเป็นเลขฐานสองแล้วยกกำลังสองซ้ำ ใน RSA จะได้ d = e⁻¹ mod φ(n) โดย φ(n) = (p − 1)(q − 1)

ทฤษฎีกราฟ

เล็มมาการจับมือ
Σ deg(v) = 2|E|
กราฟบริบูรณ์
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
กราฟปรกติ
|E| = n·k/2
ต้นไม้และป่า
|E| = n − 1, |E| = n − c
ใบของต้นไม้
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
ออยเลอร์
วงจร: ดีกรีเป็นคู่ทุกจุดยอด; ทางเดิน: มีดีกรีคี่พอดี 2 จุดยอด
วงจรแฮมิลตันใน Kn
(n − 1)!/2
การปรับค่าของไดก์สตรา
d(v) = min(d(v), d(u) + w(u, v))
วอล์กความยาว L
(Mᴸ)ij

วิธีการ

  1. เขียนดีกรีของทุกจุดยอด ผลบวกของดีกรีเท่ากับสองเท่าของจำนวนเส้นเชื่อม
  2. สำหรับโจทย์ออยเลอร์ ให้ตรวจว่ากราฟเชื่อมโยงกัน และนับจุดยอดที่มีดีกรีคี่
  3. สำหรับต้นไม้ ให้ใช้ว่ามี n − 1 เส้นเชื่อม และเล็มมาการจับมือ
  4. สำหรับไดก์สตรา ให้เก็บตารางระยะทางชั่วคราว และยืนยันจุดยอดที่ยังไม่ยืนยันซึ่งมีค่าน้อยที่สุดในแต่ละรอบ
  5. สำหรับต้นไม้ทอดข้ามค่าน้อยที่สุด ให้เรียงเส้นเชื่อมตามน้ำหนักและข้ามทุกเส้นที่ทำให้เกิดวัฏจักร (ครัสคัล) หรือขยายต้นไม้ต้นเดียวจากจุดยอดเริ่มต้น (พริม)

การแบ่งซับเน็ต IPv4

โฮสต์ต่อซับเน็ต
2(32 − prefix) − 2 (/31: 2, /32: 1)
ขนาดบล็อก
256 − (mask octet)
ที่อยู่เครือข่าย
IP AND มาสก์
ที่อยู่บรอดคาสต์
IP OR (NOT mask): บิตโฮสต์ทั้งหมดเป็น 1
ซับเน็ตจาก n บิตที่ยืม
2n

2โจทย์ฝึก

1.ระบบเลขปานกลาง
ค่าประจำตำแหน่งใน two's complement1−12806403211608141211

รูปแบบ 8 บิต 1001 0111 เก็บจำนวนเต็มมีเครื่องหมายแบบ two's complement ค่าของมัน N ในเลขฐานสิบคือเท่าใด

1001 01118 bit
N =
2.ระบบเลขยาก
คลิกบิตเพื่อตั้งค่า012806403201608040201

ตั้งบิตให้เป็นผลลัพธ์ 8 บิตของ 1101 0001 << 1 ค่าของผลลัพธ์ R เป็นเท่าใดในเลขฐานสิบ

1101 0001<< 1
R =
3.ตรรกศาสตร์ประพจน์และการพิสูจน์ปานกลาง
ซ้ำซ้อน (tautology)ขัดแย้ง (contradiction)contingency

((p → q) ∧ q) → p เป็น tautology, contradiction หรือ contingency ให้คลิกคำตอบของคุณ

((p → q) ∧ q) → p
  1. 1ซ้ำซ้อน (tautology)
  2. 2ขัดแย้ง (contradiction)
  3. 3contingency
4.ตรรกศาสตร์ประพจน์และการพิสูจน์ยาก
∀x ¬A(x)∃x ¬A(x)∀x A(x)∃x A(x)

ประโยคใดสมมูลกับ ¬∃x A(x) เมื่อย้ายนิเสธเข้าด้านในสุด ให้คลิกประโยคนั้น

¬∃x A(x)
  1. 1∀x ¬A(x)
  2. 2∃x ¬A(x)
  3. 3∀x A(x)
  4. 4∃x A(x)
5.ตรรกะดิจิทัล: เกต แผนที่คาร์โนห์ และฟลิปฟล็อปปานกลาง
ABC00011110010001131214051716

ใช้แผนที่คาร์โนห์หารูปผลบวกของผลคูณ (SOP) ที่น้อยที่สุดของ F(A, B, C) = Σm(2, 3, 4, 6, 7) มีลิเทอรัลรวมกี่ตัว L (ตัวแปรที่มีไพรม์นับเป็นหนึ่งลิเทอรัล)

F(A, B, C) = Σm(2, 3, 4, 6, 7)
L =
6.ตรรกะดิจิทัล: เกต แผนที่คาร์โนห์ และฟลิปฟล็อปยาก
ABCD0001111000011110X01103121405X706X120131150140809111X10

จงหารูป SOP ที่น้อยที่สุดของ F(A, B, C, D) = Σm(1, 2, 4, 11, 15) + d(0, 7, 10, 12) โดย d แทนเงื่อนไขไม่สนใจ มีกี่พจน์ผลคูณ N

F(A, B, C, D) = Σm(1, 2, 4, 11, 15) + d(0, 7, 10, 12)
N =
7.ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ปานกลาง

จงหาฟังก์ชันโทเทียนต์ของออยเลอร์ φ(1445) ซึ่งเป็นจำนวนของจำนวนเต็มตั้งแต่ 1 ถึง 1445 ที่เป็นจำนวนเฉพาะสัมพัทธ์กับ 1445

n = 1445 = 5·172
φ(1445) =
8.ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ยาก
mc = me​ mod ncm = cd​ mod nm(n, e) = (1147, 23)d = ?

กุญแจ RSA ใช้จำนวนเฉพาะ p = 31 และ q = 37 และเลขชี้กำลังสาธารณะ e = 23 จงหาเลขชี้กำลังส่วนตัว d (0 < d < φ(n))

p = 31q = 37e = 23
d =
9.อัลกอริทึมและความซับซ้อนปานกลาง

การโปรแกรมพลวัต (dynamic programming) มีประโยชน์เมื่อปัญหามี

  1. Aลูปเพียงชั้นเดียว
  2. Bไม่มีปัญหาย่อยเลย จึงแก้ได้ในขั้นตอนเดียว
  3. Cอินพุตสุ่มเท่านั้น
  4. Dปัญหาย่อยที่ซ้อนทับกันและโครงสร้างย่อยเหมาะสมที่สุด
10.อัลกอริทึมและความซับซ้อนยาก

ขอบเขตใดถูกต้องสำหรับ log(n!)

  1. AΘ(log n)
  2. BΘ(n²)
  3. CΘ(n)
  4. DΘ(n log n)
11.โครงสร้างข้อมูลปานกลาง

เครือข่ายถนนมี 100,000 ทางแยก แต่ละแห่งเชื่อมกับประมาณ 4 แห่ง การแทนแบบใดเหมาะที่สุด

  1. Aฮีปทวิภาคของเส้นเชื่อม
  2. Bเมทริกซ์ประชิด
  3. Cอาร์เรย์เรียงลำดับเดียวของจุดยอด
  4. Dรายการประชิด
12.โครงสร้างข้อมูลยาก

เวลาทำงานของการค้นหาในแนวกว้างบนกราฟที่มี V จุดยอดที่เก็บเป็นเมทริกซ์ประชิดคือเท่าใด

  1. AO(V²)
  2. BO(V)
  3. CO(V + E)
  4. DO(E log V)
13.ทฤษฎีกราฟปานกลาง
ABCDEFGวงจรออยเลอร์ทางเดินออยเลอร์ ไม่มีวงจรไม่ใช่ทั้งสองอย่าง

กราฟเชื่อมโยงนี้มีวงจรออยเลอร์ ทางเดินออยเลอร์ที่ไม่ใช่วงจร หรือไม่มีทั้งสองอย่าง ให้คลิกคำตอบของคุณ

|V| = 7|E| = 11
  1. 1วงจรออยเลอร์
  2. 2ทางเดินออยเลอร์ ไม่มีวงจร
  3. 3ไม่ใช่ทั้งสองอย่าง
14.ทฤษฎีกราฟยาก
4201923141518ABCDEFG

ขั้นตอนวิธีของพริมสร้างต้นไม้ทอดข้ามค่าน้อยที่สุดโดยเริ่มจากจุดยอด F ให้คลิกเส้นเชื่อมที่เพิ่มเป็นเส้นหมายเลข 2

เริ่มต้น: Fk = 2
  1. 1เส้นเชื่อม AB
  2. 2เส้นเชื่อม AC
  3. 3เส้นเชื่อม BC
  4. 4เส้นเชื่อม BD
  5. 5เส้นเชื่อม CE
  6. 6เส้นเชื่อม DF
  7. 7เส้นเชื่อม GB
  8. 8เส้นเชื่อม GC
  9. 9เส้นเชื่อม GE
15.ฐานข้อมูลและ SQLปานกลาง

WHERE EXISTS (subquery) เป็นจริงสำหรับแถวเมื่อใด?

  1. Aเมื่อซับคิวรีคืนตัวเลขที่มากกว่าศูนย์
  2. Bเมื่อซับคิวรีคืนหนึ่งแถวพอดี
  3. Cเมื่อซับคิวรีคืนอย่างน้อยหนึ่งแถว
  4. Dเมื่อซับคิวรีไม่คืนค่า NULL
16.ฐานข้อมูลและ SQLยาก

ดัชนีครอบคลุม (covering index) สำหรับคิวรีคืออะไร?

  1. Aดัชนีที่สร้างใหม่ทุกคืน
  2. Bดัชนีบนคีย์หลักเท่านั้น
  3. Cดัชนีที่มีทุกคอลัมน์ที่คิวรีต้องการ จึงไม่ต้องอ่านตัวตาราง
  4. Dดัชนีที่ครอบคลุมทุกคอลัมน์ของทุกตาราง
17.เครือข่ายคอมพิวเตอร์ปานกลาง

แฟล็ก TCP ใดบอกว่าผู้ส่งส่งข้อมูลเสร็จแล้ว?

  1. AURG
  2. BPSH
  3. CFIN
  4. DSYN
18.เครือข่ายคอมพิวเตอร์ยาก

การแบ่งส่วน (fragmentation) ใน IPv6 ต่างจาก IPv4 อย่างไร?

  1. AIPv6 แบ่งส่วนที่ชั้นทรานสปอร์ตภายใน TCP
  2. Bเราเตอร์ IPv6 แบ่งส่วนทุกแพ็กเก็ตที่ใหญ่กว่า 64 ไบต์ก่อนส่งต่อไปตามเส้นทาง
  3. CIPv6 ไม่อนุญาตแพ็กเก็ตที่ใหญ่กว่า 576 ไบต์
  4. Dเราเตอร์ไม่แบ่งส่วนแพ็กเก็ต IPv6 เลย เฉพาะต้นทางทำได้ โดยใช้ path MTU discovery
19.การแบ่งซับเน็ต IPv4ปานกลาง
/?11111111111111111111100000000000บิตเครือข่ายบิตโฮสต์

แผนกหนึ่งต้องการที่อยู่โฮสต์ 1924 ที่อยู่ในซับเน็ตเดียว ความยาวพรีฟิกซ์ที่ยาวที่สุด p (ซับเน็ตเล็กที่สุด) ที่ใหญ่พอคือเท่าใด

1924 hosts
p =
20.การแบ่งซับเน็ต IPv4ยาก
ออคเต็ตสุดท้าย = 17012806403211608040211เครือข่ายโฮสต์

โฮสต์มีที่อยู่ 10.20.225.17/26 ตัวเลขสุดท้าย (ออคเต็ตที่สี่) x ของที่อยู่บรอดคาสต์ของซับเน็ตคือเท่าใด

10.20.225.17/26
x =

3สารละลาย

1.ระบบเลข

คำตอบ: N = −105

ระบบเลขตามตำแหน่ง: แต่ละหลักมีค่าเท่ากับค่าของหลักนั้นคูณกำลังของฐาน ในเลขฐานสองแต่ละตำแหน่งมีค่า 1, 2, 4, 8, 16, …; ในเลขฐานสิบหก 1, 16, 256, … โดย A–F แทน 10–15 ในระบบ two's complement 8 บิต บิตซ้ายสุดมีค่า −128 แทนที่จะเป็น +128 ซึ่งเป็นวิธีเก็บจำนวนลบ

บวกค่าประจำตำแหน่ง

บิตอื่นยังคงมีค่าเป็นบวกตามปกติ

−128 + 16 + 4 + 2 + 1 = −105

คำตอบ

N = −105
2.ระบบเลข

คำตอบ: R = 162

การตั้งค่าบิต: แต่ละบิตมีค่าเป็นกำลังของสอง (128, 64, …, 1) เลขฐานสิบหกหนึ่งหลักคือสี่บิตพอดี และใน two's complement 8 บิต บิตซ้ายสุดมีค่า −128 การดำเนินการระดับบิตทำงานกับแต่ละตำแหน่งบิตแยกกัน

ทีละบิต

การเลื่อนซ้าย 1 ตำแหน่งย้ายทุกบิตไปทางซ้าย 1 ตำแหน่ง บิตที่หลุดออกปลายซ้ายหายไปและศูนย์เข้ามาทางขวา

1101 0001 << 1
= 1010 0010

ค่าของผลลัพธ์

1010 0010₂ = 162

คำตอบ

R = 162
3.ตรรกศาสตร์ประพจน์และการพิสูจน์

คำตอบ: contingency

ความสมมูลเชิงตรรกะ: สูตรสองสูตรสมมูลกัน (≡) เมื่อมีค่าเท่ากันทุกแถวของตารางค่าความจริง ซ้ำซ้อน (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)

ตารางค่าความจริงทีละแถว

p = 1, q = 1: p → q = 1, (p → q) ∧ q = 1, ((p → q) ∧ q) → p = 1
p = 1, q = 0: p → q = 0, (p → q) ∧ q = 0, ((p → q) ∧ q) → p = 1
p = 0, q = 1: p → q = 1, (p → q) ∧ q = 1, ((p → q) ∧ q) → p = 0
p = 0, q = 0: p → q = 1, (p → q) ∧ q = 0, ((p → q) ∧ q) → p = 1

จัดประเภท

((p → q) ∧ q) → p: 1, 1, 0, 1
1 ใน 3 จาก 4 แถว 0 ในแถวอื่น: ประพจน์ที่ไม่แน่นอน (contingency)

คำตอบ

contingency
4.ตรรกศาสตร์ประพจน์และการพิสูจน์

คำตอบ: ∀x ¬A(x)

ตัวบ่งปริมาณและการอ้างเหตุผล: ¬∀x P(x) ≡ ∃x ¬P(x) และ ¬∃x P(x) ≡ ∀x ¬P(x) ย้ายนิเสธเข้าด้านใน สลับทุกตัวบ่งปริมาณที่นิเสธผ่าน และใส่นิเสธให้สูตรด้านในด้วยกฎของประพจน์ เช่น ¬(a → b) ≡ a ∧ ¬b การอ้างเหตุผลสมเหตุสมผลเมื่อบทสรุปเป็น 1 ในทุกแถวที่สมมติฐานทั้งหมดเป็น 1 แถวเดียวที่สมมติฐานเป็นจริงแต่บทสรุปเป็นเท็จคือตัวอย่างค้านและแสดงว่าการอ้างเหตุผลนั้นไม่สมเหตุสมผล

ย้ายนิเสธเข้าด้านใน

¬∃x A(x) ≡ ∀x ¬A(x)

คำตอบ

∀x ¬A(x)

ตัวเลือกอื่นอาจคงตัวบ่งปริมาณไว้ไม่เปลี่ยน เปลี่ยนลำดับของตัวบ่งปริมาณ หรือใส่นิเสธให้สูตรด้านในผิด

5.ตรรกะดิจิทัล: เกต แผนที่คาร์โนห์ และฟลิปฟล็อป

คำตอบ: L = 3

แผนที่คาร์โนห์: เซลล์เรียงตามรหัสเกรย์ (00, 01, 11, 10) ดังนั้นเซลล์ที่อยู่ติดกัน รวมถึงเซลล์ที่อยู่ตรงข้ามขอบ ต่างกันเพียงตัวแปรเดียว จัดกลุ่ม 1 เป็นสี่เหลี่ยมที่มี 1, 2, 4, 8 หรือ 16 เซลล์ ให้ใหญ่ที่สุดและมีจำนวนกลุ่มน้อยที่สุดจนครอบคลุมทุก 1 แต่ละกลุ่มคือหนึ่งพจน์ผลคูณ: ตัวแปรที่คงที่ภายในกลุ่ม กลุ่มที่มี 2ᵏ เซลล์สูญเสียตัวแปรไป k ตัว ค่าไม่สนใจ (X) ใช้เพื่อทำให้กลุ่มใหญ่ขึ้นได้ แต่ไม่จำเป็นต้องถูกครอบคลุม การจัดกลุ่ม 0 แทนจะได้รูป POS ที่น้อยที่สุด

ABC00011110010001131214051716

จัดกลุ่ม 1

ทุกกลุ่มเป็นสี่เหลี่ยมของ 2ᵏ เซลล์ เซลล์ที่ขอบเป็นเพื่อนบ้านของเซลล์ที่ขอบตรงข้าม

B
AC′

รูป SOP ที่น้อยที่สุด

F = B + AC′
L = 3

คำตอบ

L = 3
6.ตรรกะดิจิทัล: เกต แผนที่คาร์โนห์ และฟลิปฟล็อป

คำตอบ: N = 4

แผนที่คาร์โนห์: เซลล์เรียงตามรหัสเกรย์ (00, 01, 11, 10) ดังนั้นเซลล์ที่อยู่ติดกัน รวมถึงเซลล์ที่อยู่ตรงข้ามขอบ ต่างกันเพียงตัวแปรเดียว จัดกลุ่ม 1 เป็นสี่เหลี่ยมที่มี 1, 2, 4, 8 หรือ 16 เซลล์ ให้ใหญ่ที่สุดและมีจำนวนกลุ่มน้อยที่สุดจนครอบคลุมทุก 1 แต่ละกลุ่มคือหนึ่งพจน์ผลคูณ: ตัวแปรที่คงที่ภายในกลุ่ม กลุ่มที่มี 2ᵏ เซลล์สูญเสียตัวแปรไป k ตัว ค่าไม่สนใจ (X) ใช้เพื่อทำให้กลุ่มใหญ่ขึ้นได้ แต่ไม่จำเป็นต้องถูกครอบคลุม การจัดกลุ่ม 0 แทนจะได้รูป POS ที่น้อยที่สุด

ไพรม์อิมพลิแคนต์

กลุ่มที่ใหญ่ที่สุดที่สร้างได้จาก 1 และ X

B′CD′, BC′D′, BCD, A′C′D′, ACD, A′B′D′, A′B′C′, AB′C
ABCD0001111000011110X01103121405X706X120131150140809111X10

การครอบคลุมที่น้อยที่สุด

F = B′CD′ + BC′D′ + ACD + A′B′C′
N = 4

คำตอบ

N = 4

มีการจัดกลุ่มอีกแบบที่มีขนาดเท่ากัน ซึ่งมีจำนวนพจน์และลิเทอรัลเท่ากัน

7.ทฤษฎีจำนวนและเลขคณิตมอดูลาร์

คำตอบ: φ(1445) = 1088

ตัวผกผันและความสอดคล้อง: 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)

ตัวประกอบเฉพาะ

1445 = 5·172

โทเทียนต์

φ(1445) = φ(5)·φ(289) = 4·272 = 1088

คำตอบ

φ(1445) = 1088
8.ทฤษฎีจำนวนและเลขคณิตมอดูลาร์

คำตอบ: d = 47

เลขยกกำลังมอดูลาร์และ 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

มอดูลัสและโทเทียนต์

n = 31·37 = 1147
φ(n) = 30·36 = 1080

ขั้นตอนวิธีของยูคลิดแบบขยาย

r = 1080, t = 0
r = 23, q = 46, t = 1
r = 22, q = 1, t = −46
r = 1, q = 22, t = 47

เลขชี้กำลังส่วนตัว

d = 47
ตรวจสอบ: 23·47 = 1081 = 1·1080 + 1

คำตอบ

d = 47
9.อัลกอริทึมและความซับซ้อน

คำตอบ: D · ปัญหาย่อยที่ซ้อนทับกันและโครงสร้างย่อยเหมาะสมที่สุด

เหตุผลที่เป็นคำตอบนี้

การเก็บผลของปัญหาย่อยที่ซ้อนทับกัน (memoisation หรือ tabulation) ช่วยหลีกเลี่ยงงานซ้ำ เปลี่ยนอัลกอริทึมแบบเอกซ์โพเนนเชียลให้เป็นพหุนาม

คำตอบ

D · ปัญหาย่อยที่ซ้อนทับกันและโครงสร้างย่อยเหมาะสมที่สุด
10.อัลกอริทึมและความซับซ้อน

คำตอบ: D · Θ(n log n)

เหตุผลที่เป็นคำตอบนี้

log(n!) ≤ n log n และตัวคูณที่ใหญ่ที่สุด n / 2 ตัวให้ log(n!) ≥ (n / 2) log(n / 2) นี่คือเหตุที่การเรียงแบบเปรียบเทียบต้องใช้ Ω(n log n)

คำตอบ

D · Θ(n log n)
11.โครงสร้างข้อมูล

คำตอบ: D · รายการประชิด

เหตุผลที่เป็นคำตอบนี้

เมทริกซ์ต้องใช้ 1010 ช่อง เกือบทั้งหมดว่าง รายการประชิดเก็บเพียงรายการเส้นเชื่อมราว 400,000 รายการ

คำตอบ

D · รายการประชิด
12.โครงสร้างข้อมูล

คำตอบ: A · O(V²)

เหตุผลที่เป็นคำตอบนี้

จุดยอดทั้ง V สแกนแถวที่มี V ช่อง ได้ O(V²) ส่วนรายการประชิดทำให้ BFS เป็น O(V + E)

คำตอบ

A · O(V²)
13.ทฤษฎีกราฟ

คำตอบ: ทางเดินออยเลอร์ ไม่มีวงจร

ออยเลอร์ แฮมิลตัน และต้นไม้: กราฟเชื่อมโยงมีวงจรออยเลอร์ (ผ่านทุกเส้นเชื่อมครั้งเดียวและกลับจุดเริ่มต้น) เมื่อทุกจุดยอดมีดีกรีคู่ และมีทางเดินออยเลอร์ที่ไม่ใช่วงจรเมื่อมีจุดยอดดีกรีคี่พอดีสองจุด ทางเดินนั้นไปจากจุดยอดคี่จุดหนึ่งถึงอีกจุดหนึ่ง วงจรแฮมิลตันผ่านทุกจุดยอดครั้งเดียว Kn มีวงจรแบบนี้ (n − 1)!/2 วงจร ต้นไม้ที่มี n จุดยอดมี n − 1 เส้นเชื่อม และกราฟเชื่อมโยงที่มี m เส้นเชื่อมจะเหลือต้นไม้ทอดข้ามหลังเอาเส้นเชื่อมออก m − n + 1 เส้น

ดีกรี

deg(A) = 1, deg(B) = 3, deg(C) = 4, deg(D) = 4, deg(E) = 4, deg(F) = 2, deg(G) = 4

จุดยอดคี่

A, B → 2
ทางเดินออยเลอร์ ไม่มีวงจร

คำตอบ

ทางเดินออยเลอร์ ไม่มีวงจร

ทางเดินออยเลอร์เริ่มที่จุดยอดคี่จุดหนึ่งและจบที่อีกจุดหนึ่ง

14.ทฤษฎีกราฟ

คำตอบ: เส้นเชื่อม BD

เส้นทางที่สั้นที่สุดและต้นไม้ทอดข้าม: ขั้นตอนวิธีของไดก์สตรายืนยันหนึ่งจุดยอดต่อรอบ: จุดยอดที่ยังไม่ยืนยันซึ่งมีระยะทางชั่วคราวน้อยที่สุด ระยะทางของมันเป็นค่าสุดท้ายแล้ว และเพื่อนบ้าน v ทุกจุดได้ d(v) = min(d(v), d(u) + w(u, v)) ขั้นตอนวิธีของครัสคัลสร้างต้นไม้ทอดข้ามค่าน้อยที่สุดโดยเลือกเส้นเชื่อมจากเบาไปหนักและข้ามเส้นที่ทำให้เกิดวัฏจักร ขั้นตอนวิธีของพริมขยายต้นไม้หนึ่งต้นจากจุดยอดเริ่มต้นโดยเพิ่มเส้นเชื่อมที่เบาที่สุดที่ออกจากต้นไม้เสมอ ต้นไม้ทอดข้ามที่มี n จุดยอดมี n − 1 เส้นเชื่อม

ขั้นตอนวิธีของพริม

1. DF (14)
2. BD (2)
3. AB (4)
4. GB (15)
5. GC (1)
6. CE (3)

เส้นเชื่อมหมายเลข 2

BD

คำตอบ

เส้นเชื่อม BD
15.ฐานข้อมูลและ SQL

คำตอบ: C · เมื่อซับคิวรีคืนอย่างน้อยหนึ่งแถว

เหตุผลที่เป็นคำตอบนี้

EXISTS ตรวจเพียงว่ามีแถวถูกสร้างหรือไม่ ส่วน NOT EXISTS เป็นจริงเมื่อซับคิวรีไม่คืนแถวเลย

คำตอบ

C · เมื่อซับคิวรีคืนอย่างน้อยหนึ่งแถว
16.ฐานข้อมูลและ SQL

คำตอบ: C · ดัชนีที่มีทุกคอลัมน์ที่คิวรีต้องการ จึงไม่ต้องอ่านตัวตาราง

เหตุผลที่เป็นคำตอบนี้

หากทุกคอลัมน์ที่อ้างถึงอยู่ในดัชนี DBMS สแกนเฉพาะดัชนีได้และข้ามการดึงแถวตาราง ซึ่งประหยัด I/O

คำตอบ

C · ดัชนีที่มีทุกคอลัมน์ที่คิวรีต้องการ จึงไม่ต้องอ่านตัวตาราง
17.เครือข่ายคอมพิวเตอร์

คำตอบ: C · FIN

เหตุผลที่เป็นคำตอบนี้

แต่ละฝ่ายส่ง FIN เมื่อไม่มีข้อมูลเหลือ และอีกฝ่ายตอบรับ SYN ใช้เปิดการเชื่อมต่อ ส่วน RST ยกเลิกการเชื่อมต่อ

คำตอบ

C · FIN
18.เครือข่ายคอมพิวเตอร์

คำตอบ: D · เราเตอร์ไม่แบ่งส่วนแพ็กเก็ต IPv6 เลย เฉพาะต้นทางทำได้ โดยใช้ path MTU discovery

เหตุผลที่เป็นคำตอบนี้

เราเตอร์ IPv6 ทิ้งแพ็กเก็ตที่ใหญ่เกินและส่ง ICMPv6 Packet Too Big กลับ จากนั้นต้นทางส่งแพ็กเก็ตที่เล็กลงหรือใช้ส่วนหัวขยายสำหรับการแบ่งส่วน

คำตอบ

D · เราเตอร์ไม่แบ่งส่วนแพ็กเก็ต IPv6 เลย เฉพาะต้นทางทำได้ โดยใช้ path MTU discovery
19.การแบ่งซับเน็ต IPv4

คำตอบ: p = 21

การแบ่งซับเน็ต IPv4: ที่อยู่มี 32 บิต พรีฟิกซ์ /p บอกว่าบิตนำหน้ากี่บิตระบุเครือข่าย ส่วน 32 − p บิตที่เหลือใช้ระบุเลขโฮสต์ ซับเน็ตมี 2³²⁻ᵖ ที่อยู่ แต่ที่อยู่แรก (ที่อยู่เครือข่าย) และที่อยู่สุดท้าย (ที่อยู่บรอดคาสต์) ใช้เป็นโฮสต์ไม่ได้ จึงมีโฮสต์ได้ 2³²⁻ᵖ − 2 เครื่อง ข้อยกเว้น: /31 (ลิงก์แบบจุดต่อจุด, RFC 3021) ใช้ทั้ง 2 แอดเดรสสำหรับโฮสต์ และ /32 เป็นแอดเดรสเดียว (โฮสต์เดียวหรือลูปแบ็ก)

บิตโฮสต์ที่ต้องใช้

210 − 2 = 1022 < 1924
211 − 2 = 2046 ≥ 1924 → h = 11

ความยาวพรีฟิกซ์

p = 32 − 11 = 21

คำตอบ

p = /21
20.การแบ่งซับเน็ต IPv4

คำตอบ: x = 63

การแบ่งซับเน็ต IPv4: ที่อยู่มี 32 บิต พรีฟิกซ์ /p บอกว่าบิตนำหน้ากี่บิตระบุเครือข่าย ส่วน 32 − p บิตที่เหลือใช้ระบุเลขโฮสต์ ซับเน็ตมี 2³²⁻ᵖ ที่อยู่ แต่ที่อยู่แรก (ที่อยู่เครือข่าย) และที่อยู่สุดท้าย (ที่อยู่บรอดคาสต์) ใช้เป็นโฮสต์ไม่ได้ จึงมีโฮสต์ได้ 2³²⁻ᵖ − 2 เครื่อง ข้อยกเว้น: /31 (ลิงก์แบบจุดต่อจุด, RFC 3021) ใช้ทั้ง 2 แอดเดรสสำหรับโฮสต์ และ /32 เป็นแอดเดรสเดียว (โฮสต์เดียวหรือลูปแบ็ก)

ขนาดบล็อก

26 = 64

ซับเน็ตของโฮสต์นี้

เครือข่าย: ⌊17/64⌋·64 = 0
บรอดคาสต์: 0 + 64 − 1 = 63
โฮสต์ที่ใช้ได้: 1 … 62

คำตอบ

x = 63

ExamProblems · examproblems.com/courses/computer-science-fundamentals