Formelsammlungen, die wichtigsten Lösungsschritte zu jedem Thema und 20 Übungsaufgaben, mit vollständigen Lösungen am Ende.
Setze die Bits so, dass sie −23 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 1111 0001 << 3. Welchen Wert R hat das Ergebnis dezimal?
Welche Formel ist logisch äquivalent zu ¬(q ∨ p)? Klicke sie an.
Welche Aussage ist äquivalent zu ¬∀x P(x), wenn die Negation ganz nach innen gezogen ist? Klicke sie an.
Bestimme mit dem Karnaugh-Diagramm die minimale Summe von Produkten (SOP) von F(A, B, C, D) = Σm(2, 3, 6, 9, 12, 15). Wie viele Literale L enthält sie insgesamt (eine Variable mit Strich zählt als ein Literal)?
Bestimme für F(A, B, C, D) = Σm(0, 3, 7, 9, 10, 13, 14, 15) + d(4, 8, 12), wobei d die Don’t-Care-Bedingungen kennzeichnet, die Anzahl N der wesentlichen Primimplikanten.
Bestimme die kleinste positive ganze Zahl x mit x ≡ 2 (mod 9) und x ≡ 3 (mod 10).
Bestimme 4991 mod 79 durch wiederholtes Quadrieren.
Eine Funktion führt eine Schleife mit n Iterationen und danach, getrennt davon, eine weitere Schleife mit n Iterationen aus. Welche Zeitkomplexität hat sie?
Warum ist eine Suche in einer Hashtabelle im Durchschnitt O(1), im Worst Case aber O(n)?
Wozu dient ein Sentinel-Knoten (Dummy-Knoten) in einer verketteten Liste?
Wie hoch ist unter der Annahme des einfachen gleichverteilten Hashings die erwartete Suchzeit in einer Hashtabelle mit Chaining, n Schlüsseln und m Buckets?
Ein Baum hat 4 Knoten vom Grad 3, 3 Knoten vom Grad 4, 4 Knoten vom Grad 5, 4 Knoten vom Grad 2, und alle seine anderen Knoten sind Blätter (Grad 1). Wie viele Blätter L hat er?
Bestimme mit dem Dijkstra-Algorithmus die Länge d(F) des kürzesten Weges von A nach F im 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?
Was berechnet SELECT day, SUM(amount) OVER (ORDER BY day) FROM sales?
Wie viele nutzbare Hostadressen hat ein IPv4-Subnetz mit /26?
Ein Pfad hat 100 Mbit/s Bandbreite und 40 ms Round-Trip-Time. Wie viele Daten müssen unterwegs sein, um ihn voll auszulasten?
Das Netz 192.168.10.0/24 soll in mindestens 30 gleich große Subnetze aufgeteilt werden. Wenn du so wenige Bits wie möglich leihst, wie viele nutzbare Hosts H hat jedes Subnetz?
Ein Host hat die Adresse 10.20.183.73/29. Welches ist das vierte Oktett x seiner Netzadresse?
Antwort: U = 233
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 = 136
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.
Das Linksschieben um 3 verschiebt jedes Bit um 3 Stellen nach links; Bits, die am linken Ende herausfallen, gehen verloren, und rechts kommen Nullen nach.
Antwort: ¬q ∧ ¬p
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 Spalten nach dem Strich sind die Optionen in der angezeigten Reihenfolge.
Antwort: ∃x ¬P(x)
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 = 18
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.
Jede Gruppe ist ein Rechteck aus 2ᵏ Feldern; Randfelder sind Nachbarn der Felder am gegenüberliegenden Rand.
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: x = 83
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: 4991 mod 79 = 55
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: A · O(n)
n + n = 2n, und konstante Faktoren fallen weg, also ist die Funktion O(n).
Antwort: D · Viele Schlüssel können im selben Bucket kollidieren
Mit einer guten Hashfunktion und einem passenden Füllgrad (Load Factor) bleiben Buckets im Durchschnitt kurz; gezielte Angriffe oder schlechtes Hashing können alle Schlüssel in einen Bucket legen.
Antwort: B · Er vereinfacht den Code, weil Sonderfälle am Kopf oder Ende wegfallen
Mit einem Sentinel hat jeder echte Knoten einen Vorgänger, daher braucht Einfügen oder Löschen am Kopf keine Sonderbehandlung.
Antwort: A · O(1 + α), wobei α = n / m
Das Berechnen des Hashs kostet O(1), und die erwartete Kettenlänge ist α; hält man α durch Vergrößern beschränkt, ergibt sich eine erwartete Zeit von O(1).
Antwort: L = 24
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.
Abkürzung: L = 2 + Σ (d − 2) über die Knoten mit Grad d ≥ 3.
Antwort: d(F) = 37
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: 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 · Eine laufende Summe von amount, geordnet nach day
Mit ORDER BY und ohne expliziten Frame reicht das Fenster von der ersten Zeile bis zur aktuellen Zeile (und ihren Gleichständen), was eine kumulierte Summe ergibt.
Antwort: A · 62
Ein /26 hat 6 Host-Bits: 2⁶ = 64 Adressen, abzüglich Netz- und Broadcast-Adresse ergibt 62 nutzbare Hosts.
Antwort: A · 500 kB
Das Bandbreite-Verzögerungs-Produkt beträgt 100 × 10⁶ Bit/s × 0,04 s = 4 × 10⁶ Bit = 500 kB. Das Fenster des Senders muss mindestens so groß sein.
Antwort: H = 6
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 = 72
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