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

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

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

N = −798 bit
U =
2.ระบบเลขยาก
8 bit1 px1280 px720 pxM = ? KiB

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

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

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

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

ตารางค่าความจริง 16 แถวมีกี่แถวที่ทำให้ ¬(b ∧ c) ↔ (a ↔ d) เป็นจริง เรียกจำนวนนี้ว่า N

¬(b ∧ c) ↔ (a ↔ d)
N =
5.ตรรกะดิจิทัล: เกต แผนที่คาร์โนห์ และฟลิปฟล็อปปานกลาง
ABCD000111100001111010111302040507061121131150140809111110

ใช้แผนที่คาร์โนห์หารูปผลคูณของผลบวก (POS) ที่น้อยที่สุดของ F(A, B, C, D) = Σm(0, 1, 3, 10, 11, 12, 13, 15) มีกี่พจน์ผลบวก (ตัวประกอบ) N

F(A, B, C, D) = Σm(0, 1, 3, 10, 11, 12, 13, 15)
N =
6.ตรรกะดิจิทัล: เกต แผนที่คาร์โนห์ และฟลิปฟล็อปยาก
TQ0​Q0​TQ1​Q1​TQ2​Q2​CLKDOWN

ตัวนับลงฐานสอง 3 บิต เริ่มที่ 6 (ฐานสิบ, Q = 110) หลังพัลส์นาฬิกา 15 พัลส์ จะแสดงค่านับ Q (เป็นเลขฐานสิบ) เท่าใด

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

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

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

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

p = 19k = 24694
624694 mod 19 =
9.อัลกอริทึมและความซับซ้อนปานกลาง

การเรียกซ้ำของ merge sort สำหรับอาร์เรย์ n สมาชิกมีกี่ระดับ

  1. Aประมาณ n / 2
  2. Bประมาณ n
  3. Cประมาณ √n
  4. Dประมาณ log₂ n
10.อัลกอริทึมและความซับซ้อนยาก

การคำนวณจำนวนฟีโบนักชีตัวที่ n ด้วยลูปที่เก็บเพียงสองค่าล่าสุดมีต้นทุนด้านเวลาและพื้นที่เท่าใด

  1. Aเวลา O(2ⁿ) และพื้นที่ O(1)
  2. Bเวลา O(n) และพื้นที่ O(n)
  3. Cเวลา O(n) และพื้นที่ O(1)
  4. Dเวลา O(log n) และพื้นที่ O(n)
11.โครงสร้างข้อมูลปานกลาง

คิวถูกสร้างด้วยสแตกสองตัว: push ลงสแตก "in" และ pop จากสแตก "out" โดยเติมจาก "in" เมื่อว่าง ต้นทุนกระจายต่อการดำเนินการคือเท่าใด

  1. AO(1)
  2. BO(n)
  3. CO(n²)
  4. DO(log n)
12.โครงสร้างข้อมูลยาก

คุณสมบัติใดทำให้ B-tree ทุกต้นสมดุลอย่างสมบูรณ์

  1. Aแต่ละโหนดเก็บหนึ่งคีย์
  2. Bใบทั้งหมดอยู่ที่ความลึกเดียวกัน
  3. Cคีย์ถูกเก็บเฉพาะที่ราก
  4. Dทุกโหนดมีลูกสองตัวพอดี
13.ทฤษฎีกราฟปานกลาง

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

|V| = 6|E| = 10
k =
14.ทฤษฎีกราฟยาก
511111014411151ABCDEFG

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

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

SELECT name, CASE WHEN grade >= 5.5 THEN 'pass' ELSE 'fail' END FROM results คืนอะไร?

  1. Aข้อผิดพลาด เพราะ CASE ไม่อนุญาตใน SELECT
  2. Bชื่อแต่ละคนพร้อมป้าย 'pass' หรือ 'fail' ตามเกรด
  3. Cจำนวนนักเรียนที่สอบผ่านและสอบตก
  4. Dเฉพาะนักเรียนที่สอบผ่าน
16.ฐานข้อมูลและ SQLยาก

สำหรับการเชื่อมแบบเท่ากันระหว่างสองตารางใหญ่ที่ไม่มีดัชนีที่เป็นประโยชน์ ตัวปรับแต่งมักเลือกอัลกอริทึมการเชื่อมใด?

  1. Ahash join
  2. Bbitmap join บนคีย์หลัก
  3. Ccross join
  4. Dnested loop join ที่ค้นด้วยดัชนี
17.เครือข่ายคอมพิวเตอร์ปานกลาง

ความแตกต่างหลักระหว่างเมทอด HTTP แบบ GET และ POST คืออะไร?

  1. AGET เข้ารหัส ส่วน POST ไม่เข้ารหัส
  2. BGET ใช้ UDP ส่วน POST ใช้ TCP
  3. CGET ดึงทรัพยากร ส่วน POST ส่งข้อมูลในเนื้อหาของคำขอ
  4. DGET ลบทรัพยากร ส่วน POST อ่านทรัพยากรจากฐานข้อมูลของเซิร์ฟเวอร์
18.เครือข่ายคอมพิวเตอร์ยาก

ตามทฤษฎีบทของแชนนอน ความจุของช่องสัญญาณ 1 MHz ที่มีอัตราส่วนสัญญาณต่อสัญญาณรบกวนเท่ากับ 255 คือเท่าใด?

  1. A8 Mbit/s
  2. B255 Mbit/s
  3. C1 Mbit/s
  4. D2 Mbit/s
19.การแบ่งซับเน็ต IPv4ปานกลาง
/24 → /2511111111111111111111111110000000บิตเครือข่ายบิตโฮสต์

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

192.168.139.0/24/25ซับเน็ต 2 (ซับเน็ต 1 เริ่มที่ .0)
x =
20.การแบ่งซับเน็ต IPv4ยาก

เครือข่าย 192.168.79.0/24 ถูกแบ่งด้วย VLSM สำหรับ LAN เหล่านี้: A: 10 โฮสต์, B: 4 โฮสต์, C: 99 โฮสต์, D: 37 โฮสต์ ซับเน็ตถูกจัดสรรจาก .0 ขึ้นไป โดย LAN ที่มีโฮสต์มากที่สุดมาก่อน แต่ละ LAN ได้ซับเน็ตที่เล็กที่สุดที่พอดี ออกเท็ตที่สี่ x ของที่อยู่เครือข่ายของ LAN D คือเท่าใด

A: 10B: 4C: 99D: 37
x =

3สารละลาย

1.ระบบเลข

คำตอบ: U = 177

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

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

79 = 0100 1111
ที่กลับบิตแล้ว: 1011 0000
+1 → 1011 0001

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

1011 0001₂ = 256 − 79 = 177

คำตอบ

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

คำตอบ: M = 900 KiB

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

บิตและไบต์

1280·720·8 = 7372800 bit = 921600 B

แปลงเป็น KiB

921600/1024 = 900 KiB

คำตอบ

M = 900 KiB
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 = p ∧ r, b = ¬q

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

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

คำตอบ

¬¬q → ¬(p ∧ r)

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

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

คำตอบ: N = 8

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

คอลัมน์

b ∧ c; ¬(b ∧ c); a ↔ d; ¬(b ∧ c) ↔ (a ↔ d)

แยกตาม a

a = 1: 4
a = 0: 4
N = 4 + 4 = 8

คำตอบ

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

คำตอบ: N = 4

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

ABCD000111100001111010111302040507061121131150140809111110

จัดกลุ่ม 0

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

(B′ + C′ + D)
(A + C′ + D)
(A + B′)
(A′ + B + C)

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

F = (B′ + C′ + D)(A + C′ + D)(A + B′)(A′ + B + C)
N = 4

คำตอบ

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

คำตอบ: Q = 7

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

รอบเต็ม

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

15 = 1·8 + 7

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

Q = (6 − 7) mod 8 = 7
Q = 111₂

คำตอบ

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

คำตอบ: 32−1 mod 61 = 21

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

r = 61, t = 0
r = 32, q = 1, t = 1
r = 29, q = 1, t = −1
r = 3, q = 9, t = 2
r = 2, q = 1, t = −19
r = 1, q = 2, t = 21

อินเวอร์ส

1 ≡ 21·32 (mod 61)
x = 21
ตรวจสอบ: 32·21 = 672 = 11·61 + 1

คำตอบ

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

คำตอบ: 624694 mod 19 = 9

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

ลดเลขชี้กำลัง

24694 mod 18 = 16
624694 ≡ 616 (mod 19)

เลขยกกำลังขนาดเล็ก

616 mod 19 = 9

คำตอบ

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

คำตอบ: D · ประมาณ log₂ n

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

การแบ่งครึ่งจาก n ลงถึง 1 ใช้ประมาณ log₂ n ระดับ และแต่ละระดับทำงานผสาน O(n) ได้ O(n log n)

คำตอบ

D · ประมาณ log₂ n
10.อัลกอริทึมและความซับซ้อน

คำตอบ: C · เวลา O(n) และพื้นที่ O(1)

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

แต่ละขั้นต้องการเพียงสองค่าก่อนหน้า ตารางของวิธีล่างขึ้นบนจึงแทนที่ด้วยตัวแปรสองตัวได้

คำตอบ

C · เวลา O(n) และพื้นที่ O(1)
11.โครงสร้างข้อมูล

คำตอบ: A · O(1)

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

แต่ละสมาชิกถูก push และ pop ไม่เกินสองครั้งรวม แม้การเติมหนึ่งครั้งอาจใช้ O(n) ค่าเฉลี่ยตลอดลำดับเป็น O(1)

คำตอบ

A · O(1)
12.โครงสร้างข้อมูล

คำตอบ: B · ใบทั้งหมดอยู่ที่ความลึกเดียวกัน

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

โหนดแยกขึ้นด้านบนเมื่อเต็ม และต้นไม้สูงขึ้นเฉพาะเมื่อรากแยก ใบทั้งหมดจึงอยู่ที่ระดับเดียวกันเสมอ

คำตอบ

B · ใบทั้งหมดอยู่ที่ความลึกเดียวกัน
13.ทฤษฎีกราฟ

คำตอบ: k = 5

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

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

6 − 1 = 5

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

k = 10 − 5 = 5

คำตอบ

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

คำตอบ: G

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

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

1. A (0): B: 5, C: 11
2. B (5): D: 15, G: 9
3. G (9): E: 10
4. E (10)
5. C (11)
6. D (15): F: 29
7. F (29)

รอบ 3

G

คำตอบ

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

คำตอบ: B · ชื่อแต่ละคนพร้อมป้าย 'pass' หรือ 'fail' ตามเกรด

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

นิพจน์ CASE ประเมินเงื่อนไขต่อแถวและคืนค่าที่ตรงกัน ทุกแถวจึงได้ป้าย

คำตอบ

B · ชื่อแต่ละคนพร้อมป้าย 'pass' หรือ 'fail' ตามเกรด
16.ฐานข้อมูลและ SQL

คำตอบ: A · hash join

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

hash join สร้างตารางแฮชบนอินพุตหนึ่งและค้นด้วยอีกอินพุต ซึ่งเหมาะกับ equi-join ขนาดใหญ่ที่ไม่มีดัชนี

คำตอบ

A · hash join
17.เครือข่ายคอมพิวเตอร์

คำตอบ: C · GET ดึงทรัพยากร ส่วน POST ส่งข้อมูลในเนื้อหาของคำขอ

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

GET ขอทรัพยากรและไม่ควรเปลี่ยนสถานะของเซิร์ฟเวอร์ ส่วน POST ส่งข้อมูล เช่น แบบฟอร์ม ในเนื้อหาให้เซิร์ฟเวอร์ประมวลผล

คำตอบ

C · GET ดึงทรัพยากร ส่วน POST ส่งข้อมูลในเนื้อหาของคำขอ
18.เครือข่ายคอมพิวเตอร์

คำตอบ: A · 8 Mbit/s

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

C = 10⁶ × log₂(256) = 10⁶ × 8 = 8 Mbit/s นี่คือขีดจำกัดบนของอัตราข้อมูลที่ไม่มีข้อผิดพลาดบนช่องสัญญาณที่มีสัญญาณรบกวน

คำตอบ

A · 8 Mbit/s
19.การแบ่งซับเน็ต IPv4

คำตอบ: x = 255

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

ขนาดบล็อก

27 = 128

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

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

คำตอบ

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

คำตอบ: x = 128

VLSM: แต่ละ LAN ได้ซับเน็ตที่เล็กที่สุดที่ 2ʰ − 2 ≥ จำนวนโฮสต์ของมัน คือพรีฟิกซ์ 32 − h การจัดสรรซับเน็ตที่ใหญ่ที่สุดก่อนทำให้ทุกบล็อกอยู่ในแนวพหุคูณของขนาดตัวเอง ที่อยู่เครือข่ายจึงได้จากการบวกขนาดบล็อก

ขนาดบล็อกของแต่ละ LAN

C: 99 โฮสต์ → 27 = 128 (/25)
D: 37 โฮสต์ → 26 = 64 (/26)
A: 10 โฮสต์ → 24 = 16 (/28)
B: 4 โฮสต์ → 23 = 8 (/29)

การจัดสรร จากใหญ่ที่สุดก่อน

C: .0 – .127
D: .128 – .191
A: .192 – .207
B: .208 – .215

คำตอบ

x = 128

LAN D: 192.168.79.128/26

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