Podstawy informatyki: zestaw na powtórkę

Wzory, najważniejsze kroki metod dla każdego tematu i 20 zadań do ćwiczenia, z pełnymi rozwiązaniami na końcu.

Nowe zadaniaWróć do przedmiotu

W oknie drukowania wybierz „Zapisz jako PDF”, aby zachować kopię na swoim urządzeniu.

1Wzory i metody

Systemy liczbowe

Wagi pozycji
dwójkowy 2k, ósemkowy 8k, szesnastkowy 16k
Na dziesiętny
Σ dk·bk
Z dziesiętnego
dziel przez podstawę, czytaj reszty od dołu do góry
Szesnastkowy ↔ dwójkowy
jedna cyfra szesnastkowa = 4 bity
Kod uzupełnień do dwóch (U2)
odwróć bity i dodaj 1

Rachunek zdań i dowody

Wiersze tablicy prawdy
2ⁿ
Implikacja
p → q ≡ ¬p ∨ q ≡ ¬q → ¬p
Zaprzeczenie implikacji
¬(p → q) ≡ p ∧ ¬q
Równoważność
p ↔ q ≡ (p → q) ∧ (q → p)
Prawa de Morgana
¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q
Prawa rozdzielności
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Zaprzeczanie kwantyfikatorów
¬∀x P(x) ≡ ∃x ¬P(x), ¬∃x P(x) ≡ ∀x ¬P(x)
Modus ponens, modus tollens
p → q, p ⊢ q; p → q, ¬q ⊢ ¬p

Metoda

  1. Policz różne zmienne: tablica prawdy ma 2ⁿ wierszy, a zaczyna się od samych jedynek.
  2. Każdej podformule daj osobną kolumnę i wypełniaj kolumny od wewnątrz na zewnątrz.
  3. Stosuj regułę każdego spójnika: → jest 0 tylko dla 1 → 0, ↔ jest 1, gdy obie strony się zgadzają.
  4. Przy równoważnościach porównaj końcowe kolumny wiersz po wierszu; przy wnioskowaniu patrz tylko na wiersze, w których każda przesłanka jest równa 1.
  5. Aby zaprzeczyć zdaniu z kwantyfikatorem, przesuń ¬ do środka, zamień ∀ i ∃ oraz zaprzecz formule wewnętrznej.

Logika cyfrowa: bramki, mapy Karnaugha i przerzutniki

Podstawowe bramki
A·B, A + B, A′, (A·B)′, (A + B)′, A ⊕ B
Reguły algebry Boole’a
X + X′ = 1, X·X′ = 0, X + XY = X, XY + XY′ = X
Prawa de Morgana
(X·Y)′ = X′ + Y′, (X + Y)′ = X′·Y′
Kolejność na mapie Karnaugha
00, 01, 11, 10 (Gray code)
Grupa 2ᵏ komórek
traci k zmiennych
Multiplekser 4-do-1
F = A′B′I0 + A′BI1 + AB′I2 + ABI3
Przerzutniki
D: Q⁺ = D, T: Q⁺ = T ⊕ Q, JK: Q⁺ = JQ′ + K′Q
Liczniki
n-bitowy: 2ⁿ stanów; mod-N: najmniejsze n z 2ⁿ ≥ N; fout = fclk/N
Licznik asynchroniczny (ripple)
fmax = 1/(n·tpd)
Liczniki pierścieniowy i Johnsona
n i 2n stanów

Metoda

  1. Dla układu przechodź od wejść do wyjścia bramka po bramce i zapisuj wartość na każdym przewodzie albo zapisz jego wyrażenie i wypełnij tablicę prawdy.
  2. Przy upraszczaniu wpisz jedynki (a stany nieokreślone jako X) na mapę Karnaugha z wierszami i kolumnami w kodzie Graya: 00, 01, 11, 10.
  3. Pokryj jedynki jak najmniejszą liczbą jak największych grup po 1, 2, 4, 8 lub 16 komórek, zawijając przez brzegi; każda grupa to jeden iloczyn ze zmiennych, które pozostają stałe. Dla postaci POS grupuj zera.
  4. Przy przerzutnikach i licznikach odczytuj wejścia przy każdym aktywnym zboczu zegara, zapisuj stan po każdym zboczu i pamiętaj, że n-bitowy licznik zawija się po 2ⁿ stanach.

Teoria liczb i arytmetyka modularna

Dzielenie z resztą
a = q·n + r, 0 ≤ r < n
Euklides
gcd(a, b) = gcd(b, a mod b)
Najmniejsza wspólna wielokrotność
lcm(a, b) = a·b/gcd(a, b)
Odwrotność
a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
Kongruencja liniowa
a·x ≡ b → x ≡ a⁻¹·b (mod n)
Funkcja φ Eulera
φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
Fermat
aᵖ⁻¹ ≡ 1 (mod p)
RSA
n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n

Metoda

  1. Najpierw zredukuj każdą liczbę modulo n; reszty leżą między 0 a n − 1.
  2. Aby znaleźć NWD, dziel wielokrotnie algorytmem Euklidesa; ostatnia niezerowa reszta jest NWD.
  3. Aby znaleźć element odwrotny, uruchom rozszerzony algorytm i zachowaj współczynnik przy a; dodaj n, jeśli jest ujemny.
  4. Rozwiąż a·x ≡ b, mnożąc przez a⁻¹; dwie kongruencje połącz, zapisując x = r₁ + m₁k.
  5. Przy potęgach zapisz wykładnik binarnie i wielokrotnie podnoś do kwadratu; w RSA d = e⁻¹ mod φ(n), gdzie φ(n) = (p − 1)(q − 1).

Teoria grafów

Lemat o uściskach dłoni
Σ deg(v) = 2|E|
Grafy pełne
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
Graf regularny
|E| = n·k/2
Drzewo i las
|E| = n − 1, |E| = n − c
Liście drzewa
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Euler
cykl: wszystkie stopnie parzyste; ścieżka: dokładnie 2 stopnie nieparzyste
Cykle Hamiltona w Kn
(n − 1)!/2
Aktualizacja w algorytmie Dijkstry
d(v) = min(d(v), d(u) + w(u, v))
Marsze o długości L
(Mᴸ)ij

Metoda

  1. Zapisz stopień każdego wierzchołka; suma stopni jest równa dwukrotności liczby krawędzi.
  2. W zadaniach o grafach eulerowskich sprawdź, czy graf jest spójny, i policz wierzchołki o nieparzystym stopniu.
  3. Dla drzew użyj n − 1 krawędzi i lematu o uściskach dłoni.
  4. W algorytmie Dijkstry prowadź tabelę tymczasowych odległości i w każdej rundzie zatwierdzaj niezatwierdzony wierzchołek o najmniejszej odległości.
  5. Dla minimalnego drzewa rozpinającego posortuj krawędzie według wagi i pomijaj każdą krawędź zamykającą cykl (Kruskal) albo rozbudowuj jedno drzewo od wierzchołka startowego (Prim).

Podsieci IPv4

Hosty na podsieć
2(32 − prefix) − 2 (/31: 2, /32: 1)
Rozmiar bloku
256 − (mask octet)
Adres sieci
IP AND maska
Adres rozgłoszeniowy
IP OR (NOT maska): wszystkie bity hosta równe 1
Podsieci z n pożyczonych bitów
2n

2Zadania do ćwiczenia

1.Systemy liczboweŚredni
wagi w kodzie U21−12816413201608040201

8-bitowy wzór 1110 0000 zapisuje liczbę całkowitą ze znakiem w kodzie uzupełnień do dwóch. Jaka jest jej wartość N dziesiętnie?

1110 00008 bit
N =
2.Systemy liczboweTrudny
8 bit1 px640 px480 pxM = ? KiB

Nieskompresowany obraz ma 640 × 480 pikseli i 8 bitów na piksel. Ile pamięci M zajmuje, w KiB (1 KiB = 1024 bajty)?

640 × 480 px8 bit/px1 KiB = 1024 B
M = KiB
3.Rachunek zdań i dowodyŚredni
abcb ↔ ac ∧ (b ↔ a)(b → (c → a)) → (c ∧ (b ↔ a))111?110?101?100?011?010?001?000?

W ilu z 8 wierszy tablicy prawdy (b → (c → a)) → (c ∧ (b ↔ a)) jest prawdziwe? Nazwij tę liczbę N.

(b → (c → a)) → (c ∧ (b ↔ a))
N =
4.Rachunek zdań i dowodyTrudny
∀x ¬F(x)∀x F(x)∃x ¬F(x)∃x F(x)

Które zdanie jest równoważne ¬∃x F(x), gdy negację przesunięto całkiem do środka? Kliknij je.

¬∃x F(x)
  1. 1∀x ¬F(x)
  2. 2∀x F(x)
  3. 3∃x ¬F(x)
  4. 4∃x F(x)
5.Logika cyfrowa: bramki, mapy Karnaugha i przerzutnikiŚredni
ABCD000111100001111010010312141507060120130150141819011010

Użyj mapy Karnaugha, aby znaleźć minimalną postać sumy iloczynów (SOP) funkcji F(A, B, C, D) = Σm(0, 2, 4, 5, 8, 9). Ile literałów L zawiera łącznie (zmienna z negacją liczy się jako jeden literał)?

F(A, B, C, D) = Σm(0, 2, 4, 5, 8, 9)
L =
6.Logika cyfrowa: bramki, mapy Karnaugha i przerzutnikiTrudny
ABCD0001111000011110101113120405X706012113115X141809X11110

Dla F(A, B, C, D) = Σm(0, 1, 2, 3, 8, 10, 13, 15) + d(7, 11, 14), gdzie d oznacza stany nieokreślone, znajdź liczbę N istotnych implikantów prostych.

F(A, B, C, D) = Σm(0, 1, 2, 3, 8, 10, 13, 15) + d(7, 11, 14)
N =
7.Teoria liczb i arytmetyka modularnaŚredni

Znajdź funkcję φ Eulera φ(931), czyli liczbę liczb całkowitych od 1 do 931 względnie pierwszych z 931.

n = 931 = 72·19
φ(931) =
8.Teoria liczb i arytmetyka modularnaTrudny

Rozwiąż 27x ≡ 33 (mod 48). Podaj najmniejsze dodatnie rozwiązanie x.

27x ≡ 33 (mod 48)
x =
9.Algorytmy i złożonośćŚredni

Quicksort zawsze używa pierwszego elementu jako elementu osiowego. Dla jakich danych wykazuje zachowanie pesymistyczne?

  1. ADla tablicy o długości 2
  2. BDla tablicy, w której wszystkie elementy są różne
  3. CDla tablicy w losowej kolejności
  4. DDla tablicy już posortowanej
10.Algorytmy i złożonośćTrudny

Co by wynikało, gdyby ktoś znalazł algorytm wielomianowy dla jednego problemu NP-zupełnego?

  1. ATylko ten jeden problem przeszedłby do P
  2. BKażdy problem z NP dałoby się rozwiązać w czasie wielomianowym, więc P = NP
  3. CWszystkie algorytmy o czasie wykładniczym od razu działałyby w czasie liniowym
  4. DProblem stopu stałby się rozstrzygalny
11.Struktury danychŚredni

Jaki jest koszt wstawienia elementu w środek tablicy o n elementach?

  1. AO(1), bo indeks jest znany
  2. BO(n²), bo każdy element przesuwa się n razy
  3. CO(log n), z powodu wyszukiwania binarnego
  4. DO(n), bo dalsze elementy trzeba przesunąć
12.Struktury danychTrudny

Drzewo przedziałowe (segment tree) służy zwykle do:

  1. AAlfabetycznego sortowania napisów przez przechowywanie każdego prefiksu w osobnym węźle drzewa
  2. BOdpowiadania na zapytania o zakresy (np. sumy zakresów) i aktualizacji w O(log n)
  3. CPrzechowywania krawędzi grafu
  4. DImplementacji stosu
13.Teoria grafówŚredni

Drzewo ma 4× wierzchołek stopnia 3, 2× wierzchołek stopnia 2, a wszystkie jego pozostałe wierzchołki są liśćmi (stopień 1). Ile liści L ma to drzewo?

4 × deg 32 × deg 2
L =
14.Teoria grafówTrudny
3107371431141510ABCDEFG

Użyj algorytmu Dijkstry, aby znaleźć długość d(F) najkrótszej ścieżki z A do F w grafie ważonym.

start: Akoniec: F
d(F) =
15.Bazy danych i SQLŚredni

Co zwraca EXCEPT (w Oracle nazywane MINUS)?

  1. AWszystkie wiersze z obu zapytań bez duplikatów
  2. BWiersze występujące w obu zapytaniach
  3. CWiersze drugiego zapytania, które nie występują w pierwszym
  4. DWiersze pierwszego zapytania, które nie występują w drugim
16.Bazy danych i SQLTrudny

Kiedy plan wykonania (harmonogram) współbieżnych transakcji nazywa się szeregowalnym?

  1. AGdy każda transakcja dostaje numer seryjny
  2. BGdy transakcje działają tylko na jednym procesorze
  3. CGdy żadna transakcja nigdy nie odczytuje danych
  4. DGdy jego skutek jest równoważny pewnemu szeregowemu wykonaniu tych samych transakcji
17.Sieci komputeroweŚredni

Jakie właściwości bezpieczeństwa zapewnia TLS w HTTPS?

  1. AWyłącznie szybsze ładowanie
  2. BPoufność, integralność i uwierzytelnienie serwera
  3. COchronę przed każdym złośliwym oprogramowaniem i phishingiem na odwiedzanej stronie
  4. DAnonimowość użytkownika
18.Sieci komputeroweTrudny

Musisz podzielić 192.168.1.0/24 na co najmniej 5 podsieci, z których każda pomieści do 25 hostów. Która długość prefiksu pasuje najlepiej?

  1. A/26
  2. B/27
  3. C/25
  4. D/28
19.Podsieci IPv4Średni
/24 → /2811111111111111111111111111110000bity siecibity hosta

Sieć 192.168.195.0/24 podzielono na podsieci /28, ponumerowane 1, 2, 3, … od najniższego adresu (podsieć 1 zaczyna się od .0). Jaki jest czwarty oktet x adresu rozgłoszeniowego podsieci 4?

192.168.195.0/24/28podsieć 4 (podsieć 1 zaczyna się od .0)
x =
20.Podsieci IPv4Trudny
ostatni oktet = 186112806413211618041201siećhost

Host ma adres 10.20.102.186/29. Jaki jest czwarty oktet x ostatniego użytecznego adresu hosta w jego podsieci?

10.20.102.186/29
x =

3Roztwory

1.Systemy liczbowe

Odpowiedź: N = −32

Pozycyjne systemy liczbowe: każda cyfra jest warta swoją wartość razy potęgę podstawy. W systemie dwójkowym pozycje są warte 1, 2, 4, 8, 16, …, w szesnastkowym 1, 16, 256, …, a A–F oznaczają 10–15. W 8-bitowym kodzie uzupełnień do dwóch skrajny lewy bit jest wart −128 zamiast +128; tak zapisuje się liczby ujemne.

Dodaj wagi

Pozostałe bity mają swoje zwykłe dodatnie wartości.

−128 + 64 + 32 = −32

Odpowiedź

N = −32
2.Systemy liczbowe

Odpowiedź: M = 300 KiB

Pozycyjne systemy liczbowe: każda cyfra jest warta swoją wartość razy potęgę podstawy. W systemie dwójkowym pozycje są warte 1, 2, 4, 8, 16, …, w szesnastkowym 1, 16, 256, …, a A–F oznaczają 10–15. W 8-bitowym kodzie uzupełnień do dwóch skrajny lewy bit jest wart −128 zamiast +128; tak zapisuje się liczby ujemne.

Bity i bajty

640·480·8 = 2457600 bit = 307200 B

Zamień na KiB

307200/1024 = 300 KiB

Odpowiedź

M = 300 KiB
3.Rachunek zdań i dowody

Odpowiedź: N = 3

Tablice prawdy: formuła z n różnymi zmiennymi ma 2ⁿ wierszy, po jednym dla każdej kombinacji wartości logicznych (1 = prawda, 0 = fałsz). Pracuj od wewnątrz na zewnątrz i każdej podformule daj osobną kolumnę. ¬a odwraca wartość; a ∧ b jest równe 1 tylko wtedy, gdy oba są równe 1; a ∨ b jest równe 0 tylko wtedy, gdy oba są równe 0; a → b jest równe 0 tylko wtedy, gdy a = 1 i b = 0; a ↔ b jest równe 1, gdy obie strony są równe.

Tablica prawdy wiersz po wierszu

a = 1, b = 1, c = 1: c → a = 1, b → (c → a) = 1, b ↔ a = 1, c ∧ (b ↔ a) = 1, (b → (c → a)) → (c ∧ (b ↔ a)) = 1
a = 1, b = 1, c = 0: c → a = 1, b → (c → a) = 1, b ↔ a = 1, c ∧ (b ↔ a) = 0, (b → (c → a)) → (c ∧ (b ↔ a)) = 0
a = 1, b = 0, c = 1: c → a = 1, b → (c → a) = 1, b ↔ a = 0, c ∧ (b ↔ a) = 0, (b → (c → a)) → (c ∧ (b ↔ a)) = 0
a = 1, b = 0, c = 0: c → a = 1, b → (c → a) = 1, b ↔ a = 0, c ∧ (b ↔ a) = 0, (b → (c → a)) → (c ∧ (b ↔ a)) = 0
a = 0, b = 1, c = 1: c → a = 0, b → (c → a) = 0, b ↔ a = 0, c ∧ (b ↔ a) = 0, (b → (c → a)) → (c ∧ (b ↔ a)) = 1
a = 0, b = 1, c = 0: c → a = 1, b → (c → a) = 1, b ↔ a = 0, c ∧ (b ↔ a) = 0, (b → (c → a)) → (c ∧ (b ↔ a)) = 0
a = 0, b = 0, c = 1: c → a = 0, b → (c → a) = 1, b ↔ a = 1, c ∧ (b ↔ a) = 1, (b → (c → a)) → (c ∧ (b ↔ a)) = 1
a = 0, b = 0, c = 0: c → a = 1, b → (c → a) = 1, b ↔ a = 1, c ∧ (b ↔ a) = 0, (b → (c → a)) → (c ∧ (b ↔ a)) = 0

Policz wiersze z wartością 1

(b → (c → a)) → (c ∧ (b ↔ a)): 1, 0, 0, 0, 1, 0, 1, 0
N = 3

Odpowiedź

N = 3
4.Rachunek zdań i dowody

Odpowiedź: ∀x ¬F(x)

Kwantyfikatory i wnioskowania: ¬∀x P(x) ≡ ∃x ¬P(x) oraz ¬∃x P(x) ≡ ∀x ¬P(x). Przesuń negację do środka, zamień każdy kwantyfikator, który mija, i zaneguj formułę wewnętrzną prawami rachunku zdań, takimi jak ¬(a → b) ≡ a ∧ ¬b. Wnioskowanie jest poprawne, gdy wniosek jest równy 1 w każdym wierszu, w którym wszystkie przesłanki są równe 1. Pojedynczy wiersz z prawdziwymi przesłankami i fałszywym wnioskiem jest kontrprzykładem i pokazuje, że wnioskowanie jest niepoprawne.

Przesuń negację do środka

¬∃x F(x) ≡ ∀x ¬F(x)

Odpowiedź

∀x ¬F(x)

Pozostałe opcje albo zostawiają kwantyfikator bez zmian, albo zmieniają kolejność kwantyfikatorów, albo błędnie negują formułę wewnętrzną.

5.Logika cyfrowa: bramki, mapy Karnaugha i przerzutniki

Odpowiedź: L = 9

Mapy Karnaugha: komórki są ułożone w kodzie Graya (00, 01, 11, 10), więc sąsiednie komórki, także te przez brzegi, różnią się dokładnie jedną zmienną. Grupuj jedynki w prostokąty po 1, 2, 4, 8 lub 16 komórek, jak największe i jak najmniej, aż każda jedynka będzie pokryta. Każda grupa to jeden iloczyn: zmienne, które wewnątrz niej pozostają stałe. Grupa 2ᵏ komórek traci k zmiennych. Stany nieokreślone (X) można wykorzystać, by powiększyć grupy, ale nigdy nie trzeba ich pokrywać. Grupowanie zer daje minimalną postać POS.

ABCD000111100001111010010312141507060120130150141819011010

Zgrupuj jedynki

Każda grupa to prostokąt z 2ᵏ komórek; komórki na brzegu sąsiadują z komórkami na przeciwległym brzegu.

A′B′D′
A′BC′
AB′C′

Minimalna postać SOP

F = A′B′D′ + A′BC′ + AB′C′
L = 9

Odpowiedź

L = 9
6.Logika cyfrowa: bramki, mapy Karnaugha i przerzutniki

Odpowiedź: N = 3

Mapy Karnaugha: komórki są ułożone w kodzie Graya (00, 01, 11, 10), więc sąsiednie komórki, także te przez brzegi, różnią się dokładnie jedną zmienną. Grupuj jedynki w prostokąty po 1, 2, 4, 8 lub 16 komórek, jak największe i jak najmniej, aż każda jedynka będzie pokryta. Każda grupa to jeden iloczyn: zmienne, które wewnątrz niej pozostają stałe. Grupa 2ᵏ komórek traci k zmiennych. Stany nieokreślone (X) można wykorzystać, by powiększyć grupy, ale nigdy nie trzeba ich pokrywać. Grupowanie zer daje minimalną postać POS.

Implikanty proste

Największe grupy, jakie można utworzyć z jedynek i X.

CD, B′D′, B′C, AC, A′B′, ABD
ABCD0001111000011110101113120405X706012113115X141809X11110

Istotne implikanty proste

B′D′, A′B′, ABD
N = 3

Odpowiedź

N = 3
7.Teoria liczb i arytmetyka modularna

Odpowiedź: φ(931) = 756

Elementy odwrotne i kongruencje: a ma element odwrotny modulo n dokładnie wtedy, gdy NWD(a, n) = 1. Rozszerzony algorytm Euklidesa zapisuje 1 = s·n + t·a, a wtedy a⁻¹ ≡ t (mod n). Kongruencja a·x ≡ b (mod n) przy NWD(a, n) = 1 ma rozwiązanie x ≡ a⁻¹·b. Dwie kongruencje x ≡ r₁ (mod m₁) i x ≡ r₂ (mod m₂) o względnie pierwszych modułach mają jedno rozwiązanie modulo m₁·m₂ (chińskie twierdzenie o resztach). Funkcja φ(n) Eulera zlicza liczby od 1 do n względnie pierwsze z n: φ(n) = n·∏(1 − 1/p).

Czynniki pierwsze

931 = 72·19

Funkcja φ

φ(931) = φ(49)·φ(19) = 42·18 = 756

Odpowiedź

φ(931) = 756
8.Teoria liczb i arytmetyka modularna

Odpowiedź: x = 3

Elementy odwrotne i kongruencje: a ma element odwrotny modulo n dokładnie wtedy, gdy NWD(a, n) = 1. Rozszerzony algorytm Euklidesa zapisuje 1 = s·n + t·a, a wtedy a⁻¹ ≡ t (mod n). Kongruencja a·x ≡ b (mod n) przy NWD(a, n) = 1 ma rozwiązanie x ≡ a⁻¹·b. Dwie kongruencje x ≡ r₁ (mod m₁) i x ≡ r₂ (mod m₂) o względnie pierwszych modułach mają jedno rozwiązanie modulo m₁·m₂ (chińskie twierdzenie o resztach). Funkcja φ(n) Eulera zlicza liczby od 1 do n względnie pierwsze z n: φ(n) = n·∏(1 − 1/p).

Podziel przez NWD

gcd(27, 48) = 3
9x ≡ 11 (mod 16)

Rozwiąż skróconą kongruencję

9−1 ≡ 9 (mod 16) → x ≡ 3 (mod 16)

Rozwiązania modulo 48

x ∈ {3, 19, 35}
x = 3

Odpowiedź

x = 3
9.Algorytmy i złożoność

Odpowiedź: D · Dla tablicy już posortowanej

Dlaczego to jest odpowiedź

Dla danych posortowanych element osiowy jest zawsze minimum, więc jedna strona jest pusta, a druga ma n − 1 elementów, co daje O(n²).

Odpowiedź

D · Dla tablicy już posortowanej
10.Algorytmy i złożoność

Odpowiedź: B · Każdy problem z NP dałoby się rozwiązać w czasie wielomianowym, więc P = NP

Dlaczego to jest odpowiedź

Ponieważ cała klasa NP redukuje się w czasie wielomianowym do dowolnego problemu NP-zupełnego, szybki algorytm dla jednego daje szybki algorytm dla wszystkich.

Odpowiedź

B · Każdy problem z NP dałoby się rozwiązać w czasie wielomianowym, więc P = NP
11.Struktury danych

Odpowiedź: D · O(n), bo dalsze elementy trzeba przesunąć

Dlaczego to jest odpowiedź

Wszystkie elementy za miejscem wstawienia przesuwają się o jedną pozycję w prawo, co zajmuje czas proporcjonalny do n.

Odpowiedź

D · O(n), bo dalsze elementy trzeba przesunąć
12.Struktury danych

Odpowiedź: B · Odpowiadania na zapytania o zakresy (np. sumy zakresów) i aktualizacji w O(log n)

Dlaczego to jest odpowiedź

Drzewo przedziałowe przechowuje agregaty dla przedziałów, obsługując zapytania o zakresy i aktualizacje punktowe w czasie O(log n).

Odpowiedź

B · Odpowiadania na zapytania o zakresy (np. sumy zakresów) i aktualizacji w O(log n)
13.Teoria grafów

Odpowiedź: L = 6

Euler, Hamilton i drzewa: graf spójny ma cykl Eulera (każda krawędź raz, powrót do startu), gdy każdy wierzchołek ma stopień parzysty, oraz ścieżkę Eulera, która nie jest cyklem, gdy dokładnie dwa wierzchołki mają stopień nieparzysty; ścieżka biegnie wtedy od jednego wierzchołka nieparzystego do drugiego. Cykl Hamiltona odwiedza każdy wierzchołek raz; Kn ma ich (n − 1)!/2. Drzewo o n wierzchołkach ma n − 1 krawędzi, a graf spójny o m krawędziach zachowuje drzewo rozpinające po usunięciu m − n + 1 krawędzi.

Lemat o uściskach dłoni dla drzewa

L + 16 = 2(L + 6) − 2
L = 6

Odpowiedź

L = 6

Skrót: L = 2 + Σ (d − 2) po wierzchołkach o stopniu d ≥ 3.

14.Teoria grafów

Odpowiedź: d(F) = 9

Najkrótsze ścieżki i drzewa rozpinające: algorytm Dijkstry zatwierdza jeden wierzchołek na rundę: niezatwierdzony wierzchołek o najmniejszej tymczasowej odległości. Jego odległość jest wtedy ostateczna, a każdy sąsiad v dostaje d(v) = min(d(v), d(u) + w(u, v)). Algorytm Kruskala buduje minimalne drzewo rozpinające, biorąc krawędzie od lekkich do ciężkich i pomijając każdą, która zamknęłaby cykl; algorytm Prima rozbudowuje jedno drzewo od wierzchołka startowego, zawsze dodając najlżejszą krawędź wychodzącą z niego. Drzewo rozpinające o n wierzchołkach ma n − 1 krawędzi.

Algorytm Dijkstry runda po rundzie

Każdy wiersz: zatwierdzony wierzchołek, jego ostateczna odległość oraz sąsiedzi, których odległość się poprawia.

A (0): B: 3, C: 10
B (3): D: 6, G: 7
D (6): E: 20, F: 9
G (7): C: 8, E: 17
C (8): E: 15
F (9)
E (15)

Najkrótsza ścieżka

A → B → D → F
d(F) = 9

Odpowiedź

d(F) = 9
15.Bazy danych i SQL

Odpowiedź: D · Wiersze pierwszego zapytania, które nie występują w drugim

Dlaczego to jest odpowiedź

A EXCEPT B daje wiersze z A, których nie ma w B, więc zamiana zapytań daje inny wynik.

Odpowiedź

D · Wiersze pierwszego zapytania, które nie występują w drugim
16.Bazy danych i SQL

Odpowiedź: D · Gdy jego skutek jest równoważny pewnemu szeregowemu wykonaniu tych samych transakcji

Dlaczego to jest odpowiedź

Szeregowalność to główne kryterium poprawności współbieżności: wynik przeplatanego wykonania musi być równy wynikowi pewnej kolejności wykonania pojedynczo.

Odpowiedź

D · Gdy jego skutek jest równoważny pewnemu szeregowemu wykonaniu tych samych transakcji
17.Sieci komputerowe

Odpowiedź: B · Poufność, integralność i uwierzytelnienie serwera

Dlaczego to jest odpowiedź

TLS szyfruje ruch, wykrywa manipulacje i uwierzytelnia serwer za pomocą certyfikatów (opcjonalnie także klienta).

Odpowiedź

B · Poufność, integralność i uwierzytelnienie serwera
18.Sieci komputerowe

Odpowiedź: B · /27

Dlaczego to jest odpowiedź

/27 daje 8 podsieci po 30 użytecznych adresów hostów. /26 daje tylko 4 podsieci, a /28 pozwala na zaledwie 14 hostów w podsieci.

Odpowiedź

B · /27
19.Podsieci IPv4

Odpowiedź: x = 63

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

Rozmiar bloku

24 = 16

Podsieć numer 4

sieć: (4 − 1)·16 = 48
rozgłoszeniowy: 48 + 16 − 1 = 63

Odpowiedź

x = 63
20.Podsieci IPv4

Odpowiedź: x = 190

Podsieci IPv4: adres ma 32 bity. Prefiks /p mówi, ile początkowych bitów wskazuje sieć; pozostałe 32 − p bitów numeruje hosty. Podsieć ma 2³²⁻ᵖ adresów, ale pierwszego (adres sieci) i ostatniego (adres rozgłoszeniowy) nie można przydzielić hostom, więc mieści się 2³²⁻ᵖ − 2 hostów. Wyjątki: /31 (łącze punkt-punkt, RFC 3021) wykorzystuje oba swoje 2 adresy dla hostów, a /32 to jeden adres (pojedynczy host lub loopback).

Rozmiar bloku

23 = 8

Podsieć tego hosta

sieć: ⌊186/8⌋·8 = 184
rozgłoszeniowy: 184 + 8 − 1 = 191
użyteczne hosty: 185 … 190

Odpowiedź

x = 190

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