Formulių lapai, pagrindiniai kiekvienos temos metodų žingsniai ir 20 uždavinių, o pilni sprendimai pateikti gale.
8 bitų seka 1001 1000 saugo sveikąjį skaičių su ženklu papildomajame kode. Kokia jo reikšmė N dešimtainėje sistemoje?
Nesuspaustas vaizdas yra 1920 × 1080 pikselių, 24 bitų pikseliui. Kiek atminties M jis užima, KiB (1 KiB = 1024 baitai)?
Norite įrodyti ¬q → ¬r prieštara. Kurį teiginį darote prielaida pradžioje? Spustelėkite jį.
Argumentas su prielaidomis b → a; ¬b ir išvada ¬a negalioja. Spustelėkite teisingumo lentelės eilutę, kuri yra kontrapavyzdys.
Karno žemėlapiu raskite minimalią F(A, B, C) = Σm(0, 1, 4, 5, 6) sandaugų sumos (SOP) formą. Kiek sandaugos narių N ji turi?
Raskite minimalią F(A, B, C, D) = Σm(2, 8, 12, 13) + d(0, 9, 14) SOP formą, kur d žymi nesvarbias sąlygas. Kiek literalų L ji turi?
Raskite mažiausią teigiamą sveikąjį skaičių x, kur x ≡ 2 (mod 3) ir x ≡ 12 (mod 13).
61 yra pirminis skaičius. Pasinaudokite mažąja Ferma teorema ir raskite 2651552 mod 61.
Koks yra Bellmano–Fordo algoritmo laiko sudėtingumas grafui su V viršūnių ir E briaunų?
Kuris rėžis teisingas log(n!)?
Kodėl masyvo apėjimas praktikoje dažnai daug greitesnis nei tokio pat ilgio susietojo sąrašo apėjimas?
AVL mazgas nesubalansuotas, nes jo kairiojo vaiko dešinysis pomedis tapo per aukštas (kairė–dešinė atvejis). Koks taisymas taikomas?
Kiek skirtingų Hamiltono ciklų H turi pilnasis grafas K8? Ciklai, besiskiriantys tik pradine viršūne ar kryptimi, laikomi tuo pačiu.
Dijkstros algoritmu raskite trumpiausio kelio nuo A iki F svertiniame grafe ilgį d(F).
Ką reiškia funkcinė priklausomybė A → B?
Ką apskaičiuoja SELECT day, SUM(amount) OVER (ORDER BY day) FROM sales?
Kokį terpės prieigos metodą naudojo klasikinis bendrosios terpės (pusiau dupleksinis) Ethernet?
TCP perkrovos valdymo „lėto starto“ (slow start) fazė:
Skyriui viename potinklyje reikia 273 mazgų adresų. Koks yra ilgiausias prefiksas p (mažiausias potinklis), kurio pakanka?
Tinklas 192.168.90.0/24 VLSM būdu dalijamas šiems LAN: A: 3 mazgai, B: 28 mazgai, C: 17 mazgai, D: 92 mazgai. Potinkliai skiriami nuo .0 aukštyn, pirmiausia LAN su daugiausia mazgų, kiekvienam mažiausias tinkamas potinklis. Koks LAN B tinklo adreso ketvirtasis oktetas x?
Atsakymas: N = −104
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: M = 6075 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: ¬q ∧ ¬¬r
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).
Jei prielaida lemia prieštarą, implikacija turi būti teisinga.
Atsakymas: a = 1, b = 0
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.
Tokios formos argumentas atrodo kaip galiojanti taisyklė, bet vienos eilutės pakanka parodyti, kad ji negalioja.
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: L = 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.
Didžiausios grupės, kurias galima sudaryti iš vienetų ir X.
Atsakymas: x = 38
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: 2651552 mod 61 = 9
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(V × E)
Kiekvienas iš V − 1 etapų relaksuoja visas E briaunas, todėl gaunama O(VE); mainais algoritmas tvarkosi su neigiamais briaunų svoriais.
Atsakymas: A · Θ(n log n)
log(n!) ≤ n log n, o didžiausi n / 2 daugiklių duoda log(n!) ≥ (n / 2) log(n / 2); todėl rikiavimui palyginimais reikia Ω(n log n).
Atsakymas: A · Masyvo elementai išdėstyti vientisai, todėl gerai išnaudoja procesoriaus podėlį (cache)
Vientisa atmintis užtikrina gerą kreipčių lokalumą, o susieti mazgai gali būti išbarstyti ir sukelti daug podėlio praleidimų.
Atsakymas: B · Kairysis posūkis kairiajame vaike, tada dešinysis posūkis mazge
Pirmasis posūkis kairė–dešinė atvejį paverčia kairė–kairė atveju, kurį tada ištaiso dešinysis posūkis nesubalansuotame mazge.
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: d(F) = 28
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 · Kiekviena A reikšmė susijusi su lygiai viena B reikšme
A → B reiškia, kad bet kurios dvi eilutės su ta pačia A reikšme turi turėti tą pačią B reikšmę; A apibrėžia B.
Atsakymas: B · Kaupiamąją amount sumą, sutvarkytą pagal day
Esant ORDER BY ir nenurodžius rėmo, langas tęsiasi nuo pirmosios eilutės iki einamosios (ir jai lygių), todėl gaunama kaupiamoji suma.
Atsakymas: B · CSMA/CD
Daugkartinė prieiga su nešlio jutimu ir kolizijų aptikimu: aptikusios koliziją stotys sustoja ir bando vėl po atsitiktinės delsos. Visiškai dupleksiniame komutuojamame Ethernet kolizijų nėra.
Atsakymas: C · Eksponentiškai didina perkrovos langą, kol pasiekiama riba arba įvyksta praradimas
Lėtas startas eksponentiškai didina perkrovos langą; peržengus ribą, perkrovos vengimo fazė jį didina tiesiškai, o praradimas jį sumažina.
Atsakymas: p = 23
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 = 128
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 B: 192.168.90.128/27.
ExamProblems · examproblems.com/courses/computer-science-fundamentals