Formulių lapai, pagrindiniai kiekvienos temos metodų žingsniai ir 20 uždavinių, o pilni sprendimai pateikti gale.
8 bitų seka 1010 0010 saugo sveikąjį skaičių su ženklu papildomajame kode. Kokia jo reikšmė N dešimtainėje sistemoje?
Nustatykite bitus pagal 8 bitų rezultatą 0010 1111 AND 0100 1000. Kokia rezultato reikšmė R dešimtainėje sistemoje?
Kuri formulė yra logiškai ekvivalenti q ↔ p? Spustelėkite ją.
Argumentas su prielaidomis q → (p ∨ r); q 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₁ = C, I₂ = 1, I₃ = 1. Kiek iš 8 A, B ir C derinių duoda išėjimą F = 1? Raskite N.
Sinchroninis mod-6 skaitiklis skaičiuoja 0, 1, …, 5 ir tada grįžta į 0. Jis pradeda nuo 4. Kokį skaičių Q (dešimtainiu pavidalu) jis rodo po 19 taktinių impulsų?
Raskite 29 atvirkštinį moduliu 89: skaičių x, kur 0 < x < 89 ir 29·x ≡ 1 (mod 89).
Kartotiniu kėlimu kvadratu raskite 9155 mod 26.
Kam lygus rekurentinės lygties T(n) = T(n − 1) + O(n) sprendinys?
Kokia amortizuotoji dvejetainio skaitiklio padidinimo kaina, žinant, kad vienas padidinimas gali pakeisti daug bitų?
AVL medžiai ir raudonai juodi medžiai garantuoja:
Ką skleidžiamasis medis (splay tree) atlieka po kiekvienos prieigos?
Jungus grafas turi 11 viršūnių ir 13 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).
Kuri užklausa grąžina didžiausią atlyginimą kiekviename skyriuje?
Lentelėje yra milijonas eilučių, o loginio tipo stulpelis is_active 95% iš jų yra TRUE. Kodėl optimizatorius užklausai WHERE is_active = TRUE gali nenaudoti is_active indekso?
Kuris vienas prefiksas apibendrina ir 192.168.0.0/24, ir 192.168.1.0/24?
Po pasikartojančių kolizijų klasikinio Ethernet stotys laukimo laiką renkasi iš intervalo, kuris kaskart padvigubėja. Kodėl?
Tinklas 192.168.159.0/24 padalytas į /28 potinklius, sunumeruotus 1, 2, 3, … nuo mažiausio adreso (1 potinklis prasideda nuo .0). Koks potinklio Nr. 5 tinklo adreso ketvirtasis oktetas x?
Mazgo adresas yra 172.20.212.178/23. Koks jo tinklo adreso trečiasis oktetas x?
Atsakymas: N = −94
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 = 8
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.
AND duoda 1 tik ten, kur abu bitai yra 1.
Atsakymas: (q → p) ∧ (p → q)
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).
Stulpeliai po brūkšniu yra variantai pateikta tvarka.
Atsakymas: p = 0, q = 1, r = 1
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 = 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: Q = 5
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.
Kas 6 impulsų skaitiklis grįžta į tą pačią būseną.
Atsakymas: 29−1 mod 89 = 43
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·29 (mod 89).
Atsakymas: 9155 mod 26 = 3
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(n²)
Darbas susumuoja iki maždaug n² / 2; tai rikiavimo išrinkimu arba greitojo rikiavimo su blogiausiu atraminiu elementu rekurentinė lygtis.
Atsakymas: A · O(1) vienam padidinimui
Per n padidinimų i-asis bitas pasikeičia apie n / 2ⁱ kartų, todėl iš viso yra mažiau nei 2n pakeitimų, vidutiniškai O(1) kiekvienam.
Atsakymas: C · 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: C · Posūkiais iškelia pasiektą mazgą į šaknį
Skleidimas posūkiais perkelia pasiektą mazgą į šaknį; viena operacija gali kainuoti O(n), bet amortizuota kaina yra O(log n).
Atsakymas: k = 3
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) = 20
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: B · SELECT dept, MAX(salary) FROM emp GROUP BY dept
GROUP BY dept sukuria grupę kiekvienam skyriui, o MAX(salary) kiekvienoje išrenka didžiausią reikšmę.
Atsakymas: A · Atitinka dauguma eilučių, todėl visos lentelės peržiūra pigesnė nei daugybė paieškų indekse
Indeksas padeda, kai susiaurina paiešką iki nedaug eilučių; kai tinka dauguma eilučių, atsitiktinės paieškos indekse kainuoja daugiau nei nuoseklus lentelės skaitymas.
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: C · Kad sumažėtų tikimybė vėl susidurti, kai varžosi daug stočių
Kiekviena nauja kolizija rodo didesnę konkurenciją, todėl atsitiktinis intervalas didėja ir stotys su didesne tikimybe pasirenka skirtingus laiko tarpsnius. Tai prisitaiko prie apkrovos be centrinio valdymo.
Atsakymas: x = 64
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 = 212
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