Wzory, najważniejsze kroki metod dla każdego tematu i 20 zadań do ćwiczenia, z pełnymi rozwiązaniami na końcu.
Ustaw bity tak, aby zapisywały −20 w 8-bitowym kodzie uzupełnień do dwóch. Jaka jest wartość wzorca U odczytanego jako liczba bez znaku?
Jaka jest największa liczba całkowita bez znaku N, która mieści się w 20 bitach?
Chcesz udowodnić p → (q ∨ r) nie wprost. Jakie zdanie zakładasz na początku? Kliknij je.
Wnioskowanie z przesłankami a ∨ c; a i wnioskiem ¬c jest niepoprawne. Kliknij wiersz tablicy prawdy, który jest kontrprzykładem.
Użyj mapy Karnaugha, aby znaleźć minimalną postać sumy iloczynów (SOP) funkcji F(A, B, C, D) = Σm(2, 3, 5, 12). Ile literałów L zawiera łącznie (zmienna z negacją liczy się jako jeden literał)?
Układ (3-bitowy licznik binarny zliczający w dół) startuje od 5 (dziesiętnie, Q = 101). Jaki stan Q (dziesiętnie) pokaże po 16 impulsach zegara?
Znajdź element odwrotny do 41 modulo 59: liczbę x, dla której 0 < x < 59 oraz 41·x ≡ 1 (mod 59).
Klucz RSA używa liczb pierwszych p = 7 i q = 19 oraz wykładnika publicznego e = 11. Znajdź wykładnik prywatny d (0 < d < φ(n)).
Dlaczego programowanie dynamiczne nie daje realnego przyspieszenia sortowania przez scalanie?
Korzystając z twierdzenia o rekurencji uniwersalnej (master theorem), rozwiązaniem T(n) = 8T(n/2) + O(n²) jest:
Ile pamięci zajmują listy sąsiedztwa dla grafu o V wierzchołkach i E krawędziach?
Drzewo przedziałowe (segment tree) służy zwykle do:
Czy graf spójny ma cykl Eulera, ścieżkę Eulera, która nie jest cyklem, czy żadne z nich? Kliknij odpowiedź.
Algorytm Dijkstry rusza z A. Kliknij wierzchołek zatwierdzony (uczyniony stałym) w rundzie 4; sam A to runda 1.
Które zapytanie zwraca najwyższą pensję w każdym dziale?
Wyniki to 90, 90 i 80. Jakie wartości daje RANK() OVER (ORDER BY score DESC)?
Przeglądarka otrzymuje kod stanu HTTP 404. Co on oznacza?
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?
Dział potrzebuje 1370 adresów hostów w jednej podsieci. Jaki jest najdłuższy prefiks p (najmniejsza podsieć), który wystarczy?
Host ma adres 10.20.120.181/30. Jaki jest czwarty oktet x jego adresu sieci?
Odpowiedź: U = 236
Ustawianie bitów: każdy bit ma wartość będącą potęgą dwójki (128, 64, …, 1). Jedna cyfra szesnastkowa to dokładnie cztery bity, a w 8-bitowym kodzie uzupełnień do dwóch skrajny lewy bit ma wartość −128. Operacje bitowe działają osobno na każdej pozycji bitu.
Odpowiedź: N = 1,049 × 10⁶
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ź: p ∧ ¬(q ∨ r)
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).
Jeśli założenie prowadzi do sprzeczności, implikacja musi być prawdziwa.
Odpowiedź: a = 1, c = 1
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.
Wnioskowanie o tej postaci wygląda jak poprawna reguła, ale jeden wiersz wystarczy, by pokazać, że nią nie jest.
Odpowiedź: L = 11
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.
Każda grupa to prostokąt z 2ᵏ komórek; komórki na brzegu sąsiadują z komórkami na przeciwległym brzegu.
Odpowiedź: Q = 5
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.
Co 8 impulsów licznik wraca do tego samego stanu.
Odpowiedź: 41−1 mod 59 = 36
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·41 (mod 59).
Odpowiedź: d = 59
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ź: C · Jego podproblemy się nie nakładają, więc nie ma czego ponownie wykorzystać
Połowy w sortowaniu przez scalanie są rozłączne i każdą rozwiązuje się raz; DP pomaga tylko, gdy podproblemy się powtarzają, jak przy liczbach Fibonacciego.
Odpowiedź: B · Θ(n³)
log₂ 8 = 3, a n² rośnie wolniej niż n³, więc dominują liście: Θ(n³).
Odpowiedź: A · O(V + E)
Każdy wierzchołek ma listę, a każda krawędź pojawia się raz (graf skierowany) lub dwa razy (nieskierowany), co daje O(V + E).
Odpowiedź: B · Odpowiadania na zapytania o zakresy (np. sumy zakresów) i aktualizacji w O(log n)
Drzewo przedziałowe przechowuje agregaty dla przedziałów, obsługując zapytania o zakresy i aktualizacje punktowe w czasie O(log n).
Odpowiedź: ani jedno, ani drugie
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ź: B
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.
Odpowiedź: D · SELECT dept, MAX(salary) FROM emp GROUP BY dept
GROUP BY dept tworzy grupę dla każdego działu, a MAX(salary) wybiera najwyższą wartość w każdej z nich.
Odpowiedź: C · 1, 1, 3
RANK daje wierszom remisowym tę samą rangę i pomija kolejne numery (1, 1, 3); DENSE_RANK dałoby 1, 1, 2.
Odpowiedź: C · Żądanego zasobu nie znaleziono
404 Not Found oznacza, że serwer nie ma zasobu pod tym adresem URL. 200 to OK, 401 to Unauthorized, a 500 to Internal Server Error.
Odpowiedź: B · /27
/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ź: p = 21
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 = 180
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