Formelsammlungen, die wichtigsten Lösungsschritte zu jedem Thema und 20 Übungsaufgaben, mit vollständigen Lösungen am Ende.
Das 8-Bit-Muster 1100 0011 speichert eine vorzeichenbehaftete Ganzzahl im Zweierkomplement. Welchen Wert N hat sie im Dezimalsystem?
Setze die Bits auf das 8-Bit-Ergebnis von 0100 1110 OR 0111 0110. Welchen Wert R hat das Ergebnis dezimal?
Du willst (q ∨ p) → ¬r durch Widerspruch beweisen. Welche Aussage nimmst du am Anfang an? Klicke sie an.
Welche Aussage ist äquivalent zu ¬∀x (A(x) ∨ B(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(1, 2, 5, 10, 11). Wie viele Literale L enthält sie insgesamt (eine Variable mit Strich zählt als ein Literal)?
Ein flankengesteuertes T-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 das Inverse von 68 modulo 89: die Zahl x mit 0 < x < 89 und 68·x ≡ 1 (mod 89).
Wie viele Lösungen N hat 20x ≡ 36 (mod 68) in {0, 1, …, 67}?
Die untere Schranke für vergleichsbasiertes Sortieren im Worst Case ist:
Welche zwei Dinge müssen gezeigt werden, um zu beweisen, dass ein Entscheidungsproblem X NP-vollständig ist?
Ein Ringpuffer (Circular Buffer) wird häufig verwendet, um Folgendes zu implementieren:
Durch das Einfügen eines Schlüssels in einen AVL-Baum wird der linke Teilbaum eines Knotens zu hoch, und der neue Schlüssel landete im linken Teilbaum seines linken Kindes (Links-links-Fall). Welche Korrektur wird angewendet?
Hat der zusammenhängende Graph einen Euler-Kreis, einen Euler-Weg, der kein Kreis ist, oder keines von beiden? Klicke deine Antwort an.
Der Dijkstra-Algorithmus läuft von A aus. Klicke den Knoten an, der in Runde 5 abgeschlossen (endgültig gemacht) wird; A selbst ist Runde 1.
Was bewirkt ROLLBACK TO SAVEPOINT s1?
Eine korrelierte Unterabfrage ist eine Unterabfrage, die:
Wie lautet die Netzadresse des Hosts 192.168.10.77/26?
Warum warnt ein Browser, wenn eine Website ein selbstsigniertes Zertifikat vorlegt?
Das Netz 10.140.255.0/24 wird in gleich große Subnetze mit dem Präfix /30 aufgeteilt. Wie viele Subnetze N gibt es?
Ein Host hat die Adresse 172.20.33.227/17. Wie lautet das dritte Oktett x der Broadcastadresse seines Subnetzes?
Antwort: N = −61
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: R = 126
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.
OR ergibt dort 1, wo mindestens ein Bit 1 ist.
Antwort: (q ∨ p) ∧ ¬¬r
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).
Führt die Annahme zu einem Widerspruch, muss die Implikation wahr sein.
Antwort: ∃x (¬A(x) ∧ ¬B(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 = 9
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 = 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 T-Flipflop kippt bei jeder steigenden Flanke mit T = 1 und hält bei T = 0.
Antwort: 68−1 mod 89 = 72
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·68 (mod 89) geschrieben.
Antwort: N = 4
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: D · Ω(n log n)
Jedes vergleichsbasierte Sortierverfahren benötigt im Worst Case mindestens log₂(n!) ≈ n log n Vergleiche. Countingsort unterbietet dies, weil es keine Vergleiche durchführt.
Antwort: B · X liegt in NP, und ein bekanntes NP-vollständiges Problem lässt sich in polynomieller Zeit auf X reduzieren
Die Zugehörigkeit zu NP zeigt, dass X nicht schwerer als NP ist; die Reduktion von einem bekannten NP-vollständigen Problem zeigt, dass X mindestens so schwer ist wie ganz NP.
Antwort: B · Eine Warteschlange fester Größe
Ein Ringpuffer verwendet Head- und Tail-Indizes, die umlaufen, und ermöglicht so enqueue und dequeue in O(1) bei festem Speicher.
Antwort: B · Eine einfache Rechtsrotation am unbalancierten Knoten
Im Links-links-Fall hebt eine Rechtsrotation das linke Kind nach oben und stellt die Balance wieder her; Zickzack-Fälle brauchen eine Doppelrotation.
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: E
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 · Es macht die nach dem Savepoint s1 vorgenommenen Änderungen rückgängig und lässt die Transaktion offen
Ein Savepoint markiert einen Punkt innerhalb einer Transaktion; ein Rollback dorthin verwirft spätere Arbeit, während frühere Änderungen bis zum COMMIT ausstehend bleiben.
Antwort: D · Auf Spalten der äußeren Abfrage verweist und für jede äußere Zeile ausgewertet wird
Korrelierte Unterabfragen hängen von der aktuellen äußeren Zeile ab und werden daher logisch pro Zeile ausgewertet (Optimierer können sie in Joins umschreiben).
Antwort: B · 192.168.10.64
/26-Subnetze beginnen bei 0, 64, 128 und 192. 77 liegt im Block 64–127, also ist die Netzadresse 192.168.10.64.
Antwort: A · Keine vertrauenswürdige Zertifizierungsstelle bestätigt, dass der Schlüssel zu dieser Website gehört
Browser vertrauen Zertifikaten, die direkt oder über eine Kette von CAs in ihrem Truststore signiert sind. Ein selbstsigniertes Zertifikat könnte jeder erstellen, etwa ein Man-in-the-Middle.
Antwort: N = 64
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).
Jedes /30-Subnetz hat 22 − 2 = 2 nutzbare Hosts.
Antwort: x = 127
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