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

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

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

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

ตั้งบิตให้เป็นผลลัพธ์ 8 บิตของ 0110 0100 << 3 ค่าของผลลัพธ์ R เป็นเท่าใดในเลขฐานสิบ

0110 0100<< 3
R =
3.ตรรกศาสตร์ประพจน์และการพิสูจน์ปานกลาง
abca ∧ cb ∨ (a ∧ c)(¬b ↔ (c ∨ a)) ∧ (b ∨ (a ∧ c))111?110?101?100?011?010?001?000?

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

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

การอ้างเหตุผลที่มีสมมติฐาน c → (b ∨ a); c และบทสรุป b ไม่สมเหตุสมผล ให้คลิกแถวของตารางค่าความจริงที่เป็นตัวอย่างค้าน

c → (b ∨ a)c∴ b
  1. 1a = 1, b = 1, c = 1
  2. 2a = 1, b = 1, c = 0
  3. 3a = 1, b = 0, c = 1
  4. 4a = 1, b = 0, c = 0
  5. 5a = 0, b = 1, c = 1
  6. 6a = 0, b = 1, c = 0
  7. 7a = 0, b = 0, c = 1
  8. 8a = 0, b = 0, c = 0
5.ตรรกะดิจิทัล: เกต แผนที่คาร์โนห์ และฟลิปฟล็อปปานกลาง
ABC00011110010011031214050716

ใช้แผนที่คาร์โนห์หารูปผลบวกของผลคูณ (SOP) ที่น้อยที่สุดของ F(A, B, C) = Σm(1, 2, 4, 6) มีลิเทอรัลรวมกี่ตัว L (ตัวแปรที่มีไพรม์นับเป็นหนึ่งลิเทอรัล)

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

ฟลิปฟล็อป T ที่ทริกเกอร์ขอบขาขึ้นเริ่มด้วย Q = 0 และได้รับอินพุตที่แสดง ให้คลิกขอบสัญญาณนาฬิกาแรกที่ Q เปลี่ยนจาก 1 กลับเป็น 0

Q₀ = 0T
  1. 1ขอบสัญญาณนาฬิกา 1
  2. 2ขอบสัญญาณนาฬิกา 2
  3. 3ขอบสัญญาณนาฬิกา 3
  4. 4ขอบสัญญาณนาฬิกา 4
  5. 5ขอบสัญญาณนาฬิกา 5
  6. 6ขอบสัญญาณนาฬิกา 6
  7. 7ขอบสัญญาณนาฬิกา 7
  8. 8ขอบสัญญาณนาฬิกา 8
7.ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ปานกลาง

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

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

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

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

อัลกอริทึมการเรียงลำดับใดเป็นแบบเสถียร (stable)

  1. AQuicksort (แบบทำในที่เดิมทั่วไป)
  2. BHeap sort
  3. CMerge sort
  4. DSelection sort (แบบทั่วไป)
10.อัลกอริทึมและความซับซ้อนยาก

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

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

extract-min ใน min-heap ทวิภาคทำงานอย่างไร

  1. Aย้ายสมาชิกสุดท้ายไปที่รากและเลื่อนลง (sift down)
  2. Bค้นหาใบทั้งหมดเพื่อหาค่าต่ำสุดใหม่
  3. Cลบสมาชิกสุดท้ายของอาร์เรย์
  4. Dลบรากและเลื่อนสมาชิกทั้งหมดไปทางซ้ายหนึ่งตำแหน่ง
12.โครงสร้างข้อมูลยาก

Fenwick tree (binary indexed tree) บนอาร์เรย์ที่มีตัวเลข n ตัว รองรับการดำเนินการใดใน O(log n)

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

ต้นไม้มี 2 จุดยอดดีกรี 3, 3 จุดยอดดีกรี 4, 3 จุดยอดดีกรี 5, 4 จุดยอดดีกรี 2 และจุดยอดอื่นทั้งหมดเป็นใบ (ดีกรี 1) มีกี่ใบ L

2 × deg 33 × deg 43 × deg 54 × deg 2
L =
14.ทฤษฎีกราฟยาก
2013410919171416ABCDEFG

ขั้นตอนวิธีของครัสคัลสร้างต้นไม้ทอดข้ามค่าน้อยที่สุด ให้คลิกเส้นเชื่อมที่เพิ่มเป็นเส้นหมายเลข 5 เส้นที่ถูกข้ามไม่นับ

k = 5
  1. 1เส้นเชื่อม AB
  2. 2เส้นเชื่อม AC
  3. 3เส้นเชื่อม BC
  4. 4เส้นเชื่อม BD
  5. 5เส้นเชื่อม DF
  6. 6เส้นเชื่อม EF
  7. 7เส้นเชื่อม GB
  8. 8เส้นเชื่อม GC
  9. 9เส้นเชื่อม GE
15.ฐานข้อมูลและ SQLปานกลาง

นักเรียนลงเรียนได้หลายวิชา และวิชามีนักเรียนหลายคน จะสร้างแบบจำลองนี้ในตารางอย่างไร?

  1. Aโดยรวม students และ courses เป็นตารางเดียว
  2. Bด้วยรายการ id ของวิชาที่เก็บในคอลัมน์เดียว
  3. Cด้วยคอลัมน์คีย์นอก course_id ในตาราง students ที่ชี้ไปยัง courses
  4. Dด้วยตารางเชื่อม (junction table) ที่เก็บคีย์นอกไปยังทั้ง students และ courses
16.ฐานข้อมูลและ SQLยาก

SELECT name, dept, AVG(salary) OVER (PARTITION BY dept) FROM emp คืนอะไร?

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

ช่วงหมายเลขพอร์ต TCP/UDP ใดสงวนไว้เป็นพอร์ต "ที่รู้จักกันดี" (well-known)?

  1. A0–1023
  2. B1024–49151
  3. C0–65535
  4. D49152–65535
18.เครือข่ายคอมพิวเตอร์ยาก

ผู้ใช้ ping 8.8.8.8 ได้แต่เปิดเว็บไซต์ใดด้วยชื่อไม่ได้ ปัญหาน่าจะอยู่ที่ใด?

  1. Aสายเคเบิลทางกายภาพ
  2. Bไดรเวอร์การ์ดเครือข่าย
  3. Cเกตเวย์เริ่มต้น
  4. Dการแปลงชื่อ (DNS)
19.การแบ่งซับเน็ต IPv4ปานกลาง
/24 → /2711111111111111111111111111100000บิตเครือข่ายบิตโฮสต์

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

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

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

10.20.227.49/27
x =

3สารละลาย

1.ระบบเลข

คำตอบ: N = −62

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

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

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

−128 + 64 + 2 = −62

คำตอบ

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

คำตอบ: R = 32

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

ทีละบิต

การเลื่อนซ้าย 3 ตำแหน่งย้ายทุกบิตไปทางซ้าย 3 ตำแหน่ง บิตที่หลุดออกปลายซ้ายหายไปและศูนย์เข้ามาทางขวา

0110 0100 << 3
= 0010 0000

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

0010 0000₂ = 32

คำตอบ

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

คำตอบ: N = 2

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

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

(¬b ↔ (c ∨ a)) ∧ (b ∨ (a ∧ c)): 0, 0, 1, 0, 0, 1, 0, 0
N = 2

คำตอบ

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

คำตอบ: a = 1, b = 0, c = 1

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

สมมติฐานและบทสรุปทีละแถว

a = 1, b = 1, c = 1: 1 1 | 1
a = 1, b = 1, c = 0: 1 0 | 1
a = 1, b = 0, c = 1: 1 1 | 0
a = 1, b = 0, c = 0: 1 0 | 0
a = 0, b = 1, c = 1: 1 1 | 1
a = 0, b = 1, c = 0: 1 0 | 1
a = 0, b = 0, c = 1: 0 1 | 0
a = 0, b = 0, c = 0: 1 0 | 0

ตัวอย่างค้าน

a = 1, b = 0, c = 1

คำตอบ

a = 1, b = 0, c = 1

การอ้างเหตุผลรูปแบบนี้ดูเหมือนกฎที่สมเหตุสมผล แต่แถวเดียวก็เพียงพอที่จะแสดงว่าไม่ใช่

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

คำตอบ: L = 7

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

ABC00011110010011031214050716

จัดกลุ่ม 1

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

BC′
AC′
A′B′C

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

F = BC′ + AC′ + A′B′C
L = 7

คำตอบ

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

คำตอบ: ขอบสัญญาณนาฬิกา 4

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

Q หลังทุกขอบ

ฟลิปฟล็อป T สลับค่าทุกขอบขาขึ้นเมื่อ T = 1 และคงค่าเมื่อ T = 0

1: T = 1 → Q = 1
2: T = 0 → Q = 1
3: T = 0 → Q = 1
4: T = 1 → Q = 0
5: T = 1 → Q = 1
6: T = 1 → Q = 0
7: T = 0 → Q = 0
8: T = 0 → Q = 0

การเปลี่ยนจาก 1 เป็น 0 ครั้งแรก

ขอบสัญญาณนาฬิกา 4

คำตอบ

ขอบสัญญาณนาฬิกา 4
7.ทฤษฎีจำนวนและเลขคณิตมอดูลาร์

คำตอบ: 10−1 mod 63 = 19

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

r = 63, t = 0
r = 10, q = 6, t = 1
r = 3, q = 3, t = −6
r = 1, q = 3, t = 19

อินเวอร์ส

1 ≡ 19·10 (mod 63)
x = 19
ตรวจสอบ: 10·19 = 190 = 3·63 + 1

คำตอบ

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

คำตอบ: c = 868

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

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

23 = 16 + 4 + 2 + 1
2471 ≡ 247 (mod 989)
2472 ≡ 680 (mod 989)
2474 ≡ 537 (mod 989)
2478 ≡ 570 (mod 989)
24716 ≡ 508 (mod 989)
24723 ≡ 247·680·537·508 ≡ 868 (mod 989)

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

c = 868

คำตอบ

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

คำตอบ: C · Merge sort

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

Merge sort เสถียรเมื่อการผสานหยิบจากครึ่งซ้ายก่อนในกรณีที่เท่ากัน ส่วน quicksort แบบทำในที่เดิม heap sort และ selection sort มักไม่เสถียร

คำตอบ

C · Merge sort
10.อัลกอริทึมและความซับซ้อน

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

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

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

คำตอบ

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

คำตอบ: A · ย้ายสมาชิกสุดท้ายไปที่รากและเลื่อนลง (sift down)

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

สมาชิกสุดท้ายเติมช่องว่างที่ราก และสลับกับลูกที่เล็กกว่าจนคุณสมบัติฮีปเป็นจริง ใช้ O(log n)

คำตอบ

A · ย้ายสมาชิกสุดท้ายไปที่รากและเลื่อนลง (sift down)
12.โครงสร้างข้อมูล

คำตอบ: B · คำถามผลรวมคำนำหน้าและการอัปเดตสมาชิกเดียว

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

Fenwick tree เก็บผลรวมบางส่วนของช่วงที่กำหนดโดยบิตต่ำของแต่ละดัชนี ทั้งผลรวมคำนำหน้าและการอัปเดตจุดจึงใช้ O(log n)

คำตอบ

B · คำถามผลรวมคำนำหน้าและการอัปเดตสมาชิกเดียว
13.ทฤษฎีกราฟ

คำตอบ: L = 19

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

เล็มมาการจับมือสำหรับต้นไม้

L + 41 = 2(L + 12) − 2
L = 19

คำตอบ

L = 19

ทางลัด: L = 2 + Σ (d − 2) ของจุดยอดที่มีดีกรี d ≥ 3

14.ทฤษฎีกราฟ

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

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

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

1. BC (4)
2. DF (9)
3. BD (10)
4. AC (13)
5. GC (14)
6. GE (16)

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

GC

คำตอบ

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

คำตอบ: D · ด้วยตารางเชื่อม (junction table) ที่เก็บคีย์นอกไปยังทั้ง students และ courses

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

ความสัมพันธ์แบบหลายต่อหลายต้องใช้ตารางสัมพันธ์ (junction) เช่น enrolment(student_id, course_id) ซึ่งมักมีคีย์หลักประกอบ

คำตอบ

D · ด้วยตารางเชื่อม (junction table) ที่เก็บคีย์นอกไปยังทั้ง students และ courses
16.ฐานข้อมูลและ SQL

คำตอบ: A · ทุกแถวพนักงานพร้อมเงินเดือนเฉลี่ยของแผนกตน

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

ต่างจาก GROUP BY ฟังก์ชันหน้าต่างคงทุกแถวนำเข้าและเพิ่มค่าที่คำนวณบนพาร์ทิชันของมัน ในที่นี้คือแผนก

คำตอบ

A · ทุกแถวพนักงานพร้อมเงินเดือนเฉลี่ยของแผนกตน
17.เครือข่ายคอมพิวเตอร์

คำตอบ: A · 0–1023

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

พอร์ต 0–1023 เป็นพอร์ตที่รู้จักกันดีสำหรับบริการมาตรฐาน 1024–49151 เป็นพอร์ตที่ลงทะเบียน และ 49152–65535 เป็นพอร์ตไดนามิกหรือส่วนตัว

คำตอบ

A · 0–1023
18.เครือข่ายคอมพิวเตอร์

คำตอบ: D · การแปลงชื่อ (DNS)

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

การ ping ไปยัง IP ภายนอกสำเร็จพิสูจน์ว่าสายเคเบิล การกำหนดที่อยู่ และการกำหนดเส้นทางใช้ได้ ชื่อที่ล้มเหลวชี้ไปที่ปัญหาเซิร์ฟเวอร์ DNS หรือการตั้งค่ารีโซลเวอร์

คำตอบ

D · การแปลงชื่อ (DNS)
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 = 62

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

ขนาดบล็อก

25 = 32

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

เครือข่าย: ⌊49/32⌋·32 = 32
บรอดคาสต์: 32 + 32 − 1 = 63
โฮสต์ที่ใช้ได้: 33 … 62

คำตอบ

x = 62

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