Formelsammlungen, die wichtigsten Lösungsschritte zu jedem Thema und 20 Übungsaufgaben, mit vollständigen Lösungen am Ende.
Das 8-Bit-Muster 0011 1100 speichert eine vorzeichenbehaftete Ganzzahl im Zweierkomplement. Welchen Wert N hat sie im Dezimalsystem?
Ein unkomprimiertes Bild hat 640 × 480 Pixel mit 24 Bits pro Pixel. Wie viel Speicher M braucht es in KiB (1 KiB = 1024 Bytes)?
Ist ((q → r) ∧ (q → p)) → (r → p) eine Tautologie, eine Kontradiktion oder eine Kontingenz? Klicke deine Antwort an.
Welche Aussage ist äquivalent zu ¬∀x ∃y R(x, y), wenn die Negation ganz nach innen gezogen ist? Klicke sie an.
Vereinfache F = A′BC + A′B′C + B′C + AB′C′ zur minimalen Summe von Produkten. Wie viele Literale L enthält der vereinfachte Ausdruck?
Ein 8-Bit-Asynchronzähler wird aus Flipflops mit einer Signallaufzeit von je 15 ns aufgebaut. Alle Ausgänge müssen sich vor der nächsten Taktflanke eingestellt haben. Bestimme die maximale Taktfrequenz fmax.
Löse 63x ≡ 43 (mod 71). Gib die Lösung x mit 0 < x < 71 an.
Bestimme 29199 mod 78 durch wiederholtes Quadrieren.
Dynamische Programmierung ist nützlich, wenn ein Problem Folgendes aufweist:
Welche Aussage über die Klein-o-Notation ist richtig?
Mit welcher Datenstruktur prüft man, ob die Klammern in "{[()]}" ausgeglichen sind?
Ein dynamisches Array verdoppelt sich, wenn es voll ist. Warum verkleinern es viele Implementierungen erst, wenn es zu einem Viertel gefüllt ist, und nicht schon bei halber Füllung?
Hat der zusammenhängende Graph einen Euler-Kreis, einen Euler-Weg, der kein Kreis ist, oder keines von beiden? Klicke deine Antwort an.
Bestimme das Gesamtgewicht W eines minimalen aufspannenden Baums des gewichteten Graphen.
Eine Tabelle employees hat eine Spalte manager_id, die auf einen anderen Mitarbeiter verweist. Wie listest du jeden Mitarbeiter neben dem Namen seines Vorgesetzten auf?
Warum gilt NATURAL JOIN in Produktionsabfragen als riskant?
In welcher Reihenfolge laufen die Nachrichten üblicherweise ab, wenn ein Client eine Adresse per DHCP erhält?
Welche Schicht im TCP/IP-Modell fügt Portnummern hinzu?
Ein Subnetz verwendet die Maske 255.255.252.0. Wie viele nutzbare Hostadressen H hat es?
Ein Host hat die Adresse 10.20.189.113/28. Welche ist die letzte Zahl (viertes Oktett) x der Broadcast-Adresse seines Subnetzes?
Antwort: N = 60
Stellenwertsysteme: Jede Ziffer ist ihren Wert mal eine Potenz der Basis wert. Im Binärsystem sind die Stellen 1, 2, 4, 8, 16, … wert, im Hexadezimalsystem 1, 16, 256, …, wobei A–F für 10–15 stehen. Im 8-Bit-Zweierkomplement ist das linke Bit −128 statt +128 wert; so werden negative Zahlen gespeichert.
Die übrigen Bits behalten ihre normalen positiven Werte.
Antwort: M = 900 KiB
Stellenwertsysteme: Jede Ziffer ist ihren Wert mal eine Potenz der Basis wert. Im Binärsystem sind die Stellen 1, 2, 4, 8, 16, … wert, im Hexadezimalsystem 1, 16, 256, …, wobei A–F für 10–15 stehen. Im 8-Bit-Zweierkomplement ist das linke Bit −128 statt +128 wert; so werden negative Zahlen gespeichert.
Antwort: Kontingenz
Logische Äquivalenz: Zwei Formeln sind äquivalent (≡), wenn sie in jeder Zeile der Wahrheitstafel denselben Wert haben. Eine Tautologie ist in jeder Zeile 1, eine Kontradiktion in jeder Zeile 0, und eine Kontingenz ist keines von beiden. Nützliche Gesetze: De Morgan, ¬(a ∧ b) ≡ ¬a ∨ ¬b und ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (Kontraposition); ¬(a → b) ≡ a ∧ ¬b; und die Distributivgesetze, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).
Antwort: ∃x ∀y ¬R(x, y)
Quantoren und Argumente: ¬∀x P(x) ≡ ∃x ¬P(x) und ¬∃x P(x) ≡ ∀x ¬P(x). Ziehe eine Negation nach innen, vertausche jeden Quantor, den sie passiert, und negiere die innere Formel mit den aussagenlogischen Gesetzen, etwa ¬(a → b) ≡ a ∧ ¬b. Ein Argument ist gültig, wenn die Konklusion in jeder Zeile 1 ist, in der alle Prämissen 1 sind. Eine einzige Zeile mit wahren Prämissen und falscher Konklusion ist ein Gegenbeispiel und zeigt, dass das Argument ungültig ist.
Die anderen Optionen lassen entweder einen Quantor unverändert, ändern die Reihenfolge der Quantoren oder negieren die innere Formel falsch.
Antwort: L = 4
Boolesche Algebra: Die Regeln, die Ausdrücke vereinfachen, sind X + X′ = 1 und X·X′ = 0, X + X = X, die Absorption X + X·Y = X, die Zusammenfassungsregel X·Y + X·Y′ = X, X + X′Y = X + Y und das Konsensus-Theorem XY + X′Z + YZ = XY + X′Z. Die De-Morganschen Gesetze machen aus (X·Y)′ den Ausdruck X′ + Y′ und aus (X + Y)′ den Ausdruck X′·Y′. Ein Karnaugh-Diagramm wendet diese Regeln grafisch an: Jede Gruppe aus zwei benachbarten Feldern ist eine Anwendung von XY + XY′ = X.
Antwort: fmax = 8,333 MHz
Flipflops und Zähler: Ein Flipflop ändert sich nur bei der aktiven Taktflanke. D übernimmt seinen Eingang (Q⁺ = D); T kippt bei T = 1; JK hält bei 00, setzt bei 01 zurück, setzt bei 10 und kippt bei 11. Ein n-Bit-Binärzähler hat 2ⁿ Zustände und zählt modulo 2ⁿ; ein Mod-N-Zähler läuft 0, 1, …, N − 1 und wieder auf 0 und braucht die kleinste Anzahl n von Flipflops mit 2ⁿ ≥ N. Jede Stufe eines Asynchronzählers halbiert die Frequenz, daher läuft der letzte Ausgang eines Mod-N-Zählers mit fclk/N. Ein Johnson-Zähler aus n Flipflops hat 2n Zustände, ein Ringzähler n.
Antwort: x = 39
Inverse und Kongruenzen: a hat genau dann ein Inverses modulo n, wenn ggT(a, n) = 1. Der erweiterte euklidische Algorithmus schreibt 1 = s·n + t·a, und dann ist a⁻¹ ≡ t (mod n). Eine Kongruenz a·x ≡ b (mod n) mit ggT(a, n) = 1 hat die Lösung x ≡ a⁻¹·b. Zwei Kongruenzen x ≡ r₁ (mod m₁) und x ≡ r₂ (mod m₂) mit teilerfremden Moduln haben eine Lösung modulo m₁·m₂ (chinesischer Restsatz). Eulers φ(n) zählt die Zahlen von 1 bis n, die zu n teilerfremd sind: φ(n) = n·∏(1 − 1/p).
Antwort: 29199 mod 78 = 29
Modulare Potenzen und RSA: Berechne aᵏ mod n durch wiederholtes Quadrieren: Schreibe k binär, quadriere, reduziere nach jedem Schritt und multipliziere die Potenzen, deren Bit 1 ist. Fermat: aᵖ⁻¹ ≡ 1 (mod p) für eine Primzahl p, die a nicht teilt, der Exponent lässt sich also modulo p − 1 reduzieren. RSA: Wähle Primzahlen p und q, n = p·q und φ(n) = (p − 1)(q − 1); der öffentliche Exponent e ist teilerfremd zu φ(n), und der private Exponent ist d = e⁻¹ mod φ(n). Verschlüssele mit c = mᵉ mod n und entschlüssele mit m = cᵈ mod n.
Antwort: D · Überlappende Teilprobleme und optimale Teilstruktur
Das Speichern der Ergebnisse überlappender Teilprobleme (Memoisation oder Tabellierung) vermeidet doppelte Arbeit und macht aus exponentiellen Algorithmen polynomielle.
Antwort: A · n = o(n²), aber n ist nicht o(n)
f = o(g) bedeutet, dass f(n) / g(n) gegen 0 strebt; n / n² strebt gegen 0, aber n / n = 1 nicht.
Antwort: A · Mit einem Stack
Lege jede öffnende Klammer mit push ab und hole bei einer schließenden Klammer mit pop eine heraus; sie muss zur entnommenen Klammer passen, und am Ende muss der Stack leer sein.
Antwort: C · Um wiederholtes Umdimensionieren zu vermeiden, wenn sich push und pop nahe der Grenze abwechseln
Verkleinern bei halber Füllung könnte in einer solchen Folge bei jeder Operation ein Umdimensionieren auslösen; der Abstand zwischen 1/4 und voll hält die amortisierten Kosten bei O(1).
Antwort: Euler-Kreis
Euler, Hamilton und Bäume: Ein zusammenhängender Graph hat einen Euler-Kreis (jede Kante einmal, zurück zum Start), wenn jeder Knoten geraden Grad hat, und einen Euler-Weg, der kein Kreis ist, wenn genau zwei Knoten ungeraden Grad haben; der Weg verläuft dann von einem ungeraden Knoten zum anderen. Ein Hamilton-Kreis besucht jeden Knoten einmal; Kn hat (n − 1)!/2 davon. Ein Baum mit n Knoten hat n − 1 Kanten, und ein zusammenhängender Graph mit m Kanten behält einen aufspannenden Baum, wenn man m − n + 1 Kanten entfernt.
Antwort: W = 19
Kürzeste Wege und aufspannende Bäume: Der Dijkstra-Algorithmus schließt in jeder Runde einen Knoten ab: den offenen Knoten mit dem kleinsten vorläufigen Abstand. Sein Abstand ist dann endgültig, und jeder Nachbar v erhält d(v) = min(d(v), d(u) + w(u, v)). Der Kruskal-Algorithmus baut einen minimalen aufspannenden Baum auf, indem er die Kanten von leicht nach schwer nimmt und jede Kante überspringt, die einen Kreis schließen würde; der Prim-Algorithmus lässt einen Baum von einem Startknoten aus wachsen, indem er immer die leichteste Kante hinzufügt, die aus ihm herausführt. Ein aufspannender Baum mit n Knoten hat n − 1 Kanten.
Antwort: D · Die Tabelle employees mit sich selbst über zwei Aliase verbinden
Ein Self-Join wie FROM employees e JOIN employees m ON e.manager_id = m.id lässt einen Alias den Mitarbeiter und den anderen den Vorgesetzten darstellen.
Antwort: C · Er verbindet über jede gleichnamige Spalte, sodass eine neue Spalte das Ergebnis unbemerkt verändern kann
Ein Natural Join verbindet alle gleichnamigen Spalten, zum Beispiel ein nicht zusammengehöriges "name" oder "created_at"; eine explizite ON- oder USING-Klausel ist sicherer.
Antwort: C · Discover, Offer, Request, Acknowledge
Der Client sendet Discover als Broadcast, Server antworten mit Offers, der Client fordert mit Request ein Angebot an, und der gewählte Server bestätigt mit Acknowledge.
Antwort: A · Transportschicht
TCP- und UDP-Header enthalten Quell- und Zielports; die Internetschicht (IP) fügt die Adressen hinzu.
Antwort: H = 1022
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).
Antwort: x = 127
IPv4-Subnetting: Eine Adresse hat 32 Bits. Das Präfix /p gibt an, wie viele führende Bits das Netz bezeichnen; die übrigen 32 − p Bits nummerieren die Hosts. Ein Subnetz hat 2³²⁻ᵖ Adressen, aber die erste (Netzadresse) und die letzte (Broadcast-Adresse) können keinem Host gegeben werden, also passen 2³²⁻ᵖ − 2 Hosts hinein. Ausnahmen: Ein /31 (Punkt-zu-Punkt-Verbindung, RFC 3021) nutzt beide seiner 2 Adressen für Hosts, und ein /32 ist eine einzelne Adresse (ein einzelner Host oder ein Loopback).
ExamProblems · examproblems.com/courses/computer-science-fundamentals