Informatikos pagrindai: pasiruošimo paketas

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

Nauji uždaviniai Atgal į 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ė 2^k, aštuntainė 8^k, šešioliktainė 16^k
Į dešimtainę: Σ d_k·b^k
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

Suskaičiuokite skirtingus kintamuosius: teisingumo lentelėje yra 2ⁿ eilučių, o pirmoji eilutė – visi kintamieji lygūs 1.
Kiekvienai posakio daliai skirkite savo stulpelį ir užpildykite stulpelius iš vidaus į išorę.
Taikykite kiekvienos jungties taisyklę: → yra 0 tik tada, kai 1 → 0, o ↔ yra 1, kai abi pusės sutampa.
Tikrindami ekvivalentumą, palyginkite galutinius stulpelius eilutė po eilutės; tikrindami argumentą, žiūrėkite tik į eilutes, kuriose visos prielaidos lygios 1.
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′I₀ + A′BI₁ + AB′I₂ + ABI₃
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; f_out = f_clk/N
Nuosekliojo veikimo (ripple) skaitiklis: f_max = 1/(n·t_pd)
Žiediniai ir Johnsono skaitikliai: n ir 2n būsenų

Metodas

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ę.
Supaprastindami įrašykite vienetus (o nesvarbias reikšmes kaip X) į Karno žemėlapį su Grejaus kodo eilutėmis ir stulpeliais: 00, 01, 11, 10.
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.
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

Pirmiausia visus skaičius suredukuokite moduliu n; liekanos yra nuo 0 iki n − 1.
Didžiausiam bendrajam dalikliui kartokite dalybą Euklido algoritmu; paskutinė nenulinė liekana yra DBD.
Atvirkštiniam skaičiui taikykite išplėstinį algoritmą ir pasilikite a koeficientą; jei jis neigiamas, pridėkite n.
Sprendžiant a·x ≡ b, dauginkite iš a⁻¹; dvi kongruencijas sujunkite rašydami x = r₁ + m₁k.
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(K_n)| = n(n − 1)/2, |E(K_m,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 K_n: (n − 1)!/2
Dijkstros atnaujinimas: d(v) = min(d(v), d(u) + w(u, v))
L ilgio maršrutai: (Mᴸ)_ij

Metodas

Užrašykite kiekvienos viršūnės laipsnį; laipsnių suma lygi dvigubam briaunų skaičiui.
Oilerio uždaviniuose patikrinkite, ar grafas jungus, ir suskaičiuokite nelyginio laipsnio viršūnes.
Medžiams naudokite n − 1 briaunų ir rankų paspaudimo lemą.
Dijkstros algoritme laikykite preliminarių atstumų lentelę ir kiekviename etape užfiksuokite mažiausio atstumo dar neužfiksuotą viršūnę.
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ų: 2ⁿ

2Uždaviniai

1.Skaičiavimo sistemosVidutinis

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

N = −298 bit

U =

2.Skaičiavimo sistemosSunkus

Sistema kiekvienam iš 1465 elementų turi suteikti atskirą tokio pat ilgio dvejetainį kodą. Kiek mažiausiai bitų b reikia?

1465

b = bit

3.Teiginių logika ir įrodymaiVidutinis

Kuri formulė yra logiškai ekvivalenti ¬(a ↔ b)? Spustelėkite ją.

¬(a ↔ b)

1¬a ↔ ¬b
2¬a ∨ ¬b
3a ↔ ¬b
4a ∧ ¬b

4.Teiginių logika ir įrodymaiSunkus

Kuris teiginys yra ekvivalentus ¬∀x (A(x) → B(x)), kai neigimas perkeltas iki pat vidaus? Spustelėkite jį.

¬∀x (A(x) → B(x))

1∀x (A(x) → ¬B(x))
2∃x (A(x) → ¬B(x))
3∃x (A(x) ∧ ¬B(x))
4∀x (A(x) ∧ ¬B(x))

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

Karno žemėlapiu raskite minimalią F(A, B, C, D) = Σm(0, 6, 9, 10, 11, 12, 13, 14, 15) sumų sandaugos (POS) formą. Kiek sumos narių (daugiklių) N ji turi?

F(A, B, C, D) = Σm(0, 6, 9, 10, 11, 12, 13, 14, 15)

N =

6.Skaitmeninė logika: elementai, Karno žemėlapiai ir trigeriaiSunkus

Sinchroninis mod-5 skaitiklis skaičiuoja 0, 1, …, 4 ir tada grįžta į 0. Jis pradeda nuo 4. Kokį skaičių Q (dešimtainiu pavidalu) jis rodo po 20 taktinių impulsų?

Q₀ = 420N = 5

Q =

7.Skaičių teorija ir modulinė aritmetikaVidutinis

Raskite 14 atvirkštinį moduliu 47: skaičių x, kur 0 < x < 47 ir 14·x ≡ 1 (mod 47).

a = 14n = 47

14⁻¹ mod 47 =

8.Skaičių teorija ir modulinė aritmetikaSunkus

Išspręskite 10x ≡ 14 (mod 34). Pateikite mažiausią teigiamą sprendinį x.

10x ≡ 14 (mod 34)

x =

9.Algoritmai ir sudėtingumasVidutinis

Kam lygus rekurentinės lygties T(n) = 2T(n − 1) + O(1) sprendinys?

AO(n)
BO(n log n)
CO(n²)
DO(2ⁿ)

10.Algoritmai ir sudėtingumasSunkus

Kuris NP klasės apibrėžimas teisingas?

AUždaviniai, kurių neišsprendžia joks algoritmas
BUždaviniai, kurių negalima išspręsti per polinominį laiką
CSprendimo uždaviniai, kurių teigiamus atsakymus, turint sertifikatą, galima patikrinti per polinominį laiką
DUždaviniai, kurie nėra polinominiai

11.Duomenų struktūrosVidutinis

Kokią balanso sąlygą AVL medis palaiko kiekviename mazge?

AKiekvienas mazgas nuspalvintas raudonai arba juodai
BKairiojo ir dešiniojo pomedžių aukščiai skiriasi daugiausia 1
CAbiejuose kiekvieno mazgo pomedžiuose yra lygiai tiek pat mazgų
DVisi lapai lygiai tame pačiame gylyje

12.Duomenų struktūrosSunkus

Bloomo filtras į klausimą „ar šis elementas yra aibėje?“ gali atsakyti:

AVisada tiksliai
BSu galimais klaidingai teigiamais, bet be klaidingai neigiamų atsakymų
CSu galimais klaidingai neigiamais, bet be klaidingai teigiamų atsakymų
DTik skaičiams

13.Grafų teorijaVidutinis

Medis turi 2 viršūnių, kurių laipsnis 3, 2 viršūnių, kurių laipsnis 4, 3 viršūnių, kurių laipsnis 5, 2 viršūnių, kurių laipsnis 2, o visos kitos jo viršūnės yra lapai (laipsnis 1). Kiek lapų L jis turi?

2 × deg 32 × deg 43 × deg 52 × deg 2

L =

14.Grafų teorijaSunkus

Dijkstros algoritmas vykdomas nuo A. Spustelėkite viršūnę, užfiksuojamą (padaromą galutine) 3 etape; pats A yra 1 etapas.

pradžia: Aetapas 3

15.Duomenų bazės ir SQLVidutinis

LEFT JOIN grąžina:

ATik atitinkančias abiejų lentelių eilutes
BEilutes, neturinčias atitikmens nė vienoje lentelėje
CTik visas dešiniosios lentelės eilutes
DVisas kairiosios lentelės eilutes ir atitinkančias dešiniosios lentelės eilutes, o ten, kur atitikmens nėra, – NULL

16.Duomenų bazės ir SQLSunkus

Boyce’o–Coddo normalinė forma (BCNF) reikalauja, kad kiekvienai netrivialiai funkcinei priklausomybei X → Y:

AY būtų atominis
BY būtų pirminis raktas
CX turėtų NULL
DX būtų superraktas

17.Kompiuterių tinklaiVidutinis

Kurį protokolą naudoja komanda „ping“?

AICMP
BUDP
CTCP
DHTTP

18.Kompiuterių tinklaiSunkus

Naudotojas gali „pingu“ pasiekti 8.8.8.8, bet negali atidaryti jokios svetainės pagal vardą. Kur labiausiai tikėtina problema?

ANumatytajame šliuze
BTinklo plokštės tvarkyklėje
CVardų išsprendime (DNS)
DFiziniame kabelyje

19.IPv4 potinkliaiVidutinis

Tinklą 192.168.10.0/24 reikia padalyti į bent 4 vienodų potinklių. Jei pasiskolinsite kuo mažiau bitų, kiek naudojamų mazgų H turės kiekvienas potinklis?

192.168.10.0/244 subnets

H =

20.IPv4 potinkliaiSunkus

Mazgo adresas yra 10.20.83.207/25. Koks yra jo tinklo adreso ketvirtasis oktetas x?

10.20.83.207/25

x =

3Tirpalai

1.Skaičiavimo sistemos

Atsakymas: U = 227

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ą

29 = 0001 1101

invertuota: 1110 0010

+1 → 1110 0011

Perskaitykite be ženklo

1110 0011₂ = 256 − 29 = 227

Atsakymas

U = 227

2.Skaičiavimo sistemos

Atsakymas: b = 11 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.

Dvejeto laipsniai

2¹⁰ = 1024 < 1465

2¹¹ = 2048 ≥ 1465

Atsakymas

b = 11

3.Teiginių logika ir įrodymai

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

¬(a ↔ b) yra 1 lygiai tada, kai a ir b skiriasi, o tai yra a ↔ ¬b.

¬(a ↔ b) ≡ a ↔ ¬b

Patikrinkite teisingumo lentele

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

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

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

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

Atsakymas

a ↔ ¬b

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

4.Teiginių logika ir įrodymai

Atsakymas: ∃x (A(x) ∧ ¬B(x))

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 (A(x) → B(x)) ≡ ∃x (A(x) ∧ ¬B(x))

Atsakymas

∃x (A(x) ∧ ¬B(x))

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.

Sugrupuokite nulius

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

(A + D′)

(A + B + C′)

(A + B′ + C)

(A′ + B + C + D)

Minimali POS forma

F = (A + D′)(A + B + C′)(A + B′ + C)(A′ + B + C + D)

N = 4

Atsakymas

N = 4

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

Atsakymas: Q = 4

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 f_clk/N dažniu. n trigerių Johnsono skaitiklis turi 2n būsenų, žiedinis – n.

Pilni ciklai

Kas 5 impulsų skaitiklis grįžta į tą pačią būseną.

20 = 4·5 + 0

Skaičius po likusių impulsų

Q = (4 + 0) mod 5 = 4

Q = 100₂

Atsakymas

Q = 4

7.Skaičių teorija ir modulinė aritmetika

Atsakymas: 14⁻¹ mod 47 = 37

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

Išplėstinis Euklido algoritmas

Kiekviena liekana r užrašoma kaip r ≡ t·14 (mod 47).

r = 47, t = 0

r = 14, q = 3, t = 1

r = 5, q = 2, t = −3

r = 4, q = 1, t = 7

r = 1, q = 4, t = −10

Atvirkštinė

1 ≡ −10·14 (mod 47)

x = 37

patikra: 14·37 = 518 = 11·47 + 1

Atsakymas

14⁻¹ mod 47 = 37

8.Skaičių teorija ir modulinė aritmetika

Atsakymas: x = 15

Padalykite iš DBD

gcd(10, 34) = 2

5x ≡ 7 (mod 17)

Išspręskite suprastintą kongruenciją

5⁻¹ ≡ 7 (mod 17) → x ≡ 15 (mod 17)

Sprendiniai moduliu 34

x ∈ {15, 32}

x = 15

Atsakymas

x = 15

9.Algoritmai ir sudėtingumas

Atsakymas: D · O(2ⁿ)

Kodėl tai yra atsakymas

Kvietimų skaičius kiekviename lygmenyje padvigubėja, o lygmenų yra n, todėl iš viso gaunama apie 2ⁿ, kaip Hanojaus bokštų uždavinyje.

Atsakymas

D · O(2ⁿ)

10.Algoritmai ir sudėtingumas

Atsakymas: C · Sprendimo uždaviniai, kurių teigiamus atsakymus, turint sertifikatą, galima patikrinti per polinominį laiką

Kodėl tai yra atsakymas

NP uždaviniui pasiūlytą sprendinį (sertifikatą) galima greitai patikrinti, pvz., patikrinti, ar duotas priskyrimas tenkina loginę formulę.

Atsakymas

C · Sprendimo uždaviniai, kurių teigiamus atsakymus, turint sertifikatą, galima patikrinti per polinominį laiką

11.Duomenų struktūros

Atsakymas: B · Kairiojo ir dešiniojo pomedžių aukščiai skiriasi daugiausia 1

Kodėl tai yra atsakymas

Balanso koeficientas (kairiojo aukštis − dešiniojo aukštis) turi būti −1, 0 arba 1; po įterpimų ir šalinimų jį atkuria posūkiai.

Atsakymas

B · Kairiojo ir dešiniojo pomedžių aukščiai skiriasi daugiausia 1

12.Duomenų struktūros

Atsakymas: B · Su galimais klaidingai teigiamais, bet be klaidingai neigiamų atsakymų

Kodėl tai yra atsakymas

Jei bet kuris elemento bitas lygus 0, elemento tikrai nėra; jei visi lygūs 1, jis tikriausiai yra. Bloomo filtrai iškeičia tikslumą į labai mažą atminties sąnaudą.

Atsakymas

B · Su galimais klaidingai teigiamais, bet be klaidingai neigiamų atsakymų

13.Grafų teorija

Atsakymas: L = 17

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ą; K_n 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ų.

Rankų paspaudimo lema medžiui

L + 33 = 2(L + 9) − 2

L = 17

Atsakymas

L = 17

Trumpesnis kelias: L = 2 + Σ (d − 2) pagal viršūnes, kurių laipsnis d ≥ 3.

14.Grafų teorija

Atsakymas: C

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

Dijkstra etapas po etapo

1. A (0): B: 4, C: 5

2. B (4)

3. C (5): E: 12, G: 10

4. G (10): D: 18

5. E (12)

6. D (18): F: 27

7. F (27)

etapas 3

Atsakymas

15.Duomenų bazės ir SQL

Atsakymas: D · Visas kairiosios lentelės eilutes ir atitinkančias dešiniosios lentelės eilutes, o ten, kur atitikmens nėra, – NULL

Kodėl tai yra atsakymas

Kairysis išorinis sujungimas palieka kiekvieną kairiosios lentelės eilutę; neatitikę dešiniosios lentelės stulpeliai užpildomi NULL.

Atsakymas

D · Visas kairiosios lentelės eilutes ir atitinkančias dešiniosios lentelės eilutes, o ten, kur atitikmens nėra, – NULL

16.Duomenų bazės ir SQL

Atsakymas: D · X būtų superraktas

Kodėl tai yra atsakymas

BCNF reikalauja, kad kiekvienas determinantas būtų kandidatinis raktas (superraktas); 3NF leidžia išimtį, kai Y yra kandidatinio rakto dalis.

Atsakymas

D · X būtų superraktas

17.Kompiuterių tinklai

Atsakymas: A · ICMP

Kodėl tai yra atsakymas

Ping siunčia ICMP aido užklausas (echo request) ir matuoja laiką, kol grįžta aido atsakymai (echo reply).

Atsakymas

A · ICMP

18.Kompiuterių tinklai

Atsakymas: C · Vardų išsprendime (DNS)

Kodėl tai yra atsakymas

Sėkmingas ping į išorinį IP įrodo, kad kabeliai, adresavimas ir maršrutizavimas veikia. Neveikiantys vardai rodo DNS serverio ar resolverio nustatymo problemą.

Atsakymas

C · Vardų išsprendime (DNS)

19.IPv4 potinkliai

Atsakymas: H = 62

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

Skolinami bitai

2² = 4 ≥ 4 → b = 2, /26

Mazgai potinklyje

2⁶ − 2 = 62

Atsakymas

H = 62

20.IPv4 potinkliai

Atsakymas: x = 128

Bloko dydis

2⁷ = 128

Šio mazgo potinklis

tinklas: ⌊207/128⌋·128 = 128

transliacija: 128 + 128 − 1 = 255

naudojami mazgai: 129 … 254

Atsakymas

x = 128

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