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 −35 w 8-bitowym kodzie uzupełnień do dwóch. Jaka jest wartość wzorca U odczytanego jako liczba bez znaku?
Ustaw bity na 8-bitowy wynik działania 1010 1001 OR 1000 0110. Jaka jest wartość wyniku R w zapisie dziesiętnym?
Chcesz udowodnić (p ∧ r) → ¬q nie wprost. Jakie zdanie zakładasz na początku? Kliknij je.
Które zdanie jest równoważne ¬∀x ∀y (R(x, y) → R(y, 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ę.
Znajdź minimalną postać SOP funkcji F(A, B, C, D) = Σm(0, 3, 4, 5, 6, 15) + d(11, 13), gdzie d oznacza stany nieokreślone. Ile iloczynów N ona zawiera?
Znajdź funkcję φ Eulera φ(95), czyli liczbę liczb całkowitych od 1 do 95 względnie pierwszych z 95.
Rozwiąż 33x ≡ 42 (mod 75). Podaj najmniejsze dodatnie rozwiązanie x.
Jaka jest zamortyzowana złożoność czasowa dodawania elementu na koniec tablicy dynamicznej, która podwaja swoją pojemność, gdy się zapełni?
Który z tych problemów spełnialności jest rozwiązywalny w czasie wielomianowym?
Drzewa AVL i drzewa czerwono-czarne gwarantują:
Którą własność musi spełniać drzewo czerwono-czarne?
Drzewo ma 4× wierzchołek stopnia 4, 2× wierzchołek stopnia 5, 4× wierzchołek stopnia 2, a wszystkie jego pozostałe wierzchołki są liśćmi (stopień 1). Ile liści L ma to drzewo?
Ile jest marszów o długości 2 z C do A? Marsz może powtarzać wierzchołki i krawędzie. Nazwij tę liczbę N.
Co zwraca SELECT COALESCE(phone, 'unknown') FROM customers dla klienta, którego phone jest NULL?
Czym jest odczyt fantomowy (phantom read)?
Który host jest w tej samej podsieci /16 co 10.1.2.3?
Jaka jest według wzoru Nyquista maksymalna szybkość bitowa bezszumowego kanału 3 kHz przy 4 poziomach sygnału?
Sieć 10.141.52.0/22 podzielono na równe podsieci z prefiksem /25. Ile jest podsieci N?
Host ma adres 10.20.205.119/25. Jaka jest ostatnia liczba (czwarty oktet) x adresu rozgłoszeniowego jego podsieci?
Odpowiedź: U = 221
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ź: R = 175
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.
OR daje 1 tam, gdzie przynajmniej jeden bit jest równy 1.
Odpowiedź: (p ∧ r) ∧ ¬¬q
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ź: ∃x ∃y (R(x, y) ∧ ¬R(y, 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 = 00, CD = 10
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ź: N = 5
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.
Największe grupy, jakie można utworzyć z jedynek i X.
Istnieje inne grupowanie tego samego rozmiaru; ma tę samą liczbę składników i literałów.
Odpowiedź: φ(95) = 72
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).
Odpowiedź: x = 24
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).
Odpowiedź: D · O(1)
Kopiowanie wszystkich elementów następuje tylko przy potęgach dwójki; po rozłożeniu na wszystkie operacje dodawania średni koszt jednej operacji jest stały.
Odpowiedź: A · 2-SAT, w którym każda klauzula ma najwyżej dwa literały
2-SAT należy do P (czas liniowy dzięki silnie spójnym składowym), a 3-SAT jest NP-zupełny.
Odpowiedź: D · Wysokość O(log n) dzięki równoważeniu
Drzewa samorównoważące utrzymują wysokość logarytmiczną, więc wyszukiwanie, wstawianie i usuwanie mają w najgorszym przypadku złożoność O(log n).
Odpowiedź: D · Każda ścieżka od węzła do jego liści potomnych zawiera tyle samo czarnych węzłów
Zasady drzewa czerwono-czarnego: węzły są czerwone lub czarne, korzeń jest czarny, czerwone węzły mają czarne dzieci, a wszystkie ścieżki mają równą czarną wysokość, co utrzymuje wysokość ≤ 2 log₂(n + 1).
Odpowiedź: L = 16
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.
Skrót: L = 2 + Σ (d − 2) po wierzchołkach o stopniu d ≥ 3.
Odpowiedź: N = 1
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ź: C · 'unknown'
COALESCE sprawdza argumenty od lewej do prawej i zwraca pierwszy, który nie jest NULL, tutaj 'unknown'.
Odpowiedź: D · Powtórzone zapytanie zwraca nowe wiersze wstawione przez inną zatwierdzoną transakcję
Fantomy pojawiają się, gdy inna transakcja wstawia wiersze spełniające warunek zakresowy; izolacja serializable im zapobiega.
Odpowiedź: C · 10.1.200.5
Przy /16 pierwsze 16 bitów (10,1) to część sieciowa. Tylko 10.1.200.5 ma je takie same, więc należy do 10.1.0.0/16.
Odpowiedź: C · 12 kbit/s
2 × 3000 × log₂ 4 = 2 × 3000 × 2 = 12,000 bit/s. Więcej poziomów zwiększa szybkość, ale szum ogranicza, ile z nich da się rozróżnić.
Odpowiedź: N = 8
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).
Każda podsieć /25 ma 27 − 2 = 126 użytecznych hostów.
Odpowiedź: x = 127
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