Dasar-Dasar Ilmu Komputer: paket kilat

Lembar rumus, langkah-langkah metode utama untuk setiap topik, dan 20 soal latihan, dengan pembahasan lengkap di bagian belakang.

Soal baru Kembali ke mata kuliah

Di jendela cetak, pilih “Simpan sebagai PDF” untuk menyimpan salinan di perangkat Anda.

1Rumus dan metode

Sistem bilangan

Nilai tempat: biner 2^k, oktal 8^k, heksadesimal 16^k
Ke desimal: Σ d_k·b^k
Dari desimal: bagi dengan basis, baca sisanya dari bawah ke atas
Heksadesimal ↔ biner: satu digit heksadesimal = 4 bit
Komplemen dua: balik bitnya lalu tambahkan 1

Logika proposisional & pembuktian

Baris tabel kebenaran: 2ⁿ
Implikasi: p → q ≡ ¬p ∨ q ≡ ¬q → ¬p
Negasi implikasi: ¬(p → q) ≡ p ∧ ¬q
Bikondisional: p ↔ q ≡ (p → q) ∧ (q → p)
De Morgan: ¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q
Hukum distributif: p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Negasi kuantor: ¬∀x P(x) ≡ ∃x ¬P(x), ¬∃x P(x) ≡ ∀x ¬P(x)
Modus ponens, modus tollens: p → q, p ⊢ q; p → q, ¬q ⊢ ¬p

Metode

Hitung banyaknya variabel yang berbeda: tabel kebenaran memiliki 2ⁿ baris, dimulai dengan semuanya bernilai 1.
Beri setiap subformula kolomnya sendiri dan isi kolom-kolom itu dari dalam ke luar.
Terapkan aturan setiap penghubung: → bernilai 0 hanya untuk 1 → 0, ↔ bernilai 1 jika kedua sisi sama.
Untuk ekuivalensi, bandingkan kolom akhir baris demi baris; untuk suatu argumen, lihat hanya baris yang semua premisnya bernilai 1.
Untuk menegasikan pernyataan berkuantor, pindahkan ¬ ke dalam, tukar ∀ dan ∃, lalu negasikan rumus di dalamnya.

Logika digital: gerbang, peta-K & flip-flop

Gerbang dasar: A·B, A + B, A′, (A·B)′, (A + B)′, A ⊕ B
Aturan Boolean: X + X′ = 1, X·X′ = 0, X + XY = X, XY + XY′ = X
De Morgan: (X·Y)′ = X′ + Y′, (X + Y)′ = X′·Y′
Urutan peta Karnaugh: 00, 01, 11, 10 (Gray code)
Kelompok 2ᵏ sel: kehilangan k variabel
Multiplekser 4-ke-1: F = A′B′I₀ + A′BI₁ + AB′I₂ + ABI₃
Flip-flop: D: Q⁺ = D, T: Q⁺ = T ⊕ Q, JK: Q⁺ = JQ′ + K′Q
Pencacah: n bit: 2ⁿ keadaan; mod-N: n terkecil dengan 2ⁿ ≥ N; f_out = f_clk/N
Pencacah ripple: f_max = 1/(n·t_pd)
Pencacah cincin dan Johnson: n dan 2n keadaan

Metode

Untuk rangkaian, bekerjalah dari masukan ke keluaran satu gerbang demi satu gerbang dan tulis nilai pada setiap kawat, atau tulis ekspresinya dan isi tabel kebenaran.
Untuk penyederhanaan, taruh angka 1 (dan don’t-care sebagai X) ke dalam peta Karnaugh dengan baris dan kolom kode Gray: 00, 01, 11, 10.
Cakup angka 1 dengan kelompok sesedikit dan sebesar mungkin yang berisi 1, 2, 4, 8, atau 16 sel, melingkar melewati tepi; setiap kelompok adalah satu suku hasil kali yang tersusun dari variabel yang tetap konstan. Kelompokkan angka 0 untuk bentuk POS.
Untuk flip-flop dan pencacah, baca masukan pada setiap tepi clock aktif, tulis keadaan setelah setiap tepi, dan ingat bahwa pencacah n bit berputar kembali setelah 2ⁿ keadaan.

Teori bilangan & aritmetika modular

Pembagian dengan sisa: a = q·n + r, 0 ≤ r < n
Euclid: gcd(a, b) = gcd(b, a mod b)
Kelipatan persekutuan terkecil: lcm(a, b) = a·b/gcd(a, b)
Invers: a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
Kongruensi linear: a·x ≡ b → x ≡ a⁻¹·b (mod n)
Fungsi totien Euler: φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
Fermat: aᵖ⁻¹ ≡ 1 (mod p)
RSA: n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n

Metode

Reduksi dulu setiap bilangan modulo n; sisa berada di antara 0 dan n − 1.
Untuk FPB, bagi berulang kali dengan algoritma Euclid; sisa taknol terakhir adalah FPB.
Untuk invers, jalankan algoritma yang diperluas dan ambil koefisien a; tambahkan n jika negatif.
Selesaikan a·x ≡ b dengan mengalikan a⁻¹; gabungkan dua kongruensi dengan menuliskan x = r₁ + m₁k.
Untuk pangkat, tuliskan eksponen dalam biner dan kuadratkan berulang; dalam RSA, d = e⁻¹ mod φ(n) dengan φ(n) = (p − 1)(q − 1).

Teori graf

Lema jabat tangan: Σ deg(v) = 2|E|
Graf lengkap: |E(K_n)| = n(n − 1)/2, |E(K_m,n)| = m·n
Graf beraturan: |E| = n·k/2
Pohon dan hutan: |E| = n − 1, |E| = n − c
Daun pohon: L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Euler: sirkuit: semua derajat genap; lintasan: tepat 2 derajat ganjil
Sirkuit Hamilton di K_n: (n − 1)!/2
Pembaruan Dijkstra: d(v) = min(d(v), d(u) + w(u, v))
Jalan dengan panjang L: (Mᴸ)_ij

Metode

Tuliskan derajat setiap simpul; jumlah derajat sama dengan dua kali banyaknya sisi.
Untuk soal Euler, periksa bahwa graf terhubung dan hitung simpul berderajat ganjil.
Untuk pohon, gunakan n − 1 sisi dan lema jabat tangan.
Untuk Dijkstra, buat tabel jarak sementara dan tetapkan simpul belum tetap dengan jarak terkecil di setiap putaran.
Untuk pohon rentang minimum, urutkan sisi menurut bobot dan lewati setiap sisi yang membentuk siklus (Kruskal), atau tumbuhkan satu pohon dari simpul awal (Prim).

Subnetting IPv4

Host per subnet: 2^{(32 − prefix)} − 2 (/31: 2, /32: 1)
Ukuran blok: 256 − (mask octet)
Alamat jaringan: IP AND mask
Alamat broadcast: IP OR (NOT mask): semua bit host bernilai 1
Subnet dari n bit pinjaman: 2ⁿ

2Soal latihan

1.Sistem bilanganSedang

Atur bit sehingga menyimpan −18 dalam komplemen dua 8-bit. Dibaca sebagai bilangan tak bertanda, berapa nilai pola U?

N = −188 bit

U =

2.Sistem bilanganSulit

Atur bit menjadi hasil 8-bit dari 0011 1011 >> 3. Berapa nilai hasil R dalam desimal?

0011 1011>> 3

R =

3.Logika proposisional & pembuktianSedang

Anda ingin membuktikan ¬p → ¬q dengan kontrapositif. Implikasi mana yang Anda buktikan sebagai gantinya? Klik implikasi itu.

¬p → ¬q

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

4.Logika proposisional & pembuktianSulit

Berapa dari 16 baris tabel kebenaran yang membuat ((q ∧ r) ∨ s) ∧ ¬((p ∧ s) ↔ (p ∨ ¬q)) benar? Sebut bilangan ini N.

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

N =

5.Logika digital: gerbang, peta-K & flip-flopSedang

Pakai peta Karnaugh untuk mencari bentuk jumlah dari hasil kali (SOP) minimal dari F(A, B, C, D) = Σm(1, 2, 3, 4, 8, 9, 11). Berapa suku hasil kali N yang dimilikinya?

F(A, B, C, D) = Σm(1, 2, 3, 4, 8, 9, 11)

N =

6.Logika digital: gerbang, peta-K & flip-flopSulit

Untuk F(A, B, C, D) = Σm(4, 6, 7, 12, 14) + d(2, 5, 13), dengan d menandai kondisi don’t-care, carilah banyaknya N implikan prima esensial.

F(A, B, C, D) = Σm(4, 6, 7, 12, 14) + d(2, 5, 13)

N =

7.Teori bilangan & aritmetika modularSedang

Carilah invers 43 modulo 67: bilangan x dengan 0 < x < 67 dan 43·x ≡ 1 (mod 67).

a = 43n = 67

43⁻¹ mod 67 =

8.Teori bilangan & aritmetika modularSulit

Enkripsikan pesan m = 467 dengan kunci publik RSA (n, e) = (1189, 11). Carilah teks sandi c.

n = 1189e = 11m = 467

c =

9.Algoritma & kompleksitasSedang

Bagaimana algoritma Prim membangun minimum spanning tree?

AMengurutkan semua sisi berdasarkan bobot dan menambahkan masing-masing kecuali jika membentuk siklus dalam hutan
BMenumbuhkan satu pohon dari simpul awal, setiap kali menambahkan sisi termurah yang keluar dari pohon
CMenghapus sisi termahal sampai tidak ada siklus tersisa
DMenjalankan breadth-first search dan menyimpan pohon BFS

10.Algoritma & kompleksitasSulit

Teknik manakah yang memberikan waktu eksekusi harapan (expected) O(n log n) untuk quicksort pada input apa pun?

AMenggunakan rekursi hanya pada sisi kiri
BSelalu memilih elemen pertama
CMemilih pivot secara acak seragam
DMengurutkan input sebelum menjalankan quicksort

11.Struktur dataSedang

Pohon AVL dan pohon red-black menjamin:

APencarian dalam waktu konstan pada setiap kasus
BTinggi O(log n) melalui penyeimbangan ulang
CTidak ada node yang memiliki dua anak
DKunci disimpan sesuai urutan penyisipan

12.Struktur dataSulit

Pada hash table dengan open addressing, mengapa penghapusan sering dilakukan dengan penanda "tombstone"?

AKunci yang dihapus harus disimpan selamanya demi keamanan, sehingga slot tidak pernah dapat dipakai ulang
BTombstone mempercepat proses hashing
CMengosongkan slot dapat memutus urutan probe untuk kunci lain
DPenanda ini membuat tabel menjadi terurut

13.Teori grafSedang

Sebuah graf terhubung memiliki 18 simpul dan 29 sisi. Berapa sisi k yang harus dihapus agar tersisa pohon rentang?

|V| = 18|E| = 29

k =

14.Teori grafSulit

Pakai algoritma Dijkstra untuk mencari panjang d(F) lintasan terpendek dari A ke F pada graf berbobot.

awal: Aakhir: F

d(F) =

15.Basis data & SQLSedang

Kueri mana yang menampilkan pelanggan yang belum pernah membuat pesanan?

ASELECT c.name FROM customers c INNER JOIN orders o ON o.customer_id = c.id WHERE o.id IS NULL
BSELECT c.name FROM customers c LEFT JOIN orders o ON o.customer_id = c.id WHERE o.id IS NOT NULL
CSELECT c.name FROM customers c LEFT JOIN orders o ON o.customer_id = c.id WHERE o.id IS NULL
DSELECT c.name FROM customers c LEFT JOIN orders o ON o.customer_id = c.id WHERE o.id = NULL

16.Basis data & SQLSulit

Kueri FROM customers c LEFT JOIN orders o ON o.customer_id = c.id WHERE o.status = 'paid' secara tak terduga membuang pelanggan tanpa pesanan. Mengapa?

ALEFT JOIN tidak pernah mempertahankan baris yang tidak cocok
Bstatus adalah kata yang dicadangkan
CKondisi WHERE pada o menolak baris berisi NULL, sehingga menjadi inner join
DJoin seharusnya menggunakan USING, bukan ON

17.Jaringan komputerSedang

Apa alamat loopback IPv6?

Afe80::1
Bff02::1
C::
D::1

18.Jaringan komputerSulit

Pada protokol sliding window, apa perbedaan Go-Back-N dan Selective Repeat setelah satu frame hilang?

AKeduanya mengirim ulang seluruh window dari awal
BGo-Back-N hanya mengirim ulang frame yang hilang; Selective Repeat mengirim ulang frame itu dan semua frame sesudahnya
CGo-Back-N mengirim ulang frame yang hilang dan semua frame sesudahnya; Selective Repeat hanya frame yang hilang
DKeduanya tidak pernah mengirim ulang frame yang hilang

19.Subnetting IPv4Sedang

Jaringan 192.168.28.0/24 dibagi menjadi subnet /28, bernomor 1, 2, 3, … dari alamat terendah (subnet 1 dimulai di .0). Berapa oktet keempat x alamat broadcast subnet 8?

192.168.28.0/24/28subnet 8 (subnet 1 dimulai di .0)

x =

20.Subnetting IPv4Sulit

Sebuah host memiliki alamat 10.20.67.33/27. Berapa oktet keempat x dari alamat jaringannya?

10.20.67.33/27

x =

3Larutan

1.Sistem bilangan

Jawaban: U = 238

Mengatur bit: setiap bit bernilai pangkat dua (128, 64, …, 1). Satu digit heksa tepat empat bit, dan pada komplemen dua 8-bit bit paling kiri bernilai −128. Operasi bitwise bekerja pada setiap posisi bit secara terpisah.

Balik dan tambah satu

18 = 0001 0010

dibalik: 1110 1101

+1 → 1110 1110

Baca sebagai tak bertanda

1110 1110₂ = 256 − 18 = 238

Jawaban

U = 238

2.Sistem bilangan

Jawaban: R = 7

Bit demi bit

Menggeser ke kanan sebanyak 3 memindahkan setiap bit 3 tempat ke kanan; bit yang keluar dari ujung kanan hilang dan nol masuk dari kiri.

0011 1011 >> 3

= 0000 0111

Nilai hasil

0000 0111₂ = 7

Jawaban

R = 7

3.Logika proposisional & pembuktian

Jawaban: ¬¬q → ¬¬p

Ekuivalensi logis: dua rumus ekuivalen (≡) jika bernilai sama pada setiap baris tabel kebenaran. Tautologi bernilai 1 pada setiap baris, kontradiksi bernilai 0 pada setiap baris, dan kontingensi bukan keduanya. Hukum yang berguna: De Morgan, ¬(a ∧ b) ≡ ¬a ∨ ¬b dan ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (kontrapositif); ¬(a → b) ≡ a ∧ ¬b; dan hukum distributif, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).

Bagian-bagian implikasi

a = ¬p, b = ¬q

Kontrapositif

¬b → ¬a = ¬¬q → ¬¬p

Jawaban

¬¬q → ¬¬p

Kontrapositif ekuivalen dengan pernyataan asli, jadi membuktikannya berarti membuktikan pernyataan itu.

4.Logika proposisional & pembuktian

Jawaban: N = 3

Tabel kebenaran: rumus dengan n variabel berbeda memiliki 2ⁿ baris, satu untuk setiap kombinasi nilai kebenaran (1 = benar, 0 = salah). Bekerjalah dari dalam ke luar dan beri setiap subformula kolomnya sendiri. ¬a membalik nilainya; a ∧ b bernilai 1 hanya jika keduanya 1; a ∨ b bernilai 0 hanya jika keduanya 0; a → b bernilai 0 hanya jika a = 1 dan b = 0; a ↔ b bernilai 1 jika kedua sisi sama.

Kolom

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

Bagi menurut p

p = 1: 1

p = 0: 2

N = 1 + 2 = 3

Jawaban

N = 3

5.Logika digital: gerbang, peta-K & flip-flop

Jawaban: N = 4

Peta Karnaugh: sel-sel diurutkan dalam kode Gray (00, 01, 11, 10), sehingga sel bertetangga, termasuk yang melewati tepi, berbeda tepat pada satu variabel. Kelompokkan angka 1 dalam persegi panjang berisi 1, 2, 4, 8, atau 16 sel, sebesar mungkin dan sesedikit mungkin, sampai setiap angka 1 tercakup. Setiap kelompok adalah satu suku hasil kali: variabel yang tetap konstan di dalamnya. Kelompok 2ᵏ sel kehilangan k variabel. Don’t-care (X) boleh dipakai untuk memperbesar kelompok tetapi tidak harus dicakup. Mengelompokkan angka 0 sebagai gantinya menghasilkan bentuk POS minimal.

Kelompokkan angka 1

Setiap kelompok adalah persegi panjang berisi 2ᵏ sel; sel di tepi bertetangga dengan sel di tepi seberangnya.

B′D

A′B′C

AB′C′

A′BC′D′

Bentuk SOP minimal

F = B′D + A′B′C + AB′C′ + A′BC′D′

N = 4

Jawaban

N = 4

6.Logika digital: gerbang, peta-K & flip-flop

Jawaban: N = 2

Implikan prima

Kelompok terbesar yang dapat dibentuk dari angka 1 dan X.

BD′, BC′, A′CD′, A′B

Implikan prima esensial

BD′, A′B

N = 2

Jawaban

N = 2

7.Teori bilangan & aritmetika modular

Jawaban: 43⁻¹ mod 67 = 53

Invers dan kongruensi: a memiliki invers modulo n tepat ketika FPB(a, n) = 1. Algoritma Euclid yang diperluas menuliskan 1 = s·n + t·a, dan kemudian a⁻¹ ≡ t (mod n). Kongruensi a·x ≡ b (mod n) dengan FPB(a, n) = 1 memiliki penyelesaian x ≡ a⁻¹·b. Dua kongruensi x ≡ r₁ (mod m₁) dan x ≡ r₂ (mod m₂) dengan modulus saling prima memiliki satu penyelesaian modulo m₁·m₂ (teorema sisa Cina). φ(n) Euler menghitung bilangan dari 1 sampai n yang saling prima dengan n: φ(n) = n·∏(1 − 1/p).

Algoritma Euclid yang diperluas

Setiap sisa r ditulis sebagai r ≡ t·43 (mod 67).

r = 67, t = 0

r = 43, q = 1, t = 1

r = 24, q = 1, t = −1

r = 19, q = 1, t = 2

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

r = 4, q = 1, t = 11

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

Invers

1 ≡ −14·43 (mod 67)

x = 53

periksa: 43·53 = 2279 = 34·67 + 1

Jawaban

43⁻¹ mod 67 = 53

8.Teori bilangan & aritmetika modular

Jawaban: c = 508

Pangkat modular dan RSA: hitung aᵏ mod n dengan pengkuadratan berulang: tulis k dalam biner, kuadratkan, reduksi setelah setiap langkah, dan kalikan pangkat yang bitnya 1. Fermat: aᵖ⁻¹ ≡ 1 (mod p) untuk bilangan prima p yang tidak membagi a, sehingga eksponen dapat direduksi modulo p − 1. RSA: pilih bilangan prima p dan q, n = p·q dan φ(n) = (p − 1)(q − 1); eksponen publik e saling prima dengan φ(n), dan eksponen privat adalah d = e⁻¹ mod φ(n). Enkripsi dengan c = mᵉ mod n dan dekripsi dengan m = cᵈ mod n.

Pengkuadratan berulang

11 = 8 + 2 + 1

467¹ ≡ 467 (mod 1189)

467² ≡ 502 (mod 1189)

C · Mengosongkan slot dapat memutus urutan probe untuk kunci lain

13.Teori graf

Jawaban: k = 12

Euler, Hamilton, dan pohon: graf terhubung memiliki sirkuit Euler (setiap sisi sekali, kembali ke awal) jika setiap simpul berderajat genap, dan lintasan Euler yang bukan sirkuit jika tepat dua simpul berderajat ganjil; lintasan itu berjalan dari satu simpul ganjil ke simpul ganjil lainnya. Sirkuit Hamilton mengunjungi setiap simpul sekali; K_n memiliki (n − 1)!/2 sirkuit seperti itu. Pohon dengan n simpul memiliki n − 1 sisi, dan graf terhubung dengan m sisi masih memiliki pohon rentang setelah m − n + 1 sisi dihapus.

Sisi pohon rentang

18 − 1 = 17

Sisi yang dihapus

k = 29 − 17 = 12

Jawaban

k = 12

14.Teori graf

Jawaban: d(F) = 23

Lintasan terpendek dan pohon rentang: algoritma Dijkstra menetapkan satu simpul per putaran: simpul belum tetap dengan jarak sementara terkecil. Jaraknya lalu final, dan setiap tetangga v mendapat d(v) = min(d(v), d(u) + w(u, v)). Algoritma Kruskal membangun pohon rentang minimum dengan mengambil sisi dari yang ringan ke berat dan melewati sisi yang akan membentuk siklus; algoritma Prim menumbuhkan satu pohon dari simpul awal dengan selalu menambahkan sisi teringan yang keluar dari pohon. Pohon rentang dengan n simpul memiliki n − 1 sisi.

Dijkstra putaran demi putaran

Setiap baris: simpul yang ditetapkan, jarak finalnya, dan tetangga yang jaraknya membaik.

A (0): B: 3

B (3): C: 15, D: 14, G: 16

D (14): E: 24

C (15): E: 17

G (16)

E (17): F: 23

F (23)

Lintasan terpendek

A → B → C → E → F

Ukuran blok

2⁴ = 16

Subnet nomor 8

jaringan: (8 − 1)·16 = 112

broadcast: 112 + 16 − 1 = 127

Jawaban

x = 127

20.Subnetting IPv4

Jawaban: x = 32

Subnetting IPv4: sebuah alamat terdiri dari 32 bit. Prefiks /p menyatakan berapa bit awal yang mengidentifikasi jaringan; sisa 32 − p bit menomori host. Sebuah subnet memiliki 2³²⁻ᵖ alamat, tetapi yang pertama (alamat jaringan) dan terakhir (alamat broadcast) tidak dapat diberikan ke host, sehingga muat 2³²⁻ᵖ − 2 host. Pengecualian: /31 (tautan point-to-point, RFC 3021) memakai kedua alamatnya yang berjumlah 2 untuk host, dan /32 hanya satu alamat (satu host atau loopback).

Ukuran blok

2⁵ = 32

Subnet host ini

jaringan: ⌊33/32⌋·32 = 32

broadcast: 32 + 32 − 1 = 63

host yang dapat dipakai: 33 … 62

Jawaban

x = 32

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