Formelsammlungen, die wichtigsten Lösungsschritte zu jedem Thema und 20 Übungsaufgaben, mit vollständigen Lösungen am Ende.
Setze die Bits so, dass sie −25 im 8-Bit-Zweierkomplement speichern. Welchen Wert U hat das Muster, wenn man es als vorzeichenlose Zahl liest?
Setze die Bits auf das 8-Bit-Ergebnis von 1010 1001 << 2. Welchen Wert R hat das Ergebnis dezimal?
Welche Formel ist logisch äquivalent zu (q ∧ p) → r? Klicke sie an.
Wie viele der 16 Zeilen der Wahrheitstafel machen ¬((¬d ∧ c) ∧ (a → ¬b)) ↔ ¬(c ∨ (a ∧ b)) wahr? Nenne diese Zahl N.
Vereinfache F = AB′C + AB′C′ + ABC′ + A′B zur minimalen Summe von Produkten. Wie viele Literale L enthält der vereinfachte Ausdruck?
Ein flankengesteuertes JK-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?
Löse 8x ≡ 13 (mod 35). Gib die Lösung x mit 0 < x < 35 an.
Ein RSA-Schlüssel verwendet die Primzahlen p = 17 und q = 29 und den öffentlichen Exponenten e = 3. Bestimme den privaten Exponenten d (0 < d < φ(n)).
Wie baut der Algorithmus von Prim einen minimalen Spannbaum auf?
Was ist die Lösung der Rekursionsgleichung T(n) = 2T(n/2) + n log n?
Wie wird in einer zirkulären Queue, die in einem Array der Kapazität n gespeichert ist, die nächste Position nach Index i berechnet?
Welches Problem des linearen Sondierens verringert Double Hashing vor allem?
Ein zusammenhängender Graph hat 11 Knoten und 12 Kanten. Wie viele Kanten k müssen entfernt werden, damit ein aufspannender Baum übrig bleibt?
Wie viele geschlossene Wege der Länge 2 beginnen und enden bei A? Ein Weg darf Knoten und Kanten wiederholen. Nenne die Zahl N.
Ein LEFT JOIN liefert:
Es gibt einen zusammengesetzten Index auf (last_name, first_name). Welche Bedingung kann ihn am wirksamsten nutzen?
Warum wird UDP bei Live-Videoanrufen oft bevorzugt?
Die Stationen A und C erreichen beide den Access Point B, hören sich aber gegenseitig nicht, sodass ihre Rahmen bei B kollidieren. Wie hilft 802,11?
Eine Abteilung braucht 220 Hostadressen in einem einzigen Subnetz. Welche ist die längste Präfixlänge p (kleinstes Subnetz), die groß genug ist?
Ein Host hat die Adresse 10.20.233.162/28. Welches ist das vierte Oktett x seiner Netzadresse?
Antwort: U = 231
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.
Antwort: R = 164
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.
Das Linksschieben um 2 verschiebt jedes Bit um 2 Stellen nach links; Bits, die am linken Ende herausfallen, gehen verloren, und rechts kommen Nullen nach.
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).
Die Spalten nach dem Strich sind die Optionen in der angezeigten Reihenfolge.
Antwort: N = 9
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: L = 6
Boolesche Algebra: Die Regeln, die Ausdrücke vereinfachen, sind X + X′ = 1 und X·X′ = 0, X + X = X, die Absorption X + X·Y = X, die Zusammenfassungsregel X·Y + X·Y′ = X, X + X′Y = X + Y und das Konsensus-Theorem XY + X′Z + YZ = XY + X′Z. Die De-Morganschen Gesetze machen aus (X·Y)′ den Ausdruck X′ + Y′ und aus (X + Y)′ den Ausdruck X′·Y′. Ein Karnaugh-Diagramm wendet diese Regeln grafisch an: Jede Gruppe aus zwei benachbarten Feldern ist eine Anwendung von XY + XY′ = X.
Es gibt eine weitere Gruppierung derselben Größe; sie hat dieselbe Anzahl von Literalen.
Antwort: N = 4
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: x = 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).
Antwort: d = 299
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: B · Er lässt einen Baum von einem Startknoten aus wachsen und fügt die günstigste Kante hinzu, die den Baum verlässt
Der Algorithmus von Prim läuft mit einer Prioritätswarteschlange der kreuzenden Kanten bei einem binären Heap in O(E log V).
Antwort: A · Θ(n log² n)
Ebene k leistet etwa n log(n / 2ᵏ) Arbeit, und die Summe über log n Ebenen ergibt Θ(n log² n), den erweiterten zweiten Fall des Master-Theorems.
Antwort: B · (i + 1) mod n
Die Modulo-Operation lässt Index n − 1 wieder auf 0 umlaufen, sodass das Array ohne Verschieben von Elementen wiederverwendet wird.
Antwort: C · Primäre Clusterbildung, bei der lange Folgen belegter Plätze entstehen
Lineares Sondieren geht in Schritten von 1, daher wachsen belegte Folgen und verschmelzen; Double Hashing nutzt einen zweiten Hash für die Schrittweite, sodass verschiedene Schlüssel verschiedene Folgen sondieren.
Antwort: k = 2
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: D · Alle Zeilen der linken Tabelle und die passenden Zeilen der rechten, mit NULLs, wo es keine Übereinstimmung gibt
Ein Left Outer Join behält jede linke Zeile; nicht zugeordnete Spalten der rechten Tabelle werden mit NULL gefüllt.
Antwort: B · WHERE last_name = 'Jansen'
Ein zusammengesetzter B-Baum-Index ist nach last_name und dann nach first_name geordnet, daher funktioniert eine Suche über die führende Spalte, first_name allein kann die Ordnung aber nicht nutzen.
Antwort: D · Geringe Verzögerung ist wichtiger als die Neuübertragung jedes verlorenen Pakets
Die Neuübertragung verlorener Pakete würde Verzögerung verursachen; Echtzeitmedien tolerieren etwas Verlust, daher werden UDP-basierte Protokolle wie RTP verwendet.
Antwort: D · Mit optionalem RTS/CTS-Austausch: Das CTS des AP sagt allen Stationen in der Nähe, dass sie warten sollen
Eine Station sendet Request to Send; der AP antwortet mit Clear to Send, das jede Station in seiner Reichweite hört, sodass verdeckte Stationen für die reservierte Zeit warten.
Antwort: p = 24
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 = 160
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