Formulių lapai, pagrindiniai kiekvienos temos metodų žingsniai ir 20 uždavinių, o pilni sprendimai pateikti gale.
8 bitų seka 1111 1010 saugo sveikąjį skaičių su ženklu papildomajame kode. Kokia jo reikšmė N dešimtainėje sistemoje?
Nesuspaustas vaizdas yra 512 × 512 pikselių, 24 bitų pikseliui. Kiek atminties M jis užima, KiB (1 KiB = 1024 baitai)?
Kiek iš 8 teisingumo lentelės eilučių (¬a ∧ (a → c)) → (b → c) yra teisinga? Pažymėkite šį skaičių N.
Argumentas su prielaidomis b → a; a ir išvada b 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₀ = C, I₁ = C′, I₂ = 1, I₃ = 0. Kiek iš 8 A, B ir C derinių duoda išėjimą F = 1? Raskite N.
Kylančiuoju frontu valdomas JK trigeris pradeda nuo Q = 0 ir gauna parodytus įėjimus. Spustelėkite pirmąjį taktinį frontą, kuriuo Q iš 1 grįžta į 0.
Raskite 23 atvirkštinį moduliu 68: skaičių x, kur 0 < x < 68 ir 23·x ≡ 1 (mod 68).
Išspręskite 35x ≡ 30 (mod 65). Pateikite mažiausią teigiamą sprendinį x.
Koks yra standartinio dinaminio programavimo algoritmo, ieškančio m ir n ilgio eilučių ilgiausio bendro posekio, laiko sudėtingumas?
Kodėl dvejetainė paieška vienkrypčiame susietajame sąraše neužtikrina O(log n) laiko?
Prefiksų medis (trie) ypač efektyvus:
Kodėl duomenų bazės indeksams dažnai naudoja B+ medžius, o ne paprastus B medžius?
Ar jungus grafas turi Oilerio ciklą, Oilerio kelią, kuris nėra ciklas, ar nei vieno? Spustelėkite savo atsakymą.
Kiek yra 2 ilgio maršrutų iš B į D? Maršrutas gali kartoti viršūnes ir briaunas. Pažymėkite skaičių N.
Antroji normalinė forma (2NF) pašalina:
Lentelės b stulpelyje y yra reikšmės 1, 2 ir NULL. Ką grąžina SELECT * FROM a WHERE x NOT IN (SELECT y FROM b)?
Ką nurodo DNS MX įrašas?
Studentas paleidžia žaidimų serverį kompiuteryje už namų NAT maršrutizatoriaus. Draugai iš interneto negali prisijungti. Koks įprastas sprendimas?
Potinklio kaukė yra 255.255.255.240. Kiek naudojamų mazgų adresų H jame yra?
Mazgo adresas yra 10.20.227.180/25. Koks yra jo tinklo adreso ketvirtasis oktetas x?
Atsakymas: N = −6
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 = 768 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: N = 7
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: 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 = 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: taktinis frontas 6
Trigeriai ir skaitikliai: trigeris keičiasi tik aktyviu taktinio signalo frontu. D nukopijuoja savo įėjimą (Q⁺ = D); T perjungia, kai T = 1; JK išlaiko esant 00, nustato į 0 esant 01, nustato į 1 esant 10 ir perjungia esant 11. n bitų dvejetainis skaitiklis turi 2ⁿ būsenų ir skaičiuoja moduliu 2ⁿ; mod-N skaitiklis skaičiuoja 0, 1, …, N − 1 ir grįžta į 0, jam reikia mažiausiai n trigerių, kad 2ⁿ ≥ N. Kiekviena nuosekliojo (ripple) skaitiklio pakopa perpus sumažina dažnį, todėl paskutinis mod-N skaitiklio išėjimas veikia fclk/N dažniu. n trigerių Johnsono skaitiklis turi 2n būsenų, žiedinis – n.
JK trigeris: 00 išlaiko, 01 nustato į 0 (Q = 0), 10 nustato į 1 (Q = 1), 11 perjungia.
Atsakymas: 23−1 mod 68 = 3
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·23 (mod 68).
Atsakymas: x = 12
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: B · O(mn)
Lentelėje yra (m + 1)(n + 1) langelių, ir kiekvienas apskaičiuojamas per O(1) iš kaimynų.
Atsakymas: C · Iki vidurinio elemento nueiti reikia O(n) žingsnių, nes nėra tiesioginės prieigos pagal indeksą
Dvejetainei paieškai reikia O(1) prieigos prie vidurio; susietajame sąraše ėjimas iki jo kainuoja tiesinį laiką, todėl iš viso gaunama O(n).
Atsakymas: D · Prefiksų paieškai, pavyzdžiui, automatiniam užbaigimui
Trie saugo eilutes simboliais keliuose, todėl paieška ir prefiksų užklausos trunka laiką, proporcingą rakto ilgiui.
Atsakymas: D · Visi įrašai yra susietuose lapuose, todėl intervalų peržiūra efektyvi
B+ medyje vidiniai mazgai tik nukreipia paiešką, o lapai susieti raktų tvarka, todėl intervalo užklausa randa pirmąjį raktą ir tada eina lapais.
Atsakymas: Oilerio 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ų.
Atsakymas: N = 1
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: C · Visai jokių eilučių
Palyginimas su NULL yra UNKNOWN, todėl visa sąlyga niekada nebūna TRUE; NOT EXISTS ar NULL reikšmių atfiltravimas padeda išvengti šių spąstų.
Atsakymas: C · Pašto serverius, priimančius domeno el. laiškus
MX (mail exchange) įrašai išvardija pašto serverius su prioritetais, kad siunčiantys serveriai žinotų, kur pristatyti to domeno laiškus.
Atsakymas: D · Maršrutizatoriuje sukonfigūruoti prievado persiuntimą į kompiuterio privatų adresą
NAT sukuria susiejimus tik ryšiams, pradėtiems iš vidaus. Prievado persiuntimo taisyklė susieja viešąjį prievadą su vidiniu mazgu, kad įeinantys ryšiai jį pasiektų.
Atsakymas: H = 14
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).
Atsakymas: x = 128
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