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

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

ตั้งบิตให้เป็นผลลัพธ์ 8 บิตของ 0011 0010 XOR 0011 0111 ค่าของผลลัพธ์ R เป็นเท่าใดในเลขฐานสิบ

0011 0010XOR0011 0111

R =

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

สูตรใดสมมูลเชิงตรรกะกับ r ∧ (q ∨ p) ให้คลิกสูตรนั้น

r ∧ (q ∨ p)

1(r ∧ q) ∨ p
2(r ∧ q) ∨ (r ∧ p)
3(r ∨ q) ∧ (r ∨ p)
4r ∨ (q ∧ p)

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

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

¬((¬(d ∧ c) → ¬b) ∨ ((¬c ↔ d) ∨ ¬(¬a ∨ ¬b)))

N =

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

มัลติเพล็กเซอร์ 4 ต่อ 1 มีอินพุตเลือก S₁ = A และ S₀ = B และอินพุตข้อมูลต่อเข้ากับ I₀ = C′, I₁ = 1, I₂ = 1, I₃ = C จาก 8 ชุดของ A, B และ C มีกี่ชุดที่เอาต์พุต F = 1 จงหา N

I₀ = C′I₁ = 1I₂ = 1I₃ = C

N =

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

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

Q₀ = 0JK

1ขอบสัญญาณนาฬิกา 1
2ขอบสัญญาณนาฬิกา 2
3ขอบสัญญาณนาฬิกา 3
4ขอบสัญญาณนาฬิกา 4
5ขอบสัญญาณนาฬิกา 5
6ขอบสัญญาณนาฬิกา 6
7ขอบสัญญาณนาฬิกา 7
8ขอบสัญญาณนาฬิกา 8

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

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

a = 10n = 19

10⁻¹ mod 19 =

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

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

n = 703e = 13m = 301

c =

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

ความซับซ้อนเชิงเวลาของอัลกอริทึม Bellman–Ford บนกราฟที่มี V จุดยอดและ E เส้นเชื่อมคือเท่าใด

AO(V + E)
BO(V³ × E)
CO(E log V)
DO(V × E)

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

การคูณแบบ Karatsuba ตรงตาม T(n) = 3T(n/2) + O(n) ผลเฉลยคืออะไร

AΘ(n log n)
BΘ(n²)
CΘ(n³)
DΘ(n^{log₂ 3}) ประมาณ n^1.585

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

ต้นไม้ AVL รักษาเงื่อนไขสมดุลใดที่ทุกโหนด

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

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

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

Aคิว FIFO ของ k ค่าล่าสุด
Bmin-heap ที่เก็บค่าทั้ง n ตัว แล้วดึงค่าที่น้อยที่สุด k ตัวออกมาตอนท้าย
Cmax-heap ขนาด k โดยแทนที่รากเมื่อมีค่าที่เล็กกว่ามา
Dอาร์เรย์เรียงลำดับของค่าทั้ง n

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

กราฟบริบูรณ์ K₄ มีวงจรแฮมิลตันที่แตกต่างกันกี่วงจร H วงจรที่ต่างกันเพียงจุดยอดเริ่มต้นหรือทิศทางนับเป็นวงจรเดียวกัน

K₄

H =

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

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

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

d(F) =

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

รูปแบบบรรทัดฐานที่หนึ่ง (1NF) กำหนดว่า:

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

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

การล็อกสองระยะ (two-phase locking, 2PL) รับประกัน:

Aว่าไม่ต้องใช้ล็อก
Bว่า deadlock ไม่มีทางเกิดขึ้น
Cว่าทรานแซกชันไม่ต้องรอเลย
Dตารางเวลาที่ conflict-serializable

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

ลำดับข้อความตามปกติเมื่อไคลเอนต์ได้รับที่อยู่จาก DHCP คืออะไร?

AOffer, Discover, Acknowledge, Request
BDiscover, Request, Offer, Acknowledge
CRequest, Offer, Discover, Acknowledge
DDiscover, Offer, Request, Acknowledge

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

การแบ่งส่วน (fragmentation) ใน IPv6 ต่างจาก IPv4 อย่างไร?

AIPv6 ไม่อนุญาตแพ็กเก็ตที่ใหญ่กว่า 576 ไบต์
Bเราเตอร์ไม่แบ่งส่วนแพ็กเก็ต IPv6 เลย เฉพาะต้นทางทำได้ โดยใช้ path MTU discovery
Cเราเตอร์ IPv6 แบ่งส่วนทุกแพ็กเก็ตที่ใหญ่กว่า 64 ไบต์ก่อนส่งต่อไปตามเส้นทาง
DIPv6 แบ่งส่วนที่ชั้นทรานสปอร์ตภายใน TCP

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

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

192.168.76.0/24/28ซับเน็ต 2 (ซับเน็ต 1 เริ่มที่ .0)

x =

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

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

10.203.64.0/24 … 10.203.67.0/24

p =

3สารละลาย

1.ระบบเลข

คำตอบ: U = 172

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

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

84 = 0101 0100

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

+1 → 1010 1100

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

1010 1100₂ = 256 − 84 = 172

คำตอบ

U = 172

2.ระบบเลข

คำตอบ: R = 5

ทีละบิต

XOR ให้ 1 เมื่อสองบิตต่างกัน

0011 0010

XOR 0011 0111

= 0000 0101

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

0000 0101₂ = 5

คำตอบ

R = 5

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

คำตอบ: (r ∧ q) ∨ (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)

กฎ

∧ แจกแจงเหนือ ∨: a ∧ (b ∨ c) ≡ (a ∧ b) ∨ (a ∧ c)

r ∧ (q ∨ p) ≡ (r ∧ q) ∨ (r ∧ p)

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

p = 1, q = 1, r = 1: 1 | 1 1 1 1

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

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

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

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

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

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

p = 0, q = 0, r = 0: 0 | 0 0 0 0

คำตอบ

(r ∧ q) ∨ (r ∧ p)

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

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

คำตอบ: N = 1

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

คอลัมน์

d ∧ c; ¬(d ∧ c); ¬b; ¬(d ∧ c) → ¬b; ¬c; ¬c ↔ d; ¬a; ¬a ∨ ¬b; ¬(¬a ∨ ¬b); (¬c ↔ d) ∨ ¬(¬a ∨ ¬b); (¬(d ∧ c) → ¬b) ∨ ((¬c ↔ d) ∨ ¬(¬a ∨ ¬b)); ¬((¬(d ∧ c) → ¬b) ∨ ((¬c ↔ d) ∨ ¬(¬a ∨ ¬b)))

แยกตาม a

a = 1: 0

a = 0: 1

N = 0 + 1 = 1

คำตอบ

N = 1

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

คำตอบ: N = 6

มัลติเพล็กเซอร์: มัลติเพล็กเซอร์ 2ⁿ ต่อ 1 ส่งอินพุตข้อมูลหนึ่งตัวไปยังเอาต์พุต สายเลือก (select) เมื่ออ่านเป็นเลขฐานสองจะเลือกว่าตัวใด สำหรับ MUX 4 ต่อ 1 ที่สายเลือก S₁S₀ = AB จะได้ F = A′B′·I₀ + A′B·I₁ + AB′·I₂ + AB·I₃ การต่ออินพุตข้อมูลเข้ากับ 0, 1, C หรือ C′ ทำให้ MUX สร้างฟังก์ชันใดก็ได้ของ A, B และ C ซึ่งเป็นวิธีที่พบบ่อยในการสร้างตรรกะด้วยชิปตัวเดียว

นิพจน์เอาต์พุต

F = A′B′C′ + A′B + AB′ + ABC

แถวที่ F = 1

ABC = 000, 010, 011, 100, 101, 111

N = 6

คำตอบ

N = 6

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

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

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

Q หลังทุกขอบ

ฟลิปฟล็อป JK: 00 คงค่า, 01 รีเซ็ต (Q = 0), 10 เซต (Q = 1), 11 สลับค่า

1: J = 0, K = 1 → Q = 0

2: J = 1, K = 1 → Q = 1

3: J = 0, K = 1 → Q = 0

4: J = 0, K = 1 → Q = 0

5: J = 0, K = 0 → Q = 0

6: J = 0, K = 1 → Q = 0

7: J = 0, K = 0 → Q = 0

8: J = 0, K = 1 → Q = 0

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

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

คำตอบ

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

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

คำตอบ: 10⁻¹ mod 19 = 2

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

r = 19, t = 0

r = 10, q = 1, t = 1

r = 9, q = 1, t = −1

r = 1, q = 9, t = 2

อินเวอร์ส

1 ≡ 2·10 (mod 19)

x = 2

ตรวจสอบ: 10·2 = 20 = 1·19 + 1

คำตอบ

10⁻¹ mod 19 = 2

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

คำตอบ: c = 309

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

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

13 = 8 + 4 + 1

301¹ ≡ 301 (mod 703)

301² ≡ 617 (mod 703)

C · max-heap ขนาด k โดยแทนที่รากเมื่อมีค่าที่เล็กกว่ามา

13.ทฤษฎีกราฟ

คำตอบ: H = 3

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

นับ

H = (4 − 1)!/2 = 6/2 = 3

คำตอบ

H = 3

14.ทฤษฎีกราฟ

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

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

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

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

A (0): B: 1, C: 6

B (1): C: 5, D: 2, E: 5

D (2)

C (5)

E (5): F: 16

F (16)

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

A → B → E → F

ขนาดบล็อก

2⁴ = 16

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

เครือข่าย: (2 − 1)·16 = 16

บรอดคาสต์: 16 + 16 − 1 = 31

คำตอบ

x = 16

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

คำตอบ: p = 22

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

เทียบบิต

64 = 01000000

67 = 01000011

บิตนำหน้าที่ตรงกัน: 6

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

p = 16 + 6 = 22

คำตอบ

p = /22

เส้นทางสรุป: 10.203.64.0/22

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