Formulių lapai, pagrindiniai kiekvienos temos metodų žingsniai ir 20 uždavinių, o pilni sprendimai pateikti gale.
Nustatykite bitus, kad jie saugotų −77 8 bitų dvejetainiu papildomuoju kodu. Skaitant kaip skaičių be ženklo, kokia šablono reikšmė U?
Nesuspaustas vaizdas yra 640 × 480 pikselių, 16 bitų pikseliui. Kiek atminties M jis užima, KiB (1 KiB = 1024 baitai)?
Kiek iš 8 teisingumo lentelės eilučių (q → p) ↔ ¬(¬p ∧ r) yra teisinga? Pažymėkite šį skaičių N.
Kuris teiginys yra ekvivalentus ¬∀x ∀y (R(x, y) → R(y, x)), kai neigimas perkeltas iki pat vidaus? Spustelėkite jį.
Supaprastinkite F = BC + A′B′C + AB′C′ + AB′C iki minimalios sandaugų sumos formos. Kiek literalų L turi supaprastinta išraiška?
Funkcijai F(A, B, C, D) = Σm(2, 4, 6, 9, 12, 13) + d(5, 15), kur d žymi nesvarbias sąlygas, raskite esminių pagrindinių implikantų skaičių N.
Išspręskite 64x ≡ 73 (mod 75). Pateikite sprendinį x, kur 0 < x < 75.
Užšifruokite pranešimą m = 118 RSA viešuoju raktu (n, e) = (893, 7). Raskite šifrogramą c.
Koks yra šio kodo laiko sudėtingumas: for i = 1 to n: (j = 1; while j < n: j = j × 2)?
Heldo–Karpo dinaminio programavimo algoritmas tiksliai išsprendžia keliaujančio pirklio uždavinį. Koks jo vykdymo laikas n miestų?
Dvejetainio medžio šaknis yra 1, jos kairysis vaikas 2, dešinysis 3; mazgas 2 turi vaikus 4 (kairįjį) ir 5 (dešinįjį). Koks postorder apėjimas?
Koks pagrindinis šuolių sąrašo (skip list) pranašumas prieš surikiuotą susietąjį sąrašą?
Ar jungus grafas turi Oilerio ciklą, Oilerio kelią, kuris nėra ciklas, ar nei vieno? Spustelėkite savo atsakymą.
Dijkstros algoritmu raskite trumpiausio kelio nuo A iki E svertiniame grafe ilgį d(E).
Ką grąžina SELECT SUM(amount) FROM orders, kai WHERE sąlyga neatitinka jokių eilučių?
Kada R skaidymas į R1 ir R2 garantuotai yra be nuostolių?
Koks yra numatytojo šliuzo (default gateway) vaidmuo mazge?
Kokio tipo maršrutizavimo protokoluose atsiranda skaičiavimo iki begalybės problema ir kas nuo jos padeda?
Tinklą 192.168.10.0/24 reikia padalyti į bent 12 vienodų potinklių. Jei pasiskolinsite kuo mažiau bitų, kiek naudojamų mazgų H turės kiekvienas potinklis?
Mazgo adresas yra 10.20.67.178/30. Koks yra jo potinklio transliacijos adreso paskutinis skaičius (ketvirtasis oktetas) x?
Atsakymas: U = 179
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.
Atsakymas: M = 600 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: 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: ∃x ∃y (R(x, y) ∧ ¬R(y, 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: L = 3
Būlio algebra: išraiškas supaprastinančios taisyklės yra X + X′ = 1 ir X·X′ = 0, X + X = X, sugėrimas X + X·Y = X, jungimo taisyklė X·Y + X·Y′ = X, X + X′Y = X + Y ir konsensuso teorema XY + X′Z + YZ = XY + X′Z. De Morgano dėsniai (X·Y)′ paverčia X′ + Y′, o (X + Y)′ – X′·Y′. Karno žemėlapis šias taisykles taiko grafiškai: kiekviena dviejų gretimų langelių grupė yra vienas XY + XY′ = X taikymas.
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.
Didžiausios grupės, kurias galima sudaryti iš vienetų ir X.
Atsakymas: x = 7
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: c = 253
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: A · O(n log n)
Vidinis ciklas kiekvienai iš n išorinių iteracijų vykdomas apie log₂ n kartų, todėl gaunama O(n log n).
Atsakymas: D · O(n² 2ⁿ)
Yra apie n 2ⁿ būsenų, kurių kiekviena apskaičiuojama per O(n); tai eksponentinis laikas, bet daug greitesnis nei visų (n − 1)! maršrutų išbandymas.
Atsakymas: B · 4 5 2 3 1
Postorder apdoroja 4 ir 5 prieš 2, tada 3 ir galiausiai šaknį 1.
Atsakymas: B · Tikėtina O(log n) paieška naudojant kelis į priekį rodančių rodyklių lygmenis
Atsitiktiniai lygmenys leidžia paieškai praleisti daug mazgų, todėl paieškos, įterpimo ir šalinimo tikėtinas sudėtingumas yra O(log n).
Atsakymas: nei viena
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: d(E) = 20
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ą.
Kiekviena eilutė: užfiksuota viršūnė, jos galutinis atstumas ir kaimynai, kurių atstumas pagerėja.
Atsakymas: C · NULL
SUM, AVG, MIN ir MAX tuščiai aibei grąžina NULL, o COUNT grąžina 0; COALESCE(SUM(amount), 0) vietoj to duoda 0.
Atsakymas: C · Kai bendri R1 ir R2 atributai sudaro R1 arba R2 superraktą
Jei bendri atributai apibrėžia visus R1 ar R2 atributus, juos sujungus atgal gaunamos lygiai pradinės eilutės ir jokių netikrų kortežų.
Atsakymas: C · Tai maršrutizatorius, naudojamas srautui į kitus tinklus
Mazgas paketus ne vietinėms paskirties vietoms siunčia numatytajam šliuzui, paprastai savo vietiniam maršrutizatoriui.
Atsakymas: C · Atstumo vektoriaus; skaidytas horizontas (split horizon) ir atvirkštinis nuodijimas (poison reverse)
Po gedimo atstumo vektoriaus maršrutizatoriai gali toliau vienas kitam skelbti pasenusius maršrutus, lėtai didindami metriką. Skaidytas horizontas, atvirkštinis nuodijimas ir didžiausia metrika tai riboja.
Atsakymas: H = 14
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 = 179
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