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

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

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

1010 00118 bit
N =
2.ระบบเลขยาก
10 บิต two's complement, N = ??เครื่องหมาย?????????

จำนวนเต็มที่ติดลบมากที่สุด N ที่เก็บได้ใน two's complement 10 บิตคือเท่าใด

10 bit
N =
3.ตรรกศาสตร์ประพจน์และการพิสูจน์ปานกลาง
abcb → ca ∧ (b → c)(b ∨ a) ↔ (a ∧ (b → c))111?110?101?100?011?010?001?000?

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

(b ∨ a) ↔ (a ∧ (b → c))
N =
4.ตรรกศาสตร์ประพจน์และการพิสูจน์ยาก
∃x ¬F(x)∀x ¬F(x)∃x F(x)∀x F(x)

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

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

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

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

ตัวนับริปเปิล (อะซิงโครนัส) 3 บิตสร้างจากฟลิปฟล็อปที่มีความหน่วงการแพร่กระจายตัวละ 15 ns เอาต์พุตทั้งหมดต้องนิ่งก่อนขอบสัญญาณนาฬิกาถัดไป จงหาความถี่นาฬิกาสูงสุด fmax

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

จงหาจำนวนเต็มบวกที่น้อยที่สุด x ที่ x ≡ 3 (mod 5) และ x ≡ 5 (mod 12)

x ≡ 3 (mod 5)x ≡ 5 (mod 12)
x =
8.ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ยาก

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

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

เหตุใดรูทีนการเรียงลำดับในไลบรารีจำนวนมากจึงเปลี่ยนไปใช้ insertion sort กับอาร์เรย์ย่อยที่เล็กมาก

  1. Aอัลกอริทึมแบบเรียกซ้ำจัดการอาร์เรย์ที่เล็กกว่า 10 สมาชิกไม่ได้
  2. BInsertion sort ใช้หน่วยความจำน้อยกว่าอัลกอริทึมการเรียงลำดับอื่นทุกตัวกับอินพุตใหญ่
  3. CInsertion sort มีภาระเพิ่มน้อยและเร็วกับอินพุตที่เล็กหรือเกือบเรียงแล้ว
  4. DInsertion sort เป็น O(n log n) ในกรณีเลวร้ายที่สุด
10.อัลกอริทึมและความซับซ้อนยาก

ข้อใดเกี่ยวกับสัญกรณ์ little-o ถูกต้อง

  1. An = o(n) เพราะทุกฟังก์ชันเป็น little-o ของตัวมันเอง
  2. Bn² = o(n)
  3. Cn = o(n²) แต่ n ไม่ใช่ o(n)
  4. D2n = o(n) เพราะ 2n เติบโตช้า
11.โครงสร้างข้อมูลปานกลาง

โครงสร้างข้อมูลใดใช้ตรวจว่าวงเล็บใน "{[()]}" สมดุลหรือไม่

  1. Aสแตก
  2. Bคิว
  3. Cตารางแฮช
  4. Dbinary search tree
12.โครงสร้างข้อมูลยาก

segment tree มักใช้เพื่อ

  1. Aตอบคำถามช่วง (เช่น ผลรวมช่วง) และอัปเดตใน O(log n)
  2. Bเรียงสตริงตามตัวอักษรโดยเก็บแต่ละคำนำหน้าไว้ในโหนดต้นไม้แยกกัน
  3. Cเก็บเส้นเชื่อมของกราฟ
  4. Dสร้างสแตก
13.ทฤษฎีกราฟปานกลาง

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

|V| = 6|E| = 8
k =
14.ทฤษฎีกราฟยาก
13514161122ABCDE

ขั้นตอนวิธีของครัสคัลสร้างต้นไม้ทอดข้ามค่าน้อยที่สุด ให้คลิกเส้นเชื่อมที่เพิ่มเป็นเส้นหมายเลข 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ปานกลาง

ทริกเกอร์ (trigger) ของฐานข้อมูลคืออะไร?

  1. Aการสำรองฐานข้อมูลตามกำหนดเวลา
  2. Bชนิดของดัชนีที่เร่งการค้นหา
  3. Cคิวรีที่ผู้ใช้รันด้วยมือ
  4. Dโค้ดที่ทำงานอัตโนมัติเมื่อเกิดเหตุการณ์ที่กำหนด เช่น INSERT, UPDATE หรือ DELETE บนตาราง
16.ฐานข้อมูลและ SQLยาก

ตารางเวลาของทรานแซกชันที่ทำพร้อมกันเรียกว่า serializable เมื่อใด?

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

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

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

ไฟร์วอลล์บล็อก ICMP ทั้งหมด คำขอเว็บขนาดเล็กใช้ได้ แต่การดาวน์โหลดขนาดใหญ่บนบางเส้นทางค้าง สาเหตุที่น่าจะเป็นคืออะไร?

  1. Apath MTU discovery ล้มเหลวเพราะข้อความ "fragmentation needed" ถูกบล็อก
  2. Bใบรับรอง TLS ถูกส่งผ่าน ICMP
  3. CTCP เปิดการเชื่อมต่อไม่ได้หากไม่มี ICMP
  4. DDNS ต้องใช้ ICMP ในการแปลงชื่อ
19.การแบ่งซับเน็ต IPv4ปานกลาง
/16 → /2011111111111111111111000000000000บิตเครือข่ายบิตโฮสต์

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

172.19.0.0/16/20
N =
20.การแบ่งซับเน็ต IPv4ยาก
ออกเท็ตที่สาม 6 … 10012806403201608141201ร่วมกันเปลี่ยนแปลง

เราเตอร์มีเส้นทางไปยังเครือข่ายเหล่านี้: 10.232.6.0/24, 10.232.7.0/24, 10.232.8.0/24, 10.232.9.0/24, 10.232.10.0/24 ความยาวพรีฟิกซ์ยาวที่สุด p ของเส้นทางสรุปเส้นเดียวที่ครอบคลุมทั้งหมดคือเท่าใด

10.232.6.0/24 … 10.232.10.0/24
p =

3สารละลาย

1.ระบบเลข

คำตอบ: N = −93

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

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

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

−128 + 32 + 2 + 1 = −93

คำตอบ

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

คำตอบ: N = −512

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

ค่าที่ติดลบมากที่สุด

−29 = −512

คำตอบ

N = −512
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 เมื่อทั้งสองข้างเท่ากัน

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

a = 1, b = 1, c = 1: b ∨ a = 1, b → c = 1, a ∧ (b → c) = 1, (b ∨ a) ↔ (a ∧ (b → c)) = 1
a = 1, b = 1, c = 0: b ∨ a = 1, b → c = 0, a ∧ (b → c) = 0, (b ∨ a) ↔ (a ∧ (b → c)) = 0
a = 1, b = 0, c = 1: b ∨ a = 1, b → c = 1, a ∧ (b → c) = 1, (b ∨ a) ↔ (a ∧ (b → c)) = 1
a = 1, b = 0, c = 0: b ∨ a = 1, b → c = 1, a ∧ (b → c) = 1, (b ∨ a) ↔ (a ∧ (b → c)) = 1
a = 0, b = 1, c = 1: b ∨ a = 1, b → c = 1, a ∧ (b → c) = 0, (b ∨ a) ↔ (a ∧ (b → c)) = 0
a = 0, b = 1, c = 0: b ∨ a = 1, b → c = 0, a ∧ (b → c) = 0, (b ∨ a) ↔ (a ∧ (b → c)) = 0
a = 0, b = 0, c = 1: b ∨ a = 0, b → c = 1, a ∧ (b → c) = 0, (b ∨ a) ↔ (a ∧ (b → c)) = 1
a = 0, b = 0, c = 0: b ∨ a = 0, b → c = 1, a ∧ (b → c) = 0, (b ∨ a) ↔ (a ∧ (b → c)) = 1

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

(b ∨ a) ↔ (a ∧ (b → c)): 1, 0, 1, 1, 0, 0, 1, 1
N = 5

คำตอบ

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

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

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

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

¬∃x F(x) ≡ ∀x ¬F(x)

คำตอบ

∀x ¬F(x)

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

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

คำตอบ: N = 4

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

ABCD000111100001111010111312140517061120130150140809011010

จัดกลุ่ม 0

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

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

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

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

คำตอบ

N = 4

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

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

คำตอบ: fmax = 22.22 MHz

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

เวลานิ่งในกรณีเลวร้ายที่สุด

T = 3·15 ns = 45 ns

ความถี่สูงสุด

fmax = 1/45 ns = 22.22 MHz

คำตอบ

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

คำตอบ: x = 53

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

ความสอดคล้องข้อแรก

x = 3 + 5k

ความสอดคล้องข้อที่สอง

3 + 5k ≡ 5 (mod 12) → 5k ≡ 2 (mod 12)
k ≡ 5·2 ≡ 10 (mod 12)

ผลลัพธ์

x = 3 + 5·10 = 53
x = 53
ตรวจสอบ: 53 mod 5 = 3, 53 mod 12 = 5

คำตอบ

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

คำตอบ: 2761586 mod 41 = 32

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

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

61586 mod 40 = 26
2761586 ≡ 2726 (mod 41)

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

2726 mod 41 = 32

คำตอบ

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

คำตอบ: C · Insertion sort มีภาระเพิ่มน้อยและเร็วกับอินพุตที่เล็กหรือเกือบเรียงแล้ว

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

เมื่อ n น้อย ลูปง่าย ๆ ของ insertion sort ชนะภาระการเรียกซ้ำของ quicksort หรือ merge sort แม้จะเป็น O(n²)

คำตอบ

C · Insertion sort มีภาระเพิ่มน้อยและเร็วกับอินพุตที่เล็กหรือเกือบเรียงแล้ว
10.อัลกอริทึมและความซับซ้อน

คำตอบ: C · n = o(n²) แต่ n ไม่ใช่ o(n)

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

f = o(g) หมายความว่า f(n) / g(n) เข้าใกล้ 0 โดย n / n² เข้าใกล้ 0 แต่ n / n = 1 ไม่เข้าใกล้ 0

คำตอบ

C · n = o(n²) แต่ n ไม่ใช่ o(n)
11.โครงสร้างข้อมูล

คำตอบ: A · สแตก

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

push วงเล็บเปิดแต่ละตัวและ pop เมื่อเจอวงเล็บปิด ต้องตรงกับวงเล็บที่ pop และสแตกต้องว่างเมื่อจบ

คำตอบ

A · สแตก
12.โครงสร้างข้อมูล

คำตอบ: A · ตอบคำถามช่วง (เช่น ผลรวมช่วง) และอัปเดตใน O(log n)

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

Segment tree เก็บค่ารวมของช่วง รองรับคำถามช่วงและการอัปเดตจุดในเวลา O(log n)

คำตอบ

A · ตอบคำถามช่วง (เช่น ผลรวมช่วง) และอัปเดตใน O(log n)
13.ทฤษฎีกราฟ

คำตอบ: k = 3

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

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

6 − 1 = 5

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

k = 8 − 5 = 3

คำตอบ

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

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

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

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

1. CE (1)
2. BE (2)
3. AC (5)
4. DE (12)

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

DE

คำตอบ

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

คำตอบ: D · โค้ดที่ทำงานอัตโนมัติเมื่อเกิดเหตุการณ์ที่กำหนด เช่น INSERT, UPDATE หรือ DELETE บนตาราง

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

ทริกเกอร์ทำงานอัตโนมัติก่อนหรือหลังข้อมูลเปลี่ยน เช่น เพื่อเขียนบันทึกการตรวจสอบหรือบังคับกฎที่ซับซ้อน

คำตอบ

D · โค้ดที่ทำงานอัตโนมัติเมื่อเกิดเหตุการณ์ที่กำหนด เช่น INSERT, UPDATE หรือ DELETE บนตาราง
16.ฐานข้อมูลและ SQL

คำตอบ: B · เมื่อผลของมันเทียบเท่ากับการทำงานแบบอนุกรมบางรูปแบบของทรานแซกชันเดียวกัน

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

Serializability เป็นเกณฑ์ความถูกต้องหลักของภาวะพร้อมกัน: ผลที่ทำสลับกันต้องเท่ากับผลของลำดับการทำทีละอันบางลำดับ

คำตอบ

B · เมื่อผลของมันเทียบเท่ากับการทำงานแบบอนุกรมบางรูปแบบของทรานแซกชันเดียวกัน
17.เครือข่ายคอมพิวเตอร์

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

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

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

คำตอบ

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

คำตอบ: A · path MTU discovery ล้มเหลวเพราะข้อความ "fragmentation needed" ถูกบล็อก

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

PMTUD อาศัยข้อความ ICMP เพื่อเรียนรู้ MTU ที่เล็กกว่า หากถูกทิ้ง แพ็กเก็ตขนาดใหญ่จะหายไปอย่างเงียบ ๆ ทำให้เกิดการเชื่อมต่อแบบ "หลุมดำ" (black hole)

คำตอบ

A · path MTU discovery ล้มเหลวเพราะข้อความ "fragmentation needed" ถูกบล็อก
19.การแบ่งซับเน็ต IPv4

คำตอบ: N = 16

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

บิตที่ยืมมา

20 − 16 = 4

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

N = 24 = 16

คำตอบ

N = 16

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

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

คำตอบ: p = 20

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

เทียบบิต

6 = 00000110
10 = 00001010
บิตนำหน้าที่ตรงกัน: 4

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

p = 16 + 4 = 20

คำตอบ

p = /20

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

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