Wzory, najważniejsze kroki metod dla każdego tematu i 20 zadań do ćwiczenia, z pełnymi rozwiązaniami na końcu.
Zapisz −42 jako 8-bitowy wzór w kodzie U2. Odczytaj ten wzór jako liczbę dwójkową bez znaku: jaka jest jego wartość U dziesiętnie?
Nieskompresowany obraz ma 640 × 480 pikseli i 8 bitów na piksel. Ile pamięci M zajmuje, w KiB (1 KiB = 1024 bajty)?
Chcesz udowodnić (a ∧ c) → ¬b przez kontrapozycję. Którą implikację udowadniasz zamiast niej? Kliknij ją.
Które zdanie jest równoważne ¬∀x (P(x) → Q(x)), gdy negację przesunięto całkiem do środka? Kliknij je.
Na tej mapie Karnaugha dokładnie jedna jedynka nie ma sąsiedniej jedynki, więc w minimalnej postaci SOP pozostaje grupą jednej komórki (pełnym mintermem o czterech literałach). Sąsiedztwo przez brzegi mapy się liczy. Kliknij tę komórkę.
Przerzutnik T wyzwalany zboczem narastającym startuje z Q = 0 i dostaje pokazane wejścia. Kliknij pierwsze zbocze zegara, przy którym Q przechodzi z 1 z powrotem na 0.
Znajdź element odwrotny do 22 modulo 47: liczbę x, dla której 0 < x < 47 oraz 22·x ≡ 1 (mod 47).
Klucz RSA używa p = 11, q = 29 i e = 23. Odszyfruj szyfrogram c = 73: znajdź wiadomość m.
Jaka jest złożoność czasowa mnożenia dwóch macierzy n × n standardową potrójną pętlą?
Która definicja klasy P jest poprawna?
Której struktury danych używa się, by sprawdzić, czy nawiasy w „{[()]}” są zrównoważone?
Jaki jest oczekiwany czas wyszukiwania przy prostym równomiernym haszowaniu w tablicy mieszającej z metodą łańcuchową, n kluczami i m kubełkami?
Czy graf spójny ma cykl Eulera, ścieżkę Eulera, która nie jest cyklem, czy żadne z nich? Kliknij odpowiedź.
Ile jest marszów zamkniętych o długości 3, które zaczynają się i kończą w B? Marsz może powtarzać wierzchołki i krawędzie. Nazwij tę liczbę N.
Czym jest brudny odczyt (dirty read)?
R(A, B, C, D) ma zależności funkcyjne A → B i C → D. Jaki jest klucz kandydujący?
Który typ rekordu DNS odwzorowuje nazwę hosta na adres IPv6?
Aplikacja zdalnego terminala działa ociężale, bo małe pakiety z naciśnięciami klawiszy są wstrzymywane. Który mechanizm TCP często za to odpowiada?
Sieć 192.168.10.0/24 trzeba podzielić na co najmniej 5 równych podsieci. Jeśli pożyczysz jak najmniej bitów, ile użytecznych hostów H będzie miała każda podsieć?
Host ma adres 10.20.130.236/29. Jaki jest czwarty oktet x ostatniego użytecznego adresu hosta w jego podsieci?
Odpowiedź: U = 214
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.
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.
Odpowiedź: ¬¬b → ¬(a ∧ c)
Równoważność logiczna: dwie formuły są równoważne (≡), gdy mają tę samą wartość w każdym wierszu tablicy prawdy. Tautologia jest równa 1 w każdym wierszu, kontradykcja 0 w każdym wierszu, a formuła kontyngentna nie jest ani jednym, ani drugim. Przydatne prawa: prawa de Morgana, ¬(a ∧ b) ≡ ¬a ∨ ¬b oraz ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (kontrapozycja); ¬(a → b) ≡ a ∧ ¬b; oraz prawa rozdzielności, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).
Kontrapozycja jest równoważna zdaniu wyjściowemu, więc jej udowodnienie dowodzi zdania.
Odpowiedź: ∃x (P(x) ∧ ¬Q(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.
Pozostałe opcje albo zostawiają kwantyfikator bez zmian, albo zmieniają kolejność kwantyfikatorów, albo błędnie negują formułę wewnętrzną.
Odpowiedź: AB = 10, CD = 00
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.
Jedynka z sąsiednią jedynką może dołączyć do grupy dwóch lub więcej.
Odpowiedź: zbocze zegara 4
Przerzutniki i liczniki: przerzutnik zmienia stan tylko przy aktywnym zboczu zegara. D kopiuje swoje wejście (Q⁺ = D); T zmienia stan na przeciwny, gdy T = 1; JK utrzymuje stan dla 00, zeruje dla 01, ustawia dla 10 i zmienia stan na przeciwny dla 11. N-bitowy licznik binarny ma 2ⁿ stanów i liczy modulo 2ⁿ; licznik mod-N liczy 0, 1, …, N − 1 i wraca do 0, a potrzebuje tylu przerzutników, ile wynosi najmniejsze n z 2ⁿ ≥ N. Każdy stopień licznika asynchronicznego dzieli częstotliwość przez dwa, więc ostatnie wyjście licznika mod-N pracuje z częstotliwością fclk/N. Licznik Johnsona z n przerzutników ma 2n stanów, licznik pierścieniowy n.
Przerzutnik T zmienia stan na przeciwny przy każdym zboczu narastającym, gdy T = 1, i utrzymuje, gdy T = 0.
Odpowiedź: 22−1 mod 47 = 15
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).
Każdą resztę r zapisujemy jako r ≡ t·22 (mod 47).
Odpowiedź: m = 50
Potęgi modularne i RSA: oblicz aᵏ mod n przez wielokrotne podnoszenie do kwadratu: zapisz k binarnie, podnoś do kwadratu, redukuj po każdym kroku i mnóż potęgi, których bit jest równy 1. Fermat: aᵖ⁻¹ ≡ 1 (mod p) dla liczby pierwszej p niedzielącej a, więc wykładnik można redukować modulo p − 1. RSA: wybierz liczby pierwsze p i q, n = p·q i φ(n) = (p − 1)(q − 1); wykładnik publiczny e jest względnie pierwszy z φ(n), a wykładnik prywatny to d = e⁻¹ mod φ(n). Szyfruj wzorem c = mᵉ mod n, a odszyfrowuj wzorem m = cᵈ mod n.
Odpowiedź: B · O(n³)
Jest n² elementów, a każdy wymaga n mnożeń, co daje n³ operacji.
Odpowiedź: A · Problemy decyzyjne rozwiązywalne przez algorytm deterministyczny w czasie wielomianowym
P zawiera problemy decyzyjne z deterministycznym algorytmem wielomianowym, np. sprawdzanie, czy graf jest spójny.
Odpowiedź: D · Stosu
Każdy nawias otwierający odkłada się na stos (push), a przy nawiasie zamykającym zdejmuje (pop); musi pasować do zdjętego nawiasu, a na końcu stos musi być pusty.
Odpowiedź: A · O(1 + α), gdzie α = n / m
Obliczenie funkcji mieszającej kosztuje O(1), a oczekiwana długość łańcucha to α, więc utrzymywanie ograniczonego α przez zmianę rozmiaru daje oczekiwany czas O(1).
Odpowiedź: Cykl Eulera
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.
Odpowiedź: N = 4
Stopnie: stopień wierzchołka to liczba krawędzi, które się w nim stykają. Każda krawędź ma dwa końce, więc stopnie sumują się do dwukrotności liczby krawędzi: Σ deg(v) = 2|E| (lemat o uściskach dłoni). Liczba wierzchołków o nieparzystym stopniu jest zatem parzysta. Kn ma n(n − 1)/2 krawędzi, graf k-regularny o n wierzchołkach ma nk/2, a drzewo o n wierzchołkach ma n − 1 krawędzi.
Odpowiedź: A · Odczytem danych zapisanych przez inną transakcję, która nie została jeszcze zatwierdzona
Brudny odczyt widzi niezatwierdzone zmiany, które mogą zostać cofnięte; jest możliwy tylko na poziomie read uncommitted.
Odpowiedź: D · {A, C}
A i C nie są wyznaczane przez nic, więc każdy klucz musi zawierać oba, a {A, C}+ = {A, B, C, D}.
Odpowiedź: A · AAAA
Rekord A zawiera adres IPv4, a AAAA adres IPv6. MX wskazuje serwery pocztowe, a CNAME podaje alias.
Odpowiedź: B · Algorytm Nagle'a
Algorytm Nagle'a czeka, by połączyć małe segmenty, gdy wcześniejsze dane nie są jeszcze potwierdzone. Oszczędza to przepustowość, ale dodaje opóźnienie w ruchu interaktywnym.
Odpowiedź: H = 30
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).
Odpowiedź: x = 238
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).
ExamProblems · examproblems.com/courses/computer-science-fundamentals