Informatikos pagrindai: pasiruošimo paketas

Formulių lapai, pagrindiniai kiekvienos temos metodų žingsniai ir 20 uždavinių, o pilni sprendimai pateikti gale.

Nauji uždaviniaiAtgal į kursą

Spausdinimo lange pasirinkite „Išsaugoti kaip PDF“, kad nuosavą kopiją išsaugotumėte savo įrenginyje.

1Formulės ir metodai

Skaičiavimo sistemos

Pozicijų vertės
dvejetainė 2k, aštuntainė 8k, šešioliktainė 16k
Į dešimtainę
Σ dk·bk
Iš dešimtainės
dalykite iš pagrindo, liekanas skaitykite iš apačios į viršų
Šešioliktainė ↔ dvejetainė
vienas šešioliktainis skaitmuo = 4 bitai
Papildomasis kodas
invertuokite bitus ir pridėkite 1

Teiginių logika ir įrodymai

Teisingumo lentelės eilutės
2ⁿ
Implikacija
p → q ≡ ¬p ∨ q ≡ ¬q → ¬p
Implikacijos neigimas
¬(p → q) ≡ p ∧ ¬q
Ekvivalencija
p ↔ q ≡ (p → q) ∧ (q → p)
De Morgano dėsniai
¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q
Distributyvumo dėsniai
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Kvantorių neigimas
¬∀x P(x) ≡ ∃x ¬P(x), ¬∃x P(x) ≡ ∀x ¬P(x)
Modus ponens, modus tollens
p → q, p ⊢ q; p → q, ¬q ⊢ ¬p

Metodas

  1. Suskaičiuokite skirtingus kintamuosius: teisingumo lentelėje yra 2ⁿ eilučių, o pirmoji eilutė – visi kintamieji lygūs 1.
  2. Kiekvienai posakio daliai skirkite savo stulpelį ir užpildykite stulpelius iš vidaus į išorę.
  3. Taikykite kiekvienos jungties taisyklę: → yra 0 tik tada, kai 1 → 0, o ↔ yra 1, kai abi pusės sutampa.
  4. Tikrindami ekvivalentumą, palyginkite galutinius stulpelius eilutė po eilutės; tikrindami argumentą, žiūrėkite tik į eilutes, kuriose visos prielaidos lygios 1.
  5. Norėdami paneigti kvantorių turintį teiginį, perkelkite ¬ į vidų, sukeiskite ∀ ir ∃ vietomis ir paneikite vidinę formulę.

Skaitmeninė logika: elementai, Karno žemėlapiai ir trigeriai

Pagrindiniai elementai
A·B, A + B, A′, (A·B)′, (A + B)′, A ⊕ B
Būlio taisyklės
X + X′ = 1, X·X′ = 0, X + XY = X, XY + XY′ = X
De Morgano dėsniai
(X·Y)′ = X′ + Y′, (X + Y)′ = X′·Y′
Karno žemėlapio tvarka
00, 01, 11, 10 (Gray code)
2ᵏ langelių grupė
netenka k kintamųjų
4 į 1 multiplekseris
F = A′B′I0 + A′BI1 + AB′I2 + ABI3
Trigeriai
D: Q⁺ = D, T: Q⁺ = T ⊕ Q, JK: Q⁺ = JQ′ + K′Q
Skaitikliai
n bitų: 2ⁿ būsenų; mod-N: mažiausias n, kad 2ⁿ ≥ N; fout = fclk/N
Nuosekliojo veikimo (ripple) skaitiklis
fmax = 1/(n·tpd)
Žiediniai ir Johnsono skaitikliai
n ir 2n būsenų

Metodas

  1. Grandinei dirbkite nuo įėjimų iki išėjimo po vieną elementą ir užrašykite reikšmę ant kiekvieno laido arba užrašykite išraišką ir užpildykite teisingumo lentelę.
  2. Supaprastindami įrašykite vienetus (o nesvarbias reikšmes kaip X) į Karno žemėlapį su Grejaus kodo eilutėmis ir stulpeliais: 00, 01, 11, 10.
  3. Vienetus padenkite kuo mažiau ir kuo didesnių 1, 2, 4, 8 ar 16 langelių grupių, apsisukančių per kraštus; kiekviena grupė yra vienas sandaugos narys iš kintamųjų, kurie joje nesikeičia. POS formai grupuokite nulius.
  4. Trigeriams ir skaitikliams skaitykite įėjimus kiekvienu aktyviu taktiniu frontu, užrašykite būseną po kiekvieno fronto ir atminkite, kad n bitų skaitiklis apsisuka po 2ⁿ būsenų.

Skaičių teorija ir modulinė aritmetika

Dalyba su liekana
a = q·n + r, 0 ≤ r < n
Euklidas
gcd(a, b) = gcd(b, a mod b)
Mažiausias bendrasis kartotinis
lcm(a, b) = a·b/gcd(a, b)
Atvirkštinė
a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
Tiesinė kongruencija
a·x ≡ b → x ≡ a⁻¹·b (mod n)
Oilerio funkcija
φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
Ferma
aᵖ⁻¹ ≡ 1 (mod p)
RSA
n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n

Metodas

  1. Pirmiausia visus skaičius suredukuokite moduliu n; liekanos yra nuo 0 iki n − 1.
  2. Didžiausiam bendrajam dalikliui kartokite dalybą Euklido algoritmu; paskutinė nenulinė liekana yra DBD.
  3. Atvirkštiniam skaičiui taikykite išplėstinį algoritmą ir pasilikite a koeficientą; jei jis neigiamas, pridėkite n.
  4. Sprendžiant a·x ≡ b, dauginkite iš a⁻¹; dvi kongruencijas sujunkite rašydami x = r₁ + m₁k.
  5. Laipsniams užrašykite rodiklį dvejetainiu pavidalu ir kelkite kvadratu pakartotinai; RSA atveju d = e⁻¹ mod φ(n), kur φ(n) = (p − 1)(q − 1).

Grafų teorija

Rankų paspaudimo lema
Σ deg(v) = 2|E|
Pilnieji grafai
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
Reguliarusis grafas
|E| = n·k/2
Medis ir miškas
|E| = n − 1, |E| = n − c
Medžio lapai
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Oileris
ciklas: visų viršūnių laipsniai lyginiai; kelias: lygiai 2 nelyginio laipsnio viršūnės
Hamiltono ciklai grafe Kn
(n − 1)!/2
Dijkstros atnaujinimas
d(v) = min(d(v), d(u) + w(u, v))
L ilgio maršrutai
(Mᴸ)ij

Metodas

  1. Užrašykite kiekvienos viršūnės laipsnį; laipsnių suma lygi dvigubam briaunų skaičiui.
  2. Oilerio uždaviniuose patikrinkite, ar grafas jungus, ir suskaičiuokite nelyginio laipsnio viršūnes.
  3. Medžiams naudokite n − 1 briaunų ir rankų paspaudimo lemą.
  4. Dijkstros algoritme laikykite preliminarių atstumų lentelę ir kiekviename etape užfiksuokite mažiausio atstumo dar neužfiksuotą viršūnę.
  5. Minimaliam karkasiniam medžiui surikiuokite briaunas pagal svorį ir praleiskite kiekvieną briauną, uždarančią ciklą (Kruskalis), arba auginkite vieną medį iš pradinės viršūnės (Primas).

IPv4 potinkliai

Mazgai potinklyje
2(32 − prefix) − 2 (/31: 2, /32: 1)
Bloko dydis
256 − (mask octet)
Tinklo adresas
IP AND kaukė
Transliacijos adresas
IP OR (NOT kaukė): visi mazgo bitai lygūs 1
Potinkliai iš n pasiskolintų bitų
2n

2Uždaviniai

1.Skaičiavimo sistemosVidutinis
8 bitų papildomasis kodas0−12806403201608040201

Nustatykite bitus, kad jie saugotų −63 8 bitų dvejetainiu papildomuoju kodu. Skaitant kaip skaičių be ženklo, kokia šablono reikšmė U?

N = −638 bit
U =
2.Skaičiavimo sistemosSunkus
32 bit1 px1280 px720 pxM = ? KiB

Nesuspaustas vaizdas yra 1280 × 720 pikselių, 32 bitų pikseliui. Kiek atminties M jis užima, KiB (1 KiB = 1024 baitai)?

1280 × 720 px32 bit/px1 KiB = 1024 B
M = KiB
3.Teiginių logika ir įrodymaiVidutinis
tautologijaprieštarakontingencija

Ar ((r → p) ∧ (r → q)) → (p → q) yra tautologija, prieštara ar kontingencija? Spustelėkite savo atsakymą.

((r → p) ∧ (r → q)) → (p → q)
  1. 1tautologija
  2. 2prieštara
  3. 3kontingencija
4.Teiginių logika ir įrodymaiSunkus
ba ∧ ca¬b

Duotos prielaidos a ∨ c; a → b; c → b. Kokia išvada iš jų išplaukia? Spustelėkite ją.

a ∨ ca → bc → b
  1. 1b
  2. 2a ∧ c
  3. 3a
  4. 4¬b
5.Skaitmeninė logika: elementai, Karno žemėlapiai ir trigeriaiVidutinis
ABC00011110011001031204051706

Karno žemėlapiu raskite minimalią F(A, B, C) = Σm(0, 2, 7) sandaugų sumos (SOP) formą. Kiek iš viso literalų L ji turi (su brūkšneliu žymimas kintamasis skaičiuojamas kaip vienas literalas)?

F(A, B, C) = Σm(0, 2, 7)
L =
6.Skaitmeninė logika: elementai, Karno žemėlapiai ir trigeriaiSunkus
ABCD000111100001111000010302141517X6012X130150141809011110

Raskite minimalią F(A, B, C, D) = Σm(4, 5, 7, 8, 10) + d(6, 13) SOP formą, kur d žymi nesvarbias sąlygas. Kiek literalų L ji turi?

F(A, B, C, D) = Σm(4, 5, 7, 8, 10) + d(6, 13)
L =
7.Skaičių teorija ir modulinė aritmetikaVidutinis

Raskite mažiausią teigiamą sveikąjį skaičių x, kur x ≡ 3 (mod 5) ir x ≡ 11 (mod 12).

x ≡ 3 (mod 5)x ≡ 11 (mod 12)
x =
8.Skaičių teorija ir modulinė aritmetikaSunkus

Kartotiniu kėlimu kvadratu raskite 2974 mod 33.

a = 29k = 74n = 33
2974 mod 33 =
9.Algoritmai ir sudėtingumasVidutinis

Naivaus rekursyvaus Fibonačio skaičių skaičiavimo (fib(n) = fib(n−1) + fib(n−2)) laiko sudėtingumas yra:

  1. ALogaritminis
  2. BPastovus
  3. CEksponentinis
  4. DTiesinis
10.Algoritmai ir sudėtingumasSunkus

Kodėl dvejetainė paieška vienkrypčiame susietajame sąraše neužtikrina O(log n) laiko?

  1. AIki vidurinio elemento nueiti reikia O(n) žingsnių, nes nėra tiesioginės prieigos pagal indeksą
  2. BDvejetainei paieškai reikia bent dvigubai daugiau atminties
  3. CSusietojo sąrašo mazgų palyginimai lėtesni
  4. DSusietųjų sąrašų negalima surikiuoti
11.Duomenų struktūrosVidutinis

Kurią duomenų struktūrą naudoja paieška į gylį (DFS, iteracinė versija)?

  1. ATik maišos lentelę
  2. BSteką
  3. CKrūvą
  4. DEilę
12.Duomenų struktūrosSunkus

Operacijos decrease-key dvejetainėje krūvoje (žinant elemento poziciją) laiko sudėtingumas yra:

  1. AO(n)
  2. BO(n log n)
  3. CO(1)
  4. DO(log n)
13.Grafų teorijaVidutinis
ABCDEOilerio ciklasOilerio kelias, ne ciklasnei viena

Ar jungus grafas turi Oilerio ciklą, Oilerio kelią, kuris nėra ciklas, ar nei vieno? Spustelėkite savo atsakymą.

|V| = 5|E| = 5
  1. 1Oilerio ciklas
  2. 2Oilerio kelias, ne ciklas
  3. 3nei viena
14.Grafų teorijaSunkus
ABCDE

Kiek yra 2 ilgio uždarų maršrutų, prasidedančių ir pasibaigiančių ties B? Maršrutas gali kartoti viršūnes ir briaunas. Pažymėkite skaičių N.

M = gretimumo matricaL = 2
N =
15.Duomenų bazės ir SQLVidutinis

Kada WHERE EXISTS (použklausa) eilutei yra teisinga?

  1. AKai použklausa grąžina skaičių, didesnį už nulį
  2. BKai použklausa grąžina bent vieną eilutę
  3. CKai použklausa negrąžina NULL reikšmių
  4. DKai použklausa grąžina lygiai vieną eilutę
16.Duomenų bazės ir SQLSunkus

Koreliuotoji papildoma užklausa (correlated subquery) yra tokia, kuri:

  1. ASujungia dvi lenteles išoriniu raktu
  2. BVykdoma tik vieną kartą prieš išorinę užklausą, o jos rezultatas išsaugomas visoms eilutėms
  3. CNaudoja išorinės užklausos stulpelius ir vertinama kiekvienai išorinės užklausos eilutei
  4. DNaudoja tik agregavimo funkcijas
17.Kompiuterių tinklaiVidutinis

Kokias saugumo savybes TLS suteikia HTTPS?

  1. AApsaugą nuo visos kenkėjiškos programinės įrangos ir sukčiavimo (phishing) aplankytoje svetainėje
  2. BTik greitesnį įkėlimą
  3. CKonfidencialumą, vientisumą ir serverio autentifikavimą
  4. DNaudotojo anonimiškumą
18.Kompiuterių tinklaiSunkus

Kokia pagal Šenono teoremą yra 1 MHz kanalo, kurio signalo ir triukšmo santykis 255, talpa?

  1. A255 Mbit/s
  2. B1 Mbit/s
  3. C8 Mbit/s
  4. D2 Mbit/s
19.IPv4 potinkliaiVidutinis
/?11111111111111111111111000000000tinklo bitaimazgo bitai

Skyriui viename potinklyje reikia 259 mazgų adresų. Koks yra ilgiausias prefiksas p (mažiausias potinklis), kurio pakanka?

259 hosts
p =
20.IPv4 potinkliaiSunkus
paskutinis oktetas = 69012816403201608140211tinklasmazgas

Mazgo adresas yra 10.20.67.69/29. Koks yra paskutinio naudojamo mazgo adreso jo potinklyje ketvirtasis oktetas x?

10.20.67.69/29
x =

3Tirpalai

1.Skaičiavimo sistemos

Atsakymas: U = 193

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.

Invertuokite ir pridėkite vienetą

63 = 0011 1111
invertuota: 1100 0000
+1 → 1100 0001

Perskaitykite be ženklo

1100 0001₂ = 256 − 63 = 193

Atsakymas

U = 193
2.Skaičiavimo sistemos

Atsakymas: M = 3600 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.

Bitai ir baitai

1280·720·32 = 29491200 bit = 3686400 B

Paverskite į KiB

3686400/1024 = 3600 KiB

Atsakymas

M = 3600 KiB
3.Teiginių logika ir įrodymai

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).

Teisingumo lentelė eilutė po eilutės

p = 1, q = 1, r = 1: r → p = 1, r → q = 1, (r → p) ∧ (r → q) = 1, p → q = 1, ((r → p) ∧ (r → q)) → (p → q) = 1
p = 1, q = 1, r = 0: r → p = 1, r → q = 1, (r → p) ∧ (r → q) = 1, p → q = 1, ((r → p) ∧ (r → q)) → (p → q) = 1
p = 1, q = 0, r = 1: r → p = 1, r → q = 0, (r → p) ∧ (r → q) = 0, p → q = 0, ((r → p) ∧ (r → q)) → (p → q) = 1
p = 1, q = 0, r = 0: r → p = 1, r → q = 1, (r → p) ∧ (r → q) = 1, p → q = 0, ((r → p) ∧ (r → q)) → (p → q) = 0
p = 0, q = 1, r = 1: r → p = 0, r → q = 1, (r → p) ∧ (r → q) = 0, p → q = 1, ((r → p) ∧ (r → q)) → (p → q) = 1
p = 0, q = 1, r = 0: r → p = 1, r → q = 1, (r → p) ∧ (r → q) = 1, p → q = 1, ((r → p) ∧ (r → q)) → (p → q) = 1
p = 0, q = 0, r = 1: r → p = 0, r → q = 0, (r → p) ∧ (r → q) = 0, p → q = 1, ((r → p) ∧ (r → q)) → (p → q) = 1
p = 0, q = 0, r = 0: r → p = 1, r → q = 1, (r → p) ∧ (r → q) = 1, p → q = 1, ((r → p) ∧ (r → q)) → (p → q) = 1

Klasifikuokite

((r → p) ∧ (r → q)) → (p → q): 1, 1, 1, 0, 1, 1, 1, 1
1 iš 7 iš 8 eilučių, 0 likusiose: kontingencija.

Atsakymas

kontingencija
4.Teiginių logika ir įrodymai

Atsakymas: b

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.

Eilutės, kuriose visos prielaidos teisingos

a = 1, b = 1, c = 1: b = 1, a ∧ c = 1, a = 1, ¬b = 0
a = 1, b = 1, c = 0: b = 1, a ∧ c = 0, a = 1, ¬b = 0
a = 0, b = 1, c = 1: b = 1, a ∧ c = 0, a = 0, ¬b = 0

Išvada

b (įrodymas atvejais)

Atsakymas

b
5.Skaitmeninė logika: elementai, Karno žemėlapiai ir trigeriai

Atsakymas: L = 5

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.

ABC00011110011001031204051706

Sugrupuokite vienetus

Kiekviena grupė yra 2ᵏ langelių stačiakampis; kraštiniai langeliai yra priešingo krašto langelių kaimynai.

A′C′
ABC

Minimali SOP forma

F = A′C′ + ABC
L = 5

Atsakymas

L = 5
6.Skaitmeninė logika: elementai, Karno žemėlapiai ir trigeriai

Atsakymas: L = 5

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.

Pagrindiniai implikantai

Didžiausios grupės, kurias galima sudaryti iš vienetų ir X.

BC′D, A′B, AB′D′
ABCD000111100001111000010302141517X6012X130150141809011110

Minimalus dengimas

F = A′B + AB′D′
L = 5

Atsakymas

L = 5
7.Skaičių teorija ir modulinė aritmetika

Atsakymas: x = 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).

Pirmoji kongruencija

x = 3 + 5k

Antroji kongruencija

3 + 5k ≡ 11 (mod 12) → 5k ≡ 8 (mod 12)
k ≡ 5·8 ≡ 4 (mod 12)

Rezultatas

x = 3 + 5·4 = 23
x = 23
patikra: 23 mod 5 = 3, 23 mod 12 = 11

Atsakymas

x = 23
8.Skaičių teorija ir modulinė aritmetika

Atsakymas: 2974 mod 33 = 25

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.

Dvejetainis rodiklis

74 = 10010102 = 64 + 8 + 2

Kartotinis kėlimas kvadratu

291 ≡ 29 (mod 33)
292 ≡ 16 (mod 33)
294 ≡ 25 (mod 33)
298 ≡ 31 (mod 33)
2916 ≡ 4 (mod 33)
2932 ≡ 16 (mod 33)
2964 ≡ 25 (mod 33)

Sudauginkite reikalingus laipsnius

2974 ≡ 16·31·25 ≡ 25 (mod 33)

Atsakymas

2974 mod 33 = 25
9.Algoritmai ir sudėtingumas

Atsakymas: C · Eksponentinis

Kodėl tai yra atsakymas

Iškvietimų medis auga maždaug kaip φⁿ (apie 1,618ⁿ). Memoizacija sumažina sudėtingumą iki O(n).

Atsakymas

C · Eksponentinis
10.Algoritmai ir sudėtingumas

Atsakymas: A · Iki vidurinio elemento nueiti reikia O(n) žingsnių, nes nėra tiesioginės prieigos pagal indeksą

Kodėl tai yra atsakymas

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

A · Iki vidurinio elemento nueiti reikia O(n) žingsnių, nes nėra tiesioginės prieigos pagal indeksą
11.Duomenų struktūros

Atsakymas: B · Steką

Kodėl tai yra atsakymas

DFS eina kuo giliau, natūraliai naudodama steką (arba rekursijos iškvietimų steką); BFS naudoja eilę.

Atsakymas

B · Steką
12.Duomenų struktūros

Atsakymas: D · O(log n)

Kodėl tai yra atsakymas

Sumažinus raktą, elementas kyla aukštyn ne daugiau nei krūvos aukštis. Fibonačio krūvos pasiekia O(1) amortizuotą decrease-key.

Atsakymas

D · O(log n)
13.Grafų teorija

Atsakymas: nei viena

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ų.

Laipsniai

deg(A) = 1, deg(B) = 3, deg(C) = 1, deg(D) = 2, deg(E) = 3

Nelyginės viršūnės

A, B, C, E → 4
nei viena

Atsakymas

nei viena
14.Grafų teorija

Atsakymas: N = 4

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ą.

Gretimumo matrica

A: 0 1 1 0 0
B: 1 0 1 1 1
C: 1 1 0 0 1
D: 0 1 0 0 0
E: 0 1 1 0 0

Bendri kaimynai

(M²)BB = 1·1 + 0·0 + 1·1 + 1·1 + 1·1 = 4

Atsakymas

N = 4
15.Duomenų bazės ir SQL

Atsakymas: B · Kai použklausa grąžina bent vieną eilutę

Kodėl tai yra atsakymas

EXISTS tik tikrina, ar sukuriama bent viena eilutė; NOT EXISTS teisinga, kai použklausa negrąžina jokių eilučių.

Atsakymas

B · Kai použklausa grąžina bent vieną eilutę
16.Duomenų bazės ir SQL

Atsakymas: C · Naudoja išorinės užklausos stulpelius ir vertinama kiekvienai išorinės užklausos eilutei

Kodėl tai yra atsakymas

Koreliuotosios papildomos užklausos priklauso nuo esamos išorinės eilutės, todėl logiškai vertinamos kiekvienai eilutei (optimizatoriai gali jas perrašyti į sujungimus).

Atsakymas

C · Naudoja išorinės užklausos stulpelius ir vertinama kiekvienai išorinės užklausos eilutei
17.Kompiuterių tinklai

Atsakymas: C · Konfidencialumą, vientisumą ir serverio autentifikavimą

Kodėl tai yra atsakymas

TLS šifruoja srautą, aptinka klastojimą ir sertifikatais autentifikuoja serverį (pasirinktinai ir klientą).

Atsakymas

C · Konfidencialumą, vientisumą ir serverio autentifikavimą
18.Kompiuterių tinklai

Atsakymas: C · 8 Mbit/s

Kodėl tai yra atsakymas

C = 10⁶ × log₂(256) = 10⁶ × 8 = 8 Mbit/s. Tai viršutinė be klaidų perduodamų duomenų spartos riba triukšmingame kanale.

Atsakymas

C · 8 Mbit/s
19.IPv4 potinkliai

Atsakymas: p = 23

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).

Reikalingi mazgo bitai

28 − 2 = 254 < 259
29 − 2 = 510 ≥ 259 → h = 9

Prefikso ilgis

p = 32 − 9 = 23

Atsakymas

p = /23
20.IPv4 potinkliai

Atsakymas: x = 70

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).

Bloko dydis

23 = 8

Šio mazgo potinklis

tinklas: ⌊69/8⌋·8 = 64
transliacija: 64 + 8 − 1 = 71
naudojami mazgai: 65 … 70

Atsakymas

x = 70

ExamProblems · examproblems.com/courses/computer-science-fundamentals