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

N = −418 bit
U =
2.Skaičiavimo sistemosSunkus
24 bitų dvejetainis papildomasis kodas, N = ??ženklas???????????????????????

Koks yra mažiausias (labiausiai neigiamas) sveikasis skaičius N, kurį galima užrašyti 24 bitų papildomuoju kodu?

24 bit
N =
3.Teiginių logika ir įrodymaiVidutinis
(b → a) ∧ (c → a)b → (c → a)(b → c) → ab ∧ (c → a)

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

(b ∧ c) → a
  1. 1(b → a) ∧ (c → a)
  2. 2b → (c → a)
  3. 3(b → c) → a
  4. 4b ∧ (c → a)
4.Teiginių logika ir įrodymaiSunkus

Kiek iš 16 teisingumo lentelės eilučių daro ((s ∨ q) ↔ (p → ¬r)) ∧ ((r ∨ p) → (q → s)) teisingą? Pažymėkite šį skaičių N.

((s ∨ q) ↔ (p → ¬r)) ∧ ((r ∨ p) → (q → s))
N =
5.Skaitmeninė logika: elementai, Karno žemėlapiai ir trigeriaiVidutinis
ABCD0001111000011110111111

Šiame Karno žemėlapyje lygiai vienas vienetas neturi gretimo vieneto, todėl minimalioje SOP formoje lieka vieno langelio grupe (pilna keturių literalų minterma). Kaimynai per žemėlapio kraštus skaičiuojami. Spustelėkite tą langelį.

F = Σm(1, 4, 6, 7, 10, 14)
  1. 1AB = 00, CD = 00
  2. 2AB = 00, CD = 01
  3. 3AB = 00, CD = 11
  4. 4AB = 00, CD = 10
  5. 5AB = 01, CD = 00
  6. 6AB = 01, CD = 01
  7. 7AB = 01, CD = 11
  8. 8AB = 01, CD = 10
  9. 9AB = 11, CD = 00
  10. 10AB = 11, CD = 01
  11. 11AB = 11, CD = 11
  12. 12AB = 11, CD = 10
  13. 13AB = 10, CD = 00
  14. 14AB = 10, CD = 01
  15. 15AB = 10, CD = 11
  16. 16AB = 10, CD = 10
6.Skaitmeninė logika: elementai, Karno žemėlapiai ir trigeriaiSunkus
CLKT12345678

Kylančiuoju frontu valdomas T trigeris pradeda nuo Q = 0 ir gauna parodytus įėjimus. Spustelėkite pirmąjį taktinį frontą, kuriuo Q iš 1 grįžta į 0.

Q₀ = 0T
  1. 1taktinis frontas 1
  2. 2taktinis frontas 2
  3. 3taktinis frontas 3
  4. 4taktinis frontas 4
  5. 5taktinis frontas 5
  6. 6taktinis frontas 6
  7. 7taktinis frontas 7
  8. 8taktinis frontas 8
7.Skaičių teorija ir modulinė aritmetikaVidutinis

Išspręskite 5x ≡ 6 (mod 13). Pateikite sprendinį x, kur 0 < x < 13.

5x ≡ 6 (mod 13)
x =
8.Skaičių teorija ir modulinė aritmetikaSunkus

Išspręskite 12x ≡ 60 (mod 75). Pateikite mažiausią teigiamą sprendinį x.

12x ≡ 60 (mod 75)
x =
9.Algoritmai ir sudėtingumasVidutinis

Kodėl daug bibliotekinių rikiavimo procedūrų labai mažiems daliniams masyvams pereina prie rikiavimo įterpimu?

  1. ARikiavimas įterpimu turi mažas pridėtines sąnaudas ir yra greitas su mažomis ar beveik surikiuotomis įvestimis
  2. BRikiavimas įterpimu didelėms įvestims naudoja mažiau atminties nei bet kuris kitas rikiavimo algoritmas
  3. CRikiavimas įterpimu blogiausiu atveju yra O(n log n)
  4. DRekursiniai algoritmai negali apdoroti mažesnių nei 10 elementų masyvų
10.Algoritmai ir sudėtingumasSunkus

Kuris teiginys apie mažojo o žymėjimą teisingas?

  1. A2n = o(n), nes 2n auga lėtai
  2. Bn = o(n²), bet n nėra o(n)
  3. Cn = o(n), nes kiekviena funkcija yra mažasis o pati sau
  4. Dn² = o(n)
11.Duomenų struktūrosVidutinis

Kokia kaina įterpti elementą į n elementų masyvo vidurį?

  1. AO(n), nes vėlesnius elementus reikia pastumti
  2. BO(log n), dėl dvejetainės paieškos
  3. CO(1), nes indeksas žinomas
  4. DO(n²), nes kiekvienas elementas pajuda n kartų
12.Duomenų struktūrosSunkus

Žiediniame buferyje front == rear gali reikšti, kad jis tuščias arba pilnas. Koks dažnas būdas juos atskirti?

  1. ALaikyti atskirą elementų skaitiklį arba visada palikti vieną vietą nenaudojamą
  2. BBuferio dydį padaryti dvejeto laipsniu
  3. CFront ir rear saugoti tame pačiame kintamajame
  4. DVisada išvalyti buferį, kai front lygus rear, kad būsena būtų tuščia
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
1210114865510ABCDEFG

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

pradžia: Aetapas 6
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
  7. 7G
15.Duomenų bazės ir SQLVidutinis

Kuri užklausa grąžina skirtingų miestų skaičių customers lentelėje?

  1. ASELECT COUNT(DISTINCT city) FROM customers
  2. BSELECT COUNT(city) FROM customers GROUP BY city
  3. CSELECT DISTINCT COUNT(city) FROM customers
  4. DSELECT SUM(DISTINCT city) FROM customers
16.Duomenų bazės ir SQLSunkus

Kodėl užklausa su WHERE YEAR(order_date) = 2025 gali nenaudoti stulpelio order_date indekso?

  1. AYEAR nėra galiojantis SQL
  2. BIndeksai niekada neveikia su datomis
  3. CIndeksas pagal order_date naudojamas tik ORDER BY sąlygoms, niekada WHERE
  4. DFunkcijos taikymas stulpeliui neleidžia atlikti paprastos intervalinės paieškos indekse
17.Kompiuterių tinklaiVidutinis

Kuris iš šių yra privatus IPv4 adresų diapazonas?

  1. A200.1.1.0/24
  2. B100.0.0.0/8
  3. C8.8.8.0/24
  4. D192.168.0.0/16
18.Kompiuterių tinklaiSunkus

TCP ryšio langas 64 KB, apsisukimo laikas 100 ms, lango mastelis nenaudojamas. Koks apytikslis didžiausias jo našumas?

  1. AApie 5 Mbit/s
  2. BApie 50 Mbit/s
  3. CApie 0,5 Mbit/s
  4. DApie 640 Mbit/s
19.IPv4 potinkliaiVidutinis
/?11111111111111111111111110000000tinklo bitaimazgo bitai

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

110 hosts
p =
20.IPv4 potinkliaiSunkus
paskutinis oktetas = 153112806403211618040211tinklasmazgas

Mazgo adresas yra 10.20.32.153/30. Koks yra jo potinklio transliacijos adreso paskutinis skaičius (ketvirtasis oktetas) x?

10.20.32.153/30
x =

3Tirpalai

1.Skaičiavimo sistemos

Atsakymas: U = 215

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ą

41 = 0010 1001
invertuota: 1101 0110
+1 → 1101 0111

Perskaitykite be ženklo

1101 0111₂ = 256 − 41 = 215

Atsakymas

U = 215
2.Skaičiavimo sistemos

Atsakymas: N = −8,389 × 10⁶

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.

Labiausiai neigiama reikšmė

−223 = −8388608

Atsakymas

N = −8388608
3.Teiginių logika ir įrodymai

Atsakymas: b → (c → a)

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

Eksportacija: (a ∧ b) → c ≡ a → (b → c). Abi yra 0 tik tada, kai a = 1, b = 1 ir c = 0.
(b ∧ c) → a ≡ b → (c → a)

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 0
a = 1, b = 0, c = 0: 1 | 1 1 1 0
a = 0, b = 1, c = 1: 0 | 0 0 0 0
a = 0, b = 1, c = 0: 1 | 0 1 1 1
a = 0, b = 0, c = 1: 1 | 0 1 0 0
a = 0, b = 0, c = 0: 1 | 1 1 0 0

Atsakymas

b → (c → a)

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

4.Teiginių logika ir įrodymai

Atsakymas: N = 8

Teisingumo lentelės: formulė su n skirtingų kintamųjų turi 2ⁿ eilučių, po vieną kiekvienam teisingumo reikšmių deriniui (1 = teisinga, 0 = klaidinga). Dirbkite iš vidaus į išorę ir kiekvienai posakio daliai skirkite savo stulpelį. ¬a apverčia reikšmę; a ∧ b yra 1 tik tada, kai abu lygūs 1; a ∨ b yra 0 tik tada, kai abu lygūs 0; a → b yra 0 tik tada, kai a = 1 ir b = 0; a ↔ b yra 1, kai abi pusės lygios.

Stulpeliai

s ∨ q; ¬r; p → ¬r; (s ∨ q) ↔ (p → ¬r); r ∨ p; q → s; (r ∨ p) → (q → s); ((s ∨ q) ↔ (p → ¬r)) ∧ ((r ∨ p) → (q → s))

Skaidymas pagal p

p = 1: 3
p = 0: 5
N = 3 + 5 = 8

Atsakymas

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

Atsakymas: AB = 00, CD = 01

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.

Kiekvieno vieneto kaimynai

Vienetas su gretimu vienetu gali įeiti į dviejų ar daugiau langelių grupę.

m1: m0, m3, m5, m9 → 0
ABCD0001111000011110111111

Izoliuotas vienetas

m1 = A′B′C′D → AB = 00, CD = 01

Atsakymas

AB = 00, CD = 01
6.Skaitmeninė logika: elementai, Karno žemėlapiai ir trigeriai

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

Q po kiekvieno fronto

T trigeris kiekvienu kylančiuoju frontu perjungia, kai T = 1, ir išlaiko, kai T = 0.

1: T = 0 → Q = 0
2: T = 0 → Q = 0
3: T = 1 → Q = 1
4: T = 1 → Q = 0
5: T = 1 → Q = 1
6: T = 1 → Q = 0
7: T = 0 → Q = 0
8: T = 0 → Q = 0

Pirmasis pokytis iš 1 į 0

taktinis frontas 4

Atsakymas

taktinis frontas 4
7.Skaičių teorija ir modulinė aritmetika

Atsakymas: x = 9

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

5 atvirkštinis

r = 13, t = 0
r = 5, q = 2, t = 1
r = 3, q = 1, t = −2
r = 2, q = 1, t = 3
r = 1, q = 2, t = −5
5−1 ≡ 8 (mod 13)

Išspręskite

x ≡ 8·6 = 48 ≡ 9 (mod 13)
patikra: 5·9 = 45 ≡ 6 (mod 13)

Atsakymas

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

Atsakymas: x = 5

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(12, 75) = 3
4x ≡ 20 (mod 25)

Išspręskite suprastintą kongruenciją

4−1 ≡ 19 (mod 25) → x ≡ 5 (mod 25)

Sprendiniai moduliu 75

x ∈ {5, 30, 55}
x = 5

Atsakymas

x = 5
9.Algoritmai ir sudėtingumas

Atsakymas: A · Rikiavimas įterpimu turi mažas pridėtines sąnaudas ir yra greitas su mažomis ar beveik surikiuotomis įvestimis

Kodėl tai yra atsakymas

Mažiems n paprastas rikiavimo įterpimu ciklas aplenkia greitojo rikiavimo ar rikiavimo suliejimu rekursijos pridėtines sąnaudas, nors jis ir O(n²).

Atsakymas

A · Rikiavimas įterpimu turi mažas pridėtines sąnaudas ir yra greitas su mažomis ar beveik surikiuotomis įvestimis
10.Algoritmai ir sudėtingumas

Atsakymas: B · n = o(n²), bet n nėra o(n)

Kodėl tai yra atsakymas

f = o(g) reiškia, kad f(n) / g(n) artėja prie 0; n / n² artėja prie 0, bet n / n = 1 – ne.

Atsakymas

B · n = o(n²), bet n nėra o(n)
11.Duomenų struktūros

Atsakymas: A · O(n), nes vėlesnius elementus reikia pastumti

Kodėl tai yra atsakymas

Visi elementai po įterpimo vietos pasislenka viena pozicija į dešinę, o tai užtrunka n proporcingą laiką.

Atsakymas

A · O(n), nes vėlesnius elementus reikia pastumti
12.Duomenų struktūros

Atsakymas: A · Laikyti atskirą elementų skaitiklį arba visada palikti vieną vietą nenaudojamą

Kodėl tai yra atsakymas

Su skaitikliu tuščias reiškia count = 0, o pilnas – count = talpa; palikus vieną tuščią vietą, pilnas apibrėžiamas kaip (rear + 1) mod n == front.

Atsakymas

A · Laikyti atskirą elementų skaitiklį arba visada palikti vieną vietą nenaudojamą
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) = 2, deg(C) = 3, deg(D) = 1, deg(E) = 3

Nelyginės viršūnės

A, C, D, E → 4
nei viena

Atsakymas

nei viena
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: 12
2. B (12): D: 22
3. D (22): E: 36, F: 30, G: 27
4. G (27): C: 32
5. F (30)
6. C (32): E: 33
7. E (33)

etapas 6

C

Atsakymas

C
15.Duomenų bazės ir SQL

Atsakymas: A · SELECT COUNT(DISTINCT city) FROM customers

Kodėl tai yra atsakymas

COUNT(DISTINCT city) suskaičiuoja unikalius ne NULL miestus; DISTINCT už COUNT ribų tik pašalina pasikartojančias rezultato eilutes.

Atsakymas

A · SELECT COUNT(DISTINCT city) FROM customers
16.Duomenų bazės ir SQL

Atsakymas: D · Funkcijos taikymas stulpeliui neleidžia atlikti paprastos intervalinės paieškos indekse

Kodėl tai yra atsakymas

Ši išraiška nėra „sargable“; naudojant order_date >= '2025-01-01' AND order_date < '2026-01-01' galima atlikti intervalinį indekso skenavimą.

Atsakymas

D · Funkcijos taikymas stulpeliui neleidžia atlikti paprastos intervalinės paieškos indekse
17.Kompiuterių tinklai

Atsakymas: D · 192.168.0.0/16

Kodėl tai yra atsakymas

Privatūs diapazonai yra 10.0.0.0/8, 172.16.0.0/12 ir 192.168.0.0/16; jie nemaršrutizuojami viešajame internete.

Atsakymas

D · 192.168.0.0/16
18.Kompiuterių tinklai

Atsakymas: A · Apie 5 Mbit/s

Kodėl tai yra atsakymas

Našumas ≤ langas / RTT = 65,536 × 8 bitų / 0,1 s ≈ 5,2 Mbit/s, kad ir kokia sparti būtų jungtis.

Atsakymas

A · Apie 5 Mbit/s
19.IPv4 potinkliai

Atsakymas: p = 25

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

26 − 2 = 62 < 110
27 − 2 = 126 ≥ 110 → h = 7

Prefikso ilgis

p = 32 − 7 = 25

Atsakymas

p = /25
20.IPv4 potinkliai

Atsakymas: x = 155

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

22 = 4

Šio mazgo potinklis

tinklas: ⌊153/4⌋·4 = 152
transliacija: 152 + 4 − 1 = 155
naudojami mazgai: 153 … 154

Atsakymas

x = 155

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