Formulių lapai, pagrindiniai kiekvienos temos metodų žingsniai ir 20 uždavinių, o pilni sprendimai pateikti gale.
Užrašykite −6 kaip 8 bitų papildomojo kodo seką. Perskaitykite seką kaip dvejetainį skaičių be ženklo: kokia jo reikšmė U dešimtainėje sistemoje?
Nesuspaustas vaizdas yra 640 × 480 pikselių, 24 bitų pikseliui. Kiek atminties M jis užima, KiB (1 KiB = 1024 baitai)?
Ar (a ↔ c) ∧ (a ↔ ¬c) yra tautologija, prieštara ar kontingencija? Spustelėkite savo atsakymą.
Kiek iš 16 teisingumo lentelės eilučių daro ((r → ¬p) ∧ p) ∨ (s ∨ ¬(s ↔ q)) teisingą? Pažymėkite šį skaičių N.
4 į 1 multiplekserio pasirinkimo įėjimai yra S₁ = A ir S₀ = B, o duomenų įėjimai prijungti prie I₀ = C′, I₁ = C, I₂ = C′, I₃ = C. Kiek iš 8 A, B ir C derinių duoda išėjimą F = 1? Raskite N.
4 bitų žiedinis skaitiklis Q₃Q₂Q₁Q₀ pradeda nuo 1010. Kiekvienu taktiniu frontu bitai pasislenka per vieną vietą į dešinę (Q₃ → Q₂ → Q₁ → Q₀), o Q₃ gauna Q₀. Nurodykite būseną Q = Q₃Q₂Q₁Q₀ dešimtainiu skaičiumi po 9 taktinių frontų.
Raskite 11 atvirkštinį moduliu 29: skaičių x, kur 0 < x < 29 ir 11·x ≡ 1 (mod 29).
RSA raktas naudoja p = 13, q = 47 ir e = 19. Iššifruokite šifrogramą c = 576: raskite pranešimą m.
Kaip Primo algoritmas sudaro minimalų jungiamąjį medį?
0/1 kuprinės uždavinys, sprendžiamas dinaminiu programavimu, užtrunka O(nW) laiko. Kodėl tai vadinama pseudopolinominiu laiku?
Kaip žiedinėje eilėje, saugomoje n talpos masyve, apskaičiuojama kita pozicija po indekso i?
Kuris teiginys apie rikiavimą krūva (heapsort) teisingas?
Kiek skirtingų Hamiltono ciklų H turi pilnasis grafas K5? Ciklai, besiskiriantys tik pradine viršūne ar kryptimi, laikomi tuo pačiu.
Dijkstros algoritmas vykdomas nuo A. Spustelėkite viršūnę, užfiksuojamą (padaromą galutine) 5 etape; pats A yra 1 etapas.
Kuri užklausa grąžina kiekvieno kliento užsakymų skaičių?
x yra NULL, o y = 1. Kokia sąlygos (x > 5 OR y = 1) reikšmė?
Kuri TCP vėliavėlė praneša, kad siuntėjas baigė siųsti duomenis?
Serverio privatusis raktas bus pavogtas po metų. Kuri TLS savybė apsaugo šiandien įrašytus seansus?
Skyriui viename potinklyje reikia 1139 mazgų adresų. Koks yra ilgiausias prefiksas p (mažiausias potinklis), kurio pakanka?
Mazgo adresas yra 10.20.237.104/29. Koks yra jo potinklio transliacijos adreso paskutinis skaičius (ketvirtasis oktetas) x?
Atsakymas: U = 250
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: M = 900 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: prieštara
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).
Atsakymas: N = 13
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 = 4
Multiplekseris: 2ⁿ į 1 multiplekseris perduoda vieną iš savo duomenų įėjimų į išėjimą; pasirinkimo linijos, skaitomos kaip dvejetainis skaičius, nurodo kurį. 4 į 1 MUX su pasirinkimo įėjimais S₁S₀ = AB, F = A′B′·I₀ + A′B·I₁ + AB′·I₂ + AB·I₃. Duomenų įėjimus prijungus prie 0, 1, C arba C′, MUX gali sukurti bet kurią A, B ir C funkciją; tai dažnas būdas sudaryti logiką viena mikroschema.
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.
Atsakymas: 11−1 mod 29 = 8
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).
Kiekviena liekana r užrašoma kaip r ≡ t·11 (mod 29).
Atsakymas: m = 524
Moduliniai laipsniai ir RSA: aᵏ mod n skaičiuokite kartotiniu kėlimu kvadratu: užrašykite k dvejetainiu pavidalu, keliate kvadratu, po kiekvieno žingsnio redukuokite ir sudauginkite laipsnius, kurių bitas lygus 1. Ferma: aᵖ⁻¹ ≡ 1 (mod p) pirminiam p, nedalijančiam a, todėl rodiklį galima redukuoti moduliu p − 1. RSA: pasirinkite pirminius p ir q, n = p·q ir φ(n) = (p − 1)(q − 1); viešasis rodiklis e tarpusavyje pirminis su φ(n), o privatusis rodiklis yra d = e⁻¹ mod φ(n). Šifruokite c = mᵉ mod n ir dešifruokite m = cᵈ mod n.
Atsakymas: B · Jis augina vieną medį nuo pradinės viršūnės, kaskart pridėdamas pigiausią iš medžio išeinančią briauną
Primo algoritmas su kertančių briaunų prioritetine eile, naudojant dvejetainę krūvą, veikia per O(E log V).
Atsakymas: A · W yra skaitinė reikšmė, todėl laikas yra eksponentinis bitų, reikalingų W užrašyti, skaičiaus atžvilgiu
Vykdymo laikas yra polinominis W reikšmės atžvilgiu, bet eksponentinis jos ilgio (log W bitų) atžvilgiu; 0/1 kuprinės uždavinys yra NP-pilnas.
Atsakymas: A · (i + 1) mod n
Modulio operacija indeksą n − 1 grąžina į 0, todėl masyvas naudojamas pakartotinai, nepastumiant elementų.
Atsakymas: D · Jis rikiuoja vietoje per O(n log n) blogiausiu atveju, bet nėra stabilus
Rikiavimas krūva sudaro max krūvą ir n kartų išima maksimumą tame pačiame masyve; sukeitimai dideliais atstumais gali pakeisti vienodų raktų tvarką.
Atsakymas: H = 12
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ų.
Atsakymas: G
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: B · SELECT customer_id, COUNT(*) FROM orders GROUP BY customer_id
GROUP BY customer_id sukuria po vieną grupę kiekvienam klientui, o COUNT(*) suskaičiuoja kiekvienos grupės eilutes.
Atsakymas: C · TRUE
x > 5 yra UNKNOWN, bet OR su TRUE bet kuriuo atveju yra TRUE, todėl eilutė paliekama; UNKNOWN AND FALSE analogiškai būtų FALSE.
Atsakymas: D · FIN
Kiekviena pusė siunčia FIN, kai nebeturi duomenų, o kita pusė tai patvirtina. SYN skirtas ryšiui atidaryti; RST ryšį nutraukia.
Atsakymas: D · Persiuntimo slaptumas (forward secrecy), užtikrinamas laikinaisiais Diffie-Hellman raktų mainais
Naudojant laikinąjį (EC)DHE, kiekvienas seanso raktas gaunamas iš laikinų reikšmių, kurios sunaikinamos. Ilgalaikis raktas tik pasirašo mainus, todėl vėliau jį pavogus senas srautas neiššifruojamas.
Atsakymas: p = 21
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).
Atsakymas: x = 111
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