Formulių lapai, pagrindiniai kiekvienos temos metodų žingsniai ir 20 uždavinių, o pilni sprendimai pateikti gale.
8 bitų seka 0011 0101 saugo sveikąjį skaičių su ženklu papildomajame kode. Kokia jo reikšmė N dešimtainėje sistemoje?
Nustatykite bitus pagal 8 bitų rezultatą 0001 1011 XOR 1100 0011. Kokia rezultato reikšmė R dešimtainėje sistemoje?
Ar (p ∨ r) → (p ∧ r) yra tautologija, prieštara ar kontingencija? Spustelėkite savo atsakymą.
Kuris teiginys yra ekvivalentus ¬∀x (F(x) → ∃y R(x, y)), kai neigimas perkeltas iki pat vidaus? Spustelėkite jį.
4 į 1 multiplekserio pasirinkimo įėjimai yra S₁ = A ir S₀ = B, o duomenų įėjimai prijungti prie I₀ = C′, I₁ = C′, I₂ = 1, 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, 1, 3, 7, 11, 13, 15) + d(5, 6, 9), kur d žymi nesvarbias sąlygas, raskite esminių pagrindinių implikantų skaičių N.
Raskite 35 atvirkštinį moduliu 89: skaičių x, kur 0 < x < 89 ir 35·x ≡ 1 (mod 89).
Užšifruokite pranešimą m = 1268 RSA viešuoju raktu (n, e) = (1457, 7). Raskite šifrogramą c.
Kodėl daug bibliotekinių rikiavimo procedūrų labai mažiems daliniams masyvams pereina prie rikiavimo įterpimu?
Ar 22n priklauso O(2ⁿ)?
Turite nuorodą į mazgą sąrašo viduryje. Kuriame sąraše jį galite pašalinti per O(1)?
Kiekvienam masyvo elementui norite rasti artimiausią didesnį elementą į dešinę, iš viso per O(n). Kuri struktūra padeda?
Ar jungus grafas turi Oilerio ciklą, Oilerio kelią, kuris nėra ciklas, ar nei vieno? Spustelėkite savo atsakymą.
Kiek yra 2 ilgio uždarų maršrutų, prasidedančių ir pasibaigiančių ties A? Maršrutas gali kartoti viršūnes ir briaunas. Pažymėkite skaičių N.
Antroji normalinė forma (2NF) pašalina:
Kuri SQL galimybė geriausiai tinka visiems vadovui pavaldiems darbuotojams rasti nežinomo gylio organizacijos medyje?
Koks yra numatytojo šliuzo (default gateway) vaidmuo mazge?
Tinklą 192.168.1.0/24 reikia padalyti į bent 5 potinklius, kuriuose būtų iki 25 mazgų. Kuris prefikso ilgis tinka geriausiai?
Tinklas 172.29.0.0/16 padalytas į vienodus potinklius su prefiksu /20. Kiek yra potinklių N?
Mazgo adresas yra 172.20.200.213/18. Koks jo tinklo adreso trečiasis oktetas x?
Atsakymas: N = 53
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: R = 216
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.
XOR duoda 1, kur du bitai skiriasi.
Atsakymas: kontingencija
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).
Atsakymas: ∃x (F(x) ∧ ∀y ¬R(x, y))
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: N = 5
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 = 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.
Didžiausios grupės, kurias galima sudaryti iš vienetų ir X.
Atsakymas: 35−1 mod 89 = 28
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·35 (mod 89).
Atsakymas: c = 1409
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 · Rikiavimas įterpimu turi mažas pridėtines sąnaudas ir yra greitas su mažomis ar beveik surikiuotomis įvestimis
Mažiems n paprastas rikiavimo įterpimu ciklas aplenkia greitojo rikiavimo ar rikiavimo suliejimu rekursijos pridėtines sąnaudas, nors jis ir O(n²).
Atsakymas: A · Ne, nes 22n = 4ⁿ, o 4ⁿ / 2ⁿ = 2ⁿ auga neaprėžtai
Prie laipsnio rodiklio pridėta konstanta duoda pastovų daugiklį, bet konstanta, iš kurios dauginamas laipsnio rodiklis, pakeičia pagrindą ir augimo greitį.
Atsakymas: D · Dvikrypčiame susietajame sąraše
Dvikrypčio sąrašo mazgas žino savo pirmtaką, todėl galite tiesiogiai sujungti prev ir next; vienkrypčiame sąraše pirmtako reikia ieškoti.
Atsakymas: D · Stekas, kuriame laikomi atsakymo laukiantys elementai
Einant iš kairės į dešinę, iš steko išimami visi už einamąjį mažesni elementai (einamasis elementas yra jų atsakymas), tada jis įdedamas; kiekvienas elementas juda daugiausia dukart.
Atsakymas: Oilerio kelias, ne ciklas
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ų.
Oilerio kelias prasideda vienoje nelyginėje viršūnėje ir baigiasi kitoje.
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: A · Neraktinių stulpelių dalines priklausomybes nuo sudėtinio rakto dalies
2NF reikalauja 1NF ir kad kiekvienas neraktinis atributas priklausytų nuo viso rakto, o ne tik nuo jo dalies.
Atsakymas: D · Rekursinis bendrasis lentelės reiškinys (WITH RECURSIVE)
Rekursinis CTE pradeda nuo inkarinės užklausos ir pakartotinai sujungia ankstesnį rezultatą su lentele, todėl tvarko bet kokio gylio hierarchijas.
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 · /27
/27 duoda 8 potinklius po 30 tinkamų mazgų. /26 duoda tik 4 potinklius, o /28 leidžia tik 14 mazgų potinklyje.
Atsakymas: N = 16
IPv4 subnetting: an address has 32 bits. The prefix /p says how many leading bits identify the network; the remaining 32 − p bits number the hosts. A subnet has 2³²⁻ᵖ addresses, but the first (network address) and last (broadcast address) cannot be given to hosts, so 2³²⁻ᵖ − 2 hosts fit. Exceptions: a /31 (point-to-point link, RFC 3021) uses both of its 2 addresses for hosts, and a /32 is one single address (a single host or a loopback).
Kiekviename /20 potinklyje yra 212 − 2 = 4094 naudojamų mazgų adresų.
Atsakymas: x = 192
IPv4 subnetting: an address has 32 bits. The prefix /p says how many leading bits identify the network; the remaining 32 − p bits number the hosts. A subnet has 2³²⁻ᵖ addresses, but the first (network address) and last (broadcast address) cannot be given to hosts, so 2³²⁻ᵖ − 2 hosts fit. Exceptions: a /31 (point-to-point link, RFC 3021) uses both of its 2 addresses for hosts, and a /32 is one single address (a single host or a loopback).
ExamProblems · examproblems.com/courses/computer-science-fundamentals