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 −106 w 8-bitowym kodzie uzupełnień do dwóch. Jaka jest wartość wzorca U odczytanego jako liczba bez znaku?
System musi nadać każdemu z 790 elementów własny kod dwójkowy tej samej długości. Ile co najmniej bitów b potrzeba?
Chcesz udowodnić (c ∧ b) → ¬a przez kontrapozycję. Którą implikację udowadniasz zamiast niej? Kliknij ją.
Które zdanie jest równoważne ¬∃x ∀y R(x, y), gdy negację przesunięto całkiem do środka? Kliknij je.
Użyj mapy Karnaugha, aby znaleźć minimalną postać iloczynu sum (POS) funkcji F(A, B, C) = Σm(0, 1, 2, 3, 6). Ile sum (czynników) N ona ma?
Znajdź minimalną postać SOP funkcji F(A, B, C, D) = Σm(1, 3, 4, 5, 9, 10, 11, 12, 14) + d(7, 13), gdzie d oznacza stany nieokreślone. Ile iloczynów N ona zawiera?
Znajdź element odwrotny do 25 modulo 37: liczbę x, dla której 0 < x < 37 oraz 25·x ≡ 1 (mod 37).
Klucz RSA używa liczb pierwszych p = 7 i q = 29 oraz wykładnika publicznego e = 11. Znajdź wykładnik prywatny d (0 < d < φ(n)).
Dlaczego programowanie dynamiczne nie daje realnego przyspieszenia sortowania przez scalanie?
Jakie jest rozwiązanie rekurencji T(n) = 2T(n/2) + n log n?
Jaka jest złożoność czasowa wyszukiwania klucza w zrównoważonym binarnym drzewie poszukiwań?
Dla każdego elementu tablicy chcesz znaleźć najbliższy większy element po jego prawej stronie, w łącznym czasie O(n). Która struktura pomaga?
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 A? Marsz może powtarzać wierzchołki i krawędzie. Nazwij tę liczbę N.
Tabela orders ma 5 wierszy, z których każdy odwołuje się do istniejącego klienta. Tabela customers ma 3 wiersze. Ile wierszy zwraca INNER JOIN po customer_id?
Tabela ma milion wierszy i kolumnę logiczną is_active, która jest TRUE dla 95% z nich. Dlaczego optymalizator może zignorować indeks na is_active dla WHERE is_active = TRUE?
W której warstwie OSI zwykle działa przełącznik (switch)?
Do 8-portowego przełącznika (bez VLAN) podłączono po jednym hoście na każdy port. Ile jest domen kolizyjnych i rozgłoszeniowych?
Sieć 192.168.10.0/24 trzeba podzielić na co najmniej 16 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.122.37/29. Jaki jest czwarty oktet x jego adresu sieci?
Odpowiedź: U = 150
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ź: b = 10 bit
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ź: ¬¬a → ¬(c ∧ b)
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 ∃y ¬R(x, y)
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ź: N = 2
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ź: 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.
Największe grupy, jakie można utworzyć z jedynek i X.
Odpowiedź: 25−1 mod 37 = 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).
Każdą resztę r zapisujemy jako r ≡ t·25 (mod 37).
Odpowiedź: d = 107
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ź: A · 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² n)
Poziom k wykonuje około n log(n / 2ᵏ) pracy, a suma po log n poziomach daje Θ(n log² n); to rozszerzony drugi przypadek twierdzenia o rekurencji uniwersalnej.
Odpowiedź: A · O(log n)
Drzewo zrównoważone ma wysokość około log₂ n, więc wyszukiwanie przechodzi jedną ścieżką od korzenia do liścia.
Odpowiedź: A · Stos przechowujący elementy czekające na swoją odpowiedź
Przechodząc od lewej do prawej, zdejmij ze stosu każdy element mniejszy od bieżącego (bieżący element jest ich odpowiedzią), a potem odłóż bieżący; każdy element przemieszcza się co najwyżej dwa razy.
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ź: N = 2
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ź: B · 5
Każde zamówienie znajduje dokładnie jednego pasującego klienta, więc złączenie zwraca jeden wiersz na zamówienie: 5 wierszy.
Odpowiedź: D · Pasuje większość wierszy, więc pełne skanowanie tabeli jest tańsze niż wiele wyszukiwań w indeksie
Indeks pomaga, gdy zawęża wyszukiwanie do niewielu wierszy; gdy kwalifikuje się większość wierszy, losowe wyszukiwania w indeksie kosztują więcej niż sekwencyjny odczyt tabeli.
Odpowiedź: B · Łącza danych (warstwa 2)
Standardowy przełącznik uczy się adresów MAC i przekazuje ramki w warstwie 2. Przełączniki warstwy 3 dodatkowo trasują.
Odpowiedź: A · 8 domen kolizyjnych, 1 domena rozgłoszeniowa
Każdy port przełącznika to osobna domena kolizyjna, ale rozgłoszenia są przekazywane na wszystkie porty, więc cały przełącznik to jedna domena rozgłoszeniowa. Koncentrator dałby po jednej z każdej.
Odpowiedź: H = 14
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 = 32
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