Formulių lapai, pagrindiniai kiekvienos temos metodų žingsniai ir 20 uždavinių, o pilni sprendimai pateikti gale.
8 bitų seka 0001 1100 saugo sveikąjį skaičių su ženklu papildomajame kode. Kokia jo reikšmė N dešimtainėje sistemoje?
Sistema kiekvienam iš 4887 elementų turi suteikti atskirą tokio pat ilgio dvejetainį kodą. Kiek mažiausiai bitų b reikia?
Kuri formulė yra logiškai ekvivalenti q ↔ r? Spustelėkite ją.
Duotos prielaidos b ∨ a; ¬b. Kokia išvada iš jų išplaukia? Spustelėkite ją.
Karno žemėlapiu raskite minimalią F(A, B, C, D) = Σm(4, 6, 7, 8, 9, 11) sumų sandaugos (POS) formą. Kiek sumos narių (daugiklių) N ji turi?
Raskite minimalią F(A, B, C, D) = Σm(1, 2, 4, 5, 6, 8, 9, 10, 12, 14) + d(0, 3, 13) SOP formą, kur d žymi nesvarbias sąlygas. Kiek literalų L ji turi?
Raskite Oilerio funkciją φ(40), t. y. sveikųjų skaičių nuo 1 iki 40, tarpusavyje pirminių su 40, skaičių.
Kartotiniu kėlimu kvadratu raskite 2962 mod 47.
Kam lygus rekurentinės lygties T(n) = T(n − 1) + O(n) sprendinys?
Koks yra Dijkstros algoritmo su dvejetaine krūva vykdymo laikas grafui su V viršūnių ir E briaunų?
Kuri duomenų struktūra naudojama tikrinti, ar skliaustai eilutėje „{[()]}“ subalansuoti?
Dinaminis masyvas užsipildęs padvigubėja. Kodėl daugelis įgyvendinimų jį sumažina tik tada, kai jis užpildytas ketvirtadaliu, o ne perpus?
Jungus grafas turi 16 viršūnių ir 26 briaunų. Kiek briaunų k reikia pašalinti, kad liktų karkasinis medis?
Kruskalio algoritmas sudaro minimalų karkasinį medį. Spustelėkite briauną, kurią jis prideda kaip briauną numeris 5; praleistos briaunos neskaičiuojamos.
Antroji normalinė forma (2NF) pašalina:
Boyce’o–Coddo normalinė forma (BCNF) reikalauja, kad kiekvienai netrivialiai funkcinei priklausomybei X → Y:
Kuri TCP vėliavėlė praneša, kad siuntėjas baigė siųsti duomenis?
Stotys A ir C abi pasiekia prieigos tašką B, bet viena kitos negirdi, todėl jų kadrai susiduria ties B. Kaip padeda 802,11?
Tinklą 192.168.10.0/24 reikia padalyti į bent 30 vienodų potinklių. Jei pasiskolinsite kuo mažiau bitų, kiek naudojamų mazgų H turės kiekvienas potinklis?
Mazgo adresas yra 10.20.133.18/28. Koks yra jo tinklo adreso ketvirtasis oktetas x?
Atsakymas: N = 28
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: b = 13 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: (q → r) ∧ (r → 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: a
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.
Atsakymas: N = 4
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.
Egzistuoja kitas to paties dydžio grupavimas; jis turi tiek pat narių ir literalų.
Atsakymas: L = 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: φ(40) = 16
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: 2962 mod 47 = 8
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: C · O(n²)
Darbas susumuoja iki maždaug n² / 2; tai rikiavimo išrinkimu arba greitojo rikiavimo su blogiausiu atraminiu elementu rekurentinė lygtis.
Atsakymas: C · O((V + E) log V)
Atliekama V minimumo išėmimo ir iki E rakto sumažinimo operacijų, kurių kiekviena O(log V); Fibonačio krūva tai pagerina iki O(E + V log V).
Atsakymas: D · Stekas
Kiekvieną atidarantį skliaustą atlikite push, o pasirodžius uždarančiam – pop; jis turi atitikti išimtą skliaustą, o pabaigoje stekas turi būti tuščias.
Atsakymas: B · Kad būtų išvengta pakartotinio dydžio keitimo, kai push ir pop kaitaliojasi prie ribos
Mažinant esant pusei talpos, tokioje sekoje kiekviena operacija galėtų sukelti dydžio keitimą; tarpas tarp 1/4 ir pilnos talpos išlaiko amortizuotą kainą O(1).
Atsakymas: k = 11
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: briauna DF
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ą.
Atsakymas: B · 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 · X būtų superraktas
BCNF reikalauja, kad kiekvienas determinantas būtų kandidatinis raktas (superraktas); 3NF leidžia išimtį, kai Y yra kandidatinio rakto dalis.
Atsakymas: B · FIN
Kiekviena pusė siunčia FIN, kai nebeturi duomenų, o kita pusė tai patvirtina. SYN skirtas ryšiui atidaryti; RST ryšį nutraukia.
Atsakymas: C · Pasirenkamais RTS/CTS mainais: prieigos taško CTS liepia visoms netoliese esančioms stotims palaukti
Stotis siunčia Request to Send; prieigos taškas atsako Clear to Send, kurį girdi kiekviena jo zonoje esanti stotis, todėl paslėptos stotys atideda siuntimą rezervuotam laikui.
Atsakymas: H = 6
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 = 16
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