Formelsammlungen, die wichtigsten Lösungsschritte zu jedem Thema und 20 Übungsaufgaben, mit vollständigen Lösungen am Ende.
Setze die Bits so, dass sie −89 im 8-Bit-Zweierkomplement speichern. Welchen Wert U hat das Muster, wenn man es als vorzeichenlose Zahl liest?
Setze die Bits auf das 8-Bit-Ergebnis von 0100 0000 OR 1000 0000. Welchen Wert R hat das Ergebnis dezimal?
Du willst ¬r → (q ∨ p) durch Kontraposition beweisen. Welche Implikation beweist du stattdessen? Klicke sie an.
Wie viele der 16 Zeilen der Wahrheitstafel machen (¬p ∨ r) ∨ ((¬p ∧ ¬q) ∨ (¬r ↔ s)) wahr? Nenne diese Zahl N.
Vereinfache F = A′C′ + AB′C + A′B + A′C zur minimalen Summe von Produkten. Wie viele Literale L enthält der vereinfachte Ausdruck?
Bestimme die minimale SOP-Form von F(A, B, C, D) = Σm(0, 4, 5, 7, 12, 13, 14) + d(1, 6), wobei d die Don’t-Care-Bedingungen kennzeichnet. Wie viele Produktterme N hat sie?
Bestimme das Inverse von 37 modulo 97: die Zahl x mit 0 < x < 97 und 37·x ≡ 1 (mod 97).
Löse 15x ≡ 78 (mod 87). Gib die kleinste positive Lösung x an.
Die Rekurrenz T(n) = 2T(n/2) + O(n) hat die Lösung:
Das Halteproblem zeigt, dass:
Wie viel Speicher benötigt eine Adjazenzliste für einen Graphen mit V Knoten und E Kanten?
Mit welcher Struktur lässt sich das Maximum jedes Fensters der Größe k in einem Array insgesamt in O(n) berechnen?
Wie viele verschiedene Hamilton-Kreise H hat der vollständige Graph K5? Kreise, die sich nur im Startknoten oder in der Richtung unterscheiden, zählen als gleich.
Der Prim-Algorithmus baut einen minimalen aufspannenden Baum auf, beginnend bei Knoten D. Klicke die Kante an, die er als Kante Nummer 4 hinzufügt.
Was liefert SELECT SUM(amount) FROM orders, wenn die WHERE-Klausel auf keine Zeilen zutrifft?
Wie können Lesende bei Multiversion Concurrency Control (MVCC) vermeiden, Schreibende zu blockieren?
HTTP ist zustandslos. Wie halten Websites einen Nutzer üblicherweise über mehrere Anfragen hinweg angemeldet?
Was steuert in einer TCP-Verbindung das Empfangsfenster (rwnd)?
Das Netz 172.22.0.0/16 wird in gleich große Subnetze mit dem Präfix /20 aufgeteilt. Wie viele Subnetze N gibt es?
Ein Host hat die Adresse 10.20.222.139/28. Welches ist das vierte Oktett x der letzten nutzbaren Hostadresse in seinem Subnetz?
Antwort: U = 167
Bits setzen: Jedes Bit hat den Wert einer Zweierpotenz (128, 64, …, 1). Eine Hexadezimalziffer entspricht genau vier Bits, und im 8-Bit-Zweierkomplement hat das linke Bit den Wert −128. Bitweise Operationen wirken auf jede Bitposition einzeln.
Antwort: R = 192
Bits setzen: Jedes Bit hat den Wert einer Zweierpotenz (128, 64, …, 1). Eine Hexadezimalziffer entspricht genau vier Bits, und im 8-Bit-Zweierkomplement hat das linke Bit den Wert −128. Bitweise Operationen wirken auf jede Bitposition einzeln.
OR ergibt dort 1, wo mindestens ein Bit 1 ist.
Antwort: ¬(q ∨ p) → ¬¬r
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).
Die Kontraposition ist äquivalent zur ursprünglichen Aussage, ihr Beweis beweist also die Aussage.
Antwort: N = 14
Wahrheitstafeln: Eine Formel mit n verschiedenen Variablen hat 2ⁿ Zeilen, eine für jede Kombination von Wahrheitswerten (1 = wahr, 0 = falsch). Arbeite von innen nach außen und gib jeder Teilformel eine eigene Spalte. ¬a kehrt den Wert um; a ∧ b ist nur 1, wenn beide 1 sind; a ∨ b ist nur 0, wenn beide 0 sind; a → b ist nur 0, wenn a = 1 und b = 0; a ↔ b ist 1, wenn beide Seiten gleich sind.
Antwort: L = 3
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: N = 4
Karnaugh-Diagramme: Die Felder sind im Gray-Code (00, 01, 11, 10) angeordnet, benachbarte Felder, auch die über den Rand hinweg, unterscheiden sich also in genau einer Variablen. Fasse die Einsen in Rechtecken aus 1, 2, 4, 8 oder 16 Feldern zusammen, so groß und so wenige wie möglich, bis jede 1 abgedeckt ist. Jede Gruppe ist ein Produktterm: die Variablen, die in ihr konstant bleiben. Eine Gruppe aus 2ᵏ Feldern verliert k Variablen. Don’t-Cares (X) dürfen genutzt werden, um Gruppen zu vergrößern, müssen aber nie abgedeckt werden. Fasst du stattdessen die Nullen zusammen, erhältst du die minimale POS-Form.
Die größten Gruppen, die sich aus Einsen und X bilden lassen.
Antwort: 37−1 mod 97 = 21
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).
Jeder Rest r wird als r ≡ t·37 (mod 97) geschrieben.
Antwort: x = 11
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: C · O(n log n)
Nach dem Master-Theorem (a = 2, b = 2, f(n) = n) gilt T(n) = Θ(n log n).
Antwort: C · Kein Algorithmus für jedes Programm und jede Eingabe entscheiden kann, ob es anhält
Turing zeigte, dass das Halteproblem unentscheidbar ist: Die Annahme, ein Entscheider existiere, führt zu einem Widerspruch mit einem Programm, das das Gegenteil tut.
Antwort: D · O(V + E)
Jeder Knoten hat eine Liste, und jede Kante erscheint einmal (gerichtet) oder zweimal (ungerichtet), das ergibt O(V + E).
Antwort: C · Eine Deque mit Indizes in absteigender Reihenfolge der Werte
Das vordere Ende der Deque ist immer das Maximum des Fensters; jeder Index kommt einmal hinein und einmal heraus, daher ist der Aufwand linear.
Antwort: H = 12
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: Kante CE
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 · NULL
SUM, AVG, MIN und MAX liefern bei einer leeren Menge NULL, COUNT dagegen 0; COALESCE(SUM(amount), 0) liefert stattdessen 0.
Antwort: B · Lesende sehen einen konsistenten Snapshot festgeschriebener Zeilenversionen, während Schreibende neue Versionen anlegen
MVCC bewahrt alte Zeilenversionen auf, sodass ein Lesender die Daten zum Zeitpunkt seines Snapshots sehen kann, während ein Schreibender eine neue Version anlegt, statt an Ort und Stelle zu überschreiben.
Antwort: D · Mit Cookies, die eine Sitzungs-ID oder ein Token enthalten
Der Server setzt ein Cookie mit einer Sitzungs-ID oder einem Token, und der Browser schickt es bei jeder Anfrage mit, sodass der Server den Nutzer wiedererkennt.
Antwort: A · Wie viele unbestätigte Daten der Sender senden darf, basierend auf dem Puffer des Empfängers
Der Empfänger teilt mit, wie viel Pufferplatz er hat; der Sender begrenzt die unbestätigten Daten entsprechend und verhindert so eine Überlastung des Empfängers.
Antwort: N = 16
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).
Jedes /20-Subnetz hat 212 − 2 = 4094 nutzbare Hosts.
Antwort: x = 142
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