Dasar-Dasar Ilmu Komputer: paket kilat

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.

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.

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.

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.

Multiplekser: multiplekser 2ⁿ-ke-1 meneruskan salah satu masukan datanya ke keluaran; saluran pemilih, yang dibaca sebagai bilangan biner, menentukan yang mana. Untuk MUX 4-ke-1 dengan pemilih S₁S₀ = AB, F = A′B′·I₀ + A′B·I₁ + AB′·I₂ + AB·I₃. Menghubungkan masukan data ke 0, 1, C, atau C′ membuat MUX menghasilkan fungsi apa pun dari A, B, dan C, yang merupakan cara umum membangun logika dengan satu chip.

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.

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

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.

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.

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.

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

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