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

สรุปสูตร ขั้นตอนวิธีทำที่สำคัญของทุกหัวข้อ และโจทย์ฝึก 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 complement 8 บิต0−12806403201608040201

ตั้งบิตให้เก็บ −10 ใน two's complement 8 บิต อ่านเป็นจำนวนไม่มีเครื่องหมาย ค่าของรูปแบบ U เป็นเท่าใด

N = −108 bit
U =
2.ระบบเลขยาก
รหัส 299 ตัว, b = ? บิต?2ᵇ⁻¹…?4?2?1

ระบบต้องให้รหัสฐานสองความยาวเท่ากันแก่สิ่งของ 299 ชิ้น ชิ้นละหนึ่งรหัส ต้องใช้อย่างน้อยกี่บิต b

299
b = bit
3.ตรรกศาสตร์ประพจน์และการพิสูจน์ปานกลาง
(b → a) ∧ (¬a → ¬b)b ∧ a(b → a) ∧ (a → b)(b → a) ∨ (a → b)

สูตรใดสมมูลเชิงตรรกะกับ b ↔ a ให้คลิกสูตรนั้น

b ↔ a
  1. 1(b → a) ∧ (¬a → ¬b)
  2. 2b ∧ a
  3. 3(b → a) ∧ (a → b)
  4. 4(b → a) ∨ (a → b)
4.ตรรกศาสตร์ประพจน์และการพิสูจน์ยาก
rq ∧ ¬r¬r¬q

กำหนดสมมติฐาน q → r; q บทสรุปใดตามมาจากสมมติฐานเหล่านี้ ให้คลิกบทสรุปนั้น

q → rq
  1. 1r
  2. 2q ∧ ¬r
  3. 3¬r
  4. 4¬q
5.ตรรกะดิจิทัล: เกต แผนที่คาร์โนห์ และฟลิปฟล็อปปานกลาง
ABCD0001111000011110111111

ในแผนที่คาร์โนห์นี้มี 1 เพียงตัวเดียวพอดีที่ไม่มี 1 อยู่ติดกัน จึงยังเป็นกลุ่มหนึ่งเซลล์ (มินเทอมเต็มที่มีสี่ลิเทอรัล) ในรูป SOP ที่น้อยที่สุด เพื่อนบ้านข้ามขอบแผนที่นับด้วย ให้คลิกเซลล์นั้น

F = Σm(3, 6, 9, 11, 12, 13)
  1. 1AB = 00, CD = 00
  2. 2AB = 00, CD = 01
  3. 3AB = 00, CD = 11
  4. 4AB = 00, CD = 10
  5. 5AB = 01, CD = 00
  6. 6AB = 01, CD = 01
  7. 7AB = 01, CD = 11
  8. 8AB = 01, CD = 10
  9. 9AB = 11, CD = 00
  10. 10AB = 11, CD = 01
  11. 11AB = 11, CD = 11
  12. 12AB = 11, CD = 10
  13. 13AB = 10, CD = 00
  14. 14AB = 10, CD = 01
  15. 15AB = 10, CD = 11
  16. 16AB = 10, CD = 10
6.ตรรกะดิจิทัล: เกต แผนที่คาร์โนห์ และฟลิปฟล็อปยาก
TQ0​Q0​TQ1​Q1​TQ2​Q2​TQ3​Q3​TQ4​Q4​TQ5​Q5​CLK

ตัวนับริปเปิล (อะซิงโครนัส) 6 บิตสร้างจากฟลิปฟล็อปที่มีความหน่วงการแพร่กระจายตัวละ 8 ns เอาต์พุตทั้งหมดต้องนิ่งก่อนขอบสัญญาณนาฬิกาถัดไป จงหาความถี่นาฬิกาสูงสุด fmax

n = 6tpd = 8 ns
fmax = MHz
7.ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ปานกลาง

จงแก้ 43x ≡ 62 (mod 73) ให้คำตอบ x ที่ 0 < x < 73

43x ≡ 62 (mod 73)
x =
8.ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ยาก
91c = me​ mod n?m = cd​ mod nm(n, e) = (145, 19)d

เข้ารหัสข้อความ m = 91 ด้วยกุญแจสาธารณะ RSA (n, e) = (145, 19) จงหาข้อความเข้ารหัส c

n = 145e = 19m = 91
c =
9.อัลกอริทึมและความซับซ้อนปานกลาง

การค้นหาแบบทวิภาคต้องเปรียบเทียบประมาณกี่ครั้งในกรณีเลวร้ายที่สุดบนอาร์เรย์ที่เรียงแล้วซึ่งมี 1,000,000 สมาชิก

  1. Aประมาณ 1,000
  2. Bประมาณ 500,000
  3. Cประมาณ 20
  4. Dประมาณ 100
10.อัลกอริทึมและความซับซ้อนยาก

เหตุใดอัลกอริทึมของ Dijkstra จึงอาจให้ผลผิดเมื่อน้ำหนักเส้นเชื่อมบางเส้นติดลบ

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

ต้นทุนของการแทรกสมาชิกตรงกลางอาร์เรย์ที่มี n สมาชิกคือเท่าใด

  1. AO(n²) เพราะแต่ละสมาชิกย้าย n ครั้ง
  2. BO(log n) เพราะการค้นหาแบบทวิภาค
  3. CO(1) เพราะทราบดัชนี
  4. DO(n) เพราะสมาชิกหลังจากนั้นต้องเลื่อน
12.โครงสร้างข้อมูลยาก

โครงสร้างข้อมูลใดรองรับแคช LRU (least recently used) ที่ get และ put เป็น O(1)

  1. Aสแตกเท่านั้น
  2. Bอาร์เรย์เรียงลำดับเดียว
  3. Chash map ร่วมกับลิงก์ลิสต์สองทิศทาง
  4. Dbinary search tree เท่านั้น
13.ทฤษฎีกราฟปานกลาง

กราฟบริบูรณ์ K5 มีวงจรแฮมิลตันที่แตกต่างกันกี่วงจร H วงจรที่ต่างกันเพียงจุดยอดเริ่มต้นหรือทิศทางนับเป็นวงจรเดียวกัน

K5
H =
14.ทฤษฎีกราฟยาก
13518820472ABCDEF

จงหาน้ำหนักรวม W ของต้นไม้ทอดข้ามค่าน้อยที่สุดของกราฟถ่วงน้ำหนัก

|V| = 6|E| = 8
W =
15.ฐานข้อมูลและ SQLปานกลาง

SELECT name, CASE WHEN grade >= 5.5 THEN 'pass' ELSE 'fail' END FROM results คืนอะไร?

  1. Aจำนวนนักเรียนที่สอบผ่านและสอบตก
  2. Bเฉพาะนักเรียนที่สอบผ่าน
  3. Cข้อผิดพลาด เพราะ CASE ไม่อนุญาตใน SELECT
  4. Dชื่อแต่ละคนพร้อมป้าย 'pass' หรือ 'fail' ตามเกรด
16.ฐานข้อมูลและ SQLยาก

แอปรัน UPDATE item SET qty = 4, version = 8 WHERE id = 1 AND version = 7 และรายงานความขัดแย้งหากไม่มีแถวถูกอัปเดต นี่คือเทคนิคใด?

  1. Awrite-ahead logging
  2. Bการควบคุมภาวะพร้อมกันแบบมองโลกในแง่ดี (optimistic concurrency control)
  3. Ctwo-phase locking แบบเข้มงวดโดยล็อกระดับแถว
  4. Dการแบ่งส่วนฐานข้อมูล (sharding)
17.เครือข่ายคอมพิวเตอร์ปานกลาง

เหตุใด UDP จึงมักเป็นที่นิยมสำหรับวิดีโอคอลสด?

  1. AUDP เข้ารหัสข้อมูลโดยอัตโนมัติ
  2. Bความหน่วงต่ำสำคัญกว่าการส่งแพ็กเก็ตที่สูญหายซ้ำทุกแพ็กเก็ต
  3. CUDP รับประกันว่าทุกแพ็กเก็ตมาถึง ภาพจึงไม่ค้างเลย
  4. Dวิดีโอทุกชนิดต้องใช้ UDP
18.เครือข่ายคอมพิวเตอร์ยาก

สวิตช์ 8 พอร์ต (ไม่มี VLAN) มีหนึ่งโฮสต์ต่อพอร์ต มีคอลลิชันโดเมนและบรอดแคสต์โดเมนอย่างละกี่โดเมน?

  1. A1 คอลลิชันโดเมน 1 บรอดแคสต์โดเมน
  2. B8 คอลลิชันโดเมน 8 บรอดแคสต์โดเมน
  3. C1 คอลลิชันโดเมน 8 บรอดแคสต์โดเมน
  4. D8 คอลลิชันโดเมน 1 บรอดแคสต์โดเมน
19.การแบ่งซับเน็ต IPv4ปานกลาง
/?11111111111111111111111000000000บิตเครือข่ายบิตโฮสต์

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

457 hosts
p =
20.การแบ่งซับเน็ต IPv4ยาก
ออกเท็ตที่สาม = 231112816413201608141211เครือข่ายโฮสต์

โฮสต์มีที่อยู่ 172.20.231.162/18 ออกเท็ตที่สาม x ของที่อยู่บรอดแคสต์ของซับเน็ตมันคือเท่าใด

172.20.231.162/18
x =

3สารละลาย

1.ระบบเลข

คำตอบ: U = 246

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

กลับบิตแล้วบวกหนึ่ง

10 = 0000 1010
ที่กลับบิตแล้ว: 1111 0101
+1 → 1111 0110

อ่านเป็นแบบไม่มีเครื่องหมาย

1111 0110₂ = 256 − 10 = 246

คำตอบ

U = 246
2.ระบบเลข

คำตอบ: b = 9 bit

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

กำลังของสอง

28 = 256 < 299
29 = 512 ≥ 299

คำตอบ

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

คำตอบ: (b → a) ∧ (a → b)

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

ตรวจสอบด้วยตารางค่าความจริง

a = 1, b = 1: 1 | 1 1 1 1
a = 1, b = 0: 0 | 1 0 0 1
a = 0, b = 1: 0 | 0 0 0 1
a = 0, b = 0: 1 | 1 0 1 1

คำตอบ

(b → a) ∧ (a → b)

คอลัมน์หลังเส้นคั่นคือตัวเลือกตามลำดับที่แสดง

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

คำตอบ: r

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

แถวที่สมมติฐานทั้งหมดเป็นจริง

q = 1, r = 1: r = 1, q ∧ ¬r = 0, ¬r = 0, ¬q = 0

สรุป

r (โมดัสโพเนนส์)

คำตอบ

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

คำตอบ: AB = 01, CD = 10

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

เพื่อนบ้านของแต่ละ 1

1 ที่มี 1 อยู่ติดกันเข้ากลุ่มสองเซลล์หรือมากกว่าได้

m6: m7, m4, m2, m14 → 0
ABCD0001111000011110111111

1 ที่อยู่โดดเดี่ยว

m6 = A′BCD′ → AB = 01, CD = 10

คำตอบ

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

คำตอบ: fmax = 20.83 MHz

ฟลิปฟล็อปและตัวนับ: ฟลิปฟล็อปเปลี่ยนค่าเฉพาะที่ขอบแอ็กทีฟของสัญญาณนาฬิกา D คัดลอกอินพุต (Q⁺ = D); T สลับค่าเมื่อ T = 1; JK คงค่าสำหรับ 00 รีเซ็ตสำหรับ 01 เซตสำหรับ 10 และสลับค่าสำหรับ 11 ตัวนับฐานสอง n บิตมี 2ⁿ สถานะและนับมอดูโล 2ⁿ ตัวนับมอด N นับ 0, 1, …, N − 1 แล้ววนกลับเป็น 0 และต้องใช้ฟลิปฟล็อปจำนวน n ที่น้อยที่สุดที่ 2ⁿ ≥ N แต่ละภาคของตัวนับริปเปิลลดความถี่ลงครึ่งหนึ่ง ดังนั้นเอาต์พุตสุดท้ายของตัวนับมอด N ทำงานที่ fclk/N ตัวนับจอห์นสันที่มีฟลิปฟล็อป n ตัวมี 2n สถานะ ตัวนับริงมี n

เวลานิ่งในกรณีเลวร้ายที่สุด

T = 6·8 ns = 48 ns

ความถี่สูงสุด

fmax = 1/48 ns = 20.83 MHz

คำตอบ

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

คำตอบ: x = 32

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

ตัวผกผันของ 43

r = 73, t = 0
r = 43, q = 1, t = 1
r = 30, q = 1, t = −1
r = 13, q = 2, t = 2
r = 4, q = 3, t = −5
r = 1, q = 4, t = 17
43−1 ≡ 17 (mod 73)

แก้สมการ

x ≡ 17·62 = 1054 ≡ 32 (mod 73)
ตรวจสอบ: 43·32 = 1376 ≡ 62 (mod 73)

คำตอบ

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

คำตอบ: c = 96

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

การยกกำลังสองซ้ำ

19 = 16 + 2 + 1
911 ≡ 91 (mod 145)
912 ≡ 16 (mod 145)
914 ≡ 111 (mod 145)
918 ≡ 141 (mod 145)
9116 ≡ 16 (mod 145)
9119 ≡ 91·16·16 ≡ 96 (mod 145)

ข้อความเข้ารหัส

c = 96

คำตอบ

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

คำตอบ: C · ประมาณ 20

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

220 ≈ 1,048,576 ดังนั้นหลังแบ่งครึ่งประมาณ 20 ครั้งจะเหลือสมาชิกเพียงตัวเดียว

คำตอบ

C · ประมาณ 20
10.อัลกอริทึมและความซับซ้อน

คำตอบ: A · จุดยอดถูกตรึงค่าเมื่อถูกดึงออก แต่เส้นเชื่อมติดลบที่มาทีหลังอาจให้เส้นทางที่สั้นกว่าแก่มัน

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

ขั้นตอนละโมบพึ่งพาน้ำหนักที่ไม่เป็นลบเพื่อให้ระยะทางที่ดึงออกเป็นค่าสุดท้าย เมื่อน้ำหนักอาจติดลบให้ใช้ Bellman–Ford

คำตอบ

A · จุดยอดถูกตรึงค่าเมื่อถูกดึงออก แต่เส้นเชื่อมติดลบที่มาทีหลังอาจให้เส้นทางที่สั้นกว่าแก่มัน
11.โครงสร้างข้อมูล

คำตอบ: D · O(n) เพราะสมาชิกหลังจากนั้นต้องเลื่อน

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

สมาชิกทั้งหมดหลังจุดแทรกเลื่อนไปทางขวาหนึ่งตำแหน่ง ซึ่งใช้เวลาแปรผันตาม n

คำตอบ

D · O(n) เพราะสมาชิกหลังจากนั้นต้องเลื่อน
12.โครงสร้างข้อมูล

คำตอบ: C · hash map ร่วมกับลิงก์ลิสต์สองทิศทาง

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

Hash map หาโหนดใน O(1) และลิงก์ลิสต์สองทิศทางย้ายรายการที่เข้าถึงไปด้านหน้าและขับออกจากด้านหลังใน O(1)

คำตอบ

C · hash map ร่วมกับลิงก์ลิสต์สองทิศทาง
13.ทฤษฎีกราฟ

คำตอบ: H = 12

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

นับ

H = (5 − 1)!/2 = 24/2 = 12

คำตอบ

H = 12
14.ทฤษฎีกราฟ

คำตอบ: W = 31

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

ขั้นตอนวิธีของครัสคัล

BE (2): เลือก
DE (4): เลือก
AC (5): เลือก
EF (7): เลือก
BD (8): ข้าม ทำให้เกิดวัฏจักร
AB (13): เลือก

น้ำหนักรวม

W = 2 + 4 + 5 + 7 + 13 = 31

คำตอบ

W = 31
15.ฐานข้อมูลและ SQL

คำตอบ: D · ชื่อแต่ละคนพร้อมป้าย 'pass' หรือ 'fail' ตามเกรด

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

นิพจน์ CASE ประเมินเงื่อนไขต่อแถวและคืนค่าที่ตรงกัน ทุกแถวจึงได้ป้าย

คำตอบ

D · ชื่อแต่ละคนพร้อมป้าย 'pass' หรือ 'fail' ตามเกรด
16.ฐานข้อมูลและ SQL

คำตอบ: B · การควบคุมภาวะพร้อมกันแบบมองโลกในแง่ดี (optimistic concurrency control)

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

optimistic locking สันนิษฐานว่าความขัดแย้งเกิดน้อย: ตรวจคอลัมน์ version ตอนเขียน และล้มเหลวหากทรานแซกชันอื่นเปลี่ยนแถวไปแล้ว

คำตอบ

B · การควบคุมภาวะพร้อมกันแบบมองโลกในแง่ดี (optimistic concurrency control)
17.เครือข่ายคอมพิวเตอร์

คำตอบ: B · ความหน่วงต่ำสำคัญกว่าการส่งแพ็กเก็ตที่สูญหายซ้ำทุกแพ็กเก็ต

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

การส่งแพ็กเก็ตที่สูญหายซ้ำจะเพิ่มความล่าช้า สื่อเรียลไทม์ทนการสูญหายบางส่วนได้ จึงใช้โพรโทคอลบน UDP เช่น RTP

คำตอบ

B · ความหน่วงต่ำสำคัญกว่าการส่งแพ็กเก็ตที่สูญหายซ้ำทุกแพ็กเก็ต
18.เครือข่ายคอมพิวเตอร์

คำตอบ: D · 8 คอลลิชันโดเมน 1 บรอดแคสต์โดเมน

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

พอร์ตสวิตช์แต่ละพอร์ตเป็นคอลลิชันโดเมนของตนเอง แต่บรอดแคสต์ถูกส่งต่อไปทุกพอร์ต สวิตช์ทั้งตัวจึงเป็นบรอดแคสต์โดเมนเดียว ฮับจะให้อย่างละหนึ่ง

คำตอบ

D · 8 คอลลิชันโดเมน 1 บรอดแคสต์โดเมน
19.การแบ่งซับเน็ต IPv4

คำตอบ: p = 23

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

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

28 − 2 = 254 < 457
29 − 2 = 510 ≥ 457 → h = 9

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

p = 32 − 9 = 23

คำตอบ

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

คำตอบ: x = 255

IPv4 subnetting: an address has 32 bits. The prefix /p says how many leading bits identify the network; the remaining 32 − p bits number the hosts. A subnet has 2³²⁻ᵖ addresses, but the first (network address) and last (broadcast address) cannot be given to hosts, so 2³²⁻ᵖ − 2 hosts fit. Exceptions: a /31 (point-to-point link, RFC 3021) uses both of its 2 addresses for hosts, and a /32 is one single address (a single host or a loopback).

ขนาดบล็อกในออกเท็ตที่สาม

26 = 64

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

เครือข่าย: 172.20.192.0
บรอดคาสต์: 172.20.255.255

คำตอบ

x = 255

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