Formelsammlungen, die wichtigsten Lösungsschritte zu jedem Thema und 20 Übungsaufgaben, mit vollständigen Lösungen am Ende.
Schreibe −102 als 8-Bit-Muster im Zweierkomplement. Lies das Muster als vorzeichenlose Binärzahl: Welchen Wert U hat es im Dezimalsystem?
Was ist die größte vorzeichenlose ganze Zahl N, die in 16 Bits passt?
Welche Formel ist logisch äquivalent zu (b ∨ c) → a? Klicke sie an.
Das Argument mit den Prämissen q → (r ∨ p); q und der Konklusion r ist ungültig. Klicke die Zeile der Wahrheitstafel an, die ein Gegenbeispiel ist.
Bestimme mit dem Karnaugh-Diagramm das minimale Produkt von Summen (POS) von F(A, B, C, D) = Σm(0, 2, 3, 9, 11, 12, 14, 15). Wie viele Summenterme (Faktoren) N hat es?
Bestimme die minimale SOP-Form von F(A, B, C, D) = Σm(3, 5, 8, 11) + d(0, 7, 12, 13), wobei d die Don’t-Care-Bedingungen kennzeichnet. Wie viele Literale L enthält sie?
Bestimme die kleinste positive ganze Zahl x mit x ≡ 1 (mod 5) und x ≡ 2 (mod 6).
Bestimme 90175 mod 97 durch wiederholtes Quadrieren.
Was bedeutet es, dass ein Problem optimale Teilstruktur hat?
Worin unterscheidet sich ein unentscheidbares Problem von einem praktisch unlösbaren (intractable)?
Wie lange dauert es, mit einer Adjazenzmatrix zu prüfen, ob die Kante (u, v) existiert?
Warum kann man Elemente aus einem Standard-Bloom-Filter nicht einfach durch Löschen ihrer Bits entfernen?
Ein Baum hat 4 Knoten vom Grad 4, 3 Knoten vom Grad 5, 2 Knoten vom Grad 2, und alle seine anderen Knoten sind Blätter (Grad 1). Wie viele Blätter L hat er?
Bestimme mit dem Dijkstra-Algorithmus die Länge d(F) des kürzesten Weges von A nach F im gewichteten Graphen.
Was liefert SELECT COALESCE(phone, 'unknown') FROM customers für einen Kunden, dessen phone NULL ist?
x ist NULL und y = 1. Welchen Wert hat die Bedingung (x > 5 OR y = 1)?
Wie lange dauert es, ein 1500-Byte-Paket auf eine 12-Mbit/s-Verbindung zu legen (Sendeverzögerung)?
Ein Angreifer in einem LAN sendet gefälschte ARP-Antworten, die die IP-Adresse des Gateways beanspruchen. Was ist die wahrscheinliche Folge?
Das Netz 192.168.10.0/24 soll in mindestens 12 gleich große Subnetze aufgeteilt werden. Wenn du so wenige Bits wie möglich leihst, wie viele nutzbare Hosts H hat jedes Subnetz?
Das Netz 192.168.247.0/24 wird mit VLSM für diese LANs aufgeteilt: A: 8 Hosts, B: 56 Hosts, C: 29 Hosts, D: 48 Hosts. Die Subnetze werden ab .0 aufwärts vergeben, das LAN mit den meisten Hosts zuerst, jedes mit dem kleinsten passenden Subnetz. Wie lautet das vierte Oktett x der Netzadresse von LAN C?
Antwort: U = 154
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 = 65535
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: (b → a) ∧ (c → a)
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: 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 = 4
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: 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.
Die größten Gruppen, die sich aus Einsen und X bilden lassen.
Es gibt eine weitere Gruppierung derselben Größe; sie hat dieselbe Anzahl von Termen und Literalen.
Antwort: x = 26
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: 90175 mod 97 = 5
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 · Eine optimale Lösung lässt sich aus optimalen Lösungen seiner Teilprobleme zusammensetzen
Optimale Teilstruktur ist sowohl für Greedy-Algorithmen als auch für dynamische Programmierung nötig, damit sie korrekte Ergebnisse liefern.
Antwort: D · Ein unentscheidbares Problem hat keinen Algorithmus für alle Eingaben; ein praktisch unlösbares hat einen, der aber zu langsam ist
Für das Halteproblem gibt es überhaupt keinen Algorithmus; ein NP-schweres Problem wie das TSP lässt sich per Brute Force lösen, nur nicht in bekannter polynomieller Zeit.
Antwort: C · O(1)
Der Matrixeintrag in Zeile u, Spalte v zeigt sofort, ob die Kante existiert; eine Adjazenzliste muss eventuell die Nachbarn von u durchsuchen.
Antwort: A · Diese Bits können auch zu anderen Elementen gehören, was falsch-negative Ergebnisse verursachen würde
Das Löschen eines geteilten Bits würde ein anderes Element als fehlend erscheinen lassen; zählende Bloom-Filter verwenden Zähler statt Bits, um Löschen zu ermöglichen.
Antwort: L = 19
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: d(F) = 25
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: D · 'unknown'
COALESCE prüft seine Argumente von links nach rechts und liefert das erste, das nicht NULL ist, hier 'unknown'.
Antwort: A · 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: C · 1 ms
1500 Byte = 12,000 Bit. 12,000 / 12,000,000 Bit/s = 0,001 s = 1 ms. Die Sendeverzögerung hängt von Paketgröße und Datenrate ab, nicht von der Entfernung.
Antwort: A · Opfer senden den Verkehr für das Gateway an den Angreifer, was einen Man-in-the-Middle-Angriff ermöglicht
ARP-Spoofing vergiftet die ARP-Caches der Hosts mit der MAC des Angreifers für die Gateway-IP. Der Angreifer kann dann Verkehr mitlesen, verändern oder verwerfen; Dynamic ARP Inspection hilft dagegen.
Antwort: H = 14
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 = 128
VLSM: Jedes LAN erhält das kleinste Subnetz mit 2ʰ − 2 ≥ seiner Hostzahl, also das Präfix 32 − h. Vergibt man die größten Subnetze zuerst, liegt jeder Block auf einem Vielfachen seiner eigenen Größe, und die Netzadressen ergeben sich durch Addieren der Blockgrößen.
LAN C: 192.168.247.128/27.
ExamProblems · examproblems.com/courses/computer-science-fundamentals