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
pozicijų vertės papildomajame kode1−12806413211618140201

8 bitų seka 1011 1100 saugo sveikąjį skaičių su ženklu papildomajame kode. Kokia jo reikšmė N dešimtainėje sistemoje?

1011 11008 bit
N =
2.Skaičiavimo sistemosSunkus
8 bit1 px256 px256 pxM = ? KiB

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

256 × 256 px8 bit/px1 KiB = 1024 B
M = KiB
3.Teiginių logika ir įrodymaiVidutinis
pqrq ↔ rp ↔ (q ↔ r)¬(q ∧ (r → p)) → (p ↔ (q ↔ r))111?110?101?100?011?010?001?000?

Kiek iš 8 teisingumo lentelės eilučių ¬(q ∧ (r → p)) → (p ↔ (q ↔ r)) yra teisinga? Pažymėkite šį skaičių N.

¬(q ∧ (r → p)) → (p ↔ (q ↔ r))
N =
4.Teiginių logika ir įrodymaiSunkus
q ∨ rp ∧ rp ∨ r¬p

Duotos prielaidos q ∨ p; ¬q ∨ r. Kokia išvada iš jų išplaukia? Spustelėkite ją.

q ∨ p¬q ∨ r
  1. 1q ∨ r
  2. 2p ∧ r
  3. 3p ∨ r
  4. 4¬p
5.Skaitmeninė logika: elementai, Karno žemėlapiai ir trigeriaiVidutinis
MUXCI0​0I1​0I2​0I3​ABS1​S0​F

4 į 1 multiplekserio pasirinkimo įėjimai yra S₁ = A ir S₀ = B, o duomenų įėjimai prijungti prie I₀ = C, I₁ = 0, I₂ = 0, I₃ = 0. Kiek iš 8 A, B ir C derinių duoda išėjimą F = 1? Raskite N.

I₀ = CI₁ = 0I₂ = 0I₃ = 0
N =
6.Skaitmeninė logika: elementai, Karno žemėlapiai ir trigeriaiSunkus
TQ0​Q0​TQ1​Q1​TQ2​Q2​CLKMOD-5

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

Q0 = 019N = 5
Q =
7.Skaičių teorija ir modulinė aritmetikaVidutinis

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

a = 33n = 70
33−1 mod 70 =
8.Skaičių teorija ir modulinė aritmetikaSunkus

Kiek sprendinių N turi 39x ≡ 6 (mod 60) aibėje {0, 1, …, 59}?

39x ≡ 6 (mod 60)
N =
9.Algoritmai ir sudėtingumasVidutinis

Kuri godžioji taisyklė veiklų atrankos uždavinyje visada duoda didžiausią nepersidengiančių veiklų skaičių?

  1. APirmiausia pasirinkti trumpiausią veiklą
  2. BPasirinkti anksčiausiai pasibaigiančią veiklą, tada kartoti su suderinamomis
  3. CPirmiausia pasirinkti veiklą, turinčią mažiausiai persidengimų, tada kartoti su suderinamomis
  4. DPasirinkti anksčiausiai prasidedančią veiklą
10.Algoritmai ir sudėtingumasSunkus

Kuris NP klasės apibrėžimas teisingas?

  1. ASprendimo uždaviniai, kurių teigiamus atsakymus, turint sertifikatą, galima patikrinti per polinominį laiką
  2. BUždaviniai, kurie nėra polinominiai
  3. CUždaviniai, kurių neišsprendžia joks algoritmas
  4. DUždaviniai, kurių negalima išspręsti per polinominį laiką
11.Duomenų struktūrosVidutinis

Kiek laiko užtrunka patikrinti, ar briauna (u, v) egzistuoja, naudojant gretimumo matricą?

  1. AO(1)
  2. BO(E)
  3. CO(log V)
  4. DO(V)
12.Duomenų struktūrosSunkus

Iš n skaičių srauto reikia išlaikyti k mažiausių reikšmių naudojant O(k) atminties. Kuris būdas veikia per O(n log k)?

  1. AVisų n reikšmių surikiuotas masyvas
  2. BMin krūva, laikanti visas n reikšmių, iš kurios pabaigoje išimama k mažiausių
  3. CPaskutinių k reikšmių FIFO eilė
  4. Dk dydžio max krūva, kurios šaknis pakeičiama atėjus mažesnei reikšmei
13.Grafų teorijaVidutinis

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

4 × deg 33 × deg 5
L =
14.Grafų teorijaSunkus
12721456577ABCDEF

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

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

Lentelėje yra eilučių, kurių col yra NULL. Kurias eilutes grąžina WHERE col = NULL?

  1. AVisas lentelės eilutes
  2. BTik eilutes, kuriose col yra NULL, kaip su IS NULL
  3. CJokių eilučių, nes palyginimo rezultatas nežinomas
  4. DKlaidą kiekvienoje duomenų bazėje
16.Duomenų bazės ir SQLSunkus

Ataskaitų duomenų bazė, kad išvengtų sujungimų, kopijuoja klientų vardus į užsakymų lentelę. Kokia pagrindinė šios denormalizacijos kaina?

  1. AUžklausos užsakymų lentelei tampa lėtesnės
  2. BPertekliniai egzemplioriai turi būti palaikomi nuoseklūs, kai tik pasikeičia kliento duomenys
  3. CDuomenų bazė nebegali naudoti indeksų
  4. DNebegalima naudoti pirminių raktų
17.Kompiuterių tinklaiVidutinis

Kokį terpės prieigos metodą naudojo klasikinis bendrosios terpės (pusiau dupleksinis) Ethernet?

  1. AŽetono perdavimą
  2. BCSMA/CA
  3. CCSMA/CD
  4. DTDMA
18.Kompiuterių tinklaiSunkus

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?

  1. APriversdamas A ir C naudoti kolizijų aptikimą, kad jos nustotų siųsti, kai kadrai persidengia
  2. BPasirenkamais RTS/CTS mainais: prieigos taško CTS liepia visoms netoliese esančioms stotims palaukti
  3. CPadidindamas kadrų TTL
  4. DMaršrutizuodamas A kadrus per C
19.IPv4 potinkliaiVidutinis
/24 → /2911111111111111111111111111111000tinklo bitaimazgo bitai

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

192.168.10.0/2420 subnets
H =
20.IPv4 potinkliaiSunkus
paskutinis oktetas = 50012806413211608041201tinklasmazgas

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

10.20.44.50/29
x =

3Tirpalai

1.Skaičiavimo sistemos

Atsakymas: N = −68

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.

Sudėkite vertes

Kiti bitai išlaiko įprastas teigiamas vertes.

−128 + 32 + 16 + 8 + 4 = −68

Atsakymas

N = −68
2.Skaičiavimo sistemos

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

256·256·8 = 524288 bit = 65536 B

Paverskite į KiB

65536/1024 = 64 KiB

Atsakymas

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

Atsakymas: N = 5

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.

Teisingumo lentelė eilutė po eilutės

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

Suskaičiuokite eilutes su reikšme 1

¬(q ∧ (r → p)) → (p ↔ (q ↔ r)): 1, 1, 0, 1, 0, 1, 1, 0
N = 5

Atsakymas

N = 5
4.Teiginių logika ir įrodymai

Atsakymas: p ∨ r

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

p = 1, q = 1, r = 1: q ∨ r = 1, p ∧ r = 1, p ∨ r = 1, ¬p = 0
p = 1, q = 0, r = 1: q ∨ r = 1, p ∧ r = 1, p ∨ r = 1, ¬p = 0
p = 1, q = 0, r = 0: q ∨ r = 0, p ∧ r = 0, p ∨ r = 1, ¬p = 0
p = 0, q = 1, r = 1: q ∨ r = 1, p ∧ r = 0, p ∨ r = 1, ¬p = 1

Išvada

p ∨ r (skiriamoji geba)

Atsakymas

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

Atsakymas: N = 1

Multiplekseris: 2ⁿ į 1 multiplekseris perduoda vieną iš savo duomenų įėjimų į išėjimą; pasirinkimo linijos, skaitomos kaip dvejetainis skaičius, nurodo kurį. 4 į 1 MUX su pasirinkimo įėjimais S₁S₀ = AB, F = A′B′·I₀ + A′B·I₁ + AB′·I₂ + AB·I₃. Duomenų įėjimus prijungus prie 0, 1, C arba C′, MUX gali sukurti bet kurią A, B ir C funkciją; tai dažnas būdas sudaryti logiką viena mikroschema.

Išėjimo išraiška

F = A′B′C

Eilutės su F = 1

ABC = 001
N = 1

Atsakymas

N = 1
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 fclk/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ą.

19 = 3·5 + 4

Skaičius po likusių impulsų

Q = (0 + 4) mod 5 = 4
Q = 100₂

Atsakymas

Q = 4
7.Skaičių teorija ir modulinė aritmetika

Atsakymas: 33−1 mod 70 = 17

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·33 (mod 70).

r = 70, t = 0
r = 33, q = 2, t = 1
r = 4, q = 8, t = −2
r = 1, q = 4, t = 17

Atvirkštinė

1 ≡ 17·33 (mod 70)
x = 17
patikra: 33·17 = 561 = 8·70 + 1

Atsakymas

33−1 mod 70 = 17
8.Skaičių teorija ir modulinė aritmetika

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

Padalykite iš DBD

gcd(39, 60) = 3
13x ≡ 2 (mod 20)

Išspręskite suprastintą kongruenciją

13−1 ≡ 17 (mod 20) → x ≡ 14 (mod 20)

Sprendiniai moduliu 60

x ∈ {14, 34, 54}
N = 3

Atsakymas

N = 3
9.Algoritmai ir sudėtingumas

Atsakymas: B · Pasirinkti anksčiausiai pasibaigiančią veiklą, tada kartoti su suderinamomis

Kodėl tai yra atsakymas

Anksčiausios pabaigos pasirinkimo optimalumą galima įrodyti mainų argumentu; kitoms taisyklėms yra kontrpavyzdžių.

Atsakymas

B · Pasirinkti anksčiausiai pasibaigiančią veiklą, tada kartoti su suderinamomis
10.Algoritmai ir sudėtingumas

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

A · Sprendimo uždaviniai, kurių teigiamus atsakymus, turint sertifikatą, galima patikrinti per polinominį laiką
11.Duomenų struktūros

Atsakymas: A · O(1)

Kodėl tai yra atsakymas

Matricos įrašas u eilutėje ir v stulpelyje iš karto parodo, ar briauna egzistuoja; gretimumo sąraše gali tekti peržiūrėti u kaimynus.

Atsakymas

A · O(1)
12.Duomenų struktūros

Atsakymas: D · k dydžio max krūva, kurios šaknis pakeičiama atėjus mažesnei reikšmei

Kodėl tai yra atsakymas

Max krūvos šaknis yra didžiausia laikoma reikšmė; bet kuri mažesnė nauja reikšmė ją pakeičia per O(log k), todėl krūvoje visada yra k mažiausių iki šiol reikšmių.

Atsakymas

D · k dydžio max krūva, kurios šaknis pakeičiama atėjus mažesnei reikšmei
13.Grafų teorija

Atsakymas: L = 15

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

Rankų paspaudimo lema medžiui

L + 27 = 2(L + 7) − 2
L = 15

Atsakymas

L = 15

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

14.Grafų teorija

Atsakymas: B

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, C: 7
2. C (7): B: 9, E: 12
3. B (9): D: 23
4. E (12): D: 18, F: 19
5. D (18)
6. F (19)

etapas 3

B

Atsakymas

B
15.Duomenų bazės ir SQL

Atsakymas: C · Jokių eilučių, nes palyginimo rezultatas nežinomas

Kodėl tai yra atsakymas

Bet koks palyginimas su NULL naudojant = duoda UNKNOWN, o WHERE palieka tik TRUE eilutes; vietoj to naudokite col IS NULL.

Atsakymas

C · Jokių eilučių, nes palyginimo rezultatas nežinomas
16.Duomenų bazės ir SQL

Atsakymas: B · Pertekliniai egzemplioriai turi būti palaikomi nuoseklūs, kai tik pasikeičia kliento duomenys

Kodėl tai yra atsakymas

Denormalizacija pagreitina skaitymą, bet sugrąžina perteklių, todėl atnaujinimai turi pakeisti kiekvieną kopiją, kitaip atsiranda anomalijų.

Atsakymas

B · Pertekliniai egzemplioriai turi būti palaikomi nuoseklūs, kai tik pasikeičia kliento duomenys
17.Kompiuterių tinklai

Atsakymas: C · CSMA/CD

Kodėl tai yra atsakymas

Daugkartinė prieiga su nešlio jutimu ir kolizijų aptikimu: aptikusios koliziją stotys sustoja ir bando vėl po atsitiktinės delsos. Visiškai dupleksiniame komutuojamame Ethernet kolizijų nėra.

Atsakymas

C · CSMA/CD
18.Kompiuterių tinklai

Atsakymas: B · Pasirenkamais RTS/CTS mainais: prieigos taško CTS liepia visoms netoliese esančioms stotims palaukti

Kodėl tai yra atsakymas

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

B · Pasirenkamais RTS/CTS mainais: prieigos taško CTS liepia visoms netoliese esančioms stotims palaukti
19.IPv4 potinkliai

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

Skolinami bitai

25 = 32 ≥ 20 → b = 5, /29

Mazgai potinklyje

23 − 2 = 6

Atsakymas

H = 6
20.IPv4 potinkliai

Atsakymas: x = 54

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: ⌊50/8⌋·8 = 48
transliacija: 48 + 8 − 1 = 55
naudojami mazgai: 49 … 54

Atsakymas

x = 54

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