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

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

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

1111 00008 bit
N =
2.ระบบเลขยาก
24 bit1 px256 px256 pxM = ? KiB

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

256 × 256 px24 bit/px1 KiB = 1024 B
M = KiB
3.ตรรกศาสตร์ประพจน์และการพิสูจน์ปานกลาง
(q ∨ r) → p¬p → ¬(q ∨ r)p ∧ ¬(q ∨ r)¬(q ∨ r) → ¬p

คุณต้องการพิสูจน์ p → (q ∨ r) ด้วยการแย้งสลับที่ ควรพิสูจน์นัยใดแทน ให้คลิกนัยนั้น

p → (q ∨ r)
  1. 1(q ∨ r) → p
  2. 2¬p → ¬(q ∨ r)
  3. 3p ∧ ¬(q ∨ r)
  4. 4¬(q ∨ r) → ¬p
4.ตรรกศาสตร์ประพจน์และการพิสูจน์ยาก
pqq ∨ pq¬p11100100

การอ้างเหตุผลที่มีสมมติฐาน q ∨ p; q และบทสรุป ¬p ไม่สมเหตุสมผล ให้คลิกแถวของตารางค่าความจริงที่เป็นตัวอย่างค้าน

q ∨ pq∴ ¬p
  1. 1p = 1, q = 1
  2. 2p = 1, q = 0
  3. 3p = 0, q = 1
  4. 4p = 0, q = 0
5.ตรรกะดิจิทัล: เกต แผนที่คาร์โนห์ และฟลิปฟล็อปปานกลาง
ABC000111100101324576

จงทำ F = AC + AB′C + ABC′ + A′BC ให้เป็นรูปผลบวกของผลคูณที่น้อยที่สุด นิพจน์ที่ทำให้ง่ายแล้วมีกี่ลิเทอรัล L

F = AC + AB′C + ABC′ + A′BC
L =
6.ตรรกะดิจิทัล: เกต แผนที่คาร์โนห์ และฟลิปฟล็อปยาก
TQ0​Q0​TQ1​Q1​TQ2​Q2​CLKMOD-5

ตัวนับมอด-5 แบบซิงโครนัสนับ 0, 1, …, 4 แล้ววนกลับเป็น 0 เริ่มที่ 2 หลังพัลส์นาฬิกา 7 พัลส์ จะแสดงค่านับ Q (เป็นเลขฐานสิบ) เท่าใด

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

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

a = 79n = 97
79−1 mod 97 =
8.ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ยาก

จงแก้ 32x ≡ 24 (mod 40) ให้คำตอบที่เป็นบวกและน้อยที่สุด x

32x ≡ 24 (mod 40)
x =
9.อัลกอริทึมและความซับซ้อนปานกลาง

ขอบเขตล่างของการเรียงลำดับแบบเปรียบเทียบในกรณีเลวร้ายที่สุดคือ

  1. AΩ(n log n)
  2. BΩ(log n)
  3. CΩ(n)
  4. DΩ(n²)
10.อัลกอริทึมและความซับซ้อนยาก

ปัญหาความสอดคล้องข้อใดต่อไปนี้ทราบว่าแก้ได้ในเวลาพหุนาม

  1. A2-SAT ซึ่งแต่ละวลีมีลิเทอรัลไม่เกินสองตัว
  2. Bความสอดคล้องของวงจร
  3. CSAT ทั่วไปบนสูตรรูปแบบนอร์มัลเชิงเชื่อม
  4. D3-SAT ซึ่งแต่ละวลีมีลิเทอรัลสามตัวพอดี
11.โครงสร้างข้อมูลปานกลาง

ต้นไม้ทวิภาคมีราก 1 ลูกซ้าย 2 ลูกขวา 3 โหนด 2 มีลูก 4 (ซ้าย) และ 5 (ขวา) การท่องแบบ preorder คืออะไร

  1. A1 2 3 4 5
  2. B4 2 5 1 3
  3. C1 2 4 5 3
  4. D4 5 2 3 1
12.โครงสร้างข้อมูลยาก

การแทรกคีย์ในต้นไม้ AVL ทำให้ต้นไม้ย่อยซ้ายของโหนดสูงเกินไป และคีย์ใหม่อยู่ในต้นไม้ย่อยซ้ายของลูกซ้าย (กรณีซ้าย–ซ้าย) ใช้วิธีแก้ใด

  1. Aหมุนขวาหนึ่งครั้งที่โหนดที่ไม่สมดุล
  2. Bเปลี่ยนสีโหนดและลูกของมัน
  3. Cหมุนซ้ายที่ลูก แล้วหมุนขวาที่โหนด
  4. Dหมุนซ้ายหนึ่งครั้งที่โหนดที่ไม่สมดุล
13.ทฤษฎีกราฟปานกลาง
ABCDEFGวงจรออยเลอร์ทางเดินออยเลอร์ ไม่มีวงจรไม่ใช่ทั้งสองอย่าง

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

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

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

k = 4
  1. 1เส้นเชื่อม AB
  2. 2เส้นเชื่อม AC
  3. 3เส้นเชื่อม BC
  4. 4เส้นเชื่อม BD
  5. 5เส้นเชื่อม CE
  6. 6เส้นเชื่อม DE
  7. 7เส้นเชื่อม BE
15.ฐานข้อมูลและ SQLปานกลาง

SELECT SUM(amount) FROM orders คืนอะไรเมื่อ WHERE ไม่ตรงกับแถวใดเลย?

  1. A0
  2. BNULL
  3. Cข้อผิดพลาด
  4. Dสตริงว่าง
16.ฐานข้อมูลและ SQLยาก

กำหนดการพึ่งพาเชิงฟังก์ชัน A → B, B → C และ C → D บน R(A, B, C, D) ตัวปิด (closure) A+ คืออะไร?

  1. A{A}
  2. B{A, B, C}
  3. C{A, B, C, D}
  4. D{A, B}
17.เครือข่ายคอมพิวเตอร์ปานกลาง

HTTP เป็นแบบไม่เก็บสถานะ (stateless) เว็บไซต์มักทำให้ผู้ใช้ล็อกอินค้างอยู่ข้ามคำขอได้อย่างไร?

  1. Aโดยเปิดการเชื่อมต่อ TCP ค้างไว้หลายวัน
  2. Bโดยเก็บรหัสผ่านใน URL
  3. Cโดยให้ผู้ใช้แต่ละคนมีที่อยู่ IP คงที่
  4. Dด้วยคุกกี้ที่เก็บตัวระบุเซสชันหรือโทเค็น
18.เครือข่ายคอมพิวเตอร์ยาก

ผู้โจมตีใน LAN ส่งการตอบ ARP ปลอมอ้างที่อยู่ IP ของเกตเวย์ ผลที่น่าจะเกิดคืออะไร?

  1. Aการค้นหา DNS ทั้งหมดล้มเหลวทั่วอินเทอร์เน็ต
  2. Bที่อยู่ IP ของเกตเวย์ถูกเปลี่ยนเป็นที่อยู่ของผู้โจมตีอย่างถาวรบนเราเตอร์ทุกตัว
  3. Cเหยื่อส่งทราฟฟิกที่ไปเกตเวย์ให้ผู้โจมตี ทำให้เกิดการโจมตีแบบคนกลาง (man-in-the-middle)
  4. Dสวิตช์ปิดพอร์ตทั้งหมด
19.การแบ่งซับเน็ต IPv4ปานกลาง
/24 → /2911111111111111111111111111111000บิตเครือข่ายบิตโฮสต์

เครือข่าย 192.168.10.0/24 ต้องแบ่งเป็นซับเน็ตขนาดเท่ากันอย่างน้อย 30 ซับเน็ต หากยืมบิตให้น้อยที่สุด แต่ละซับเน็ตมีโฮสต์ที่ใช้ได้กี่เครื่อง H

192.168.10.0/2430 subnets
H =
20.การแบ่งซับเน็ต IPv4ยาก
ออกเท็ตที่สาม 225 … 231112816413201608040211ร่วมกันเปลี่ยนแปลง

เราเตอร์มีเส้นทางไปยังเครือข่ายเหล่านี้: 10.45.225.0/24, 10.45.226.0/24, 10.45.227.0/24, 10.45.228.0/24, 10.45.229.0/24, 10.45.230.0/24, 10.45.231.0/24 ความยาวพรีฟิกซ์ยาวที่สุด p ของเส้นทางสรุปเส้นเดียวที่ครอบคลุมทั้งหมดคือเท่าใด

10.45.225.0/24 … 10.45.231.0/24
p =

3สารละลาย

1.ระบบเลข

คำตอบ: N = −16

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

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

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

−128 + 64 + 32 + 16 = −16

คำตอบ

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

คำตอบ: M = 192 KiB

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

บิตและไบต์

256·256·24 = 1572864 bit = 196608 B

แปลงเป็น KiB

196608/1024 = 192 KiB

คำตอบ

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

คำตอบ: ¬(q ∨ 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 = p, b = q ∨ r

การแย้งสลับที่

¬b → ¬a = ¬(q ∨ r) → ¬p

คำตอบ

¬(q ∨ r) → ¬p

การแย้งสลับที่สมมูลกับประโยคเดิม ดังนั้นการพิสูจน์การแย้งสลับที่ก็พิสูจน์ประโยคเดิม

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

คำตอบ: p = 1, q = 1

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

สมมติฐานและบทสรุปทีละแถว

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

ตัวอย่างค้าน

p = 1, q = 1

คำตอบ

p = 1, q = 1

การอ้างเหตุผลรูปแบบนี้ดูเหมือนกฎที่สมเหตุสมผล แต่แถวเดียวก็เพียงพอที่จะแสดงว่าไม่ใช่

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

คำตอบ: L = 6

พีชคณิตแบบบูล: กฎที่ทำให้นิพจน์ง่ายขึ้นได้แก่ X + X′ = 1 และ X·X′ = 0, X + X = X, การดูดกลืน X + X·Y = X, กฎการรวม X·Y + X·Y′ = X, X + X′Y = X + Y และทฤษฎีบทฉันทามติ XY + X′Z + YZ = XY + X′Z กฎของเดอมอร์แกนเปลี่ยน (X·Y)′ เป็น X′ + Y′ และ (X + Y)′ เป็น X′·Y′ แผนที่คาร์โนห์ใช้กฎเหล่านี้ในรูปภาพ: ทุกกลุ่มของสองเซลล์ที่อยู่ติดกันคือการใช้ XY + XY′ = X หนึ่งครั้ง

มินเทอมของนิพจน์

AC → m(5, 7)
AB′C → m(5)
ABC′ → m(6)
A′BC → m(3)
ABC00011110010001130204151716

จัดกลุ่มและอ่านค่า

F = BC + AC + AB

นับลิเทอรัล

L = 6

คำตอบ

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

คำตอบ: Q = 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 ทำงานที่ fclk/N ตัวนับจอห์นสันที่มีฟลิปฟล็อป n ตัวมี 2n สถานะ ตัวนับริงมี n

รอบเต็ม

ทุก 5 พัลส์ทำให้ตัวนับกลับสู่สถานะเดิม

7 = 1·5 + 2

ค่านับหลังพัลส์ที่เหลือ

Q = (2 + 2) mod 5 = 4
Q = 100₂

คำตอบ

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

คำตอบ: 79−1 mod 97 = 70

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

r = 97, t = 0
r = 79, q = 1, t = 1
r = 18, q = 4, t = −1
r = 7, q = 2, t = 5
r = 4, q = 1, t = −11
r = 3, q = 1, t = 16
r = 1, q = 3, t = −27

อินเวอร์ส

1 ≡ −27·79 (mod 97)
x = 70
ตรวจสอบ: 79·70 = 5530 = 57·97 + 1

คำตอบ

79−1 mod 97 = 70
8.ทฤษฎีจำนวนและเลขคณิตมอดูลาร์

คำตอบ: x = 2

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

หารด้วย gcd

gcd(32, 40) = 8
4x ≡ 3 (mod 5)

แก้ความสอดคล้องที่ลดรูปแล้ว

4−1 ≡ 4 (mod 5) → x ≡ 2 (mod 5)

คำตอบมอดูโล 40

x ∈ {2, 7, 12, 17, 22, 27, 32, 37}
x = 2

คำตอบ

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

คำตอบ: A · Ω(n log n)

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

การเรียงแบบเปรียบเทียบใด ๆ ต้องใช้อย่างน้อย log₂(n!) ≈ n log n ครั้งในกรณีเลวร้ายที่สุด การเรียงแบบนับ (counting sort) ทำได้ดีกว่าเพราะไม่ได้เปรียบเทียบ

คำตอบ

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

คำตอบ: A · 2-SAT ซึ่งแต่ละวลีมีลิเทอรัลไม่เกินสองตัว

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

2-SAT อยู่ใน P (เวลาเชิงเส้นผ่านส่วนประกอบเชื่อมโยงเข้มแข็ง) ส่วน 3-SAT เป็น NP-complete

คำตอบ

A · 2-SAT ซึ่งแต่ละวลีมีลิเทอรัลไม่เกินสองตัว
11.โครงสร้างข้อมูล

คำตอบ: C · 1 2 4 5 3

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

Preorder เยี่ยม 1 แล้วต้นไม้ย่อยซ้าย (2, 4, 5) แล้ว 3 ตัวเลือกอื่นคือ inorder, postorder และ level-order

คำตอบ

C · 1 2 4 5 3
12.โครงสร้างข้อมูล

คำตอบ: A · หมุนขวาหนึ่งครั้งที่โหนดที่ไม่สมดุล

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

ในกรณีซ้าย–ซ้าย การหมุนขวาหนึ่งครั้งยกลูกซ้ายขึ้นและคืนสมดุล กรณีซิกแซกต้องหมุนสองครั้ง

คำตอบ

A · หมุนขวาหนึ่งครั้งที่โหนดที่ไม่สมดุล
13.ทฤษฎีกราฟ

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

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

ดีกรี

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

จุดยอดคี่

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

คำตอบ

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

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

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

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

1. BC (2)
2. CE (7)
3. BD (8)
4. AC (14)

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

AC

คำตอบ

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

คำตอบ: B · NULL

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

SUM, AVG, MIN และ MAX คืน NULL เมื่อเซตว่าง ส่วน COUNT คืน 0 COALESCE(SUM(amount), 0) ให้ 0 แทน

คำตอบ

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

คำตอบ: C · {A, B, C, D}

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

เริ่มจาก A เพิ่ม B (A → B) แล้ว C (B → C) แล้ว D (C → D) เนื่องจาก A+ มีทุกแอตทริบิวต์ A จึงเป็นคีย์

คำตอบ

C · {A, B, C, D}
17.เครือข่ายคอมพิวเตอร์

คำตอบ: D · ด้วยคุกกี้ที่เก็บตัวระบุเซสชันหรือโทเค็น

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

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

คำตอบ

D · ด้วยคุกกี้ที่เก็บตัวระบุเซสชันหรือโทเค็น
18.เครือข่ายคอมพิวเตอร์

คำตอบ: C · เหยื่อส่งทราฟฟิกที่ไปเกตเวย์ให้ผู้โจมตี ทำให้เกิดการโจมตีแบบคนกลาง (man-in-the-middle)

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

ARP spoofing วางยาแคช ARP ของโฮสต์ด้วย MAC ของผู้โจมตีแทน IP ของเกตเวย์ ผู้โจมตีจึงอ่าน เปลี่ยนแปลง หรือทิ้งทราฟฟิกได้ การตรวจสอบ ARP แบบไดนามิก (dynamic ARP inspection) ช่วยป้องกัน

คำตอบ

C · เหยื่อส่งทราฟฟิกที่ไปเกตเวย์ให้ผู้โจมตี ทำให้เกิดการโจมตีแบบคนกลาง (man-in-the-middle)
19.การแบ่งซับเน็ต IPv4

คำตอบ: H = 6

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

บิตที่ต้องยืม

25 = 32 ≥ 30 → b = 5, /29

โฮสต์ต่อซับเน็ต

23 − 2 = 6

คำตอบ

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

คำตอบ: p = 21

การสรุปเส้นทาง: เส้นทางสรุป a.b.c.0/p ครอบคลุมทุกเครือข่ายที่ p บิตแรกตรงกัน เขียนออกเท็ตที่ต่างกันของเครือข่ายแรกและสุดท้ายเป็นเลขฐานสอง จำนวนบิตนำหน้าที่ตรงกัน บวกบิตของออกเท็ตก่อนหน้า คือพรีฟิกซ์สรุปที่ยาวที่สุด

เทียบบิต

225 = 11100001
231 = 11100111
บิตนำหน้าที่ตรงกัน: 5

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

p = 16 + 5 = 21

คำตอบ

p = /21

เส้นทางสรุป: 10.45.224.0/21 (ครอบคลุมเครือข่าย 1 เครือข่ายที่ไม่อยู่ในรายการด้วย)

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