Formelsammlungen, die wichtigsten Lösungsschritte zu jedem Thema und 20 Übungsaufgaben, mit vollständigen Lösungen am Ende.
Das 8-Bit-Muster 1111 0000 speichert eine vorzeichenbehaftete Ganzzahl im Zweierkomplement. Welchen Wert N hat sie im Dezimalsystem?
Ein unkomprimiertes Bild hat 1280 × 720 Pixel mit 8 Bits pro Pixel. Wie viel Speicher M braucht es in KiB (1 KiB = 1024 Bytes)?
Welche Formel ist logisch äquivalent zu q ↔ p? Klicke sie an.
Welche Aussage ist äquivalent zu ¬∀x ∀y (R(x, y) → R(y, x)), wenn die Negation ganz nach innen gezogen ist? Klicke sie an.
Ein 4-zu-1-Multiplexer hat die Auswahleingänge S₁ = A und S₀ = B, und seine Dateneingänge liegen auf I₀ = 1, I₁ = C′, I₂ = 1, I₃ = C. Für wie viele der 8 Kombinationen von A, B und C ist der Ausgang F = 1? Bestimme N.
Ein flankengesteuertes JK-Flipflop (positive Flanke) startet mit Q = 0 und erhält die gezeigten Eingänge an 7 steigenden Taktflanken. Wie oft N ändert Q seinen Zustand?
Bestimme die Eulersche φ-Funktion φ(325), die Anzahl der ganzen Zahlen von 1 bis 325, die zu 325 teilerfremd sind.
Bestimme 990 mod 17 durch wiederholtes Quadrieren.
Wie viele Ebenen hat die Rekursion von Mergesort bei einem Array mit n Elementen?
Welche Aussage über die Auswahl des k-kleinsten Elements eines unsortierten Arrays ist richtig?
Wozu dient ein Sentinel-Knoten (Dummy-Knoten) in einer verketteten Liste?
Warum werden B-Bäume in Datenbanken und Dateisystemen verwendet?
Hat der zusammenhängende Graph einen Euler-Kreis, einen Euler-Weg, der kein Kreis ist, oder keines von beiden? Klicke deine Antwort an.
Wie viele geschlossene Wege der Länge 3 beginnen und enden bei A? Ein Weg darf Knoten und Kanten wiederholen. Nenne die Zahl N.
Eine Spalte enthält die Werte 10, 20 und NULL. Was liefert AVG(col)?
Was berechnet SELECT day, SUM(amount) OVER (ORDER BY day) FROM sales?
Welche Subnetzmaske entspricht /20?
Bei welcher Art von Routingprotokoll tritt das Count-to-Infinity-Problem auf, und was hilft dagegen?
Das Netz 192.168.10.0/24 soll in mindestens 3 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.32.151/26. Welches ist das vierte Oktett x der letzten nutzbaren Hostadresse in seinem Subnetz?
Antwort: N = −16
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: M = 900 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: (q → p) ∧ (p → q)
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) ∧ ¬R(y, 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: N = 6
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.
Ein JK-Flipflop: 00 hält, 01 setzt zurück (Q = 0), 10 setzt (Q = 1), 11 kippt.
Antwort: φ(325) = 240
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: 990 mod 17 = 13
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 · Etwa log₂ n
Das Halbieren von n bis auf 1 dauert etwa log₂ n Ebenen, und jede Ebene leistet O(n) Merge-Aufwand, das ergibt O(n log n).
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 · 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: D · Ihr hoher Verzweigungsgrad hält den Baum flach und reduziert langsame Festplattenzugriffe
B-Bäume speichern viele Schlüssel pro Knoten, daher ist die Höhe gering und pro Suche sind nur wenige Blockzugriffe nötig; B+-Bäume verketten zusätzlich die Blätter für Bereichsabfragen.
Antwort: keines von beiden
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: N = 2
Grade: Der Grad eines Knotens ist die Anzahl der Kanten, die an ihm enden. Jede Kante hat zwei Enden, daher summieren sich die Grade zum Doppelten der Kantenzahl: Σ deg(v) = 2|E| (das Handschlaglemma). Die Anzahl der Knoten mit ungeradem Grad ist deshalb gerade. Kn hat n(n − 1)/2 Kanten, ein k-regulärer Graph mit n Knoten hat nk/2, und ein Baum mit n Knoten hat n − 1 Kanten.
Antwort: A · 15
AVG ignoriert NULL und mittelt daher 10 und 20 zu 15, nicht 30 / 3 = 10.
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: C · 255.255.240.0
/20 bedeutet 8 + 8 + 4 Einsen. Vier Einsen im dritten Oktett sind 11110000 = 240, also lautet die Maske 255.255.240.0.
Antwort: B · Distanzvektor; Split Horizon und Poison Reverse
Nach einem Ausfall können Distanzvektor-Router einander weiterhin veraltete Routen melden und die Metrik langsam erhöhen. Split Horizon, Poison Reverse und eine maximale Metrik begrenzen dies.
Antwort: H = 62
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 = 190
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