Formulių lapai, pagrindiniai kiekvienos temos metodų žingsniai ir 20 uždavinių, o pilni sprendimai pateikti gale.
Nustatykite bitus, kad jie saugotų −11 8 bitų dvejetainiu papildomuoju kodu. Skaitant kaip skaičių be ženklo, kokia šablono reikšmė U?
Nustatykite bitus pagal 8 bitų rezultatą 0101 1010 OR 0100 1101. Kokia rezultato reikšmė R dešimtainėje sistemoje?
Kuri formulė yra logiškai ekvivalenti p → r? Spustelėkite ją.
Duotos prielaidos r ∨ p; r → q; p → q. Kokia išvada iš jų išplaukia? Spustelėkite ją.
Karno žemėlapiu raskite minimalią F(A, B, C, D) = Σm(0, 1, 2, 5, 9, 12, 13, 14) sandaugų sumos (SOP) formą. Kiek iš viso literalų L ji turi (su brūkšneliu žymimas kintamasis skaičiuojamas kaip vienas literalas)?
Raskite minimalią F(A, B, C, D) = Σm(0, 1, 2, 3, 5, 9, 12, 14) + d(6, 8) SOP formą, kur d žymi nesvarbias sąlygas. Kiek sandaugos narių N ji turi?
Raskite mažiausią teigiamą sveikąjį skaičių x, kur x ≡ 5 (mod 11) ir x ≡ 11 (mod 13).
RSA raktas naudoja pirminius skaičius p = 5 ir q = 29 bei viešąjį rodiklį e = 13. Raskite privatųjį rodiklį d (0 < d < φ(n)).
Kam lygus rekurentinės lygties T(n) = T(n/2) + O(1) sprendinys?
Kuris teiginys apie mažojo o žymėjimą teisingas?
Kiek laiko užtrunka patikrinti, ar briauna (u, v) egzistuoja, naudojant gretimumo matricą?
Objektas saugomas kaip raktas maišos atvaizdyje, o paskui pakeičiamas laukas, kurį naudoja jo maišos funkcija. Koks tikėtinas rezultatas?
Kiek skirtingų Hamiltono ciklų H turi pilnasis grafas K4? Ciklai, besiskiriantys tik pradine viršūne ar kryptimi, laikomi tuo pačiu.
Kiek yra 3 ilgio maršrutų iš B į E? Maršrutas gali kartoti viršūnes ir briaunas. Pažymėkite skaičių N.
Kodėl SELECT price * 2 AS double_price FROM t WHERE double_price > 10 daugumoje duomenų bazių nepavyksta?
Kodėl NATURAL JOIN laikomas rizikingu gamybinėse užklausose?
Kokias saugumo savybes TLS suteikia HTTPS?
Kokia pagal Naikvisto formulę yra didžiausia be triukšmo 3 kHz kanalo bitų sparta, naudojant 4 signalo lygius?
Skyriui viename potinklyje reikia 1878 mazgų adresų. Koks yra ilgiausias prefiksas p (mažiausias potinklis), kurio pakanka?
Mazgo adresas yra 10.20.248.11/28. Koks yra paskutinio naudojamo mazgo adreso jo potinklyje ketvirtasis oktetas x?
Atsakymas: U = 245
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: R = 95
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.
OR duoda 1, kur bent vienas bitas yra 1.
Atsakymas: ¬r → ¬p
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: q
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.
Atsakymas: L = 8
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: N = 4
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 = 115
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: d = 69
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 · O(log n)
Kiekviename žingsnyje uždavinys sumažėja perpus, o darbas viename žingsnyje pastovus, todėl žingsnių yra apie log₂ n.
Atsakymas: A · n = o(n²), bet n nėra o(n)
f = o(g) reiškia, kad f(n) / g(n) artėja prie 0; n / n² artėja prie 0, bet n / n = 1 – ne.
Atsakymas: C · O(1)
Matricos įrašas u eilutėje ir v stulpelyje iš karto parodo, ar briauna egzistuoja; gretimumo sąraše gali tekti peržiūrėti u kaimynus.
Atsakymas: B · Objekto paieška gali nepavykti, nes jis yra senosios maišos reikšmės kibire
Rakto vieta buvo parinkta pagal senąją maišos reikšmę; su nauja maišos reikšme paieška ieško netinkamame kibire, todėl raktai turėtų būti nekeičiami.
Atsakymas: H = 3
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: N = 5
Laipsniai: viršūnės laipsnis yra joje susitinkančių briaunų skaičius. Kiekviena briauna turi du galus, todėl laipsnių suma lygi dvigubam briaunų skaičiui: Σ deg(v) = 2|E| (rankų paspaudimo lema). Todėl nelyginio laipsnio viršūnių skaičius lyginis. Kn turi n(n − 1)/2 briaunų, k-reguliarusis grafas su n viršūnių – nk/2, o medis su n viršūnių – n − 1 briauną.
Atsakymas: A · WHERE įvertinamas prieš SELECT sąrašą, todėl pseudonimo dar nėra
Logiškai FROM ir WHERE vykdomi prieš SELECT, todėl pakartokite reiškinį WHERE sąlygoje arba naudokite použklausą; ORDER BY pseudonimą naudoti gali, nes vykdomas po SELECT.
Atsakymas: A · Jis sujungia pagal kiekvieną vienodai pavadintą stulpelį, todėl naujas stulpelis gali nepastebimai pakeisti rezultatą
Natūralusis sujungimas sutapatina visus vienodai pavadintus stulpelius, pvz., nesusijusius „name“ ar „created_at“; aiški ON ar USING sąlyga saugesnė.
Atsakymas: A · Konfidencialumą, vientisumą ir serverio autentifikavimą
TLS šifruoja srautą, aptinka klastojimą ir sertifikatais autentifikuoja serverį (pasirinktinai ir klientą).
Atsakymas: D · 12 kbit/s
2 × 3000 × log₂ 4 = 2 × 3000 × 2 = 12,000 bit/s. Daugiau lygių padidina spartą, bet triukšmas riboja, kiek jų galima atskirti.
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 = 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).
ExamProblems · examproblems.com/courses/computer-science-fundamentals