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

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

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

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

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

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

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

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

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

((q → r) ∧ (q ∨ r)) ∨ (s → (p ∨ ¬s))
N =
5.ตรรกะดิจิทัล: เกต แผนที่คาร์โนห์ และฟลิปฟล็อปปานกลาง
ABC000111100101324576

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

F = B′C′ + AB′C′ + A′C′ + A′B′C
L =
6.ตรรกะดิจิทัล: เกต แผนที่คาร์โนห์ และฟลิปฟล็อปยาก
TQ0​Q0​TQ1​Q1​TQ2​Q2​TQ3​Q3​CLKMOD-12

ตัวนับมอด-12 แบบซิงโครนัสนับ 0, 1, …, 11 แล้ววนกลับเป็น 0 เริ่มที่ 0 หลังพัลส์นาฬิกา 21 พัลส์ จะแสดงค่านับ Q (เป็นเลขฐานสิบ) เท่าใด

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

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

a = 6n = 11
6−1 mod 11 =
8.ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ยาก
mc = me​ mod ncm = cd​ mod nm(n, e) = (667, 3)d = ?

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

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

ความซับซ้อนเชิงเวลาของ for i = 1 to n: (j = 1; while j < n: j = j × 2) คือเท่าใด

  1. AO(n²)
  2. BO(log n)
  3. CO(n log n)
  4. DO(n)
10.อัลกอริทึมและความซับซ้อนยาก

ขอบเขตใดถูกต้องสำหรับ log(n!)

  1. AΘ(log n)
  2. BΘ(n²)
  3. CΘ(n)
  4. DΘ(n log n)
11.โครงสร้างข้อมูลปานกลาง

นิพจน์ postfix 3 4 + 2 * มีค่าเท่าใด

  1. A11
  2. B14
  3. C24
  4. D10
12.โครงสร้างข้อมูลยาก

ต้นไม้แดง–ดำ (red-black tree) ต้องมีคุณสมบัติใด

  1. Aรากต้องเป็นสีแดง
  2. Bทุกเส้นทางจากโหนดไปยังใบของลูกหลานมีจำนวนโหนดสีดำเท่ากัน
  3. Cทุกโหนดต้องเป็นสีแดง
  4. Dโหนดสีแดงทุกโหนดต้องมีลูกสีแดง โหนดสีแดงจึงต่อเป็นสายไม่ขาดตอนไปจนถึงใบ
13.ทฤษฎีกราฟปานกลาง

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

3 × deg 3
L =
14.ทฤษฎีกราฟยาก
174742416ABCDEFG

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

เริ่มต้น: Aสิ้นสุด: F
d(F) =
15.ฐานข้อมูลและ SQLปานกลาง

ในพีชคณิตเชิงสัมพันธ์ ตัวดำเนินการโปรเจกชัน (π) สอดคล้องกับ:

  1. Aการเลือกว่าแถวใดเป็นไปตามเงื่อนไขที่กำหนด
  2. Bการเลือกว่าคอลัมน์ใดปรากฏในผลลัพธ์
  3. Cการเรียงลำดับผลลัพธ์
  4. Dการรวมสองตารางด้วยคีย์
16.ฐานข้อมูลและ SQLยาก

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

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

จุดประสงค์ของการแฮนด์เชก (handshake) สามทางของ TCP คืออะไร?

  1. Aเพื่อสร้างการเชื่อมต่อและซิงโครไนซ์หมายเลขลำดับ
  2. Bเพื่อปิดการเชื่อมต่ออย่างรวดเร็ว
  3. Cเพื่อหาที่อยู่ IP ของโฮสต์ก่อนที่จะส่งข้อมูลไปถึงโฮสต์นั้นได้
  4. Dเพื่อเข้ารหัสข้อมูล
18.เครือข่ายคอมพิวเตอร์ยาก

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

  1. A/28
  2. B/25
  3. C/26
  4. D/27
19.การแบ่งซับเน็ต IPv4ปานกลาง
/22 → /2811111111111111111111111111110000บิตเครือข่ายบิตโฮสต์

เครือข่าย 10.238.136.0/22 ถูกแบ่งเป็นซับเน็ตขนาดเท่ากันด้วยพรีฟิกซ์ /28 มีกี่ซับเน็ต N

10.238.136.0/22/28
N =
20.การแบ่งซับเน็ต IPv4ยาก
ออคเต็ตสุดท้าย = 123012816413211618041211เครือข่ายโฮสต์

โฮสต์มีที่อยู่ 10.20.54.123/27 ออคเต็ตที่สี่ x ของที่อยู่เครือข่ายคือเท่าใด

10.20.54.123/27
x =

3สารละลาย

1.ระบบเลข

คำตอบ: N = −32

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

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

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

−128 + 64 + 32 = −32

คำตอบ

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

คำตอบ: R = 218

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

ทีละบิต

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

1101 1010
OR 0101 1010
= 1101 1010

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

1101 1010₂ = 218

คำตอบ

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

คำตอบ: (q → p) ∧ (p → q)

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

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

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

คำตอบ

(q → p) ∧ (p → q)

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

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

คำตอบ: N = 14

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

คอลัมน์

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

แยกตาม p

p = 1: 8
p = 0: 6
N = 8 + 6 = 14

คำตอบ

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

คำตอบ: L = 6

พีชคณิตแบบบูล: กฎที่ทำให้นิพจน์ง่ายขึ้นได้แก่ 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 หนึ่งครั้ง

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

B′C′ → m(0, 4)
AB′C′ → m(4)
A′C′ → m(0, 2)
A′B′C → m(1)
ABC00011110011011031214050706

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

F = B′C′ + A′C′ + A′B′

นับลิเทอรัล

L = 6

คำตอบ

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

คำตอบ: Q = 9

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

รอบเต็ม

ทุก 12 พัลส์ทำให้ตัวนับกลับสู่สถานะเดิม

21 = 1·12 + 9

ค่านับหลังพัลส์ที่เหลือ

Q = (0 + 9) mod 12 = 9
Q = 1001₂

คำตอบ

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

คำตอบ: 6−1 mod 11 = 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·6 (mod 11)

r = 11, t = 0
r = 6, q = 1, t = 1
r = 5, q = 1, t = −1
r = 1, q = 5, t = 2

อินเวอร์ส

1 ≡ 2·6 (mod 11)
x = 2
ตรวจสอบ: 6·2 = 12 = 1·11 + 1

คำตอบ

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

คำตอบ: d = 411

เลขยกกำลังมอดูลาร์และ 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 = 23·29 = 667
φ(n) = 22·28 = 616

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

r = 616, t = 0
r = 3, q = 205, t = 1
r = 1, q = 3, t = −205

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

d = 411
ตรวจสอบ: 3·411 = 1233 = 2·616 + 1

คำตอบ

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

คำตอบ: C · O(n log n)

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

ลูปชั้นในทำงานประมาณ log₂ n ครั้งสำหรับแต่ละรอบของลูปชั้นนอก n รอบ ได้ O(n log n)

คำตอบ

C · O(n log n)
10.อัลกอริทึมและความซับซ้อน

คำตอบ: D · Θ(n log n)

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

log(n!) ≤ n log n และตัวคูณที่ใหญ่ที่สุด n / 2 ตัวให้ log(n!) ≥ (n / 2) log(n / 2) นี่คือเหตุที่การเรียงแบบเปรียบเทียบต้องใช้ Ω(n log n)

คำตอบ

D · Θ(n log n)
11.โครงสร้างข้อมูล

คำตอบ: B · 14

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

push 3 และ 4, + ได้ 7; push 2, * ได้ 7 × 2 = 14

คำตอบ

B · 14
12.โครงสร้างข้อมูล

คำตอบ: B · ทุกเส้นทางจากโหนดไปยังใบของลูกหลานมีจำนวนโหนดสีดำเท่ากัน

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

กฎของแดง–ดำ: โหนดเป็นสีแดงหรือดำ รากเป็นสีดำ โหนดสีแดงมีลูกสีดำ และทุกเส้นทางมี black-height เท่ากัน ทำให้ความสูง ≤ 2 log₂(n + 1)

คำตอบ

B · ทุกเส้นทางจากโหนดไปยังใบของลูกหลานมีจำนวนโหนดสีดำเท่ากัน
13.ทฤษฎีกราฟ

คำตอบ: L = 5

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

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

L + 9 = 2(L + 3) − 2
L = 5

คำตอบ

L = 5

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

14.ทฤษฎีกราฟ

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

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

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

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

A (0): C: 1
C (1): B: 8, E: 8, G: 5
G (5): D: 6
D (6)
B (8)
E (8): F: 10
F (10)

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

A → C → E → F
d(F) = 10

คำตอบ

d(F) = 10
15.ฐานข้อมูลและ SQL

คำตอบ: B · การเลือกว่าคอลัมน์ใดปรากฏในผลลัพธ์

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

โปรเจกชันเก็บแอตทริบิวต์ที่เลือก (รายการ SELECT) ส่วนการเลือก σ เก็บแถวที่เป็นไปตามเงื่อนไข (อนุประโยค WHERE)

คำตอบ

B · การเลือกว่าคอลัมน์ใดปรากฏในผลลัพธ์
16.ฐานข้อมูลและ SQL

คำตอบ: B · เมื่อแอตทริบิวต์ร่วมของ R1 และ R2 เป็นซูเปอร์คีย์ของ R1 หรือของ R2

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

หากแอตทริบิวต์ร่วมกำหนดทุกแอตทริบิวต์ของ R1 หรือ R2 การเชื่อมกลับจะได้แถวเดิมพอดีโดยไม่มีทูเพิลปลอม

คำตอบ

B · เมื่อแอตทริบิวต์ร่วมของ R1 และ R2 เป็นซูเปอร์คีย์ของ R1 หรือของ R2
17.เครือข่ายคอมพิวเตอร์

คำตอบ: A · เพื่อสร้างการเชื่อมต่อและซิงโครไนซ์หมายเลขลำดับ

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

การแฮนด์เชกสร้างการเชื่อมต่อและตกลงหมายเลขลำดับเริ่มต้นของทั้งสองฝ่ายก่อนส่งข้อมูล

คำตอบ

A · เพื่อสร้างการเชื่อมต่อและซิงโครไนซ์หมายเลขลำดับ
18.เครือข่ายคอมพิวเตอร์

คำตอบ: D · /27

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

/27 ให้ 8 ซับเน็ต แต่ละซับเน็ตมีโฮสต์ที่ใช้งานได้ 30 /26 ให้เพียง 4 ซับเน็ต และ /28 รองรับโฮสต์ได้เพียง 14 ต่อซับเน็ต

คำตอบ

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

คำตอบ: N = 64

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

บิตที่ยืมมา

28 − 22 = 6

จำนวนซับเน็ต

N = 26 = 64

คำตอบ

N = 64

แต่ละซับเน็ต /28 มีโฮสต์ที่ใช้ได้ 24 − 2 = 14 โฮสต์

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

คำตอบ: x = 96

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

ขนาดบล็อก

25 = 32

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

เครือข่าย: ⌊123/32⌋·32 = 96
บรอดคาสต์: 96 + 32 − 1 = 127
โฮสต์ที่ใช้ได้: 97 … 126

คำตอบ

x = 96

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