Formulių lapai, pagrindiniai kiekvienos temos metodų žingsniai ir 20 uždavinių, o pilni sprendimai pateikti gale.
Nustatykite bitus, kad jie saugotų −112 8 bitų dvejetainiu papildomuoju kodu. Skaitant kaip skaičių be ženklo, kokia šablono reikšmė U?
Sistema kiekvienam iš 1350 elementų turi suteikti atskirą tokio pat ilgio dvejetainį kodą. Kiek mažiausiai bitų b reikia?
Norite įrodyti (q ∧ p) → r kontrapozicija. Kurią implikaciją įrodote vietoj jos? Spustelėkite ją.
Argumentas su prielaidomis r → p; ¬r ir išvada ¬p negalioja. Spustelėkite teisingumo lentelės eilutę, kuri yra kontrapavyzdys.
4 į 1 multiplekserio pasirinkimo įėjimai yra S₁ = A ir S₀ = B, o duomenų įėjimai prijungti prie I₀ = 0, I₁ = 1, I₂ = C, I₃ = C′. Kiek iš 8 A, B ir C derinių duoda išėjimą F = 1? Raskite N.
Funkcijai F(A, B, C, D) = Σm(0, 4, 7, 8, 9, 12) + d(2, 14), kur d žymi nesvarbias sąlygas, raskite esminių pagrindinių implikantų skaičių N.
Raskite 27 atvirkštinį moduliu 31: skaičių x, kur 0 < x < 31 ir 27·x ≡ 1 (mod 31).
RSA raktas naudoja p = 29, q = 41 ir e = 3. Iššifruokite šifrogramą c = 523: raskite pranešimą m.
Kuris teiginys apie rekursinę funkciją be pasiekiamo bazinio atvejo teisingas?
Heldo–Karpo dinaminio programavimo algoritmas tiksliai išsprendžia keliaujančio pirklio uždavinį. Koks jo vykdymo laikas n miestų?
Žiedinis buferis (ring buffer) dažniausiai naudojamas įgyvendinti:
Kuo radix medis (suspaustas Trie) pranašesnis už paprastą Trie?
Jungus grafas turi 19 viršūnių ir 25 briaunų. Kiek briaunų k reikia pašalinti, kad liktų karkasinis medis?
Dijkstros algoritmu raskite trumpiausio kelio nuo A iki F svertiniame grafe ilgį d(F).
Ką grąžina SELECT name, CASE WHEN grade >= 5,5 THEN 'pass' ELSE 'fail' END FROM results?
Kada lygiagrečių transakcijų tvarkaraštis vadinamas serializuojamu?
Kuris vienas prefiksas apibendrina ir 192.168.0.0/24, ir 192.168.1.0/24?
DNS podėlio apnuodijimo (DNS cache poisoning) ataka siekiama:
Skyriui viename potinklyje reikia 1689 mazgų adresų. Koks yra ilgiausias prefiksas p (mažiausias potinklis), kurio pakanka?
Tinklas 192.168.136.0/24 VLSM būdu dalijamas šiems LAN: A: 23 mazgai, B: 117 mazgai, C: 26 mazgai, D: 6 mazgai. Potinkliai skiriami nuo .0 aukštyn, pirmiausia LAN su daugiausia mazgų, kiekvienam mažiausias tinkamas potinklis. Koks LAN C tinklo adreso ketvirtasis oktetas x?
Atsakymas: U = 144
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 = 11 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: ¬r → ¬(q ∧ 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).
Kontrapozicija yra ekvivalenti pradiniam teiginiui, todėl ją įrodžius įrodomas ir teiginys.
Atsakymas: p = 1, r = 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 = 4
Multiplekseris: 2ⁿ į 1 multiplekseris perduoda vieną iš savo duomenų įėjimų į išėjimą; pasirinkimo linijos, skaitomos kaip dvejetainis skaičius, nurodo kurį. 4 į 1 MUX su pasirinkimo įėjimais S₁S₀ = AB, F = A′B′·I₀ + A′B·I₁ + AB′·I₂ + AB·I₃. Duomenų įėjimus prijungus prie 0, 1, C arba C′, MUX gali sukurti bet kurią A, B ir C funkciją; tai dažnas būdas sudaryti logiką viena mikroschema.
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: 27−1 mod 31 = 23
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·27 (mod 31).
Atsakymas: m = 146
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 · Ji vis kviečia save, kol perpildomas kvietimų stekas
Be bazinio atvejo rekursija niekada nesibaigia; praktiškai pritrūksta atminties steko rėmeliams ir programa nulūžta.
Atsakymas: B · 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: D · Fiksuoto dydžio eilę
Žiedinis buferis naudoja persisukančius head ir tail indeksus, todėl enqueue ir dequeue atliekami per O(1) fiksuotoje atmintyje.
Atsakymas: D · Jis vieno vaiko mazgų grandines sujungia į vieną eilute pažymėtą briauną
Sutraukus nesišakojančius kelius, sumažėja mazgų skaičius ir naudojama atmintis, o paieška pagal prefiksą išlieka.
Atsakymas: k = 7
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) = 14
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: A · Kiekvieną vardą su žyme 'pass' arba 'fail', priklausomai nuo pažymio
CASE reiškinys įvertina savo sąlygas kiekvienai eilutei ir grąžina atitinkančią reikšmę, todėl kiekviena eilutė gauna žymę.
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: C · 192.168.0.0/23
0 ir 1 sutampa visais trečiojo okteto bitais, išskyrus paskutinį, todėl vienu bitu trumpesnis prefiksas (/23), prasidedantis nuo 192.168.0.0, tiksliai apima abu.
Atsakymas: B · Priversti resolverį išsaugoti netikrą domeno IP adresą
Apnuodijimas į resolverio podėlį įterpia suklastotus įrašus. DNSSEC prideda parašus, kad resolveriai galėtų patikrinti įrašus.
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 = 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 C: 192.168.136.128/27.
ExamProblems · examproblems.com/courses/computer-science-fundamentals