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?
Was ist die kleinste (negativste) ganze Zahl N, die im 24-Bit-Zweierkomplement gespeichert werden kann?
Welche Formel ist logisch äquivalent zu p → q? Klicke sie an.
Welche Aussage ist äquivalent zu ¬∃x ∀y R(x, y), wenn die Negation ganz nach innen gezogen ist? Klicke sie an.
Bestimme mit dem Karnaugh-Diagramm das minimale Produkt von Summen (POS) von F(A, B, C) = Σm(0, 1, 2, 3, 4). Wie viele Summenterme (Faktoren) N hat es?
Ein flankengesteuertes D-Flipflop (positive Flanke) startet mit Q = 0 und erhält die gezeigten Eingänge an 6 steigenden Taktflanken. Wie oft N ändert Q seinen Zustand?
Bestimme das Inverse von 7 modulo 23: die Zahl x mit 0 < x < 23 und 7·x ≡ 1 (mod 23).
Ein RSA-Schlüssel verwendet p = 5, q = 41 und e = 11. Entschlüssele den Geheimtext c = 49: Bestimme die Nachricht m.
Welche Greedy-Regel liefert beim Aktivitätsauswahlproblem immer eine maximale Anzahl sich nicht überschneidender Aktivitäten?
Die Karatsuba-Multiplikation erfüllt T(n) = 3T(n/2) + O(n). Was ist die Lösung?
Wozu dient ein Sentinel-Knoten (Dummy-Knoten) in einer verketteten Liste?
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?
Ein Baum hat 4 Knoten vom Grad 3, 4 Knoten vom Grad 4, 2 Knoten vom Grad 5, und alle seine anderen Knoten sind Blätter (Grad 1). Wie viele Blätter L hat er?
Bestimme das Gesamtgewicht W eines minimalen aufspannenden Baums des gewichteten Graphen.
Welche Abfrage liefert die Anzahl verschiedener Städte in der Tabelle customers?
Welche Fensterfunktion vergibt innerhalb jeder Partition die Nummern 1, 2, 3, ... an Zeilen, ohne Gleichstände?
Was gibt ein MX-Eintrag im DNS an?
Wie unterscheidet sich bei Sliding-Window-Protokollen Go-Back-N von Selective Repeat, wenn ein Rahmen verloren geht?
Das Netz 192.168.10.0/24 soll in mindestens 6 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.55.145/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: N = −8,389 × 10⁶
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: ¬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 ∃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: N = 2
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 = 2
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.
Ein D-Flipflop übernimmt D bei jeder steigenden Flanke: Q⁺ = D.
Antwort: 7−1 mod 23 = 10
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·7 (mod 23) geschrieben.
Antwort: m = 74
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 · Die Aktivität wählen, die am frühesten endet, dann mit den verträglichen wiederholen
Dass die Wahl des frühesten Endzeitpunkts optimal ist, lässt sich mit einem Austauschargument beweisen; für die anderen Regeln gibt es Gegenbeispiele.
Antwort: D · Θ(nlog₂ 3), etwa n1,585
Da log₂ 3 ≈ 1,585 > 1 ist, dominieren nach dem Master-Theorem die Blätter; das schlägt die O(n²)-Schulmethode.
Antwort: C · 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 · 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: L = 20
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: W = 41
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: C · SELECT COUNT(DISTINCT city) FROM customers
COUNT(DISTINCT city) zählt eindeutige Nicht-NULL-Städte; DISTINCT außerhalb von COUNT entfernt nur doppelte Ergebniszeilen.
Antwort: A · ROW_NUMBER()
ROW_NUMBER vergibt eindeutige fortlaufende Nummern; RANK lässt nach Gleichständen Lücken; DENSE_RANK nicht.
Antwort: D · Die Mailserver, die E-Mails für eine Domain annehmen
MX-Einträge (Mail Exchange) listen Mailserver mit Prioritäten auf, damit sendende Server wissen, wohin sie Mails für diese Domain zustellen sollen.
Antwort: A · 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: H = 30
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 = 159
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