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

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

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

N = −408 bit

U =

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

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

1280 × 720 px16 bit/px1 KiB = 1024 B

M = KiB

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

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

p → r

1¬r → ¬p
2r → p
3¬p → ¬r
4¬r ∧ ¬p

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

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

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

N =

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

จงทำ F = A′BC + ABC + A′BC′ ให้เป็นรูปผลบวกของผลคูณที่น้อยที่สุด นิพจน์ที่ทำให้ง่ายแล้วมีกี่ลิเทอรัล L

F = A′BC + ABC + A′BC′

L =

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

สำหรับ F(A, B, C, D) = Σm(1, 7, 8, 10, 15) + d(0, 2, 4, 5, 14) โดย d แทนเงื่อนไขไม่สนใจ จงหาจำนวน N ของไพรม์อิมพลิแคนต์จำเป็น

F(A, B, C, D) = Σm(1, 7, 8, 10, 15) + d(0, 2, 4, 5, 14)

N =

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

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

x ≡ 2 (mod 7)x ≡ 7 (mod 9)

x =

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

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

p = 11q = 29e = 13c = 292

m =

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

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

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

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

นิยามใดของคลาส P ถูกต้อง

Aปัญหาที่ต้องใช้เวลาเอกซ์โพเนนเชียลบนคอมพิวเตอร์ทุกเครื่อง
Bปัญหาที่ตรวจคำตอบได้แต่ไม่เคยหาคำตอบได้ในเวลาพหุนาม
Cปัญหาที่แก้แบบขนานได้
Dปัญหาการตัดสินใจที่แก้ได้ด้วยอัลกอริทึมแบบกำหนดแน่นอนในเวลาพหุนาม

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

เหตุใดการท่องอาร์เรย์จึงเร็วกว่าการท่องลิงก์ลิสต์ที่ยาวเท่ากันมากในทางปฏิบัติ

Aลิงก์ลิสต์เก็บสมาชิกบนดิสก์เสมอ
Bอาร์เรย์ใช้คำสั่งน้อยกว่าในการเปรียบเทียบค่า
Cการท่องอาร์เรย์เป็น O(1) โดยรวม ส่วนการท่องลิงก์ลิสต์เป็น O(n)
Dสมาชิกของอาร์เรย์ต่อเนื่องกัน จึงใช้แคชของ CPU ได้ดี

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

การกลับลิงก์ลิสต์เชิงเดี่ยวในที่เดิมมีต้นทุนด้านเวลาและพื้นที่เพิ่มเติมเท่าใด

Aเวลา O(n) และพื้นที่เพิ่ม O(n)
Bเวลา O(1) และพื้นที่เพิ่ม O(1)
Cเวลา O(n) และพื้นที่เพิ่ม O(1)
Dเวลา O(n log n) และพื้นที่เพิ่ม O(1)

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

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

2 × deg 33 × deg 52 × deg 2

L =

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

ใช้ขั้นตอนวิธีของไดก์สตราเพื่อหาความยาว d(F) ของเส้นทางที่สั้นที่สุดจาก A ไป F ในกราฟถ่วงน้ำหนัก

เริ่มต้น: Aสิ้นสุด: F

d(F) =

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

ตาราง employees มีคอลัมน์ manager_id ที่อ้างอิงพนักงานอีกคน จะแสดงพนักงานแต่ละคนคู่กับชื่อผู้จัดการได้อย่างไร?

Aใช้ GROUP BY manager_id อย่างเดียว
Bรวมตารางกับตัวมันเองด้วย UNION ALL และตัวกรอง WHERE
Cสร้างสำเนาที่สองของตารางบนดิสก์
Dเชื่อมตาราง employees กับตัวเองโดยใช้ชื่อแฝงสองชื่อ

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

การแยก R เป็น R1 และ R2 รับประกันว่าไม่สูญเสียเมื่อใด?

Aเมื่อทุกแอตทริบิวต์ของ R ปรากฏในทั้ง R1 และ R2
Bเมื่อ R1 และ R2 ไม่มีแอตทริบิวต์ร่วมกัน
Cเมื่อแอตทริบิวต์ร่วมของ R1 และ R2 เป็นซูเปอร์คีย์ของ R1 หรือของ R2
Dเมื่อ R1 และ R2 มีจำนวนคอลัมน์เท่ากัน

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

คำสั่ง "ping" ใช้โพรโทคอลใด?

AICMP
BHTTP
CTCP
DUDP

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

คุณต้องแบ่ง 192.168.1.0/24 เป็นอย่างน้อย 5 ซับเน็ต โดยแต่ละซับเน็ตมีโฮสต์ได้ถึง 25 เครื่อง ความยาวพรีฟิกซ์ใดเหมาะที่สุด?

A/25
B/27
C/26
D/28

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

แผนกหนึ่งต้องการที่อยู่โฮสต์ 1537 ที่อยู่ในซับเน็ตเดียว ความยาวพรีฟิกซ์ที่ยาวที่สุด p (ซับเน็ตเล็กที่สุด) ที่ใหญ่พอคือเท่าใด

1537 hosts

p =

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

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

10.20.215.83/29

x =

3สารละลาย

1.ระบบเลข

คำตอบ: U = 216

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

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

40 = 0010 1000

ที่กลับบิตแล้ว: 1101 0111

+1 → 1101 1000

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

1101 1000₂ = 256 − 40 = 216

คำตอบ

U = 216

2.ระบบเลข

คำตอบ: M = 1800 KiB

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

บิตและไบต์

1280·720·16 = 14745600 bit = 1843200 B

แปลงเป็น KiB

1843200/1024 = 1800 KiB

คำตอบ

M = 1800 KiB

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

คำตอบ: ¬r → ¬p

ความสมมูลเชิงตรรกะ: สูตรสองสูตรสมมูลกัน (≡) เมื่อมีค่าเท่ากันทุกแถวของตารางค่าความจริง ซ้ำซ้อน (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)

กฎ

นัยสมมูลกับการแย้งสลับที่ ¬b → ¬a ไม่ใช่กับคอนเวิร์ส b → a หรืออินเวิร์ส ¬a → ¬b

p → r ≡ ¬r → ¬p

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

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

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

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

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

คำตอบ

¬r → ¬p

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

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

คำตอบ: N = 10

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

คอลัมน์

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

แยกตาม p

p = 1: 3

p = 0: 7

N = 3 + 7 = 10

คำตอบ

N = 10

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

คำตอบ: L = 4

พีชคณิตแบบบูล: กฎที่ทำให้นิพจน์ง่ายขึ้นได้แก่ X + X′ = 1 และ X·X′ = 0, X + X = X, การดูดกลืน X + X·Y = X, กฎการรวม X·Y + X·Y′ = X, X + X′Y = X + Y และทฤษฎีบทฉันทามติ XY + X′Z + YZ = XY + X′Z กฎของเดอมอร์แกนเปลี่ยน (X·Y)′ เป็น X′ + Y′ และ (X + Y)′ เป็น X′·Y′ แผนที่คาร์โนห์ใช้กฎเหล่านี้ในรูปภาพ: ทุกกลุ่มของสองเซลล์ที่อยู่ติดกันคือการใช้ XY + XY′ = X หนึ่งครั้ง

มินเทอมของนิพจน์

A′BC → m(3)

ABC → m(7)

A′BC′ → m(2)

จัดกลุ่มและอ่านค่า

F = BC + A′B

นับลิเทอรัล

L = 4

คำตอบ

L = 4

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

คำตอบ: N = 2

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

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

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

B′D′, BCD, A′C′, ACD′, A′BD, ABC

ไพรม์อิมพลิแคนต์จำเป็น

B′D′, A′C′

N = 2

คำตอบ

N = 2

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

คำตอบ: x = 16

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

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

2 + 7k ≡ 7 (mod 9) → 7k ≡ 5 (mod 9)

k ≡ 4·5 ≡ 2 (mod 9)

ผลลัพธ์

x = 2 + 7·2 = 16

x = 16

ตรวจสอบ: 16 mod 7 = 2, 16 mod 9 = 7

คำตอบ

x = 16

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

คำตอบ: m = 217

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

d = 13⁻¹ mod 280 = 237

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

237 = 128 + 64 + 32 + 8 + 4 + 1

292¹ ≡ 292 (mod 319)

292² ≡ 91 (mod 319)

292⁴ ≡ 306 (mod 319)

292⁸ ≡ 169 (mod 319)

292¹⁶ ≡ 170 (mod 319)

292³² ≡ 190 (mod 319)

292⁶⁴ ≡ 53 (mod 319)

292¹²⁸ ≡ 257 (mod 319)

292²³⁷ ≡ 292·306·169·190·53·257 ≡ 217 (mod 319)

ข้อความ

m = 217

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

L + 25 = 2(L + 7) − 2

L = 13

คำตอบ

L = 13

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

14.ทฤษฎีกราฟ

คำตอบ: d(F) = 25

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

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

แต่ละบรรทัด: จุดยอดที่ยืนยัน ระยะทางสุดท้ายของมัน และเพื่อนบ้านที่ระยะทางดีขึ้น

A (0): B: 8, C: 8

B (8): E: 23

C (8): E: 17

E (17): D: 18, F: 31

D (18): F: 25

F (25)

เส้นทางที่สั้นที่สุด

A → C → E → D → F

บิตโฮสต์ที่ต้องใช้

2¹⁰ − 2 = 1022 < 1537

2¹¹ − 2 = 2046 ≥ 1537 → h = 11

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

p = 32 − 11 = 21

คำตอบ

p = /21

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

คำตอบ: x = 87

ขนาดบล็อก

2³ = 8

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

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

บรอดคาสต์: 80 + 8 − 1 = 87

โฮสต์ที่ใช้ได้: 81 … 86

คำตอบ

x = 87

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