Formulių lapai, pagrindiniai kiekvienos temos metodų žingsniai ir 20 uždavinių, o pilni sprendimai pateikti gale.
Nustatykite bitus, kad jie saugotų −91 8 bitų dvejetainiu papildomuoju kodu. Skaitant kaip skaičių be ženklo, kokia šablono reikšmė U?
Sistema kiekvienam iš 790 elementų turi suteikti atskirą tokio pat ilgio dvejetainį kodą. Kiek mažiausiai bitų b reikia?
Norite įrodyti ¬c → ¬b kontrapozicija. Kurią implikaciją įrodote vietoj jos? Spustelėkite ją.
Kiek iš 16 teisingumo lentelės eilučių daro (q ∨ ¬(¬r ∨ q)) ∧ (¬s ∧ (r ∨ p)) teisingą? Pažymėkite šį skaičių N.
Karno žemėlapiu raskite minimalią F(A, B, C) = Σm(0, 1, 3, 4, 6) sumų sandaugos (POS) formą. Kiek sumos narių (daugiklių) N ji turi?
Funkcijai F(A, B, C, D) = Σm(3, 4, 8, 9, 12, 14) + d(5, 10, 11, 13), kur d žymi nesvarbias sąlygas, raskite esminių pagrindinių implikantų skaičių N.
Raskite mažiausią teigiamą sveikąjį skaičių x, kur x ≡ 1 (mod 5) ir x ≡ 3 (mod 7).
RSA raktas naudoja pirminius skaičius p = 13 ir q = 29 bei viešąjį rodiklį e = 17. Raskite privatųjį rodiklį d (0 < d < φ(n)).
Koks yra standartinio dinaminio programavimo algoritmo, ieškančio m ir n ilgio eilučių ilgiausio bendro posekio, laiko sudėtingumas?
Kuris NP klasės apibrėžimas teisingas?
AVL medžiai ir raudonai juodi medžiai garantuoja:
Įterpus raktą į AVL medį, mazgo kairysis pomedis tampa per aukštas, o naujas raktas pateko į jo kairiojo vaiko kairįjį pomedį (kairė–kairė atvejis). Koks taisymas taikomas?
Jungus grafas turi 18 viršūnių ir 25 briaunų. Kiek briaunų k reikia pašalinti, kad liktų karkasinis medis?
Kiek yra 2 ilgio uždarų maršrutų, prasidedančių ir pasibaigiančių ties D? Maršrutas gali kartoti viršūnes ir briaunas. Pažymėkite skaičių N.
Kas yra duomenų bazės trigeris?
Užklausa FROM customers c LEFT JOIN orders o ON o.customer_id = c.id WHERE o.status = 'paid' netikėtai praranda klientus be užsakymų. Kodėl?
Koks pagrindinis HTTP metodų GET ir POST skirtumas?
Kuris mechanizmas apsaugo nuo transliavimo kilpų tinkle su perteklinėmis jungtimis tarp komutatorių?
Tinklą 192.168.10.0/24 reikia padalyti į bent 8 vienodų potinklių. Jei pasiskolinsite kuo mažiau bitų, kiek naudojamų mazgų H turės kiekvienas potinklis?
Tinklas 192.168.21.0/24 VLSM būdu dalijamas šiems LAN: A: 23 mazgai, B: 29 mazgai, C: 14 mazgai, D: 6 mazgai, E: 37 mazgai. Potinkliai skiriami nuo .0 aukštyn, pirmiausia LAN su daugiausia mazgų, kiekvienam mažiausias tinkamas potinklis. Koks LAN D tinklo adreso ketvirtasis oktetas x?
Atsakymas: U = 165
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: b = 10 bit
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 → ¬¬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 = 5
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 = 2
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 = 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 = 31
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 = 257
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(mn)
Lentelėje yra (m + 1)(n + 1) langelių, ir kiekvienas apskaičiuojamas per O(1) iš kaimynų.
Atsakymas: B · Sprendimo uždaviniai, kurių teigiamus atsakymus, turint sertifikatą, galima patikrinti per polinominį laiką
NP uždaviniui pasiūlytą sprendinį (sertifikatą) galima greitai patikrinti, pvz., patikrinti, ar duotas priskyrimas tenkina loginę formulę.
Atsakymas: B · O(log n) aukštį perbalansavimo dėka
Savaime balansuojantys medžiai išlaiko logaritminį aukštį, todėl paieška, įterpimas ir šalinimas blogiausiu atveju yra O(log n).
Atsakymas: D · Vienas dešinysis posūkis nesubalansuotame mazge
Kairė–kairė atveju vienas dešinysis posūkis pakelia kairįjį vaiką aukštyn ir atkuria balansą; zigzago atvejams reikia dvigubo posūkio.
Atsakymas: k = 8
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 = 2
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: D · Kodas, automatiškai vykdomas, kai lentelėje įvyksta nurodytas įvykis, pvz., INSERT, UPDATE ar DELETE
Trigeriai vykdomi automatiškai prieš duomenų pakeitimus ar po jų, pvz., audito žurnalui įrašyti ar sudėtingai taisyklei užtikrinti.
Atsakymas: B · WHERE sąlyga o lentelei atmeta NULL reikšmėmis užpildytas eilutes ir paverčia sujungimą vidiniu
Nesutampančių eilučių o.status yra NULL, todėl WHERE patikra nėra TRUE; perkėlus sąlygą į ON sąlygą, paliekamas kiekvienas klientas.
Atsakymas: D · GET gauna išteklių, POST pateikia duomenis užklausos turinyje
GET prašo ištekliaus ir neturėtų keisti serverio būsenos. POST siunčia duomenis, pvz., formą, užklausos turinyje, kad serveris juos apdorotų.
Atsakymas: C · Spanning Tree Protocol
STP išrenka šakninį tiltą (root bridge) ir užblokuoja perteklinius kelius, atblokuodamas juos, jei sugenda aktyvi jungtis.
Atsakymas: H = 30
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 = 144
VLSM: kiekvienas LAN gauna mažiausią potinklį, kuriame 2ʰ − 2 ≥ jo mazgų skaičius, t. y. prefiksą 32 − h. Pirmiausia skiriant didžiausius potinklius, kiekvienas blokas lygiuojamas į savo dydžio kartotinį, todėl tinklų adresai gaunami sudedant bloko dydžius.
LAN D: 192.168.21.144/29.
ExamProblems · examproblems.com/courses/computer-science-fundamentals