Wzory, najważniejsze kroki metod dla każdego tematu i 20 zadań do ćwiczenia, z pełnymi rozwiązaniami na końcu.
Zapisz −68 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?
Jaka jest najmniejsza (najbardziej ujemna) liczba całkowita N, którą można zapisać w 24-bitowym kodzie U2?
W ilu z 8 wierszy tablicy prawdy ((c ∨ b) ∨ a) ∨ (b ∧ ¬a) jest prawdziwe? Nazwij tę liczbę N.
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ć sumy iloczynów (SOP) funkcji F(A, B, C, D) = Σm(0, 1, 4, 5, 7, 14, 15). Ile literałów L zawiera łącznie (zmienna z negacją liczy się jako jeden literał)?
Znajdź minimalną postać SOP funkcji F(A, B, C, D) = Σm(2, 3, 5, 7, 10, 13) + d(1, 11, 12), gdzie d oznacza stany nieokreślone. Ile iloczynów N ona zawiera?
Znajdź funkcję φ Eulera φ(196), czyli liczbę liczb całkowitych od 1 do 196 względnie pierwszych z 196.
Użyj wielokrotnego podnoszenia do kwadratu, aby znaleźć 71161 mod 84.
Dlaczego programowanie dynamiczne nie daje realnego przyspieszenia sortowania przez scalanie?
Które ograniczenie jest poprawne dla log(n!)?
Co się dzieje, gdy tablica mieszająca wykonuje rehashing po przekroczeniu progu współczynnika zapełnienia?
Usunięcie węzła z dwojgiem dzieci z binarnego drzewa poszukiwań wykonuje się zwykle przez:
Drzewo ma 2× wierzchołek stopnia 3, 3× wierzchołek stopnia 4, a wszystkie jego pozostałe wierzchołki są liśćmi (stopień 1). Ile liści L ma to drzewo?
Znajdź łączną wagę W minimalnego drzewa rozpinającego grafu ważonego.
Co zwraca SELECT COALESCE(phone, 'unknown') FROM customers dla klienta, którego phone jest NULL?
Co zwraca SELECT name, dept, AVG(salary) OVER (PARTITION BY dept) FROM emp?
W której warstwie OSI zwykle działa przełącznik (switch)?
Dlaczego przeglądarka wyświetla ostrzeżenie, gdy strona przedstawia certyfikat samopodpisany?
Dział potrzebuje 333 adresów hostów w jednej podsieci. Jaki jest najdłuższy prefiks p (najmniejsza podsieć), który wystarczy?
Host ma adres 10.20.176.163/28. Jaki jest czwarty oktet x jego adresu sieci?
Odpowiedź: U = 188
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ź: N = −8,389 × 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ź: N = 7
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.
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ź: L = 8
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.
Istnieje inne grupowanie tego samego rozmiaru; ma tę samą liczbę składników i literałów.
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.
Istnieje inne grupowanie tego samego rozmiaru; ma tę samą liczbę składników i literałów.
Odpowiedź: φ(196) = 84
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ź: 71161 mod 84 = 71
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ź: A · Θ(n log n)
log(n!) ≤ n log n, a n / 2 największych czynników daje log(n!) ≥ (n / 2) log(n / 2); dlatego sortowanie przez porównania wymaga Ω(n log n).
Odpowiedź: A · Alokuje się większą tablicę i ponownie wstawia każdy klucz
Ponieważ indeks oblicza się modulo rozmiar tablicy, wszystkie klucze trzeba ponownie zahaszować do nowej, większej tablicy; przy podwajaniu koszt zamortyzowany pozostaje O(1).
Odpowiedź: B · Zastąpienie go następnikiem (lub poprzednikiem) w porządku in-order i usunięcie tamtego węzła
Następnik in-order ma co najwyżej jedno dziecko, więc można go łatwo usunąć po skopiowaniu jego klucza do usuwanego węzła.
Odpowiedź: L = 10
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ź: W = 36
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ź: A · 'unknown'
COALESCE sprawdza argumenty od lewej do prawej i zwraca pierwszy, który nie jest NULL, tutaj 'unknown'.
Odpowiedź: C · Każdy wiersz pracownika wraz ze średnią pensją w jego dziale
W przeciwieństwie do GROUP BY funkcja okna zachowuje każdy wiersz wejściowy i dodaje wartość obliczoną dla jego partycji, tutaj działu.
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ź: B · Żaden zaufany urząd certyfikacji nie poświadcza, że klucz należy do tej strony
Przeglądarki ufają certyfikatom podpisanym, bezpośrednio lub przez łańcuch, przez urzędy certyfikacji z ich magazynu zaufanych certyfikatów. Certyfikat samopodpisany mógł wystawić każdy, np. atakujący man-in-the-middle.
Odpowiedź: p = 23
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 = 160
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