Formelsammlungen, die wichtigsten Lösungsschritte zu jedem Thema und 20 Übungsaufgaben, mit vollständigen Lösungen am Ende.
Setze die Bits so, dass sie −95 im 8-Bit-Zweierkomplement speichern. Welchen Wert U hat das Muster, wenn man es als vorzeichenlose Zahl liest?
Ein unkomprimiertes Bild hat 800 × 600 Pixel mit 32 Bits pro Pixel. Wie viel Speicher M braucht es in KiB (1 KiB = 1024 Bytes)?
In wie vielen der 8 Zeilen ihrer Wahrheitstafel ist ((r → p) → q) ∨ (¬q → r) wahr? Nenne diese Zahl N.
Wie viele der 16 Zeilen der Wahrheitstafel machen (¬(s ∨ r) ∧ q) ∧ ((s ∧ ¬q) → p) wahr? Nenne diese Zahl N.
Ein 4-zu-1-Multiplexer hat die Auswahleingänge S₁ = A und S₀ = B, und seine Dateneingänge liegen auf I₀ = 1, I₁ = 0, I₂ = 1, I₃ = C′. Für wie viele der 8 Kombinationen von A, B und C ist der Ausgang F = 1? Bestimme N.
Ein Mod-25-Zähler muss 25 verschiedene Zustände durchlaufen. Wie viele Flipflops n braucht er mindestens?
Bestimme das Inverse von 19 modulo 53: die Zahl x mit 0 < x < 53 und 19·x ≡ 1 (mod 53).
Ein RSA-Schlüssel verwendet p = 5, q = 43 und e = 23. Entschlüssele den Geheimtext c = 116: Bestimme die Nachricht m.
Du sortierst ein Array mit n Elementen einmal und beantwortest danach k Enthaltenseinsanfragen mit binärer Suche. Wie hoch sind die Gesamtkosten?
Welche Aussage über die Auswahl des k-kleinsten Elements eines unsortierten Arrays ist richtig?
Eine Hashtabelle der Größe 7 verwendet h(k) = k mod 7 und lineares Sondieren. Wo wird 17 gespeichert, nachdem 10 eingefügt wurde?
Was macht ein Splay-Baum nach jedem Zugriff?
Wie viele verschiedene Hamilton-Kreise H hat der vollständige Graph K4? Kreise, die sich nur im Startknoten oder in der Richtung unterscheiden, zählen als gleich.
Bestimme das Gesamtgewicht W eines minimalen aufspannenden Baums des gewichteten Graphen.
Warum kann eine Tabelle nur einen Clustered Index haben?
Welche Fensterfunktion vergibt innerhalb jeder Partition die Nummern 1, 2, 3, ... an Zeilen, ohne Gleichstände?
Welches Paritätsbit wird bei gerader Parität an die Datenbits 1011001 angehängt?
Eine Remote-Terminal-Anwendung reagiert träge, weil kleine Tastendruck-Pakete zurückgehalten werden. Welcher TCP-Mechanismus ist häufig dafür verantwortlich?
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.27.186/26. Welche ist die letzte Zahl (viertes Oktett) x der Broadcast-Adresse seines Subnetzes?
Antwort: U = 161
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: M = 1875 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: 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 = 2
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 = 5
Multiplexer: Ein 2ⁿ-zu-1-Multiplexer schaltet einen seiner Dateneingänge auf den Ausgang durch; die als Binärzahl gelesenen Auswahlleitungen bestimmen, welchen. Bei einem 4-zu-1-MUX mit den Auswahleingängen S₁S₀ = AB gilt F = A′B′·I₀ + A′B·I₁ + AB′·I₂ + AB·I₃. Legt man die Dateneingänge auf 0, 1, C oder C′, erzeugt der MUX jede Funktion von A, B und C, was ein gängiger Weg ist, Logik mit einem Baustein aufzubauen.
Antwort: n = 5
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: 19−1 mod 53 = 14
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·19 (mod 53) geschrieben.
Antwort: m = 106
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: B · O(n log n + k log n)
Das Sortieren kostet O(n log n) und jede Anfrage O(log n); das schlägt k lineare Durchläufe (O(nk)), wenn k groß ist.
Antwort: A · Quickselect läuft erwartet in O(n), und Median-of-Medians garantiert O(n) im Worst Case
Der erwartete Aufwand von Quickselect ist mit zufälligen Pivots n + n/2 + n/4 + ... = O(n); wählt man das Pivot als Median der Mediane, wird der Worst Case linear.
Antwort: D · Index 4
10 mod 7 = 3 und 17 mod 7 = 3; Index 3 ist belegt, also probiert lineares Sondieren den nächsten Platz, Index 4.
Antwort: D · Er rotiert den zugegriffenen Knoten bis zur Wurzel hoch
Splaying bringt den zugegriffenen Knoten durch Rotationen in die Wurzel; eine einzelne Operation kann O(n) kosten, aber die amortisierten Kosten betragen O(log n).
Antwort: H = 3
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 = 28
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: A · Die Zeilen können physisch nur in einer Reihenfolge gespeichert werden
Ein Clustered Index ordnet die Daten der Tabelle nach seinem Schlüssel, und Daten lassen sich nur in einer Reihenfolge halten; andere Indexe sind Non-Clustered.
Antwort: B · ROW_NUMBER()
ROW_NUMBER vergibt eindeutige fortlaufende Nummern; RANK lässt nach Gleichständen Lücken; DENSE_RANK nicht.
Antwort: D · 0
1011001 enthält vier 1-Bits, bereits eine gerade Zahl, also ist das Paritätsbit 0. Bei ungerader Parität wäre es 1.
Antwort: B · Nagle-Algorithmus
Der Nagle-Algorithmus wartet und bündelt kleine Segmente, solange frühere Daten unbestätigt sind. Das spart Bandbreite, erhöht aber die Verzögerung bei interaktivem Verkehr.
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 = 191
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