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

Pola 8-bit 1011 0000 menyimpan bilangan bulat bertanda dalam komplemen dua. Berapa nilainya N dalam desimal?

1011 00008 bit

N =

2.Sistem bilanganSulit

Sebuah gambar tak terkompresi berukuran 640 × 480 piksel dengan 32 bit per piksel. Berapa memori M yang dipakainya, dalam KiB (1 KiB = 1024 byte)?

640 × 480 px32 bit/px1 KiB = 1024 B

M = KiB

3.Logika proposisional & pembuktianSedang

Rumus mana yang ekuivalen secara logis dengan (r ∧ q) → p? Klik rumus itu.

(r ∧ q) → p

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

4.Logika proposisional & pembuktianSulit

Argumen dengan premis q → r; ¬q dan kesimpulan ¬r tidak valid. Klik baris tabel kebenaran yang merupakan contoh penyangkal.

q → r¬q∴ ¬r

1q = 1, r = 1
2q = 1, r = 0
3q = 0, r = 1
4q = 0, r = 0

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

Sederhanakan F = B′C′ + B′C + A′B′C′ + AB′C′ ke bentuk jumlah dari hasil kali minimal. Berapa literal L yang dimiliki ekspresi yang sudah disederhanakan?

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

L =

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

Pencacah cincin 4 bit Q₃Q₂Q₁Q₀ dimulai dari 1000. Pada setiap tepi clock bit bergeser satu tempat ke kanan (Q₃ → Q₂ → Q₁ → Q₀) dan Q₃ menerima Q₀. Berikan keadaan Q = Q₃Q₂Q₁Q₀ sebagai bilangan desimal setelah 7 tepi clock.

Q₃Q₂Q₁Q₀ = 10007

Q =

7.Teori bilangan & aritmetika modularSedang

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

a = 19n = 41

19⁻¹ mod 41 =

8.Teori bilangan & aritmetika modularSulit

Ada berapa penyelesaian N yang dimiliki 32x ≡ 16 (mod 78) dalam {0, 1, …, 77}?

32x ≡ 16 (mod 78)

N =

9.Algoritma & kompleksitasSedang

Sebuah fungsi menjalankan satu loop berisi n iterasi, lalu secara terpisah satu loop lain berisi n iterasi. Berapa kompleksitas waktunya?

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

10.Algoritma & kompleksitasSulit

Mengapa binary search tidak menghasilkan waktu O(log n) pada singly linked list?

ALinked list tidak dapat diurutkan
BMencapai elemen tengah memerlukan O(n) langkah, karena tidak ada akses indeks langsung
CPerbandingan pada node linked list lebih lambat
DBinary search memerlukan setidaknya dua kali lipat memori

11.Struktur dataSedang

Syarat keseimbangan apa yang dijaga AVL tree di setiap node?

ATinggi subpohon kiri dan kanan berbeda paling banyak 1
BKedua subpohon dari setiap node berisi jumlah node yang persis sama
CSetiap node diberi warna merah atau hitam
DSemua daun berada pada kedalaman yang persis sama

12.Struktur dataSulit

Anda harus menyimpan k nilai terkecil dari aliran n bilangan dengan memori O(k). Pendekatan mana yang bekerja dalam waktu O(n log k)?

AMax-heap berukuran k, mengganti root-nya ketika datang nilai yang lebih kecil
BMin-heap yang menampung semua n nilai, lalu k nilai terkecil dikeluarkan di akhir
CArray terurut berisi semua n nilai
DQueue FIFO berisi k nilai terakhir

13.Teori grafSedang

Sebuah pohon memiliki 2 simpul berderajat 4, 3 simpul berderajat 2, dan semua simpul lainnya adalah daun (derajat 1). Berapa daun L yang dimilikinya?

2 × deg 43 × deg 2

L =

14.Teori grafSulit

Algoritma Dijkstra berjalan dari A. Klik simpul yang ditetapkan (dijadikan permanen) pada putaran 5; A sendiri adalah putaran 1.

awal: Aputaran 5

15.Basis data & SQLSedang

Kapan WHERE EXISTS (subkueri) bernilai benar untuk sebuah baris?

AKetika subkueri mengembalikan tepat satu baris
BKetika subkueri mengembalikan sekurang-kurangnya satu baris
CKetika subkueri mengembalikan bilangan yang lebih besar dari nol
DKetika subkueri tidak mengembalikan nilai NULL

16.Basis data & SQLSulit

Fitur SQL mana yang paling cocok untuk menemukan setiap karyawan di bawah seorang manajer dalam pohon organisasi yang kedalamannya tidak diketahui?

AConstraint UNIQUE pada manager_id
BSatu self-join tabel employees pada manager_id
CCommon table expression rekursif (WITH RECURSIVE)
DGROUP BY pada manager_id

17.Jaringan komputerSedang

Untuk apa cyclic redundancy check (CRC) digunakan dalam frame Ethernet?

AMendeteksi kesalahan transmisi
BMemperbaiki setiap kesalahan bit secara otomatis
CMemilih rute terbaik
DMengenkripsi frame

18.Jaringan komputerSulit

Apa perbedaan fragmentasi pada IPv6 dibandingkan IPv4?

ARouter tidak pernah memfragmentasi paket IPv6; hanya sumber yang dapat melakukannya, dengan path MTU discovery
BIPv6 memfragmentasi di lapisan transport di dalam TCP
CIPv6 tidak mengizinkan paket yang lebih besar dari 576 byte
DRouter IPv6 memfragmentasi setiap paket yang lebih besar dari 64 byte sebelum meneruskannya di sepanjang jalur

19.Subnetting IPv4Sedang

Sebuah subnet memakai mask 255.255.255.252. Berapa alamat host yang dapat dipakai H?

255.255.255.252

H =

20.Subnetting IPv4Sulit

Jaringan 192.168.125.0/24 dibagi dengan VLSM untuk LAN berikut: A: 41 host, B: 17 host, C: 4 host, D: 18 host, E: 14 host. Subnet dialokasikan dari .0 ke atas, LAN dengan host terbanyak lebih dulu, masing-masing dengan subnet terkecil yang cukup. Berapa oktet keempat x alamat jaringan LAN D?

A: 41B: 17C: 4D: 18E: 14

x =

3Larutan

1.Sistem bilangan

Jawaban: N = −80

Sistem bilangan posisional: setiap digit bernilai digit itu dikali pangkat dari basis. Dalam biner, posisinya bernilai 1, 2, 4, 8, 16, …; dalam heksadesimal 1, 16, 256, …, dengan A–F mewakili 10–15. Dalam komplemen dua 8-bit, bit paling kiri bernilai −128, bukan +128; begitulah bilangan negatif disimpan.

Jumlahkan nilai posisi

Bit lainnya tetap bernilai positif seperti biasa.

−128 + 32 + 16 = −80

Jawaban

N = −80

2.Sistem bilangan

Jawaban: M = 1200 KiB

Bit dan byte

640·480·32 = 9830400 bit = 1228800 B

Ubah ke KiB

1228800/1024 = 1200 KiB

Jawaban

M = 1200 KiB

3.Logika proposisional & pembuktian

Jawaban: r → (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).

Hukumnya

Eksportasi: (a ∧ b) → c ≡ a → (b → c). Keduanya bernilai 0 hanya jika a = 1, b = 1, dan c = 0.

(r ∧ q) → p ≡ r → (q → p)

Periksa dengan tabel kebenaran

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

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

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

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

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

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

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

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

Jawaban

r → (q → p)

Kolom setelah garis adalah pilihan dalam urutan yang ditampilkan.

4.Logika proposisional & pembuktian

Jawaban: q = 0, r = 1

Kuantor dan argumen: ¬∀x P(x) ≡ ∃x ¬P(x) dan ¬∃x P(x) ≡ ∀x ¬P(x). Pindahkan negasi ke dalam, tukar setiap kuantor yang dilewatinya, dan negasikan rumus di dalamnya dengan hukum proposisional, seperti ¬(a → b) ≡ a ∧ ¬b. Sebuah argumen valid jika kesimpulannya bernilai 1 pada setiap baris yang semua premisnya bernilai 1. Satu baris dengan premis benar dan kesimpulan salah adalah contoh penyangkal dan menunjukkan bahwa argumen itu tidak valid.

Premis dan kesimpulan baris demi baris

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

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

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

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

Contoh penyangkal

q = 0, r = 1

Jawaban

q = 0, r = 1

Argumen dengan bentuk ini tampak seperti aturan yang valid, tetapi satu baris cukup untuk menunjukkan bahwa itu tidak benar.

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

Jawaban: L = 1

Aljabar Boolean: aturan yang menyederhanakan ekspresi adalah X + X′ = 1 dan X·X′ = 0, X + X = X, absorpsi X + X·Y = X, aturan penggabungan X·Y + X·Y′ = X, X + X′Y = X + Y, dan teorema konsensus XY + X′Z + YZ = XY + X′Z. Hukum De Morgan mengubah (X·Y)′ menjadi X′ + Y′ dan (X + Y)′ menjadi X′·Y′. Peta Karnaugh menerapkan aturan ini secara grafis: setiap kelompok dua sel bertetangga adalah satu penggunaan XY + XY′ = X.

Minterm dari ekspresi

B′C′ → m(0, 4)

B′C → m(1, 5)

A′B′C′ → m(0)

AB′C′ → m(4)

Kelompokkan dan baca

F = B′

Hitung literalnya

L = 1

Jawaban

L = 1

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

Jawaban: Q = 1

Flip-flop dan pencacah: flip-flop hanya berubah pada tepi clock aktif. D menyalin masukannya (Q⁺ = D); T berbalik jika T = 1; JK bertahan untuk 00, reset untuk 01, set untuk 10, dan berbalik untuk 11. Pencacah biner n bit memiliki 2ⁿ keadaan dan menghitung modulo 2ⁿ; pencacah mod-N berurutan 0, 1, …, N − 1 lalu kembali ke 0, dan memerlukan flip-flop sebanyak n terkecil dengan 2ⁿ ≥ N. Setiap tahap pencacah ripple membagi dua frekuensi, sehingga keluaran terakhir pencacah mod-N berjalan pada f_clk/N. Pencacah Johnson dari n flip-flop memiliki 2n keadaan, pencacah cincin n.

Keadaan setelah setiap tepi

1000 → 0100 → 0010 → 0001 → 1000 → 0100 → 0010 → 0001

Nilai desimal

0001₂ = 1

Jawaban

Q = 1

7.Teori bilangan & aritmetika modular

Jawaban: 19⁻¹ mod 41 = 13

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·19 (mod 41).

r = 41, t = 0

r = 19, q = 2, t = 1

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

r = 1, q = 3, t = 13

Invers

1 ≡ 13·19 (mod 41)

x = 13

periksa: 19·13 = 247 = 6·41 + 1

Jawaban

19⁻¹ mod 41 = 13

8.Teori bilangan & aritmetika modular

Jawaban: N = 2

Bagi dengan FPB

gcd(32, 78) = 2

16x ≡ 8 (mod 39)

Selesaikan kongruensi yang sudah disederhanakan

16⁻¹ ≡ 22 (mod 39) → x ≡ 20 (mod 39)

Penyelesaian modulo 78

x ∈ {20, 59}

Lema jabat tangan untuk pohon

L + 14 = 2(L + 5) − 2

L = 6

Jawaban

L = 6

Jalan pintas: L = 2 + Σ (d − 2) atas simpul berderajat d ≥ 3.

14.Teori graf

Jawaban: E

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

1. A (0): B: 13, C: 4

2. C (4): B: 9, E: 11

3. B (9): D: 10

4. D (10): F: 14

5. E (11)

Router IPv6 membuang paket yang terlalu besar dan mengembalikan ICMPv6 Packet Too Big. Sumber kemudian mengirim paket yang lebih kecil atau menggunakan fragment extension header.

Jawaban

A · Router tidak pernah memfragmentasi paket IPv6; hanya sumber yang dapat melakukannya, dengan path MTU discovery

19.Subnetting IPv4

Jawaban: H = 2

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

Panjang prefiks

255.255.255.252 = /30

Host yang dapat dipakai

2² − 2 = 2

Jawaban

H = 2

20.Subnetting IPv4

Jawaban: x = 64

VLSM: setiap LAN mendapat subnet terkecil dengan 2ʰ − 2 ≥ jumlah host-nya, yaitu prefiks 32 − h. Mengalokasikan subnet terbesar lebih dulu membuat setiap blok sejajar pada kelipatan ukurannya sendiri, sehingga alamat jaringan diperoleh dengan menjumlahkan ukuran blok.

Ukuran blok per LAN

A: 41 host → 2⁶ = 64 (/26)

D: 18 host → 2⁵ = 32 (/27)

B: 17 host → 2⁵ = 32 (/27)

E: 14 host → 2⁴ = 16 (/28)

C: 4 host → 2³ = 8 (/29)

Alokasi, terbesar lebih dulu

A: .0 – .63

D: .64 – .95

B: .96 – .127

E: .128 – .143

C: .144 – .151

Jawaban

x = 64

LAN D: 192.168.125.64/27.

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