Formulių lapai, pagrindiniai kiekvienos temos metodų žingsniai ir 20 uždavinių, o pilni sprendimai pateikti gale.
8 bitų seka 1001 0111 saugo sveikąjį skaičių su ženklu papildomajame kode. Kokia jo reikšmė N dešimtainėje sistemoje?
Nesuspaustas vaizdas yra 1024 × 768 pikselių, 8 bitų pikseliui. Kiek atminties M jis užima, KiB (1 KiB = 1024 baitai)?
Norite įrodyti ¬c → (b ∨ a) kontrapozicija. Kurią implikaciją įrodote vietoj jos? Spustelėkite ją.
Kiek iš 16 teisingumo lentelės eilučių daro (q ↔ (p ∨ r)) ∧ (¬(r ↔ ¬p) ∨ ¬s) teisingą? Pažymėkite šį skaičių N.
Karno žemėlapiu raskite minimalią F(A, B, C) = Σm(0, 1, 3, 6, 7) sandaugų sumos (SOP) formą. Kiek sandaugos narių N ji turi?
3 bitų dvejetainis mažėjantis skaitiklis pradeda nuo 7 (dešimtainiu pavidalu, Q = 111). Kokį skaičių Q (dešimtainiu pavidalu) jis rodo po 26 taktinių impulsų?
Raskite mažiausią teigiamą sveikąjį skaičių x, kur x ≡ 3 (mod 4) ir x ≡ 0 (mod 11).
Išspręskite 16x ≡ 72 (mod 88). Pateikite mažiausią teigiamą sprendinį x.
Ar teisinga sakyti, kad O(n²) algoritmas yra ir O(n³)?
Kas išplauktų, jei kas nors rastų polinominio laiko algoritmą vienam NP-pilnam uždaviniui?
Kuri duomenų struktūra naudojama tikrinti, ar skliaustai eilutėje „{[()]}“ subalansuoti?
Struktūros union-find (nesikertančios aibės) su jungimu pagal rangą ir kelio suspaudimu amortizuota vienos operacijos kaina yra:
Medis turi 2 viršūnių, kurių laipsnis 3, 4 viršūnių, kurių laipsnis 2, o visos kitos jo viršūnės yra lapai (laipsnis 1). Kiek lapų L jis turi?
Raskite svertinio grafo minimalaus karkasinio medžio bendrą svorį W.
Ką reiškia funkcinė priklausomybė A → B?
Kuris izoliacijos lygis apsaugo nuo „nešvarių“ skaitymų (dirty reads), bet vis dar leidžia nepakartojamus skaitymus (non-repeatable reads)?
Kuris iš šių yra privatus IPv4 adresų diapazonas?
Mazgai VLAN 10 ir VLAN 20 tame pačiame komutatoriuje negali bendrauti. Ko reikia?
Tinklas 172.24.0.0/16 padalytas į vienodus potinklius su prefiksu /23. Kiek yra potinklių N?
Mazgo adresas yra 10.20.90.86/26. Koks yra jo potinklio transliacijos adreso paskutinis skaičius (ketvirtasis oktetas) x?
Atsakymas: N = −105
Pozicinės skaičiavimo sistemos: kiekvienas skaitmuo vertas savo reikšmės, padaugintos iš pagrindo laipsnio. Dvejetainėje sistemoje pozicijos vertos 1, 2, 4, 8, 16, …, šešioliktainėje 1, 16, 256, …, o A–F reiškia 10–15. 8 bitų papildomajame kode kairysis bitas vertas −128 vietoj +128; taip saugomi neigiami skaičiai.
Kiti bitai išlaiko įprastas teigiamas vertes.
Atsakymas: M = 768 KiB
Pozicinės skaičiavimo sistemos: kiekvienas skaitmuo vertas savo reikšmės, padaugintos iš pagrindo laipsnio. Dvejetainėje sistemoje pozicijos vertos 1, 2, 4, 8, 16, …, šešioliktainėje 1, 16, 256, …, o A–F reiškia 10–15. 8 bitų papildomajame kode kairysis bitas vertas −128 vietoj +128; taip saugomi neigiami skaičiai.
Atsakymas: ¬(b ∨ a) → ¬¬c
Loginis ekvivalentumas: dvi formulės yra ekvivalenčios (≡), kai kiekvienoje teisingumo lentelės eilutėje turi tą pačią reikšmę. Tautologija yra 1 kiekvienoje eilutėje, prieštara – 0 kiekvienoje eilutėje, o kontingencija nėra nei viena, nei kita. Naudingi dėsniai: De Morgano, ¬(a ∧ b) ≡ ¬a ∨ ¬b ir ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (kontrapozicija); ¬(a → b) ≡ a ∧ ¬b; ir distributyvumo dėsniai, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).
Kontrapozicija yra ekvivalenti pradiniam teiginiui, todėl ją įrodžius įrodomas ir teiginys.
Atsakymas: N = 6
Teisingumo lentelės: formulė su n skirtingų kintamųjų turi 2ⁿ eilučių, po vieną kiekvienam teisingumo reikšmių deriniui (1 = teisinga, 0 = klaidinga). Dirbkite iš vidaus į išorę ir kiekvienai posakio daliai skirkite savo stulpelį. ¬a apverčia reikšmę; a ∧ b yra 1 tik tada, kai abu lygūs 1; a ∨ b yra 0 tik tada, kai abu lygūs 0; a → b yra 0 tik tada, kai a = 1 ir b = 0; a ↔ b yra 1, kai abi pusės lygios.
Atsakymas: N = 3
Karno žemėlapiai: langeliai išdėstyti Grejaus kodu (00, 01, 11, 10), todėl gretimi langeliai, įskaitant esančius per kraštus, skiriasi tiksliai vienu kintamuoju. Sugrupuokite vienetus į 1, 2, 4, 8 arba 16 langelių stačiakampius, kuo didesnius ir kuo mažiau, kol bus padengtas kiekvienas vienetas. Kiekviena grupė yra vienas sandaugos narys: kintamieji, kurie joje nesikeičia. 2ᵏ langelių grupė netenka k kintamųjų. Nesvarbias reikšmes (X) galima naudoti grupėms didinti, bet jų dengti nebūtina. Grupuojant nulius, gaunama minimali POS forma.
Kiekviena grupė yra 2ᵏ langelių stačiakampis; kraštiniai langeliai yra priešingo krašto langelių kaimynai.
Egzistuoja kitas to paties dydžio grupavimas; jis turi tiek pat narių ir literalų.
Atsakymas: Q = 5
Trigeriai ir skaitikliai: trigeris keičiasi tik aktyviu taktinio signalo frontu. D nukopijuoja savo įėjimą (Q⁺ = D); T perjungia, kai T = 1; JK išlaiko esant 00, nustato į 0 esant 01, nustato į 1 esant 10 ir perjungia esant 11. n bitų dvejetainis skaitiklis turi 2ⁿ būsenų ir skaičiuoja moduliu 2ⁿ; mod-N skaitiklis skaičiuoja 0, 1, …, N − 1 ir grįžta į 0, jam reikia mažiausiai n trigerių, kad 2ⁿ ≥ N. Kiekviena nuosekliojo (ripple) skaitiklio pakopa perpus sumažina dažnį, todėl paskutinis mod-N skaitiklio išėjimas veikia fclk/N dažniu. n trigerių Johnsono skaitiklis turi 2n būsenų, žiedinis – n.
Kas 8 impulsų skaitiklis grįžta į tą pačią būseną.
Atsakymas: x = 11
Atvirkštiniai skaičiai ir kongruencijos: a turi atvirkštinį moduliu n lygiai tada, kai gcd(a, n) = 1. Išplėstinis Euklido algoritmas užrašo 1 = s·n + t·a, ir tada a⁻¹ ≡ t (mod n). Kongruencija a·x ≡ b (mod n), kai gcd(a, n) = 1, turi sprendinį x ≡ a⁻¹·b. Dvi kongruencijos x ≡ r₁ (mod m₁) ir x ≡ r₂ (mod m₂) su tarpusavyje pirminiais moduliais turi vieną sprendinį moduliu m₁·m₂ (Kinų liekanų teorema). Oilerio φ(n) skaičiuoja skaičius nuo 1 iki n, tarpusavyje pirminius su n: φ(n) = n·∏(1 − 1/p).
Atsakymas: x = 10
Atvirkštiniai skaičiai ir kongruencijos: a turi atvirkštinį moduliu n lygiai tada, kai gcd(a, n) = 1. Išplėstinis Euklido algoritmas užrašo 1 = s·n + t·a, ir tada a⁻¹ ≡ t (mod n). Kongruencija a·x ≡ b (mod n), kai gcd(a, n) = 1, turi sprendinį x ≡ a⁻¹·b. Dvi kongruencijos x ≡ r₁ (mod m₁) ir x ≡ r₂ (mod m₂) su tarpusavyje pirminiais moduliais turi vieną sprendinį moduliu m₁·m₂ (Kinų liekanų teorema). Oilerio φ(n) skaičiuoja skaičius nuo 1 iki n, tarpusavyje pirminius su n: φ(n) = n·∏(1 − 1/p).
Atsakymas: A · Taip, nes didysis O yra viršutinis rėžis, o n² auga ne greičiau už n³
Didysis O yra viršutinis rėžis, todėl teiginys teisingas, bet ne glaudus; Θ(n²) nurodo tikslų augimo greitį.
Atsakymas: C · Kiekvieną NP uždavinį būtų galima išspręsti per polinominį laiką, taigi P = NP
Kadangi visa NP klasė per polinominį laiką redukuojama į bet kurį NP-pilną uždavinį, greitas algoritmas vienam duoda greitą algoritmą visiems.
Atsakymas: C · Stekas
Kiekvieną atidarantį skliaustą atlikite push, o pasirodžius uždarančiam – pop; jis turi atitikti išimtą skliaustą, o pabaigoje stekas turi būti tuščias.
Atsakymas: B · O(α(n)), atvirkštinė Ackermanno funkcija, praktiškai pastovi
Taikant abi optimizacijas, operacijos trunka O(α(n)) amortizuoto laiko; α(n) ≤ 4 bet kokiam realiam n.
Atsakymas: L = 4
Oileris, Hamiltonas ir medžiai: jungus grafas turi Oilerio ciklą (kiekviena briauna vieną kartą, grįžtama į pradžią), kai kiekvienos viršūnės laipsnis lyginis, ir Oilerio kelią, kuris nėra ciklas, kai lygiai dvi viršūnės turi nelyginį laipsnį; tada kelias eina iš vienos nelyginės viršūnės į kitą. Hamiltono ciklas aplanko kiekvieną viršūnę vieną kartą; Kn jų turi (n − 1)!/2. Medis su n viršūnių turi n − 1 briauną, o jungus grafas su m briaunų turi karkasinį medį, pašalinus m − n + 1 briaunų.
Trumpesnis kelias: L = 2 + Σ (d − 2) pagal viršūnes, kurių laipsnis d ≥ 3.
Atsakymas: W = 34
Trumpiausi keliai ir karkasiniai medžiai: Dijkstros algoritmas kiekviename etape užfiksuoja po vieną viršūnę: neužfiksuotą viršūnę su mažiausiu preliminariu atstumu. Tada jos atstumas galutinis, o kiekvienas kaimynas v gauna d(v) = min(d(v), d(u) + w(u, v)). Kruskalio algoritmas sudaro minimalų karkasinį medį imdamas briaunas nuo lengvų iki sunkių ir praleisdamas kiekvieną briauną, kuri uždarytų ciklą; Primo algoritmas augina vieną medį iš pradinės viršūnės visada pridėdamas lengviausią iš jo išeinančią briauną. Karkasinis medis su n viršūnių turi n − 1 briauną.
Atsakymas: A · Kiekviena A reikšmė susijusi su lygiai viena B reikšme
A → B reiškia, kad bet kurios dvi eilutės su ta pačia A reikšme turi turėti tą pačią B reikšmę; A apibrėžia B.
Atsakymas: B · Read committed
Read committed paslepia nepatvirtintus pakeitimus; repeatable read taip pat apsaugo nuo nepakartojamų skaitymų; serializable apsaugo ir nuo fantomų.
Atsakymas: D · 192.168.0.0/16
Privatūs diapazonai yra 10.0.0.0/8, 172.16.0.0/12 ir 192.168.0.0/16; jie nemaršrutizuojami viešajame internete.
Atsakymas: B · Maršrutizatoriaus ar 3 lygmens komutatoriaus srautui tarp VLAN maršrutizuoti
VLAN izoliuoti 2 lygmeniu, todėl srautas tarp jų turi būti maršrutizuojamas, pvz., maršrutizatoriumi per magistralinę jungtį („router on a stick“) ar 3 lygmens komutatoriumi.
Atsakymas: N = 128
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).
Kiekviename /23 potinklyje yra 29 − 2 = 510 naudojamų mazgų adresų.
Atsakymas: x = 127
IPv4 potinkliai: adresas turi 32 bitus. Prefiksas /p nurodo, kiek pradinių bitų žymi tinklą; likę 32 − p bitai numeruoja mazgus. Potinklis turi 2³²⁻ᵖ adresų, bet pirmojo (tinklo adreso) ir paskutiniojo (transliacijos adreso) negalima priskirti mazgams, todėl telpa 2³²⁻ᵖ − 2 mazgai. Išimtys: /31 (dviejų taškų jungtis, RFC 3021) abu savo 2 adresus naudoja mazgams, o /32 yra vienas adresas (vienas mazgas arba grįžtamoji sąsaja).
ExamProblems · examproblems.com/courses/computer-science-fundamentals