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

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

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

N = −1178 bit
U =
2.ระบบเลขยาก
คลิกบิตเพื่อตั้งค่า012806403201608040201

ตั้งบิตให้เป็นผลลัพธ์ 8 บิตของ 1000 1111 OR 1000 1101 ค่าของผลลัพธ์ R เป็นเท่าใดในเลขฐานสิบ

1000 1111OR1000 1101
R =
3.ตรรกศาสตร์ประพจน์และการพิสูจน์ปานกลาง
(r → p) ∧ (p → r)(r → p) ∨ (p → r)r ∧ p(r → p) ∧ (¬p → ¬r)

สูตรใดสมมูลเชิงตรรกะกับ r ↔ p ให้คลิกสูตรนั้น

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

กำหนดสมมติฐาน r ∨ p; ¬r ∨ q บทสรุปใดตามมาจากสมมติฐานเหล่านี้ ให้คลิกบทสรุปนั้น

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

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

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

จงหารูป SOP ที่น้อยที่สุดของ F(A, B, C, D) = Σm(5, 6, 7, 8, 13) + d(3, 12, 15) โดย d แทนเงื่อนไขไม่สนใจ มีกี่ลิเทอรัล L

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

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

x ≡ 4 (mod 10)x ≡ 7 (mod 13)
x =
8.ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ยาก
mc = me​ mod ncm = cd​ mod nm(n, e) = (155, 13)d = ?

กุญแจ RSA ใช้จำนวนเฉพาะ p = 5 และ q = 31 และเลขชี้กำลังสาธารณะ e = 13 จงหาเลขชี้กำลังส่วนตัว d (0 < d < φ(n))

p = 5q = 31e = 13
d =
9.อัลกอริทึมและความซับซ้อนปานกลาง

การค้นหาในแนวกว้าง (BFS) บนกราฟที่ไม่มีน้ำหนักให้ผลเป็น

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

เพื่อแสดงว่าปัญหาใหม่ X เป็น NP-hard คุณต้องทำอะไร

  1. Aลดรูปปัญหา NP-hard ที่ทราบมาเป็น X ในเวลาพหุนาม
  2. Bแสดงว่า X ไม่มีอัลกอริทึมพหุนามสำหรับอินพุตเล็ก
  3. Cลดรูป X ไปเป็นปัญหา NP-hard ที่ทราบในเวลาพหุนาม
  4. Dแสดงว่า X ตรวจสอบได้ในเวลาพหุนาม
11.โครงสร้างข้อมูลปานกลาง

แอปพลิเคชันต้องการค้นหาเร็ว และต้องแสดงรายการคีย์เรียงลำดับและตอบคำถามช่วง โครงสร้างใดเหมาะที่สุด

  1. Aสแตก
  2. Bตารางแฮช
  3. Cbinary search tree แบบสมดุล
  4. Dลิงก์ลิสต์ที่ไม่เรียงลำดับ
12.โครงสร้างข้อมูลยาก

สำหรับแต่ละสมาชิกของอาร์เรย์ คุณต้องการสมาชิกที่ใหญ่กว่าถัดไปทางขวา ในเวลารวม O(n) โครงสร้างใดช่วยได้

  1. Abinary search tree ที่สร้างใหม่สำหรับแต่ละสมาชิก
  2. Bคิวที่เก็บทุกคู่ของสมาชิก
  3. Cตารางแฮชของสมาชิกทั้งหมด
  4. Dสแตกที่เก็บสมาชิกที่รอคำตอบ
13.ทฤษฎีกราฟปานกลาง
ABCDEFGวงจรออยเลอร์ทางเดินออยเลอร์ ไม่มีวงจรไม่ใช่ทั้งสองอย่าง

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

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

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

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

dirty read คืออะไร?

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

ฟีเจอร์ SQL ใดเหมาะที่สุดสำหรับหาพนักงานทุกคนใต้ผู้จัดการในแผนภูมิองค์กรที่ไม่ทราบความลึก?

  1. Aข้อจำกัด UNIQUE บน manager_id
  2. Bself-join ของตาราง employees บน manager_id เพียงครั้งเดียว
  3. CGROUP BY บน manager_id
  4. DCTE แบบเรียกซ้ำ (WITH RECURSIVE)
17.เครือข่ายคอมพิวเตอร์ปานกลาง

ฟิลด์ใดในส่วนหัว IPv4 ป้องกันไม่ให้แพ็กเก็ตวนไปมาตลอดไปในลูปการกำหนดเส้นทาง?

  1. ATime to live (TTL)
  2. BIdentification
  3. CType of service
  4. DHeader checksum
18.เครือข่ายคอมพิวเตอร์ยาก

พีซีเครื่องหนึ่งเข้าถึงเครื่องพิมพ์ในซับเน็ตของตนได้แต่เข้าถึงสิ่งอื่นนอกซับเน็ตไม่ได้ ที่อยู่ IP และมาสก์ถูกต้อง ความบกพร่องใดมีแนวโน้มมากที่สุด?

  1. Aหน้าต่าง TCP เล็กเกินไป
  2. Bที่อยู่ MAC ซ้ำกันบนอินเทอร์เน็ต
  3. Cเกตเวย์เริ่มต้นหายไปหรือไม่ถูกต้อง
  4. Dการตั้งค่าเซิร์ฟเวอร์ DNS ผิดพลาด
19.การแบ่งซับเน็ต IPv4ปานกลาง
/24 → /2911111111111111111111111111111000บิตเครือข่ายบิตโฮสต์

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

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

โฮสต์มีที่อยู่ 10.20.182.233/29 ตัวเลขสุดท้าย (ออคเต็ตที่สี่) x ของที่อยู่บรอดคาสต์ของซับเน็ตคือเท่าใด

10.20.182.233/29
x =

3สารละลาย

1.ระบบเลข

คำตอบ: U = 139

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

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

117 = 0111 0101
ที่กลับบิตแล้ว: 1000 1010
+1 → 1000 1011

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

1000 1011₂ = 256 − 117 = 139

คำตอบ

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

คำตอบ: R = 143

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

ทีละบิต

OR ให้ 1 เมื่ออย่างน้อยหนึ่งบิตเป็น 1

1000 1111
OR 1000 1101
= 1000 1111

ค่าของผลลัพธ์

1000 1111₂ = 143

คำตอบ

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

คำตอบ: (r → p) ∧ (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 ↔ b หมายความว่านัยเป็นจริงทั้งสองทิศทาง: (a → b) ∧ (b → a)
r ↔ p ≡ (r → p) ∧ (p → r)

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

p = 1, r = 1: 1 | 1 1 1 1
p = 1, r = 0: 0 | 0 1 0 1
p = 0, r = 1: 0 | 0 1 0 0
p = 0, r = 0: 1 | 1 1 0 1

คำตอบ

(r → p) ∧ (p → r)

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

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

คำตอบ: p ∨ q

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

แถวที่สมมติฐานทั้งหมดเป็นจริง

p = 1, q = 1, r = 1: p ∨ q = 1, ¬p = 0, p ∧ q = 1, r ∨ q = 1
p = 1, q = 1, r = 0: p ∨ q = 1, ¬p = 0, p ∧ q = 1, r ∨ q = 1
p = 1, q = 0, r = 0: p ∨ q = 1, ¬p = 0, p ∧ q = 0, r ∨ q = 0
p = 0, q = 1, r = 1: p ∨ q = 1, ¬p = 1, p ∧ q = 0, r ∨ q = 1

สรุป

p ∨ q (ความละเอียด)

คำตอบ

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

คำตอบ: N = 2

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

ABCD000111100001111000111302141517161120130151140809011010

จัดกลุ่ม 0

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

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

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

F = (B + D)(A′ + D′)
N = 2

คำตอบ

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

คำตอบ: L = 8

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

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

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

BD, A′CD, AC′D′, A′BC, ABC′
ABCD00011110000111100001X30204151716X12113X150141809011010

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

F = BD + AC′D′ + A′BC
L = 8

คำตอบ

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

คำตอบ: x = 124

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

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

4 + 10k ≡ 7 (mod 13) → 10k ≡ 3 (mod 13)
k ≡ 4·3 ≡ 12 (mod 13)

ผลลัพธ์

x = 4 + 10·12 = 124
x = 124
ตรวจสอบ: 124 mod 10 = 4, 124 mod 13 = 7

คำตอบ

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

คำตอบ: d = 37

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

มอดูลัสและโทเทียนต์

n = 5·31 = 155
φ(n) = 4·30 = 120

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

r = 120, t = 0
r = 13, q = 9, t = 1
r = 3, q = 4, t = −9
r = 1, q = 3, t = 37

เลขชี้กำลังส่วนตัว

d = 37
ตรวจสอบ: 13·37 = 481 = 4·120 + 1

คำตอบ

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

คำตอบ: C · เส้นทางสั้นที่สุดในแง่จำนวนเส้นเชื่อมจากโหนดเริ่มต้น

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

BFS เยี่ยมโหนดตามลำดับระยะทาง (จำนวนเส้นเชื่อม) จากต้นทาง จึงหาเส้นทางสั้นที่สุดแบบไม่มีน้ำหนักได้ใน O(V + E)

คำตอบ

C · เส้นทางสั้นที่สุดในแง่จำนวนเส้นเชื่อมจากโหนดเริ่มต้น
10.อัลกอริทึมและความซับซ้อน

คำตอบ: A · ลดรูปปัญหา NP-hard ที่ทราบมาเป็น X ในเวลาพหุนาม

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

ถ้าปัญหายากที่ทราบแปลงเป็น X ได้อย่างมีประสิทธิภาพ อัลกอริทึมเร็วสำหรับ X ก็จะแก้ปัญหาที่ทราบได้ด้วย

คำตอบ

A · ลดรูปปัญหา NP-hard ที่ทราบมาเป็น X ในเวลาพหุนาม
11.โครงสร้างข้อมูล

คำตอบ: C · binary search tree แบบสมดุล

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

BST สมดุลให้การค้นหา O(log n) และรักษาลำดับคีย์ การท่อง in-order และคำถามช่วงจึงทำได้ง่าย ตารางแฮชกระจายคีย์

คำตอบ

C · binary search tree แบบสมดุล
12.โครงสร้างข้อมูล

คำตอบ: D · สแตกที่เก็บสมาชิกที่รอคำตอบ

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

สแกนจากซ้ายไปขวา pop ทุกสมาชิกบนสแตกที่เล็กกว่าตัวปัจจุบัน (ตัวปัจจุบันคือคำตอบของพวกมัน) แล้ว push ตัวปัจจุบัน แต่ละสมาชิกเคลื่อนไม่เกินสองครั้ง

คำตอบ

D · สแตกที่เก็บสมาชิกที่รอคำตอบ
13.ทฤษฎีกราฟ

คำตอบ: ทางเดินออยเลอร์ ไม่มีวงจร

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

ดีกรี

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

จุดยอดคี่

C, G → 2
ทางเดินออยเลอร์ ไม่มีวงจร

คำตอบ

ทางเดินออยเลอร์ ไม่มีวงจร

ทางเดินออยเลอร์เริ่มที่จุดยอดคี่จุดหนึ่งและจบที่อีกจุดหนึ่ง

14.ทฤษฎีกราฟ

คำตอบ: D

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

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

1. A (0): B: 3
2. B (3): C: 13, D: 17, E: 5
3. E (5): D: 16, F: 9
4. F (9): D: 11
5. D (11)
6. C (13)

รอบ 5

D

คำตอบ

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

คำตอบ: C · การอ่านข้อมูลที่ทรานแซกชันอื่นเขียนไว้แต่ยังไม่ commit

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

dirty read เห็นการเปลี่ยนแปลงที่ยังไม่ commit ซึ่งอาจถูกยกเลิก เกิดได้เฉพาะที่ระดับ read uncommitted

คำตอบ

C · การอ่านข้อมูลที่ทรานแซกชันอื่นเขียนไว้แต่ยังไม่ commit
16.ฐานข้อมูลและ SQL

คำตอบ: D · CTE แบบเรียกซ้ำ (WITH RECURSIVE)

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

CTE แบบเรียกซ้ำเริ่มจากคิวรีจุดตั้งต้นและเชื่อมผลลัพธ์ก่อนหน้ากับตารางซ้ำ ๆ จึงรองรับลำดับชั้นได้ทุกความลึก

คำตอบ

D · CTE แบบเรียกซ้ำ (WITH RECURSIVE)
17.เครือข่ายคอมพิวเตอร์

คำตอบ: A · Time to live (TTL)

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

เราเตอร์ทุกตัวลดค่า TTL ลง เมื่อถึงศูนย์แพ็กเก็ตถูกทิ้งและมักส่งข้อความ ICMP Time Exceeded IPv6 เรียกว่า hop limit

คำตอบ

A · Time to live (TTL)
18.เครือข่ายคอมพิวเตอร์

คำตอบ: C · เกตเวย์เริ่มต้นหายไปหรือไม่ถูกต้อง

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

โฮสต์ส่งแพ็กเก็ตนอกซับเน็ตไปยังเกตเวย์เริ่มต้น หากผิดหรือไม่มี ทราฟฟิกท้องถิ่นยังใช้ได้แต่เข้าถึงสิ่งใดภายนอกไม่ได้ แม้ใช้ที่อยู่ IP

คำตอบ

C · เกตเวย์เริ่มต้นหายไปหรือไม่ถูกต้อง
19.การแบ่งซับเน็ต IPv4

คำตอบ: x = 55

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

ขนาดบล็อก

23 = 8

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

เครือข่าย: (7 − 1)·8 = 48
บรอดคาสต์: 48 + 8 − 1 = 55

คำตอบ

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

คำตอบ: x = 239

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

ขนาดบล็อก

23 = 8

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

เครือข่าย: ⌊233/8⌋·8 = 232
บรอดคาสต์: 232 + 8 − 1 = 239
โฮสต์ที่ใช้ได้: 233 … 238

คำตอบ

x = 239

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