Formulių lapai, pagrindiniai kiekvienos temos metodų žingsniai ir 20 uždavinių, o pilni sprendimai pateikti gale.
8 bitų seka 1011 0101 saugo sveikąjį skaičių su ženklu papildomajame kode. Kokia jo reikšmė N dešimtainėje sistemoje?
Nustatykite bitus pagal 8 bitų rezultatą 0001 1000 XOR 1110 0101. Kokia rezultato reikšmė R dešimtainėje sistemoje?
Kuri formulė yra logiškai ekvivalenti ¬(r ∨ q)? Spustelėkite ją.
Kuris teiginys yra ekvivalentus ¬∃x P(x), kai neigimas perkeltas iki pat vidaus? Spustelėkite jį.
Karno žemėlapiu raskite minimalią F(A, B, C, D) = Σm(1, 4, 5, 7, 11, 13) sandaugų sumos (SOP) formą. Kiek sandaugos narių N ji turi?
Kylančiuoju frontu valdomas T trigeris pradeda nuo Q = 0 ir gauna parodytus įėjimus. Spustelėkite pirmąjį taktinį frontą, kuriuo Q iš 1 grįžta į 0.
Raskite 23 atvirkštinį moduliu 31: skaičių x, kur 0 < x < 31 ir 23·x ≡ 1 (mod 31).
RSA raktas naudoja p = 37, q = 41 ir e = 7. Iššifruokite šifrogramą c = 276: raskite pranešimą m.
Koks yra šio kodo laiko sudėtingumas: for i = 1 to n: for j = 1 to i: atlikti O(1) darbą?
Kuris teiginys apie P ir NP yra teisingas?
Kiek mazgų turi tobulas dvejetainis medis, kurio aukštis h (aukštis skaičiuojamas briaunomis)?
Kam Kruskalo minimalaus jungiamojo medžio algoritme naudojama union-find struktūra?
Kiek skirtingų Hamiltono ciklų H turi pilnasis grafas K8? Ciklai, besiskiriantys tik pradine viršūne ar kryptimi, laikomi tuo pačiu.
Raskite svertinio grafo minimalaus karkasinio medžio bendrą svorį W.
Rodinys (view) SQL kalboje yra:
Kada lygiagrečių transakcijų tvarkaraštis vadinamas serializuojamu?
Maršrutizatorius turi maršrutus 10.0.0.0/8 ir 10.1.0.0/16. Kurį maršrutą jis naudoja paketui į 10.1.5.5?
Kodėl TCP kiekvienam ryšiui parenka nenuspėjamą pradinį sekos numerį?
Skyriui viename potinklyje reikia 1981 mazgų adresų. Koks yra ilgiausias prefiksas p (mažiausias potinklis), kurio pakanka?
Mazgo adresas yra 172.20.161.254/23. Koks jo tinklo adreso trečiasis oktetas x?
Atsakymas: N = −75
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: R = 253
Bitų nustatymas: kiekvienas bitas vertas dvejeto laipsnio (128, 64, …, 1). Vienas šešioliktainis skaitmuo yra lygiai keturi bitai, o 8 bitų dvejetainiame papildomajame kode kairysis bitas vertas −128. Bitinės operacijos atliekamos kiekvienai bito pozicijai atskirai.
XOR duoda 1, kur du bitai skiriasi.
Atsakymas: ¬r ∧ ¬q
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).
Stulpeliai po brūkšniu yra variantai pateikta tvarka.
Atsakymas: ∀x ¬P(x)
Kvantoriai ir argumentai: ¬∀x P(x) ≡ ∃x ¬P(x) ir ¬∃x P(x) ≡ ∀x ¬P(x). Perkelkite neigimą į vidų, sukeiskite kiekvieną kvantorių, pro kurį jis praeina, o vidinę formulę paneikite teiginių logikos dėsniais, pavyzdžiui, ¬(a → b) ≡ a ∧ ¬b. Argumentas yra teisingas (galiojantis), kai išvada lygi 1 kiekvienoje eilutėje, kurioje visos prielaidos lygios 1. Viena eilutė su teisingomis prielaidomis ir klaidinga išvada yra kontrapavyzdys ir rodo, kad argumentas negalioja.
Kiti variantai arba palieka kvantorių nepakeistą, arba keičia kvantorių tvarką, arba netinkamai neigia vidinę formulę.
Atsakymas: N = 5
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.
Atsakymas: taktinis frontas 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.
T trigeris kiekvienu kylančiuoju frontu perjungia, kai T = 1, ir išlaiko, kai T = 0.
Atsakymas: 23−1 mod 31 = 27
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·23 (mod 31).
Atsakymas: m = 224
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: C · O(n²)
Vidinis kūnas iš viso vykdomas n(n + 1) / 2 kartų, o tai vis tiek kvadratinis dydis.
Atsakymas: B · Kiekvienas P klasės uždavinys taip pat priklauso NP
P ⊆ NP: jei uždavinį galite greitai išspręsti, galite ir greitai patikrinti sprendinį. Ar P = NP, vis dar yra atviras klausimas.
Atsakymas: A · 2h+1 − 1
Susumavus 1 + 2 + 4 + ... + 2h gaunama 2h+1 − 1; pavyzdžiui, kai aukštis 2, yra 7 mazgai.
Atsakymas: B · Patikrinti, ar abu briaunos galai jau sujungti
Find parodo, ar abu galai yra toje pačioje komponentėje; jei ne, briauna pridedama, o union sujungia komponentes.
Atsakymas: H = 2520
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: W = 32
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 · Išsaugota užklausa, veikianti kaip virtuali lentelė
Rodinys saugo SELECT sakinį; jį užklausus vykdoma pagrindinė užklausa (materializuoti rodiniai saugo rezultatą).
Atsakymas: C · Kai jo poveikis lygiavertis kuriam nors tų pačių transakcijų nuosekliam vykdymui
Serializuojamumas yra pagrindinis lygiagretumo teisingumo kriterijus: susipynusio vykdymo rezultatas turi būti lygus kurios nors „po vieną“ tvarkos rezultatui.
Atsakymas: B · 10.1.0.0/16, nes tai ilgiausias sutampantis prefiksas
IP persiuntimas naudoja ilgiausio prefikso atitikimą: iš visų paskirtį atitinkančių maršrutų pasirenkamas tas, kurio kaukė ilgiausia.
Atsakymas: C · Kad nebūtų painiojama su senais segmentais ir būtų sunkiau įterpti suklastotus segmentus
Atsitiktiniai pradiniai sekos numeriai neleidžia priimti pavėlavusių segmentų iš senų ryšių ir apsunkina ne kelyje esantiems užpuolikams klastoti galiojančius segmentus.
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 = 160
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).
ExamProblems · examproblems.com/courses/computer-science-fundamentals