Formelsammlungen, die wichtigsten Lösungsschritte zu jedem Thema und 20 Übungsaufgaben, mit vollständigen Lösungen am Ende.
Das 8-Bit-Muster 1001 1011 speichert eine vorzeichenbehaftete Ganzzahl im Zweierkomplement. Welchen Wert N hat sie im Dezimalsystem?
Ein unkomprimiertes Bild hat 256 × 256 Pixel mit 24 Bits pro Pixel. Wie viel Speicher M braucht es in KiB (1 KiB = 1024 Bytes)?
In wie vielen der 8 Zeilen ihrer Wahrheitstafel ist ¬((b ↔ (a → c)) → ¬(¬b ∨ a)) wahr? Nenne diese Zahl N.
Das Argument mit den Prämissen p → q; r → q und der Konklusion p → r ist ungültig. Klicke die Zeile der Wahrheitstafel an, die ein Gegenbeispiel ist.
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₂ = C, I₃ = 1. Für wie viele der 8 Kombinationen von A, B und C ist der Ausgang F = 1? Bestimme N.
Ein 4-Bit-Johnson-Zähler Q₃Q₂Q₁Q₀ startet bei 0000. Bei jeder Taktflanke werden die Bits um eine Stelle nach rechts geschoben (Q₃ → Q₂ → Q₁ → Q₀), und Q₃ erhält das Inverse von Q₀. Gib den Zustand Q = Q₃Q₂Q₁Q₀ nach 11 Taktflanken als Dezimalzahl an.
Bestimme das Inverse von 51 modulo 61: die Zahl x mit 0 < x < 61 und 51·x ≡ 1 (mod 61).
Verschlüssele die Nachricht m = 217 mit dem öffentlichen RSA-Schlüssel (n, e) = (247, 5). Bestimme den Geheimtext c.
Quicksort verwendet immer das erste Element als Pivot. Bei welcher Eingabe zeigt es sein Worst-Case-Verhalten?
Welche Zeit- und Speicherkosten hat die Berechnung der n-ten Fibonacci-Zahl mit einer Schleife, die nur die letzten beiden Werte behält?
Die Schlüssel 50, 30, 70, 20, 40 werden in dieser Reihenfolge in einen leeren binären Suchbaum eingefügt. Was ist das linke Kind von 30?
Welche Aussage über Heapsort ist richtig?
Ein zusammenhängender Graph hat 11 Knoten und 14 Kanten. Wie viele Kanten k müssen entfernt werden, damit ein aufspannender Baum übrig bleibt?
Bestimme mit dem Dijkstra-Algorithmus die Länge d(F) des kürzesten Weges von A nach F im gewichteten Graphen.
Die Tabelle orders hat 5 Zeilen, die jeweils auf einen existierenden Kunden verweisen. Die Tabelle customers hat 3 Zeilen. Wie viele Zeilen liefert ein INNER JOIN über customer_id?
x ist NULL und y = 1. Welchen Wert hat die Bedingung (x > 5 OR y = 1)?
Was ist der Hauptunterschied zwischen den HTTP-Methoden GET und POST?
Du sollst 192.168.1.0/24 in mindestens 5 Subnetze mit je bis zu 25 Hosts aufteilen. Welche Präfixlänge passt am besten?
Ein Subnetz verwendet die Maske 255.255.255.252. Wie viele nutzbare Hostadressen H hat es?
Ein Host hat die Adresse 172.20.128.94/18. Wie lautet das dritte Oktett x der Broadcastadresse seines Subnetzes?
Antwort: N = −101
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 = 192 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 = 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: p = 1, q = 1, r = 0
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.
Ein Argument dieser Form sieht aus wie eine gültige Regel, aber eine Zeile genügt, um zu zeigen, dass sie es nicht ist.
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: Q = 14
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: 51−1 mod 61 = 6
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·51 (mod 61) geschrieben.
Antwort: c = 107
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: D · Bei einem bereits sortierten Array
Bei sortierter Eingabe ist das Pivot immer das Minimum, sodass eine Seite leer ist und die andere n − 1 Elemente hat; das ergibt O(n²).
Antwort: D · O(n) Zeit und O(1) Speicher
Jeder Schritt braucht nur die beiden vorherigen Werte, daher kann die Tabelle der Bottom-up-Methode durch zwei Variablen ersetzt werden.
Antwort: A · 20
20 ist kleiner als 50 und kleiner als 30, wird also das linke Kind von 30; 40 wird sein rechtes Kind.
Antwort: C · Er sortiert in place in O(n log n) im schlechtesten Fall, ist aber nicht stabil
Heapsort baut einen Max-Heap und entnimmt n-mal das Maximum innerhalb desselben Arrays; Vertauschungen über große Abstände können gleiche Schlüssel umordnen.
Antwort: k = 4
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: d(F) = 23
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 · 5
Jede Bestellung findet genau einen passenden Kunden, daher liefert der Join eine Zeile pro Bestellung: 5 Zeilen.
Antwort: D · TRUE
x > 5 ist UNKNOWN, aber OR mit TRUE ist in jedem Fall TRUE, daher wird die Zeile behalten; UNKNOWN AND FALSE wäre entsprechend FALSE.
Antwort: D · GET ruft eine Ressource ab, POST übermittelt Daten im Request-Body
GET fordert eine Ressource an und sollte den Serverzustand nicht ändern. POST sendet Daten, etwa ein Formular, im Body zur Verarbeitung an den Server.
Antwort: D · /27
/27 ergibt 8 Subnetze mit je 30 nutzbaren Hosts. /26 ergibt nur 4 Subnetze, und /28 erlaubt nur 14 Hosts pro Subnetz.
Antwort: H = 2
IPv4 subnetting: an address has 32 bits. The prefix /p says how many leading bits identify the network; the remaining 32 − p bits number the hosts. A subnet has 2³²⁻ᵖ addresses, but the first (network address) and last (broadcast address) cannot be given to hosts, so 2³²⁻ᵖ − 2 hosts fit. Exceptions: a /31 (point-to-point link, RFC 3021) uses both of its 2 addresses for hosts, and a /32 is one single address (a single host or a loopback).
Antwort: x = 191
IPv4 subnetting: an address has 32 bits. The prefix /p says how many leading bits identify the network; the remaining 32 − p bits number the hosts. A subnet has 2³²⁻ᵖ addresses, but the first (network address) and last (broadcast address) cannot be given to hosts, so 2³²⁻ᵖ − 2 hosts fit. Exceptions: a /31 (point-to-point link, RFC 3021) uses both of its 2 addresses for hosts, and a /32 is one single address (a single host or a loopback).
ExamProblems · examproblems.com/courses/computer-science-fundamentals