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ų −7 8 bitų dvejetainiu papildomuoju kodu. Skaitant kaip skaičių be ženklo, kokia šablono reikšmė U?

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

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

1280 × 720 px8 bit/px1 KiB = 1024 B
M = KiB
3.Teiginių logika ir įrodymaiVidutinis
(a ∧ c) ∨ b(a ∧ c) ∨ (a ∧ b)a ∨ (c ∧ b)(a ∨ c) ∧ (a ∨ b)

Kuri formulė yra logiškai ekvivalenti a ∧ (c ∨ b)? Spustelėkite ją.

a ∧ (c ∨ b)
  1. 1(a ∧ c) ∨ b
  2. 2(a ∧ c) ∨ (a ∧ b)
  3. 3a ∨ (c ∧ b)
  4. 4(a ∨ c) ∧ (a ∨ b)
4.Teiginių logika ir įrodymaiSunkus
∀x ∃y ¬R(x, y)∀x ∀y ¬R(x, y)∃x ∃y ¬R(x, y)∃x ∀y ¬R(x, y)

Kuris teiginys yra ekvivalentus ¬∃x ∀y R(x, y), kai neigimas perkeltas iki pat vidaus? Spustelėkite jį.

¬∃x ∀y R(x, y)
  1. 1∀x ∃y ¬R(x, y)
  2. 2∀x ∀y ¬R(x, y)
  3. 3∃x ∃y ¬R(x, y)
  4. 4∃x ∀y ¬R(x, y)
5.Skaitmeninė logika: elementai, Karno žemėlapiai ir trigeriaiVidutinis
ABCD000111100001111010011312141517161120131150141809011010

Karno žemėlapiu raskite minimalią F(A, B, C, D) = Σm(0, 2, 3, 4, 5, 6, 7, 8, 12, 15) sandaugų sumos (SOP) formą. Kiek sandaugos narių N ji turi?

F(A, B, C, D) = Σm(0, 2, 3, 4, 5, 6, 7, 8, 12, 15)
N =
6.Skaitmeninė logika: elementai, Karno žemėlapiai ir trigeriaiSunkus
ABCD00011110000111100011030214151716112013115014X819011X10

Funkcijai F(A, B, C, D) = Σm(1, 4, 5, 6, 7, 9, 12, 15) + d(8, 10), kur d žymi nesvarbias sąlygas, raskite esminių pagrindinių implikantų skaičių N.

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

Išspręskite 27x ≡ 23 (mod 29). Pateikite sprendinį x, kur 0 < x < 29.

27x ≡ 23 (mod 29)
x =
8.Skaičių teorija ir modulinė aritmetikaSunkus

Išspręskite 8x ≡ 66 (mod 86). Pateikite mažiausią teigiamą sprendinį x.

8x ≡ 66 (mod 86)
x =
9.Algoritmai ir sudėtingumasVidutinis

Kiek lygmenų turi rikiavimo suliejimu rekursija n elementų masyvui?

  1. AApie log₂ n
  2. BApie n
  3. CApie √n
  4. DApie n / 2
10.Algoritmai ir sudėtingumasSunkus

Kuris algoritmas randa minimalų jungiamąjį medį, pakartotinai pridėdamas pigiausią briauną, kuri nesudaro ciklo?

  1. APrimo algoritmas, pradedant nuo vienos viršūnės
  2. BFloido–Voršalo algoritmas
  3. CKruskalo algoritmas
  4. DDijkstros algoritmas
11.Duomenų struktūrosVidutinis

Koks yra blogiausio atvejo dvejetainio paieškos medžio su n mazgų aukštis, jei raktai įterpiami surikiuota tvarka?

  1. Alog₂ n
  2. B1
  3. Cn (medis tampa susietuoju sąrašu)
  4. D√n
12.Duomenų struktūrosSunkus

Kurią tiesinio zondavimo problemą dvigubas maišymas (double hashing) daugiausia sumažina?

  1. APirminį grupavimąsi (primary clustering), kai susidaro ilgos užimtų vietų sekos
  2. BPoreikį saugoti raktus lentelėje
  3. CRakto reikšmės skaitymo O(n) kainą
  4. DMaišos funkcijos poreikį
13.Grafų teorijaVidutinis
ABCDEFOilerio 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| = 6|E| = 7
  1. 1Oilerio ciklas
  2. 2Oilerio kelias, ne ciklas
  3. 3nei viena
14.Grafų teorijaSunkus
ABCDEF

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.

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

Kuri užklausa išvardija klientus, kurie niekada nepateikė užsakymo?

  1. ASELECT c.name FROM customers c LEFT JOIN orders o ON o.customer_id = c.id WHERE o.id = NULL
  2. BSELECT c.name FROM customers c INNER JOIN orders o ON o.customer_id = c.id WHERE o.id IS NULL
  3. CSELECT c.name FROM customers c LEFT JOIN orders o ON o.customer_id = c.id WHERE o.id IS NOT NULL
  4. DSELECT c.name FROM customers c LEFT JOIN orders o ON o.customer_id = c.id WHERE o.id IS NULL
16.Duomenų bazės ir SQLSunkus

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

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

Kas vienareikšmiškai identifikuoja vieną TCP ryšio galą internete?

  1. AVien MAC adresas
  2. BIP adresas kartu su prievado numeriu
  3. CPotinklio kaukė ir šliuzas
  4. DVien domeno vardas
18.Kompiuterių tinklaiSunkus

Eilės pradžios blokavimas (head-of-line blocking) HTTP/2 per TCP atsiranda todėl, kad:

  1. AServeriai negali apdoroti lygiagrečių užklausų
  2. BKiekvienai užklausai reikia atskiro naujo TCP ryšio, todėl vėlesnės užklausos laukia eilėje
  3. CPrarastas TCP segmentas sulaiko visus multipleksuotus srautus, kol bus pakartotinai išsiųstas
  4. DHTTP/2 naudoja UDP
19.IPv4 potinkliaiVidutinis
255.255.255.12811111111111111111111111110000000tinklo bitaimazgo bitai

Potinklio kaukė yra 255.255.255.128. Kiek naudojamų mazgų adresų H jame yra?

255.255.255.128
H =
20.IPv4 potinkliaiSunkus

Tinklas 192.168.168.0/24 VLSM būdu dalijamas šiems LAN: A: 3 mazgai, B: 9 mazgai, C: 77 mazgai, D: 59 mazgai. Potinkliai skiriami nuo .0 aukštyn, pirmiausia LAN su daugiausia mazgų, kiekvienam mažiausias tinkamas potinklis. Koks LAN D tinklo adreso ketvirtasis oktetas x?

A: 3B: 9C: 77D: 59
x =

3Tirpalai

1.Skaičiavimo sistemos

Atsakymas: U = 249

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ą

7 = 0000 0111
invertuota: 1111 1000
+1 → 1111 1001

Perskaitykite be ženklo

1111 1001₂ = 256 − 7 = 249

Atsakymas

U = 249
2.Skaičiavimo sistemos

Atsakymas: M = 900 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·8 = 7372800 bit = 921600 B

Paverskite į KiB

921600/1024 = 900 KiB

Atsakymas

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

Atsakymas: (a ∧ c) ∨ (a ∧ b)

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

Dėsnis

∧ yra distributyvi ∨ atžvilgiu: a ∧ (b ∨ c) ≡ (a ∧ b) ∨ (a ∧ c).
a ∧ (c ∨ b) ≡ (a ∧ c) ∨ (a ∧ b)

Patikrinkite teisingumo lentele

a = 1, b = 1, c = 1: 1 | 1 1 1 1
a = 1, b = 1, c = 0: 1 | 1 1 1 1
a = 1, b = 0, c = 1: 1 | 1 1 1 1
a = 1, b = 0, c = 0: 0 | 0 0 1 1
a = 0, b = 1, c = 1: 0 | 1 0 1 1
a = 0, b = 1, c = 0: 0 | 1 0 0 0
a = 0, b = 0, c = 1: 0 | 0 0 0 0
a = 0, b = 0, c = 0: 0 | 0 0 0 0

Atsakymas

(a ∧ c) ∨ (a ∧ b)

Stulpeliai po brūkšniu yra variantai pateikta tvarka.

4.Teiginių logika ir įrodymai

Atsakymas: ∀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.

Perkelkite neigimą į vidų

¬∃x ∀y R(x, y) ≡ ∀x ∃y ¬R(x, y)

Atsakymas

∀x ∃y ¬R(x, y)

Kiti variantai arba palieka kvantorių nepakeistą, arba keičia kvantorių tvarką, arba netinkamai neigia vidinę formulę.

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

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.

ABCD000111100001111010011312141517161120131150141809011010

Sugrupuokite vienetus

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

C′D′
BCD
A′C
A′B

Minimali SOP forma

F = C′D′ + BCD + A′C + A′B
N = 4

Atsakymas

N = 4
6.Skaitmeninė logika: elementai, Karno žemėlapiai ir trigeriai

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.

Pagrindiniai implikantai

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

B′C′D, BC′D′, BCD, A′C′D, AC′D′, A′B, AB′C′
ABCD00011110000111100011030214151716112013115014X819011X10

Esminiai pagrindiniai implikantai

BCD, A′B
N = 2

Atsakymas

N = 2
7.Skaičių teorija ir modulinė aritmetika

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

27 atvirkštinis

r = 29, t = 0
r = 27, q = 1, t = 1
r = 2, q = 13, t = −1
r = 1, q = 2, t = 14
27−1 ≡ 14 (mod 29)

Išspręskite

x ≡ 14·23 = 322 ≡ 3 (mod 29)
patikra: 27·3 = 81 ≡ 23 (mod 29)

Atsakymas

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

Atsakymas: x = 19

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

Padalykite iš DBD

gcd(8, 86) = 2
4x ≡ 33 (mod 43)

Išspręskite suprastintą kongruenciją

4−1 ≡ 11 (mod 43) → x ≡ 19 (mod 43)

Sprendiniai moduliu 86

x ∈ {19, 62}
x = 19

Atsakymas

x = 19
9.Algoritmai ir sudėtingumas

Atsakymas: A · Apie log₂ n

Kodėl tai yra atsakymas

Dalijant pusiau nuo n iki 1, reikia apie log₂ n lygmenų, o kiekviename lygmenyje atliekama O(n) suliejimo darbo, todėl gaunama O(n log n).

Atsakymas

A · Apie log₂ n
10.Algoritmai ir sudėtingumas

Atsakymas: C · Kruskalo algoritmas

Kodėl tai yra atsakymas

Kruskalo algoritmas surikiuoja briaunas pagal svorį ir prideda jas, jei jos jungia skirtingas komponentes; Primo algoritmas augina vieną medį nuo pradinės viršūnės.

Atsakymas

C · Kruskalo algoritmas
11.Duomenų struktūros

Atsakymas: C · n (medis tampa susietuoju sąrašu)

Kodėl tai yra atsakymas

Įterpiant surikiuotus raktus susidaro išsigimęs n aukščio medis, todėl paieška tampa O(n). Subalansuoti medžiai to išvengia.

Atsakymas

C · n (medis tampa susietuoju sąrašu)
12.Duomenų struktūros

Atsakymas: A · Pirminį grupavimąsi (primary clustering), kai susidaro ilgos užimtų vietų sekos

Kodėl tai yra atsakymas

Tiesinis zondavimas žengia po 1, todėl užimtos sekos auga ir susilieja; dvigubas maišymas žingsnio dydžiui naudoja antrą maišos funkciją, todėl skirtingi raktai zonduoja skirtingas sekas.

Atsakymas

A · Pirminį grupavimąsi (primary clustering), kai susidaro ilgos užimtų vietų sekos
13.Grafų teorija

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

Laipsniai

deg(A) = 2, deg(B) = 4, deg(C) = 2, deg(D) = 2, deg(E) = 2, deg(F) = 2

Nelyginės viršūnės

0
Oilerio ciklas

Atsakymas

Oilerio ciklas
14.Grafų teorija

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

Gretimumo matrica

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

Bendri kaimynai

(M²)AA = 0·0 + 1·1 + 0·0 + 0·0 + 0·0 + 0·0 = 1

Atsakymas

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

Atsakymas: D · SELECT c.name FROM customers c LEFT JOIN orders o ON o.customer_id = c.id WHERE o.id IS NULL

Kodėl tai yra atsakymas

Kairysis sujungimas palieka visus klientus ir, nesant atitikmens, užsakymų stulpelius užpildo NULL; tada IS NULL išrenka būtent tuos klientus.

Atsakymas

D · SELECT c.name FROM customers c LEFT JOIN orders o ON o.customer_id = c.id WHERE o.id IS NULL
16.Duomenų bazės ir SQL

Atsakymas: B · 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

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

Atsakymas: B · IP adresas kartu su prievado numeriu

Kodėl tai yra atsakymas

TCP ryšį identifikuoja šaltinio IP ir prievadas bei paskirties IP ir prievadas. Prievadai atskiria daugybę viename mazge veikiančių programų.

Atsakymas

B · IP adresas kartu su prievado numeriu
18.Kompiuterių tinklai

Atsakymas: C · Prarastas TCP segmentas sulaiko visus multipleksuotus srautus, kol bus pakartotinai išsiųstas

Kodėl tai yra atsakymas

TCP pristato baitus eilės tvarka, todėl vienas praradimas sustabdo kiekvieną ryšio srautą. QUIC (HTTP/3) srautus per UDP apdoroja nepriklausomai.

Atsakymas

C · Prarastas TCP segmentas sulaiko visus multipleksuotus srautus, kol bus pakartotinai išsiųstas
19.IPv4 potinkliai

Atsakymas: H = 126

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

Prefikso ilgis

255.255.255.128 = /25

Naudojami mazgai

27 − 2 = 126

Atsakymas

H = 126
20.IPv4 potinkliai

Atsakymas: x = 128

VLSM: kiekvienas LAN gauna mažiausią potinklį, kuriame 2ʰ − 2 ≥ jo mazgų skaičius, t. y. prefiksą 32 − h. Pirmiausia skiriant didžiausius potinklius, kiekvienas blokas lygiuojamas į savo dydžio kartotinį, todėl tinklų adresai gaunami sudedant bloko dydžius.

Kiekvieno LAN bloko dydis

C: 77 mazgai → 27 = 128 (/25)
D: 59 mazgai → 26 = 64 (/26)
B: 9 mazgai → 24 = 16 (/28)
A: 3 mazgai → 23 = 8 (/29)

Skirstymas, pradedant didžiausiu

C: .0 – .127
D: .128 – .191
B: .192 – .207
A: .208 – .215

Atsakymas

x = 128

LAN D: 192.168.168.128/26.

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