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

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

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

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

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

ระบบเลข

ค่าประจำตำแหน่ง: ฐานสอง 2^k, ฐานแปด 8^k, ฐานสิบหก 16^k
เป็นเลขฐานสิบ: Σ d_k·b^k
จากเลขฐานสิบ: หารด้วยฐาน อ่านเศษจากล่างขึ้นบน
ฐานสิบหก ↔ ฐานสอง: เลขฐานสิบหกหนึ่งหลัก = 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

วิธีการ

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

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

เกตพื้นฐาน: 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′I₀ + A′BI₁ + AB′I₂ + ABI₃
ฟลิปฟล็อป: D: Q⁺ = D, T: Q⁺ = T ⊕ Q, JK: Q⁺ = JQ′ + K′Q
ตัวนับ: n บิต: 2ⁿ สถานะ; มอด N: n ที่น้อยที่สุดที่ 2ⁿ ≥ N; f_out = f_clk/N
ตัวนับริปเปิล: f_max = 1/(n·t_pd)
ตัวนับริงและตัวนับจอห์นสัน: n และ 2n สถานะ

วิธีการ

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

วิธีการ

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

ทฤษฎีกราฟ

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

วิธีการ

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

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

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

2โจทย์ฝึก

1.ระบบเลขปานกลาง

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

0100 11018 bit

N =

2.ระบบเลขยาก

ภาพที่ไม่บีบอัดมีขนาด 800 × 600 พิกเซล และมี 16 บิตต่อพิกเซล ใช้หน่วยความจำ M เท่าใด ในหน่วย KiB (1 KiB = 1024 ไบต์)

800 × 600 px16 bit/px1 KiB = 1024 B

M = KiB

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

ในตารางค่าความจริง 8 แถวของ ((r ↔ p) ∨ q) ∧ (¬p → (q ∧ r)) มีกี่แถวที่เป็นจริง เรียกจำนวนนี้ว่า N

((r ↔ p) ∨ q) ∧ (¬p → (q ∧ r))

N =

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

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

¬∃x P(x)

1∃x P(x)
2∀x P(x)
3∃x ¬P(x)
4∀x ¬P(x)

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

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

F(A, B, C) = Σm(1, 4, 6, 7)

L =

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

ฟลิปฟล็อป D ที่ทริกเกอร์ขอบขาขึ้นเริ่มด้วย Q = 0 และได้รับอินพุตที่แสดงที่ขอบขาขึ้นของนาฬิกา 6 ขอบ Q เปลี่ยนสถานะกี่ครั้ง N

Q₀ = 0D

N =

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

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

n = 51 = 3·17

φ(51) =

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

83 เป็นจำนวนเฉพาะ ใช้ทฤษฎีบทเล็กของแฟร์มาเพื่อหา 28⁷⁰⁴⁶⁷ mod 83

p = 83k = 70467

28⁷⁰⁴⁶⁷ mod 83 =

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

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

Aประมาณ 500,000
Bประมาณ 1,000
Cประมาณ 20
Dประมาณ 100

10.อัลกอริทึมและความซับซ้อนยาก

ปัญหาหนึ่งเป็น NP-complete ถ้ามัน

Aแก้ได้ในเวลาพหุนาม
Bอยู่นอก NP แต่ยากกว่าทุกปัญหา NP เช่น ปัญหาการหยุด
Cแก้ไม่ได้เลย
Dอยู่ใน NP และทุกปัญหา NP ลดรูปมาเป็นมันได้ในเวลาพหุนาม

11.โครงสร้างข้อมูลปานกลาง

เมทริกซ์ประชิด (adjacency matrix) ของกราฟที่มี V จุดยอดใช้หน่วยความจำเท่าใด

AO(log V)
BO(V²)
CO(E)
DO(V + E)

12.โครงสร้างข้อมูลยาก

ข้อได้เปรียบหลักของ skip list เหนือลิงก์ลิสต์ที่เรียงลำดับคืออะไร

Aรับประกันการค้นหา O(1) เพราะทุกโหนดเก็บตัวชี้ไปยังทุกโหนดอื่น
Bเก็บคีย์โดยไม่เรียงลำดับ
Cไม่ใช้หน่วยความจำเพิ่ม
Dการค้นหา O(log n) คาดหมาย โดยใช้ตัวชี้ไปข้างหน้าหลายระดับ

13.ทฤษฎีกราฟปานกลาง

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

|V| = 7|E| = 8

1วงจรออยเลอร์
2ทางเดินออยเลอร์ ไม่มีวงจร
3ไม่ใช่ทั้งสองอย่าง

14.ทฤษฎีกราฟยาก

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

เริ่มต้น: Ck = 2

1เส้นเชื่อม AB
2เส้นเชื่อม BC
3เส้นเชื่อม BD
4เส้นเชื่อม CE
5เส้นเชื่อม DE
6เส้นเชื่อม DF
7เส้นเชื่อม EF
8เส้นเชื่อม GB
9เส้นเชื่อม GD

15.ฐานข้อมูลและ SQLปานกลาง

คีย์นอกถูกประกาศด้วย ON DELETE CASCADE เกิดอะไรขึ้นเมื่อแถวแม่ถูกลบ?

Aแถวแม่ถูกคัดลอกไปยังตารางเก็บถาวร
Bการลบถูกปฏิเสธเสมอ
Cคีย์นอกในแถวลูกถูกตั้งเป็น NULL โดยอัตโนมัติ
Dแถวลูกที่อ้างอิงแถวนั้นถูกลบโดยอัตโนมัติ

16.ฐานข้อมูลและ SQLยาก

ฐานข้อมูลรายงานคัดลอกชื่อลูกค้าเข้าตาราง orders เพื่อเลี่ยงการเชื่อม ต้นทุนหลักของการทำดีนอร์มัลไลซ์นี้คืออะไร?

Aสำเนาซ้ำซ้อนต้องคงความสอดคล้องกันทุกครั้งที่ข้อมูลลูกค้าเปลี่ยน
Bคิวรีบนตาราง orders ช้าลง
Cฐานข้อมูลใช้ดัชนีไม่ได้อีกต่อไป
Dใช้คีย์หลักไม่ได้อีกต่อไป

17.เครือข่ายคอมพิวเตอร์ปานกลาง

ที่อยู่เครือข่ายของโฮสต์ 192.168.10.77/26 คืออะไร?

A192.168.10.0
B192.168.10.76
C192.168.10.64
D192.168.10.128

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

การโจมตีแบบวางยาแคช DNS (DNS cache poisoning) มีเป้าหมายเพื่อ:

Aขโมยรหัสผ่าน Wi-Fi
Bทำให้เซิร์ฟเวอร์รับทราฟฟิกล้นเกินจนหยุดตอบคำถาม
Cทำให้รีโซลเวอร์เก็บที่อยู่ IP ปลอมสำหรับโดเมนหนึ่ง
Dลบเซิร์ฟเวอร์ DNS

19.การแบ่งซับเน็ต IPv4ปานกลาง

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

172.23.0.0/16/23

N =

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

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

172.20.47.206/20

x =

3สารละลาย

1.ระบบเลข

คำตอบ: N = 77

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

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

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

64 + 8 + 4 + 1 = 77

คำตอบ

N = 77

2.ระบบเลข

คำตอบ: M = 937.5 KiB

บิตและไบต์

800·600·16 = 7680000 bit = 960000 B

แปลงเป็น KiB

960000/1024 = 937.5 KiB

คำตอบ

M = 937.5 KiB

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

คำตอบ: N = 4

ตารางค่าความจริง: สูตรที่มีตัวแปรต่างกัน n ตัวมี 2ⁿ แถว หนึ่งแถวต่อทุกชุดของค่าความจริง (1 = จริง, 0 = เท็จ) ทำจากด้านในออกมาและให้ทุกประพจน์ย่อยมีคอลัมน์ของตัวเอง ¬a กลับค่า a ∧ b เป็น 1 เฉพาะเมื่อทั้งสองเป็น 1 a ∨ b เป็น 0 เฉพาะเมื่อทั้งสองเป็น 0 a → b เป็น 0 เฉพาะเมื่อ a = 1 และ b = 0 a ↔ b เป็น 1 เมื่อทั้งสองข้างเท่ากัน

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

p = 1, q = 1, r = 1: r ↔ p = 1, (r ↔ p) ∨ q = 1, ¬p = 0, q ∧ r = 1, ¬p → (q ∧ r) = 1, ((r ↔ p) ∨ q) ∧ (¬p → (q ∧ r)) = 1

p = 1, q = 1, r = 0: r ↔ p = 0, (r ↔ p) ∨ q = 1, ¬p = 0, q ∧ r = 0, ¬p → (q ∧ r) = 1, ((r ↔ p) ∨ q) ∧ (¬p → (q ∧ r)) = 1

p = 1, q = 0, r = 1: r ↔ p = 1, (r ↔ p) ∨ q = 1, ¬p = 0, q ∧ r = 0, ¬p → (q ∧ r) = 1, ((r ↔ p) ∨ q) ∧ (¬p → (q ∧ r)) = 1

p = 1, q = 0, r = 0: r ↔ p = 0, (r ↔ p) ∨ q = 0, ¬p = 0, q ∧ r = 0, ¬p → (q ∧ r) = 1, ((r ↔ p) ∨ q) ∧ (¬p → (q ∧ r)) = 0

p = 0, q = 1, r = 1: r ↔ p = 0, (r ↔ p) ∨ q = 1, ¬p = 1, q ∧ r = 1, ¬p → (q ∧ r) = 1, ((r ↔ p) ∨ q) ∧ (¬p → (q ∧ r)) = 1

p = 0, q = 1, r = 0: r ↔ p = 1, (r ↔ p) ∨ q = 1, ¬p = 1, q ∧ r = 0, ¬p → (q ∧ r) = 0, ((r ↔ p) ∨ q) ∧ (¬p → (q ∧ r)) = 0

p = 0, q = 0, r = 1: r ↔ p = 0, (r ↔ p) ∨ q = 0, ¬p = 1, q ∧ r = 0, ¬p → (q ∧ r) = 0, ((r ↔ p) ∨ q) ∧ (¬p → (q ∧ r)) = 0

p = 0, q = 0, r = 0: r ↔ p = 1, (r ↔ p) ∨ q = 1, ¬p = 1, q ∧ r = 0, ¬p → (q ∧ r) = 0, ((r ↔ p) ∨ q) ∧ (¬p → (q ∧ r)) = 0

นับแถวที่มีค่าเป็น 1

((r ↔ p) ∨ q) ∧ (¬p → (q ∧ r)): 1, 1, 1, 0, 1, 0, 0, 0

N = 4

คำตอบ

N = 4

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

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

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

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

¬∃x P(x) ≡ ∀x ¬P(x)

คำตอบ

∀x ¬P(x)

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

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

คำตอบ: L = 7

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

จัดกลุ่ม 1

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

AC′

A′B′C

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

F = AC′ + AB + A′B′C

L = 7

คำตอบ

L = 7

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

คำตอบ: N = 4

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

Q หลังทุกขอบ

ฟลิปฟล็อป D คัดลอก D ทุกขอบขาขึ้น: Q⁺ = D

1: D = 1 → Q = 1

2: D = 0 → Q = 0

3: D = 0 → Q = 0

4: D = 0 → Q = 0

5: D = 1 → Q = 1

6: D = 0 → Q = 0

นับการเปลี่ยน

0 → 1 → 0 → 0 → 0 → 1 → 0

N = 4

คำตอบ

N = 4

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

คำตอบ: φ(51) = 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)

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

51 = 3·17

โทเทียนต์

φ(51) = φ(3)·φ(17) = 2·16 = 32

คำตอบ

φ(51) = 32

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

คำตอบ: 28⁷⁰⁴⁶⁷ mod 83 = 75

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

D · การค้นหา O(log n) คาดหมาย โดยใช้ตัวชี้ไปข้างหน้าหลายระดับ

13.ทฤษฎีกราฟ

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

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

ดีกรี

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

จุดยอดคี่

A, B, D, F → 4

ไม่ใช่ทั้งสองอย่าง

คำตอบ

ไม่ใช่ทั้งสองอย่าง

14.ทฤษฎีกราฟ

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

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

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

1. CE (4)

2. DE (14)

3. GD (2)

4. GB (9)

5. DF (13)

6. AB (16)

การวางยาแทรกเรกคอร์ดปลอมลงในแคชของรีโซลเวอร์ DNSSEC เพิ่มลายเซ็นเพื่อให้รีโซลเวอร์ตรวจสอบเรกคอร์ดได้

คำตอบ

C · ทำให้รีโซลเวอร์เก็บที่อยู่ IP ปลอมสำหรับโดเมนหนึ่ง

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

คำตอบ: N = 128

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

บิตที่ยืมมา

23 − 16 = 7

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

N = 2⁷ = 128

คำตอบ

N = 128

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

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

คำตอบ: x = 47

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

2⁴ = 16

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

เครือข่าย: 172.20.32.0

บรอดคาสต์: 172.20.47.255

คำตอบ

x = 47

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