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

สรุปสูตร ขั้นตอนวิธีทำที่สำคัญของทุกหัวข้อ และโจทย์ฝึก 20 ข้อ พร้อมเฉลยละเอียดไว้ท้ายเล่ม

โจทย์ใหม่กลับไปที่รายวิชา

ในหน้าต่างพิมพ์ ให้เลือก “บันทึกเป็น PDF” เพื่อเก็บสำเนาไว้ในอุปกรณ์ของคุณ

1สูตรและวิธีทำ

ระบบเลข

ค่าประจำตำแหน่ง: ฐานสอง 2^k, ฐานแปด 8^k, ฐานสิบหก 16^k
เป็นเลขฐานสิบ: Σ d_k·b^k
จากเลขฐานสิบ: หารด้วยฐาน อ่านเศษจากล่างขึ้นบน
ฐานสิบหก ↔ ฐานสอง: เลขฐานสิบหกหนึ่งหลัก = 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

วิธีการ

นับจำนวนตัวแปรที่ต่างกัน ตารางค่าความจริงมี 2ⁿ แถว โดยเริ่มจากแถวที่ทุกตัวเป็น 1
ให้ทุกประพจน์ย่อยมีคอลัมน์ของตัวเอง และเติมคอลัมน์จากด้านในออกมาด้านนอก
ใช้กฎของตัวเชื่อมแต่ละตัว: → เป็น 0 เฉพาะเมื่อ 1 → 0 และ ↔ เป็น 1 เมื่อทั้งสองข้างมีค่าเท่ากัน
สำหรับความสมมูล ให้เปรียบเทียบคอลัมน์สุดท้ายทีละแถว สำหรับการอ้างเหตุผล ให้ดูเฉพาะแถวที่ทุกสมมติฐานเป็น 1
การหานิเสธของข้อความที่มีตัวบ่งปริมาณ ให้ย้าย ¬ เข้าไปด้านใน สลับ ∀ กับ ∃ และใส่นิเสธให้สูตรด้านใน

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

เกตพื้นฐาน: 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′I₀ + A′BI₁ + AB′I₂ + ABI₃
ฟลิปฟล็อป: D: Q⁺ = D, T: Q⁺ = T ⊕ Q, JK: Q⁺ = JQ′ + K′Q
ตัวนับ: n บิต: 2ⁿ สถานะ; มอด N: n ที่น้อยที่สุดที่ 2ⁿ ≥ N; f_out = f_clk/N
ตัวนับริปเปิล: f_max = 1/(n·t_pd)
ตัวนับริงและตัวนับจอห์นสัน: n และ 2n สถานะ

วิธีการ

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

วิธีการ

ลดทุกจำนวนมอดูโล n ก่อน เศษจะอยู่ระหว่าง 0 ถึง n − 1
สำหรับ ห.ร.ม. ให้หารซ้ำด้วยขั้นตอนวิธีของยูคลิด เศษที่ไม่เป็นศูนย์ตัวสุดท้ายคือ ห.ร.ม.
สำหรับตัวผกผัน ให้ทำขั้นตอนวิธีแบบขยาย และเก็บสัมประสิทธิ์ของ a ถ้าเป็นลบให้บวก n
แก้ a·x ≡ b โดยคูณด้วย a⁻¹ รวมสองความสอดคล้องโดยเขียน x = r₁ + m₁k
สำหรับเลขยกกำลัง ให้เขียนเลขชี้กำลังเป็นเลขฐานสองแล้วยกกำลังสองซ้ำ ใน RSA จะได้ d = e⁻¹ mod φ(n) โดย φ(n) = (p − 1)(q − 1)

ทฤษฎีกราฟ

เล็มมาการจับมือ: Σ deg(v) = 2|E|
กราฟบริบูรณ์: |E(K_n)| = n(n − 1)/2, |E(K_m,n)| = m·n
กราฟปรกติ: |E| = n·k/2
ต้นไม้และป่า: |E| = n − 1, |E| = n − c
ใบของต้นไม้: L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
ออยเลอร์: วงจร: ดีกรีเป็นคู่ทุกจุดยอด; ทางเดิน: มีดีกรีคี่พอดี 2 จุดยอด
วงจรแฮมิลตันใน K_n: (n − 1)!/2
การปรับค่าของไดก์สตรา: d(v) = min(d(v), d(u) + w(u, v))
วอล์กความยาว L: (Mᴸ)_ij

วิธีการ

เขียนดีกรีของทุกจุดยอด ผลบวกของดีกรีเท่ากับสองเท่าของจำนวนเส้นเชื่อม
สำหรับโจทย์ออยเลอร์ ให้ตรวจว่ากราฟเชื่อมโยงกัน และนับจุดยอดที่มีดีกรีคี่
สำหรับต้นไม้ ให้ใช้ว่ามี n − 1 เส้นเชื่อม และเล็มมาการจับมือ
สำหรับไดก์สตรา ให้เก็บตารางระยะทางชั่วคราว และยืนยันจุดยอดที่ยังไม่ยืนยันซึ่งมีค่าน้อยที่สุดในแต่ละรอบ
สำหรับต้นไม้ทอดข้ามค่าน้อยที่สุด ให้เรียงเส้นเชื่อมตามน้ำหนักและข้ามทุกเส้นที่ทำให้เกิดวัฏจักร (ครัสคัล) หรือขยายต้นไม้ต้นเดียวจากจุดยอดเริ่มต้น (พริม)

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

โฮสต์ต่อซับเน็ต: 2^{(32 − prefix)} − 2 (/31: 2, /32: 1)
ขนาดบล็อก: 256 − (mask octet)
ที่อยู่เครือข่าย: IP AND มาสก์
ที่อยู่บรอดคาสต์: IP OR (NOT mask): บิตโฮสต์ทั้งหมดเป็น 1
ซับเน็ตจาก n บิตที่ยืม: 2ⁿ

2โจทย์ฝึก

1.ระบบเลขปานกลาง

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

N = −848 bit

U =

2.ระบบเลขยาก

จำนวนเต็มไม่มีเครื่องหมายที่มากที่สุด N ที่ใส่ได้ใน 12 บิตคือเท่าใด

12 bit

N =

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

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

¬((p ∨ r) ∧ ¬p) ↔ ¬(r ∧ q)

N =

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

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

¬(s → ¬(p ∨ ¬q)) → (p ∧ ¬r)

N =

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

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

F(A, B, C, D) = Σm(1, 2, 6, 9, 12, 15)

L =

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

ชิฟต์รีจิสเตอร์ 4 บิต Q₃Q₂Q₁Q₀ เก็บค่า 1100 ทุกขอบสัญญาณนาฬิกา บิตเลื่อนไปทางขวาหนึ่งตำแหน่ง (Q₃ → Q₂ → Q₁ → Q₀, Q₀ หายไป) และอินพุตอนุกรมเข้าสู่ Q₃ อินพุตอนุกรมเป็น 1, 1, 0, 1 ที่ขอบ 4 จงหาสถานะสุดท้าย Q = Q₃Q₂Q₁Q₀ เป็นเลขฐานสิบ

Q₃Q₂Q₁Q₀ = 11001, 1, 0, 1

Q =

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

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

a = 33n = 52

33⁻¹ mod 52 =

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

กุญแจ RSA ใช้ p = 17, q = 29 และ e = 19 จงถอดรหัสข้อความเข้ารหัส c = 373: หาข้อความ m

p = 17q = 29e = 19c = 373

m =

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

ความสัมพันธ์เวียนเกิด T(n) = T(n/2) + O(1) มีผลเฉลยเป็นเท่าใด

AO(log n)
BO(n)
CO(1)
DO(n log n)

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

ต้นทุนแบบกระจายของการเพิ่มค่าตัวนับฐานสองหนึ่งครั้งคือเท่าใด เมื่อการเพิ่มหนึ่งครั้งอาจพลิกหลายบิต

AO(n) ต่อการเพิ่มหนึ่งครั้ง
BO(1) ต่อการเพิ่มหนึ่งครั้ง
CO(n log n) ต่อการเพิ่มหนึ่งครั้ง
DO(log n) ต่อการเพิ่มหนึ่งครั้ง

11.โครงสร้างข้อมูลปานกลาง

รายการประชิดใช้หน่วยความจำเท่าใดสำหรับกราฟที่มี V จุดยอดและ E เส้นเชื่อม

AO(V + E)
BO(V²)
CO(V × E)
DO(E²)

12.โครงสร้างข้อมูลยาก

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

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

13.ทฤษฎีกราฟปานกลาง

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

|V| = 13|E| = 15

k =

14.ทฤษฎีกราฟยาก

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

k = 6

1เส้นเชื่อม AC
2เส้นเชื่อม BC
3เส้นเชื่อม BD
4เส้นเชื่อม CE
5เส้นเชื่อม DE
6เส้นเชื่อม EF
7เส้นเชื่อม GB
8เส้นเชื่อม GC
9เส้นเชื่อม GD

15.ฐานข้อมูลและ SQLปานกลาง

คิวรีใดคืนจำนวนเมืองที่ต่างกันในตาราง customers?

ASELECT DISTINCT COUNT(city) FROM customers
BSELECT COUNT(city) FROM customers GROUP BY city
CSELECT COUNT(DISTINCT city) FROM customers
DSELECT SUM(DISTINCT city) FROM customers

16.ฐานข้อมูลและ SQLยาก

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

Ahash join
Bnested loop join ที่ค้นด้วยดัชนี
Cbitmap join บนคีย์หลัก
Dcross join

17.เครือข่ายคอมพิวเตอร์ปานกลาง

ซับเน็ต IPv4 /26 มีที่อยู่โฮสต์ที่ใช้งานได้กี่ที่อยู่?

A126
B62
C64
D30

18.เครือข่ายคอมพิวเตอร์ยาก

ในโพรโทคอลหน้าต่างเลื่อน (sliding window) Go-Back-N ต่างจาก Selective Repeat อย่างไรหลังเฟรมหนึ่งสูญหาย?

Aทั้งสองส่งหน้าต่างทั้งหมดซ้ำตั้งแต่ต้น
Bทั้งสองไม่เคยส่งเฟรมที่สูญหายซ้ำ
CGo-Back-N ส่งซ้ำเฉพาะเฟรมที่หาย ส่วน Selective Repeat ส่งซ้ำเฟรมนั้นและเฟรมหลังจากนั้นทั้งหมด
DGo-Back-N ส่งเฟรมที่หายและเฟรมหลังจากนั้นทั้งหมดซ้ำ ส่วน Selective Repeat ส่งซ้ำเฉพาะเฟรมที่หายเท่านั้น

19.การแบ่งซับเน็ต IPv4ปานกลาง

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

192.168.213.0/24/29ซับเน็ต 10 (ซับเน็ต 1 เริ่มที่ .0)

x =

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

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

10.20.205.67/29

x =

3สารละลาย

1.ระบบเลข

คำตอบ: U = 172

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

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

84 = 0101 0100

ที่กลับบิตแล้ว: 1010 1011

+1 → 1010 1100

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

1010 1100₂ = 256 − 84 = 172

คำตอบ

U = 172

2.ระบบเลข

คำตอบ: N = 4095

ค่าที่มากที่สุด

2¹² − 1 = 4095

คำตอบ

N = 4095

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

คำตอบ: N = 6

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

p = 1, q = 1, r = 0: p ∨ r = 1, ¬p = 0, (p ∨ r) ∧ ¬p = 0, ¬((p ∨ r) ∧ ¬p) = 1, r ∧ q = 0, ¬(r ∧ q) = 1, ¬((p ∨ r) ∧ ¬p) ↔ ¬(r ∧ q) = 1

p = 1, q = 0, r = 1: p ∨ r = 1, ¬p = 0, (p ∨ r) ∧ ¬p = 0, ¬((p ∨ r) ∧ ¬p) = 1, r ∧ q = 0, ¬(r ∧ q) = 1, ¬((p ∨ r) ∧ ¬p) ↔ ¬(r ∧ q) = 1

p = 1, q = 0, r = 0: p ∨ r = 1, ¬p = 0, (p ∨ r) ∧ ¬p = 0, ¬((p ∨ r) ∧ ¬p) = 1, r ∧ q = 0, ¬(r ∧ q) = 1, ¬((p ∨ r) ∧ ¬p) ↔ ¬(r ∧ q) = 1

p = 0, q = 1, r = 1: p ∨ r = 1, ¬p = 1, (p ∨ r) ∧ ¬p = 1, ¬((p ∨ r) ∧ ¬p) = 0, r ∧ q = 1, ¬(r ∧ q) = 0, ¬((p ∨ r) ∧ ¬p) ↔ ¬(r ∧ q) = 1

p = 0, q = 1, r = 0: p ∨ r = 0, ¬p = 1, (p ∨ r) ∧ ¬p = 0, ¬((p ∨ r) ∧ ¬p) = 1, r ∧ q = 0, ¬(r ∧ q) = 1, ¬((p ∨ r) ∧ ¬p) ↔ ¬(r ∧ q) = 1

p = 0, q = 0, r = 1: p ∨ r = 1, ¬p = 1, (p ∨ r) ∧ ¬p = 1, ¬((p ∨ r) ∧ ¬p) = 0, r ∧ q = 0, ¬(r ∧ q) = 1, ¬((p ∨ r) ∧ ¬p) ↔ ¬(r ∧ q) = 0

p = 0, q = 0, r = 0: p ∨ r = 0, ¬p = 1, (p ∨ r) ∧ ¬p = 0, ¬((p ∨ r) ∧ ¬p) = 1, r ∧ q = 0, ¬(r ∧ q) = 1, ¬((p ∨ r) ∧ ¬p) ↔ ¬(r ∧ q) = 1

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

¬((p ∨ r) ∧ ¬p) ↔ ¬(r ∧ q): 0, 1, 1, 1, 1, 1, 0, 1

N = 6

คำตอบ

N = 6

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

คำตอบ: N = 12

คอลัมน์

¬q; p ∨ ¬q; ¬(p ∨ ¬q); s → ¬(p ∨ ¬q); ¬(s → ¬(p ∨ ¬q)); ¬r; p ∧ ¬r; ¬(s → ¬(p ∨ ¬q)) → (p ∧ ¬r)

แยกตาม p

p = 1: 6

p = 0: 6

N = 6 + 6 = 12

คำตอบ

N = 12

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

คำตอบ: L = 14

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

จัดกลุ่ม 1

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

B′C′D

A′CD′

ABC′D′

ABCD

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

F = B′C′D + A′CD′ + ABC′D′ + ABCD

L = 14

คำตอบ

L = 14

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

คำตอบ: Q = 11

ฟลิปฟล็อปและตัวนับ: ฟลิปฟล็อปเปลี่ยนค่าเฉพาะที่ขอบแอ็กทีฟของสัญญาณนาฬิกา D คัดลอกอินพุต (Q⁺ = D); T สลับค่าเมื่อ T = 1; JK คงค่าสำหรับ 00 รีเซ็ตสำหรับ 01 เซตสำหรับ 10 และสลับค่าสำหรับ 11 ตัวนับฐานสอง n บิตมี 2ⁿ สถานะและนับมอดูโล 2ⁿ ตัวนับมอด N นับ 0, 1, …, N − 1 แล้ววนกลับเป็น 0 และต้องใช้ฟลิปฟล็อปจำนวน n ที่น้อยที่สุดที่ 2ⁿ ≥ N แต่ละภาคของตัวนับริปเปิลลดความถี่ลงครึ่งหนึ่ง ดังนั้นเอาต์พุตสุดท้ายของตัวนับมอด N ทำงานที่ f_clk/N ตัวนับจอห์นสันที่มีฟลิปฟล็อป n ตัวมี 2n สถานะ ตัวนับริงมี n

สถานะหลังทุกขอบ

1100 → 1110 → 1111 → 0111 → 1011

ค่าฐานสิบ

1011₂ = 11

คำตอบ

Q = 11

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

คำตอบ: 33⁻¹ mod 52 = 41

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

r = 52, t = 0

r = 33, q = 1, t = 1

r = 19, q = 1, t = −1

r = 14, q = 1, t = 2

r = 5, q = 2, t = −3

r = 4, q = 1, t = 8

r = 1, q = 4, t = −11

อินเวอร์ส

1 ≡ −11·33 (mod 52)

x = 41

ตรวจสอบ: 33·41 = 1353 = 26·52 + 1

คำตอบ

33⁻¹ mod 52 = 41

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

คำตอบ: m = 458

เลขยกกำลังมอดูลาร์และ 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 = 493, φ(n) = 448

d = 19⁻¹ mod 448 = 283

ถอดรหัสด้วยการยกกำลังสองซ้ำ

283 = 256 + 16 + 8 + 2 + 1

373¹ ≡ 373 (mod 493)

373² ≡ 103 (mod 493)

373⁴ ≡ 256 (mod 493)

373⁸ ≡ 460 (mod 493)

373¹⁶ ≡ 103 (mod 493)

373³² ≡ 256 (mod 493)

373⁶⁴ ≡ 460 (mod 493)

373¹²⁸ ≡ 103 (mod 493)

373²⁵⁶ ≡ 256 (mod 493)

373²⁸³ ≡ 373·103·460·103·256 ≡ 458 (mod 493)

ข้อความ

m = 458

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

13 − 1 = 12

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

k = 15 − 12 = 3

คำตอบ

k = 3

14.ทฤษฎีกราฟ

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

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

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

1. GB (6)

2. DE (9)

3. GD (12)

4. EF (13)

5. CE (14)

6. AC (20)

ผู้รับ Go-Back-N ทิ้งเฟรมที่มาไม่เป็นลำดับ ผู้ส่งจึงต้องส่งทุกอย่างหลังการสูญหายซ้ำ Selective Repeat เก็บเฟรมเหล่านั้นไว้ในบัฟเฟอร์และขอเฉพาะเฟรมที่ขาด

คำตอบ

D · Go-Back-N ส่งเฟรมที่หายและเฟรมหลังจากนั้นทั้งหมดซ้ำ ส่วน Selective Repeat ส่งซ้ำเฉพาะเฟรมที่หายเท่านั้น

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

คำตอบ: x = 72

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

ขนาดบล็อก

2³ = 8

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

เครือข่าย: (10 − 1)·8 = 72

บรอดคาสต์: 72 + 8 − 1 = 79

คำตอบ

x = 72

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

คำตอบ: x = 71

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

ขนาดบล็อก

2³ = 8

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

เครือข่าย: ⌊67/8⌋·8 = 64

บรอดคาสต์: 64 + 8 − 1 = 71

โฮสต์ที่ใช้ได้: 65 … 70

คำตอบ

x = 71

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