Formelsammlungen, die wichtigsten Lösungsschritte zu jedem Thema und 20 Übungsaufgaben, mit vollständigen Lösungen am Ende.
Setze die Bits so, dass sie −52 im 8-Bit-Zweierkomplement speichern. Welchen Wert U hat das Muster, wenn man es als vorzeichenlose Zahl liest?
Ein System muss jedem von 4462 Elementen einen eigenen Binärcode gleicher Länge geben. Wie viele Bits b braucht es mindestens?
In wie vielen der 8 Zeilen ihrer Wahrheitstafel ist (¬b ∨ a) → (c ↔ ¬(a ∨ ¬c)) wahr? Nenne diese Zahl N.
Wie viele der 16 Zeilen der Wahrheitstafel machen ¬((¬(c → ¬d) → b) ∧ ((¬b ∧ c) → a)) wahr? Nenne diese Zahl N.
In diesem Karnaugh-Diagramm hat genau eine 1 keine benachbarte 1, bleibt also in der minimalen SOP-Form eine Gruppe aus einem Feld (ein voller Minterm mit vier Literalen). Nachbarn über den Rand des Diagramms zählen mit. Klicke dieses Feld an.
Bestimme die minimale SOP-Form von F(A, B, C, D) = Σm(5, 6, 9, 11, 12, 13) + d(0, 1, 7, 14), wobei d die Don’t-Care-Bedingungen kennzeichnet. Wie viele Literale L enthält sie?
Löse 4x ≡ 13 (mod 67). Gib die Lösung x mit 0 < x < 67 an.
Wie viele Lösungen N hat 18x ≡ 22 (mod 38) in {0, 1, …, 37}?
Was berechnet der Floyd-Warshall-Algorithmus, und wie schnell?
Liegt 22n in O(2ⁿ)?
Welchen abstrakten Datentyp verwendet Dijkstras Algorithmus, um den nächsten zu verarbeitenden Knoten zu wählen?
Wie hoch sind ohne Union by Rank und Pfadkompression die Kosten eines einzelnen find im schlechtesten Fall in einer Union-Find-Struktur mit n Elementen?
Hat der zusammenhängende Graph einen Euler-Kreis, einen Euler-Weg, der kein Kreis ist, oder keines von beiden? Klicke deine Antwort an.
Bestimme mit dem Dijkstra-Algorithmus die Länge d(F) des kürzesten Weges von A nach F im gewichteten Graphen.
Studierende können viele Kurse belegen, und Kurse haben viele Studierende. Wie wird das in Tabellen modelliert?
Zwei Ärzte im Bereitschaftsdienst prüfen jeweils, dass der andere noch Dienst hat, und melden sich dann beide gleichzeitig ab. Welche Anomalie kann Snapshot Isolation hier noch zulassen?
Wie unterscheidet sich eine zustandsbehaftete (stateful) Firewall von einem einfachen Paketfilter?
Wie unterscheidet sich bei Sliding-Window-Protokollen Go-Back-N von Selective Repeat, wenn ein Rahmen verloren geht?
Eine Abteilung braucht 1447 Hostadressen in einem einzigen Subnetz. Welche ist die längste Präfixlänge p (kleinstes Subnetz), die groß genug ist?
Das Netz 192.168.34.0/24 wird mit VLSM für diese LANs aufgeteilt: A: 25 Hosts, B: 100 Hosts, C: 21 Hosts, D: 5 Hosts. Die Subnetze werden ab .0 aufwärts vergeben, das LAN mit den meisten Hosts zuerst, jedes mit dem kleinsten passenden Subnetz. Wie lautet das vierte Oktett x der Netzadresse von LAN D?
Antwort: U = 204
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: b = 13 bit
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: N = 6
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: N = 3
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: AB = 00, CD = 10
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.
Eine 1 mit einer benachbarten 1 kann einer Gruppe aus zwei oder mehr Feldern angehören.
Antwort: L = 11
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.
Es gibt eine weitere Gruppierung derselben Größe; sie hat dieselbe Anzahl von Termen und Literalen.
Antwort: x = 20
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: N = 2
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: D · Kürzeste Wege zwischen allen Knotenpaaren in O(V³)
Floyd-Warshall ist ein Algorithmus der dynamischen Programmierung, der nacheinander jeden Knoten als Zwischenknoten zulässt und O(V³) Zeit braucht.
Antwort: B · Nein, denn 22n = 4ⁿ und 4ⁿ / 2ⁿ = 2ⁿ wächst unbeschränkt
Eine zum Exponenten addierte Konstante ergibt einen konstanten Faktor, aber eine Konstante, die den Exponenten multipliziert, ändert die Basis und die Wachstumsrate.
Antwort: A · Eine Min-Prioritätswarteschlange
Eine Min-Prioritätswarteschlange, meist ein binärer Heap, liefert effizient den unbesuchten Knoten mit der kleinsten Distanz.
Antwort: C · O(n)
Naive Vereinigungen können Bäume zu einer langen Kette verbinden, sodass find n − 1 Elternzeigern folgen muss; die beiden Heuristiken bringen es nahe an konstante Kosten.
Antwort: Euler-Weg, kein 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.
Der Euler-Weg beginnt an einem ungeraden Knoten und endet am anderen.
Antwort: d(F) = 34
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.
Jede Zeile: der abgeschlossene Knoten, sein endgültiger Abstand und die Nachbarn, deren Abstand sich verbessert.
Antwort: C · Mit einer Verknüpfungstabelle, die Fremdschlüssel auf Studierende und Kurse enthält
Eine Viele-zu-viele-Beziehung braucht eine Zuordnungstabelle (Verknüpfungstabelle), zum Beispiel enrolment(student_id, course_id), oft mit einem zusammengesetzten Primärschlüssel.
Antwort: C · Write Skew
Unter Snapshot Isolation sehen beide Transaktionen den alten Zustand und ändern verschiedene Zeilen, sodass kein Schreibkonflikt erkannt wird; die Isolationsstufe Serializable verhindert das.
Antwort: B · Sie verfolgt Verbindungen und lässt Antworten zu, die zu bestehenden Sitzungen gehören
Eine Stateful Firewall führt eine Tabelle aktiver Verbindungen, sodass Rückverkehr automatisch zugelassen wird. Ein zustandsloser Filter beurteilt jedes Paket isoliert.
Antwort: B · Go-Back-N sendet den verlorenen Rahmen und alle späteren erneut; Selective Repeat nur den verlorenen
Ein Go-Back-N-Empfänger verwirft Rahmen außer der Reihe, daher muss der Sender alles nach dem Verlust wiederholen. Selective Repeat puffert sie und fordert nur den fehlenden an.
Antwort: p = 21
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).
Antwort: x = 192
VLSM: Jedes LAN erhält das kleinste Subnetz mit 2ʰ − 2 ≥ seiner Hostzahl, also das Präfix 32 − h. Vergibt man die größten Subnetze zuerst, liegt jeder Block auf einem Vielfachen seiner eigenen Größe, und die Netzadressen ergeben sich durch Addieren der Blockgrößen.
LAN D: 192.168.34.192/29.
ExamProblems · examproblems.com/courses/computer-science-fundamentals