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

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

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

N = −1168 bit
U =
2.ระบบเลขยาก
24 bit1 px1024 px768 pxM = ? KiB

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

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

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

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

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

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

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

F = ABC′ + A′BC + B′C + A′BC′
L =
6.ตรรกะดิจิทัล: เกต แผนที่คาร์โนห์ และฟลิปฟล็อปยาก
ABCD00011110000111100001X30204X50716112113015114X809X11110

สำหรับ F(A, B, C, D) = Σm(6, 10, 12, 13, 14) + d(3, 5, 8, 11) โดย d แทนเงื่อนไขไม่สนใจ จงหาจำนวน N ของไพรม์อิมพลิแคนต์จำเป็น

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

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

n = 44 = 22·11
φ(44) =
8.ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ยาก

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

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

ความซับซ้อนเชิงเวลาของการคูณเมทริกซ์ n × n สองเมทริกซ์ด้วยลูปสามชั้นมาตรฐานคือเท่าใด

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

เหตุใดการค้นหาแบบเปรียบเทียบใด ๆ ในอาร์เรย์ที่เรียงแล้วจึงต้องใช้ Ω(log n) การเปรียบเทียบในกรณีเลวร้ายที่สุด

  1. Aต้นไม้ตัดสินใจที่มีผลลัพธ์ที่เป็นไปได้ n แบบต้องมีความลึกอย่างน้อย log₂ n
  2. Bการเปรียบเทียบแต่ละครั้งใช้เวลาแบบลอการิทึม
  3. Cทุกสมาชิกต้องถูกเปรียบเทียบอย่างน้อยหนึ่งครั้ง
  4. Dการค้นหาแบบทวิภาคเป็นอัลกอริทึมเดียวที่เป็นไปได้ และต้องใช้ log₂ n การเปรียบเทียบ
11.โครงสร้างข้อมูลปานกลาง

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

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

ใน BST ที่มีราก 50 ต้นไม้ย่อยซ้าย 30 (ลูก 20, 40) และต้นไม้ย่อยขวา 70 (ลูก 60, 80) ลบรากโดยใช้ in-order successor คีย์ใดกลายเป็นรากใหม่

  1. A80
  2. B60
  3. C70
  4. D40
13.ทฤษฎีกราฟปานกลาง

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

K4
H =
14.ทฤษฎีกราฟยาก
1146771357ABCDEF

ใช้ขั้นตอนวิธีของไดก์สตราเพื่อหาความยาว d(F) ของเส้นทางที่สั้นที่สุดจาก A ไป F ในกราฟถ่วงน้ำหนัก

เริ่มต้น: Aสิ้นสุด: F
d(F) =
15.ฐานข้อมูลและ SQLปานกลาง

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

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

ข้อเสียที่รู้จักของการแยกตารางเป็น BCNF เมื่อเทียบกับ 3NF คืออะไร?

  1. ABCNF ยอมให้มีความซ้ำซ้อนมากกว่า 3NF
  2. Bตาราง BCNF มีคีย์หลักไม่ได้
  3. Cการพึ่งพาเชิงฟังก์ชันบางอย่างอาจตรวจสอบภายในตารางเดียวไม่ได้อีกต่อไป
  4. Dการแยกทำให้ข้อมูลหายเสมอเมื่อเชื่อมกลับ
17.เครือข่ายคอมพิวเตอร์ปานกลาง

RIP ใช้เมตริกใดเลือกเส้นทาง?

  1. Aความล่าช้าที่วัดได้
  2. Bแบนด์วิดท์ของลิงก์
  3. Cนโยบายทางธุรกิจ
  4. Dจำนวนฮอป (hop count)
18.เครือข่ายคอมพิวเตอร์ยาก

แอปพลิเคชันเทอร์มินัลระยะไกลรู้สึกอืดเพราะแพ็กเก็ตการกดแป้นเล็ก ๆ ถูกกั้นไว้ กลไก TCP ใดมักเป็นสาเหตุ?

  1. ASlow start
  2. Bอัลกอริทึมของ Nagle (Nagle's algorithm)
  3. Cการแฮนด์เชกสามทาง
  4. DFast retransmit
19.การแบ่งซับเน็ต IPv4ปานกลาง
/?11111111111111111111111100000000บิตเครือข่ายบิตโฮสต์

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

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

โฮสต์มีที่อยู่ 10.20.159.116/30 ออคเต็ตที่สี่ x ของที่อยู่โฮสต์ที่ใช้ได้สุดท้ายในซับเน็ตคือเท่าใด

10.20.159.116/30
x =

3สารละลาย

1.ระบบเลข

คำตอบ: U = 140

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

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

116 = 0111 0100
ที่กลับบิตแล้ว: 1000 1011
+1 → 1000 1100

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

1000 1100₂ = 256 − 116 = 140

คำตอบ

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

คำตอบ: M = 2304 KiB

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

บิตและไบต์

1024·768·24 = 18874368 bit = 2359296 B

แปลงเป็น KiB

2359296/1024 = 2304 KiB

คำตอบ

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

คำตอบ: ¬q ∨ ¬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 ∧ b) ≡ ¬a ∨ ¬b ตัว ∧ เปลี่ยนเป็น ∨ และทั้งสองส่วนถูกใส่นิเสธ
¬(q ∧ p) ≡ ¬q ∨ ¬p

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

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

คำตอบ

¬q ∨ ¬p

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

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

คำตอบ: ∃x (A(x) ∧ ∀y ¬R(x, y))

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

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

¬∀x (A(x) → ∃y R(x, y)) ≡ ∃x (A(x) ∧ ∀y ¬R(x, y))

คำตอบ

∃x (A(x) ∧ ∀y ¬R(x, y))

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

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 หนึ่งครั้ง

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

ABC′ → m(6)
A′BC → m(3)
B′C → m(1, 5)
A′BC′ → m(2)
ABC00011110010011131204150716

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

F = B′C + BC′ + A′C

นับลิเทอรัล

L = 6

คำตอบ

L = 6

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

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

คำตอบ: N = 1

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

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

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

BC′D, BCD′, AD′, AB′C, ABC′
ABCD00011110000111100001X30204X50716112113015114X809X11110

ไพรม์อิมพลิแคนต์จำเป็น

BCD′
N = 1

คำตอบ

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

คำตอบ: φ(44) = 20

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

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

44 = 22·11

โทเทียนต์

φ(44) = φ(4)·φ(11) = 2·10 = 20

คำตอบ

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

คำตอบ: x = 12

ตัวผกผันและความสอดคล้อง: 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(25, 65) = 5
5x ≡ 8 (mod 13)

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

5−1 ≡ 8 (mod 13) → x ≡ 12 (mod 13)

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

x ∈ {12, 25, 38, 51, 64}
x = 12

คำตอบ

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

คำตอบ: C · O(n³)

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

มี n² ช่องและแต่ละช่องต้องคูณ n ครั้ง ได้ n³ การดำเนินการ

คำตอบ

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

คำตอบ: A · ต้นไม้ตัดสินใจที่มีผลลัพธ์ที่เป็นไปได้ n แบบต้องมีความลึกอย่างน้อย log₂ n

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

การเปรียบเทียบแต่ละครั้งลดเซตความเป็นไปได้ที่เหลือลงอย่างมากที่สุดครึ่งหนึ่ง การแยกแยะ n ตำแหน่งจึงต้องใช้อย่างน้อย log₂ n การเปรียบเทียบ

คำตอบ

A · ต้นไม้ตัดสินใจที่มีผลลัพธ์ที่เป็นไปได้ n แบบต้องมีความลึกอย่างน้อย log₂ n
11.โครงสร้างข้อมูล

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

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

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

คำตอบ

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

คำตอบ: B · 60

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

โหนดซ้ายสุดของต้นไม้ย่อยขวาคือ 60 ดังนั้น 60 แทนที่ 50 และตำแหน่งเดิมของมันถูกลบ ถ้าใช้ predecessor จะได้ 40

คำตอบ

B · 60
13.ทฤษฎีกราฟ

คำตอบ: H = 3

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

นับ

H = (4 − 1)!/2 = 6/2 = 3

คำตอบ

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

คำตอบ: d(F) = 23

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

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

แต่ละบรรทัด: จุดยอดที่ยืนยัน ระยะทางสุดท้ายของมัน และเพื่อนบ้านที่ระยะทางดีขึ้น

A (0): C: 11
C (11): B: 15, E: 18
B (15): D: 21
E (18): F: 23
D (21)
F (23)

เส้นทางที่สั้นที่สุด

A → C → E → F
d(F) = 23

คำตอบ

d(F) = 23
15.ฐานข้อมูลและ SQL

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

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

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

คำตอบ

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

คำตอบ: C · การพึ่งพาเชิงฟังก์ชันบางอย่างอาจตรวจสอบภายในตารางเดียวไม่ได้อีกต่อไป

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

การแยก BCNF แบบไม่สูญเสียมีอยู่เสมอ แต่อาจไม่รักษาการพึ่งพา ส่วน 3NF ทำได้ทั้งแบบไม่สูญเสียและรักษาการพึ่งพาเสมอ

คำตอบ

C · การพึ่งพาเชิงฟังก์ชันบางอย่างอาจตรวจสอบภายในตารางเดียวไม่ได้อีกต่อไป
17.เครือข่ายคอมพิวเตอร์

คำตอบ: D · จำนวนฮอป (hop count)

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

RIP เป็นโพรโทคอลแบบเวกเตอร์ระยะทางที่นับฮอป โดย 16 หมายถึงเข้าถึงไม่ได้ จึงจำกัดอยู่ที่เครือข่ายขนาดเล็ก

คำตอบ

D · จำนวนฮอป (hop count)
18.เครือข่ายคอมพิวเตอร์

คำตอบ: B · อัลกอริทึมของ Nagle (Nagle's algorithm)

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

อัลกอริทึมของ Nagle รอรวมเซกเมนต์ขนาดเล็กขณะที่ข้อมูลก่อนหน้ายังไม่ได้รับการตอบรับ ช่วยประหยัดแบนด์วิดท์แต่เพิ่มความล่าช้าให้ทราฟฟิกแบบโต้ตอบ

คำตอบ

B · อัลกอริทึมของ Nagle (Nagle's algorithm)
19.การแบ่งซับเน็ต IPv4

คำตอบ: p = 24

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

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

27 − 2 = 126 < 199
28 − 2 = 254 ≥ 199 → h = 8

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

p = 32 − 8 = 24

คำตอบ

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

คำตอบ: x = 118

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

ขนาดบล็อก

22 = 4

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

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

คำตอบ

x = 118

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