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

สรุปสูตร ขั้นตอนวิธีทำที่สำคัญของทุกหัวข้อ และโจทย์ฝึก 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 บิต?−128?64?32?16?8?4?2?1

เขียน −26 เป็นรูปแบบ two's complement 8 บิต อ่านรูปแบบนั้นเป็นเลขฐานสองแบบไม่มีเครื่องหมาย ค่าของมัน U ในเลขฐานสิบคือเท่าใด

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

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

1101 0011OR0111 0100
R =
3.ตรรกศาสตร์ประพจน์และการพิสูจน์ปานกลาง
(q → r) ∧ (p → r)(q → p) → rq → (p → r)q ∧ (p → r)

สูตรใดสมมูลเชิงตรรกะกับ (q ∧ p) → r ให้คลิกสูตรนั้น

(q ∧ p) → r
  1. 1(q → r) ∧ (p → r)
  2. 2(q → p) → r
  3. 3q → (p → r)
  4. 4q ∧ (p → r)
4.ตรรกศาสตร์ประพจน์และการพิสูจน์ยาก
∀x (A(x) ∧ ¬B(x))∃x (A(x) ∧ ¬B(x))∀x (A(x) → ¬B(x))∀x (¬A(x) → ¬B(x))

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

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

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

F = Σm(1, 2, 4, 6, 7, 12, 13, 15)
  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.ตรรกะดิจิทัล: เกต แผนที่คาร์โนห์ และฟลิปฟล็อปยาก
FFQ0​Q0​FFQ1​Q1​FFQ2​Q2​FFQ3​Q3​FFQ4​Q4​FFQ5​Q5​CLKMOD-50

ตัวนับมอด-50 สร้างจากฟลิปฟล็อปจำนวนน้อยที่สุด มีสถานะที่เป็นไปได้กี่สถานะ U ที่ไม่เคยถูกใช้

N = 50
U =
7.ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ปานกลาง

จงหาตัวผกผันของ 15 มอดูโล 83: จำนวน x ที่ 0 < x < 83 และ 15·x ≡ 1 (mod 83)

a = 15n = 83
15−1 mod 83 =
8.ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ยาก
mc = me​ mod ncm = cd​ mod nm(n, e) = (91, 23)d = ?

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

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

คุณเรียงอาร์เรย์ n สมาชิกหนึ่งครั้ง แล้วตอบคำถามการเป็นสมาชิก k ข้อด้วยการค้นหาแบบทวิภาค ต้นทุนรวมเท่าใด

  1. AO(k n log n)
  2. BO(n log n + k log n)
  3. CO(nk)
  4. DO(n + k)
10.อัลกอริทึมและความซับซ้อนยาก

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

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

ความสูงในกรณีเลวร้ายที่สุดของ binary search tree ที่มี n โหนดคือเท่าใด ถ้าแทรกคีย์ตามลำดับที่เรียงแล้ว

  1. A1
  2. Blog₂ n
  3. C√n
  4. Dn (กลายเป็นลิงก์ลิสต์)
12.โครงสร้างข้อมูลยาก

โครงสร้าง union-find (เซตไม่เชื่อมกัน) ที่ใช้ union by rank และ path compression มีต้นทุนกระจายต่อการดำเนินการเป็น

  1. AO(n²)
  2. BO(α(n)) ซึ่งเป็นฟังก์ชันผกผันของอัคเคอร์มันน์ ที่แทบเป็นค่าคงที่ในทางปฏิบัติ
  3. CO(n)
  4. DO(log n) พอดี
13.ทฤษฎีกราฟปานกลาง
ABCDEFGวงจรออยเลอร์ทางเดินออยเลอร์ ไม่มีวงจรไม่ใช่ทั้งสองอย่าง

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

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

ขั้นตอนวิธีของไดก์สตราเริ่มจาก A ให้คลิกจุดยอดที่ถูกยืนยัน (ทำให้เป็นค่าถาวร) ในรอบที่ 3 โดย A เองคือรอบที่ 1

เริ่มต้น: Aรอบ 3
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
  7. 7G
15.ฐานข้อมูลและ SQLปานกลาง

คุณสมบัติ ACID ใดรับประกันว่าการเปลี่ยนแปลงที่ commit แล้วรอดจากระบบล่ม?

  1. AConsistency
  2. BDurability
  3. CAtomicity
  4. DIsolation
16.ฐานข้อมูลและ SQLยาก

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

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

ซับเน็ต IPv4 /26 มีที่อยู่โฮสต์ที่ใช้งานได้กี่ที่อยู่?

  1. A30
  2. B126
  3. C62
  4. D64
18.เครือข่ายคอมพิวเตอร์ยาก

เหตุใด TCP จึงเลือกหมายเลขลำดับเริ่มต้นที่คาดเดาไม่ได้สำหรับแต่ละการเชื่อมต่อ?

  1. Aเพื่อบีบอัดข้อมูลได้มีประสิทธิภาพขึ้น
  2. Bเพื่อหลีกเลี่ยงความสับสนกับเซกเมนต์เก่าและทำให้แทรกเซกเมนต์ปลอมได้ยากขึ้น
  3. Cเพื่อเข้ารหัสเพย์โหลดของแต่ละเซกเมนต์
  4. Dเพื่อเลือกเส้นทางที่ดีที่สุดไปยังปลายทางสำหรับเซกเมนต์ของการเชื่อมต่อนั้น
19.การแบ่งซับเน็ต IPv4ปานกลาง
/16 → /2411111111111111111111111100000000บิตเครือข่ายบิตโฮสต์

เครือข่าย 172.17.0.0/16 ถูกแบ่งเป็นซับเน็ตขนาดเท่ากันด้วยพรีฟิกซ์ /24 มีกี่ซับเน็ต N

172.17.0.0/16/24
N =
20.การแบ่งซับเน็ต IPv4ยาก
ออคเต็ตสุดท้าย = 160112806413201608040201เครือข่ายโฮสต์

โฮสต์มีที่อยู่ 10.20.157.160/30 ออคเต็ตที่สี่ x ของที่อยู่เครือข่ายคือเท่าใด

10.20.157.160/30
x =

3สารละลาย

1.ระบบเลข

คำตอบ: U = 230

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

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

26 = 0001 1010
ที่กลับบิตแล้ว: 1110 0101
+1 → 1110 0110

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

1110 0110₂ = 256 − 26 = 230

คำตอบ

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

คำตอบ: R = 247

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

ทีละบิต

OR ให้ 1 เมื่ออย่างน้อยหนึ่งบิตเป็น 1

1101 0011
OR 0111 0100
= 1111 0111

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

1111 0111₂ = 247

คำตอบ

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

คำตอบ: q → (p → r)

ความสมมูลเชิงตรรกะ: สูตรสองสูตรสมมูลกัน (≡) เมื่อมีค่าเท่ากันทุกแถวของตารางค่าความจริง ซ้ำซ้อน (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 ≡ a → (b → c) ทั้งสองเป็น 0 เฉพาะเมื่อ a = 1, b = 1 และ c = 0
(q ∧ p) → r ≡ q → (p → r)

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

p = 1, q = 1, r = 1: 1 | 1 1 1 1
p = 1, q = 1, r = 0: 0 | 0 0 0 0
p = 1, q = 0, r = 1: 1 | 1 1 1 0
p = 1, q = 0, r = 0: 1 | 0 0 1 0
p = 0, q = 1, r = 1: 1 | 1 1 1 1
p = 0, q = 1, r = 0: 1 | 0 1 1 1
p = 0, q = 0, r = 1: 1 | 1 1 1 0
p = 0, q = 0, r = 0: 1 | 1 0 1 0

คำตอบ

q → (p → r)

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

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

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

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

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

¬∃x (A(x) → B(x)) ≡ ∀x (A(x) ∧ ¬B(x))

คำตอบ

∀x (A(x) ∧ ¬B(x))

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

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

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

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

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

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

m1: m0, m3, m5, m9 → 0
ABCD000111100001111011111111

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

m1 = A′B′C′D → AB = 00, CD = 01

คำตอบ

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

คำตอบ: U = 14

ฟลิปฟล็อปและตัวนับ: ฟลิปฟล็อปเปลี่ยนค่าเฉพาะที่ขอบแอ็กทีฟของสัญญาณนาฬิกา 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

จำนวนฟลิปฟล็อป

2ⁿ ≥ 50 → n = 6 (2⁶ = 64)

สถานะที่ไม่ได้ใช้

U = 64 − 50 = 14

คำตอบ

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

คำตอบ: 15−1 mod 83 = 72

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

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

เศษ r แต่ละตัวเขียนเป็น r ≡ t·15 (mod 83)

r = 83, t = 0
r = 15, q = 5, t = 1
r = 8, q = 1, t = −5
r = 7, q = 1, t = 6
r = 1, q = 7, t = −11

อินเวอร์ส

1 ≡ −11·15 (mod 83)
x = 72
ตรวจสอบ: 15·72 = 1080 = 13·83 + 1

คำตอบ

15−1 mod 83 = 72
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 = 7·13 = 91
φ(n) = 6·12 = 72

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

r = 72, t = 0
r = 23, q = 3, t = 1
r = 3, q = 7, t = −3
r = 2, q = 1, t = 22
r = 1, q = 2, t = −25

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

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

คำตอบ

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

คำตอบ: B · O(n log n + k log n)

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

การเรียงใช้ O(n log n) และแต่ละคำถามใช้ O(log n) ดีกว่าการสแกนเชิงเส้น k ครั้ง (O(nk)) เมื่อ k มาก

คำตอบ

B · O(n log n + k log n)
10.อัลกอริทึมและความซับซ้อน

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

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

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

คำตอบ

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

คำตอบ: D · n (กลายเป็นลิงก์ลิสต์)

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

การแทรกตามลำดับสร้างต้นไม้เสื่อมที่มีความสูง n ทำให้การค้นหาเป็น O(n) ต้นไม้สมดุลป้องกันเรื่องนี้

คำตอบ

D · n (กลายเป็นลิงก์ลิสต์)
12.โครงสร้างข้อมูล

คำตอบ: B · O(α(n)) ซึ่งเป็นฟังก์ชันผกผันของอัคเคอร์มันน์ ที่แทบเป็นค่าคงที่ในทางปฏิบัติ

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

เมื่อใช้ทั้งสองการปรับปรุง การดำเนินการใช้เวลา O(α(n)) แบบกระจายต้นทุน และ α(n) ≤ 4 สำหรับ n ที่เป็นจริงทุกขนาด

คำตอบ

B · O(α(n)) ซึ่งเป็นฟังก์ชันผกผันของอัคเคอร์มันน์ ที่แทบเป็นค่าคงที่ในทางปฏิบัติ
13.ทฤษฎีกราฟ

คำตอบ: ไม่ใช่ทั้งสองอย่าง

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

ดีกรี

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

จุดยอดคี่

A, B, E, G → 4
ไม่ใช่ทั้งสองอย่าง

คำตอบ

ไม่ใช่ทั้งสองอย่าง
14.ทฤษฎีกราฟ

คำตอบ: C

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

ไดก์สตราทีละรอบ

1. A (0): B: 11, C: 12
2. B (11): D: 18, G: 23
3. C (12): E: 14
4. E (14): F: 22
5. D (18): G: 21
6. G (21)
7. F (22)

รอบ 3

C

คำตอบ

C
15.ฐานข้อมูลและ SQL

คำตอบ: B · Durability

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

Durability หมายความว่าเมื่อทรานแซกชัน commit แล้ว ผลของมันจะถูกเก็บรักษาไว้ โดยปกติด้วยการเขียนล็อกลงที่เก็บข้อมูลที่เสถียร

คำตอบ

B · Durability
16.ฐานข้อมูลและ SQL

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

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

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

คำตอบ

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

คำตอบ: C · 62

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

/26 มีบิตโฮสต์ 6 บิต: 2⁶ = 64 ที่อยู่ ลบที่อยู่เครือข่ายและบรอดแคสต์ ได้โฮสต์ที่ใช้งานได้ 62

คำตอบ

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

คำตอบ: B · เพื่อหลีกเลี่ยงความสับสนกับเซกเมนต์เก่าและทำให้แทรกเซกเมนต์ปลอมได้ยากขึ้น

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

หมายเลขลำดับเริ่มต้นแบบสุ่มป้องกันไม่ให้ยอมรับเซกเมนต์ที่ล่าช้าจากการเชื่อมต่อเก่า และทำให้ผู้โจมตีนอกเส้นทางปลอมเซกเมนต์ที่ใช้ได้ยาก

คำตอบ

B · เพื่อหลีกเลี่ยงความสับสนกับเซกเมนต์เก่าและทำให้แทรกเซกเมนต์ปลอมได้ยากขึ้น
19.การแบ่งซับเน็ต IPv4

คำตอบ: N = 256

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).

บิตที่ยืมมา

24 − 16 = 8

จำนวนซับเน็ต

N = 28 = 256

คำตอบ

N = 256

แต่ละซับเน็ต /24 มีโฮสต์ที่ใช้ได้ 28 − 2 = 254 โฮสต์

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

คำตอบ: x = 160

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

ขนาดบล็อก

22 = 4

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

เครือข่าย: ⌊160/4⌋·4 = 160
บรอดคาสต์: 160 + 4 − 1 = 163
โฮสต์ที่ใช้ได้: 161 … 162

คำตอบ

x = 160

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