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

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

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

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

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

893
b = bit
3.ตรรกศาสตร์ประพจน์และการพิสูจน์ปานกลาง
pqr¬p → r(¬p → r) → q((r ∨ ¬q) ∨ p) → ((¬p → r) → q)111?110?101?100?011?010?001?000?

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

((r ∨ ¬q) ∨ p) → ((¬p → r) → q)
N =
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.ตรรกะดิจิทัล: เกต แผนที่คาร์โนห์ และฟลิปฟล็อปปานกลาง
ABC00011110010001031214051706

ใช้แผนที่คาร์โนห์หารูปผลบวกของผลคูณ (SOP) ที่น้อยที่สุดของ F(A, B, C) = Σm(2, 4, 7) มีกี่พจน์ผลคูณ N

F(A, B, C) = Σm(2, 4, 7)
N =
6.ตรรกะดิจิทัล: เกต แผนที่คาร์โนห์ และฟลิปฟล็อปยาก
ABCD00011110000111100001030214X5X71611201301501408X9111010

จงหารูป SOP ที่น้อยที่สุดของ F(A, B, C, D) = Σm(4, 6, 11, 12) + d(5, 7, 9) โดย d แทนเงื่อนไขไม่สนใจ มีกี่พจน์ผลคูณ N

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

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

a = 6n = 11
6−1 mod 11 =
8.ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ยาก
87c = me​ mod n?m = cd​ mod nm(n, e) = (115, 5)d

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

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

การกล่าวว่าอัลกอริทึม O(n²) เป็น O(n³) ด้วย ถูกต้องหรือไม่

  1. Aถูกต้อง แต่เฉพาะเมื่อ n น้อยกว่า 100
  2. Bไม่ถูก เพราะ Big O ต้องระบุอัตราการเติบโตที่แน่นอนของฟังก์ชันเสมอ
  3. Cไม่ถูก เพราะ n³ น้อยกว่า n² เมื่อ n มาก
  4. Dถูกต้อง เพราะ Big O เป็นขอบเขตบน และ n² เติบโตไม่เร็วกว่า n³
10.อัลกอริทึมและความซับซ้อนยาก

การเรียงลำดับทอพอโลยีทำได้เฉพาะกับ

  1. Aกราฟไม่มีทิศทาง
  2. Bกราฟมีทิศทางแบบไม่มีวงจร (DAG)
  3. Cกราฟที่มีน้ำหนักติดลบ
  4. Dกราฟบริบูรณ์
11.โครงสร้างข้อมูลปานกลาง

ตารางแฮชขนาด 7 ใช้ h(k) = k mod 7 และ linear probing หลังแทรก 10 แล้ว 17 ถูกเก็บที่ใด

  1. Aดัชนี 4
  2. Bดัชนี 0
  3. Cดัชนี 3
  4. Dดัชนี 6
12.โครงสร้างข้อมูลยาก

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

  1. Aหมุนซ้ายหนึ่งครั้งที่โหนด
  2. Bหมุนขวาที่ลูกซ้าย แล้วหมุนซ้ายที่โหนด
  3. Cหมุนขวาหนึ่งครั้งที่โหนด
  4. Dหมุนซ้ายที่ลูกซ้าย แล้วหมุนขวาที่โหนด
13.ทฤษฎีกราฟปานกลาง

กราฟเชื่อมโยงมี 15 จุดยอดและ 20 เส้นเชื่อม ต้องเอาเส้นเชื่อมออกกี่เส้น k เพื่อให้เหลือต้นไม้ทอดข้าม

|V| = 15|E| = 20
k =
14.ทฤษฎีกราฟยาก
87511119118ABCDEF

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

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

วิว (view) ใน SQL คือ:

  1. Aหน้าจอในโปรแกรมไคลเอนต์ฐานข้อมูลสำหรับเรียกดูตาราง
  2. Bสำเนาของตารางบนดิสก์
  3. Cชนิดของดัชนี
  4. Dคิวรีที่เก็บไว้ซึ่งทำงานเหมือนตารางเสมือน
16.ฐานข้อมูลและ SQLยาก

FULL OUTER JOIN ให้ผลลัพธ์อะไร?

  1. Aทุกแถวจากทั้งสองตาราง จับคู่เท่าที่ทำได้และเติม NULL ในส่วนที่เหลือ
  2. Bเฉพาะแถวที่ตรงกัน
  3. Cเฉพาะแถวที่ไม่ตรงกัน
  4. Dผลคูณคาร์ทีเซียน โดยจับคู่ทุกแถวของตารางหนึ่งกับทุกแถวของอีกตาราง
17.เครือข่ายคอมพิวเตอร์ปานกลาง

เบราว์เซอร์ได้รับรหัสสถานะ HTTP 404 หมายความว่าอย่างไร?

  1. Aไม่พบทรัพยากรที่ขอ
  2. Bเซิร์ฟเวอร์เกิดข้อผิดพลาดภายใน
  3. Cคำขอสำเร็จ
  4. Dไคลเอนต์ต้องล็อกอินก่อน
18.เครือข่ายคอมพิวเตอร์ยาก

ที่อยู่ใดต่อไปนี้เป็นที่อยู่ IPv4 สาธารณะ (ไม่ใช่ที่อยู่ส่วนตัวตาม RFC 1918)?

  1. A172.32.0.1
  2. B192.168.255.1
  3. C10.255.0.1
  4. D172.31.0.1
19.การแบ่งซับเน็ต IPv4ปานกลาง
/24 → /2711111111111111111111111111100000บิตเครือข่ายบิตโฮสต์

เครือข่าย 192.168.31.0/24 ถูกแบ่งเป็นซับเน็ต /27 หมายเลข 1, 2, 3, … จากแอดเดรสต่ำสุด (ซับเน็ต 1 เริ่มที่ .0) ออกเท็ตที่สี่ x ของบรอดคาสต์แอดเดรสของซับเน็ต 2 คือเท่าใด

192.168.31.0/24/27ซับเน็ต 2 (ซับเน็ต 1 เริ่มที่ .0)
x =
20.การแบ่งซับเน็ต IPv4ยาก
ออคเต็ตสุดท้าย = 244112816413211608140201เครือข่ายโฮสต์

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

10.20.236.244/26
x =

3สารละลาย

1.ระบบเลข

คำตอบ: U = 246

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

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

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

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

1111 0110₂ = 256 − 10 = 246

คำตอบ

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

คำตอบ: b = 10 bit

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

กำลังของสอง

29 = 512 < 893
210 = 1024 ≥ 893

คำตอบ

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

คำตอบ: N = 5

ตารางค่าความจริง: สูตรที่มีตัวแปรต่างกัน 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: ¬q = 0, r ∨ ¬q = 1, (r ∨ ¬q) ∨ p = 1, ¬p = 0, ¬p → r = 1, (¬p → r) → q = 1, ((r ∨ ¬q) ∨ p) → ((¬p → r) → q) = 1
p = 1, q = 1, r = 0: ¬q = 0, r ∨ ¬q = 0, (r ∨ ¬q) ∨ p = 1, ¬p = 0, ¬p → r = 1, (¬p → r) → q = 1, ((r ∨ ¬q) ∨ p) → ((¬p → r) → q) = 1
p = 1, q = 0, r = 1: ¬q = 1, r ∨ ¬q = 1, (r ∨ ¬q) ∨ p = 1, ¬p = 0, ¬p → r = 1, (¬p → r) → q = 0, ((r ∨ ¬q) ∨ p) → ((¬p → r) → q) = 0
p = 1, q = 0, r = 0: ¬q = 1, r ∨ ¬q = 1, (r ∨ ¬q) ∨ p = 1, ¬p = 0, ¬p → r = 1, (¬p → r) → q = 0, ((r ∨ ¬q) ∨ p) → ((¬p → r) → q) = 0
p = 0, q = 1, r = 1: ¬q = 0, r ∨ ¬q = 1, (r ∨ ¬q) ∨ p = 1, ¬p = 1, ¬p → r = 1, (¬p → r) → q = 1, ((r ∨ ¬q) ∨ p) → ((¬p → r) → q) = 1
p = 0, q = 1, r = 0: ¬q = 0, r ∨ ¬q = 0, (r ∨ ¬q) ∨ p = 0, ¬p = 1, ¬p → r = 0, (¬p → r) → q = 1, ((r ∨ ¬q) ∨ p) → ((¬p → r) → q) = 1
p = 0, q = 0, r = 1: ¬q = 1, r ∨ ¬q = 1, (r ∨ ¬q) ∨ p = 1, ¬p = 1, ¬p → r = 1, (¬p → r) → q = 0, ((r ∨ ¬q) ∨ p) → ((¬p → r) → q) = 0
p = 0, q = 0, r = 0: ¬q = 1, r ∨ ¬q = 1, (r ∨ ¬q) ∨ p = 1, ¬p = 1, ¬p → r = 0, (¬p → r) → q = 1, ((r ∨ ¬q) ∨ p) → ((¬p → r) → q) = 1

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

((r ∨ ¬q) ∨ p) → ((¬p → r) → q): 1, 1, 0, 0, 1, 1, 0, 1
N = 5

คำตอบ

N = 5
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.ตรรกะดิจิทัล: เกต แผนที่คาร์โนห์ และฟลิปฟล็อป

คำตอบ: N = 3

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

ABC00011110010001031214051706

จัดกลุ่ม 1

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

A′BC′
AB′C′
ABC

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

F = A′BC′ + AB′C′ + ABC
N = 3

คำตอบ

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

คำตอบ: N = 3

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

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

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

BC′D′, A′B, AB′D
ABCD00011110000111100001030214X5X71611201301501408X9111010

การครอบคลุมที่น้อยที่สุด

F = BC′D′ + A′B + AB′D
N = 3

คำตอบ

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

คำตอบ: 6−1 mod 11 = 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)

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

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

r = 11, t = 0
r = 6, q = 1, t = 1
r = 5, q = 1, t = −1
r = 1, q = 5, t = 2

อินเวอร์ส

1 ≡ 2·6 (mod 11)
x = 2
ตรวจสอบ: 6·2 = 12 = 1·11 + 1

คำตอบ

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

คำตอบ: c = 72

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

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

5 = 4 + 1
871 ≡ 87 (mod 115)
872 ≡ 94 (mod 115)
874 ≡ 96 (mod 115)
875 ≡ 87·96 ≡ 72 (mod 115)

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

c = 72

คำตอบ

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

คำตอบ: D · ถูกต้อง เพราะ Big O เป็นขอบเขตบน และ n² เติบโตไม่เร็วกว่า n³

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

Big O เป็นขอบเขตบน ข้อความนี้จึงจริงแต่ไม่แน่น ส่วน Θ(n²) ระบุอัตราการเติบโตที่แน่นอน

คำตอบ

D · ถูกต้อง เพราะ Big O เป็นขอบเขตบน และ n² เติบโตไม่เร็วกว่า n³
10.อัลกอริทึมและความซับซ้อน

คำตอบ: B · กราฟมีทิศทางแบบไม่มีวงจร (DAG)

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

ลำดับทอพอโลยีมีอยู่ก็ต่อเมื่อกราฟมีทิศทางไม่มีวงจร และหาได้ใน O(V + E) ด้วย DFS หรืออัลกอริทึมของ Kahn

คำตอบ

B · กราฟมีทิศทางแบบไม่มีวงจร (DAG)
11.โครงสร้างข้อมูล

คำตอบ: A · ดัชนี 4

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

10 mod 7 = 3 และ 17 mod 7 = 3 ดัชนี 3 ถูกใช้แล้ว linear probing จึงลองช่องถัดไป คือดัชนี 4

คำตอบ

A · ดัชนี 4
12.โครงสร้างข้อมูล

คำตอบ: D · หมุนซ้ายที่ลูกซ้าย แล้วหมุนขวาที่โหนด

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

การหมุนครั้งแรกเปลี่ยนกรณีซ้าย–ขวาเป็นซ้าย–ซ้าย ซึ่งการหมุนขวาที่โหนดไม่สมดุลแก้ได้

คำตอบ

D · หมุนซ้ายที่ลูกซ้าย แล้วหมุนขวาที่โหนด
13.ทฤษฎีกราฟ

คำตอบ: k = 6

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

เส้นเชื่อมของต้นไม้ทอดข้าม

15 − 1 = 14

เส้นเชื่อมที่ต้องเอาออก

k = 20 − 14 = 6

คำตอบ

k = 6
14.ทฤษฎีกราฟ

คำตอบ: B

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

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

1. A (0): B: 8, C: 7
2. C (7): E: 18
3. B (8): D: 19, E: 16
4. E (16): F: 27
5. D (19)
6. F (27)

รอบ 3

B

คำตอบ

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

คำตอบ: D · คิวรีที่เก็บไว้ซึ่งทำงานเหมือนตารางเสมือน

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

วิวเก็บคำสั่ง SELECT การคิวรีวิวจะรันคิวรีเบื้องหลัง (materialised view เก็บผลลัพธ์ไว้)

คำตอบ

D · คิวรีที่เก็บไว้ซึ่งทำงานเหมือนตารางเสมือน
16.ฐานข้อมูลและ SQL

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

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

full outer join เก็บทุกแถวของทั้งสองตาราง จับคู่ที่ตรงกันและเติม NULL ให้ฝั่งที่ขาด

คำตอบ

A · ทุกแถวจากทั้งสองตาราง จับคู่เท่าที่ทำได้และเติม NULL ในส่วนที่เหลือ
17.เครือข่ายคอมพิวเตอร์

คำตอบ: A · ไม่พบทรัพยากรที่ขอ

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

404 Not Found หมายความว่าเซิร์ฟเวอร์ไม่มีทรัพยากรที่ URL นั้น 200 คือ OK, 401 คือ Unauthorized และ 500 คือ Internal Server Error

คำตอบ

A · ไม่พบทรัพยากรที่ขอ
18.เครือข่ายคอมพิวเตอร์

คำตอบ: A · 172.32.0.1

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

172.16.0.0/12 ครอบคลุมตั้งแต่ 172.16.0.0 ถึง 172.31.255.255 ดังนั้น 172.32.0.1 อยู่นอกช่วงนั้น อีกสามที่อยู่อยู่ในช่วงส่วนตัว

คำตอบ

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

คำตอบ: x = 63

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

ขนาดบล็อก

25 = 32

ซับเน็ตหมายเลข 2

เครือข่าย: (2 − 1)·32 = 32
บรอดคาสต์: 32 + 32 − 1 = 63

คำตอบ

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

คำตอบ: x = 192

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

ขนาดบล็อก

26 = 64

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

เครือข่าย: ⌊244/64⌋·64 = 192
บรอดคาสต์: 192 + 64 − 1 = 255
โฮสต์ที่ใช้ได้: 193 … 254

คำตอบ

x = 192

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