INF-Modell - Boolesche Logik, UML und Modellierung — Informatik · Matura-Zusammenfassung

Boolesche Algebra und Schaltnetze#

StandardINF-Modell-1.1

Die gesamte digitale Technik beruht auf boolescher Algebra - dem Rechnen mit den zwei Werten 0 und 1. Sie ist die Mathematik hinter jedem Logikgatter und damit hinter jeder CPU.

Die Grundoperatoren sind AND (

\land

, nur 1, wenn beide 1), OR (

\lor

, 1 bei mindestens einer 1) und NOT (

\lnot

, kippt den Wert); dazu XOR (

\oplus

, 1 genau bei Ungleichheit) sowie NAND und NOR (negiertes AND/OR). Ihr Verhalten hält man in Wahrheitstafeln fest ().

Wahrheitstafel der Grundoperatoren

Abb. 1AND ist nur bei zwei Einsen wahr, OR bei mindestens einer, XOR genau bei Ungleichheit.

Wichtigstes Rechengesetz sind die De-Morgan-Regeln

\lnot(A \land B) = \lnot A \lor \lnot B

und

\lnot(A \lor B) = \lnot A \land \lnot B

: Eine Negation „zieht" über die Klammer und tauscht dabei AND und OR. Ausdrücke vereinfacht man algebraisch (mit solchen Gesetzen) oder visuell mit Karnaugh-Diagrammen (siehe Beispiel).

Bemerkenswert: NAND (ebenso NOR) ist funktional vollständig - allein damit lässt sich jede boolesche Funktion bauen (

\lnot A

= NAND mit gleichen Eingängen, daraus AND und OR). Deshalb fertigt man Chips oft einheitlich aus NAND-Gattern.

Aus Gattern baut man Schaltungen zweier Arten: Schaltnetze (kombinatorisch) berechnen ihre Ausgabe nur aus der aktuellen Eingabe, ohne Gedächtnis - etwa der Halbaddierer (Summe

= A \oplus B

, Übertrag

= A \land B

), Volladdierer oder Multiplexer.

Schaltwerke (sequenziell) besitzen dagegen Zustand über Flip-Flops (Register, Zähler) und sind die Grundlage von Speicher und CPU. Häufige Fehler: XOR und OR verwechseln (XOR ist bei „beide 1" gerade 0), bei De Morgan Klammern/Operatoren falsch verteilen, oder Schaltnetz (ohne Gedächtnis) und Schaltwerk (mit Zustand) gleichsetzen.

\lnot(A \land B) = \lnot A \lor \lnot B,\quad \lnot(A \lor B) = \lnot A \land \lnot B

De Morgan

Musterbeispiel

Wahrheitstafel und Vereinfachung

Erstelle die Wahrheitstafel für $f = (A \land \lnot B) \lor (A \land B)$ und vereinfache.

Wahrheitstafel
| A | B | $\lnot B$ | $A \land \lnot B$ | $A \land B$ | f | |---|---|---|---|---|---| | 0 | 0 | 1 | 0 | 0 | 0 | | 0 | 1 | 0 | 0 | 0 | 0 | | 1 | 0 | 1 | 1 | 0 | 1 | | 1 | 1 | 0 | 0 | 1 | 1 |
Algebraisch vereinfachen
$f = A \land (\lnot B \lor B) = A \land 1 = A$ .
Begründung
Komplement-Gesetz: $\lnot B \lor B = 1$ ; Neutralität: $A \land 1 = A$ .

Ergebnis: Die Funktion ist äquivalent zu $f = A$ - der B-Anteil hebt sich auf.

Schritt-für-Schritt Erklärung3 Schritte

1
Boolesche Algebra ist die Mathematik hinter jeder CPU.
2
NAND-Gatter können ganze Computer bauen - das nennt man funktionale Vollständigkeit.
3
De Morgan ist deine Lieblingsregel für Negation komplexer Ausdrücke.

SRDP-Aufgaben

SelbsttestAus der Fragenbank7 Punkte

Aufgabenstellung

Erstelle die Wahrheitstafel der Funktion

f = (A \lor B) \land \lnot(A \land B)

. Wofür steht diese Funktion?

Deine Antwortwird nicht automatisch bewertet

Typische Fehler

XOR und OR verwechselt.
De Morgan: Klammern werden vergessen, Vorzeichen falsch verteilt.
Schaltnetz und Schaltwerk gleichgesetzt.

Aktive Wiederholung

Erstelle die Wahrheitstafel für einen Halbaddierer (Eingänge A, B; Ausgänge Summe S, Übertrag C). Welche Gatter braucht er?

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Quellen: Patterson, Hennessy: Computer Organization and Design (Morgan Kaufmann)

UML-Diagramme - Klassen, Sequenz, Use Case#

StandardINF-Modell-2.1

MVC vs. MVVM Architekturmuster

Abb. 2MVC: Controller vermittelt; MVVM: ViewModel mit Datenbindung an View.

Bevor man komplexe Software schreibt, modelliert man sie. Die UML (Unified Modeling Language) ist die standardisierte grafische Sprache dafür - mit über einem Dutzend Diagrammtypen, die Struktur und Verhalten eines Systems zeigen.

Das Klassendiagramm ist der wichtigste Strukturtyp: Es zeigt Klassen (mit Attributen und Methoden) und ihre Beziehungen - Vererbung, Assoziation, Aggregation und Komposition - samt Multiplizitäten (siehe Beispiel). Es ist die Brücke vom Entwurf zur objektorientierten Implementierung.

Die Notation muss man sicher lesen: ein Dreieckspfeil zeigt Vererbung (is-a), eine leere Raute eine Aggregation (lose „hat ein", Teile leben unabhängig weiter), eine gefüllte Raute eine Komposition (existenziell „besteht aus", Teile sterben mit dem Ganzen) und ein gestrichelter Pfeil eine Abhängigkeit. Aggregation und Komposition zu verwechseln ist der klassische Fehler.

Für das Verhalten gibt es weitere Typen: Das Sequenzdiagramm zeigt die zeitliche Interaktion zwischen Objekten als Nachrichten entlang von Lebenslinien; das Use-Case-Diagramm stellt Akteure und ihre Anwendungsfälle dar (etwa Kunde → „Bestellung aufgeben") und dient der Verständigung mit Stakeholdern.

Das Aktivitätsdiagramm beschreibt Workflows mit Verzweigungen und Parallelität (ähnlich einem Flowchart), das Zustandsdiagramm die Zustände eines Objekts und ihre Übergänge. So deckt UML den ganzen Bogen von der Struktur bis zur Dynamik ab.

Häufige Fehler: Aggregation (lose) und Komposition (existenziell) vermischen, Pfeilrichtungen vertauschen, oder die Multiplizitäten (z. B. 1 — 0..n) vergessen, ohne die ein Klassendiagramm unvollständig ist.

Musterbeispiel

Klassendiagramm für eine Bibliothek

Modelliere ein UML-Klassendiagramm für Buch, Schüler und Ausleihe mit passenden Beziehungen und Multiplizitäten.

Klassen finden
Die Substantive der Anforderung werden zu Klassen: Buch(bNr, titel, autor), Schüler(sNr, name), Ausleihe(datum, rueckgabe).
Attribute und Methoden
Jede Klasse erhält ihre Attribute; Schüler etwa die Methode ausleihen(buch).
Beziehung modellieren
Ein Schüler leiht viele Bücher, ein Buch wird nacheinander von vielen Schülern geliehen → eine n:m-Beziehung, realisiert über die Assoziationsklasse Ausleihe.
Multiplizitäten
Schüler „1" — „0..n" Ausleihe und Buch „1" — „0..n" Ausleihe; jede Ausleihe verweist auf genau einen Schüler und ein Buch.
Beziehungsart wählen
Hier eine Assoziation (keine Aggregation/Komposition), da Buch und Schüler unabhängig voneinander existieren.

Ergebnis: Drei Klassen mit der Assoziationsklasse Ausleihe und Multiplizitäten 1 — 0..n an beiden Enden. Aggregation („hat ein") und Komposition („besteht aus") wären unpassend, weil keine Lebenszyklus-Abhängigkeit besteht.

Schritt-für-Schritt Erklärung3 Schritte

1
UML ist die universelle Sprache für Softwarearchitektur.
2
Klassendiagramme zeigen Struktur, Sequenzdiagramme zeigen Dynamik - beide brauchst du im Designprozess.
3
Use Cases helfen, mit Stakeholdern über das System zu sprechen, ohne in Implementierung zu versinken.

SRDP-Aufgaben

SelbsttestAus der Fragenbank7 Punkte

Aufgabenstellung

Beschreibe die wichtigsten UML-Diagrammtypen. Modelliere für eine Bibliothek ein Klassendiagramm (Buch, Schüler, Ausleihe) mit Beziehungen.

Deine Antwortwird nicht automatisch bewertet

Typische Fehler

Aggregation (lose) und Komposition (existenziell) vermischt.
Pfeilrichtungen vertauscht.
Multiplizitäten nicht angegeben.

Aktive Wiederholung

Modelliere für ein Online-Shop-System ein Use-Case-Diagramm mit Akteuren Kunde, Admin und externem Bezahldienst. Welche Anwendungsfälle gibt es?

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Quellen: Fowler: UML Distilled, 3. Auflage (Addison-Wesley)

Pseudocode, Flowcharts und Programmverifikation#

BasisINF-Modell-3.1

Bevor man einen Algorithmus in einer konkreten Sprache codiert, beschreibt man ihn sprachunabhängig - in Pseudocode oder als Flowchart. So trennt man die Idee von syntaktischen Details und kann sie mit jedem teilen.

Pseudocode ist eine klar lesbare, halbformale Notation: Einrückung statt Klammern, gängige Konstrukte wie `if/then/else`, `while`, `for` und `return`, aber ohne sprachspezifischen Ballast (keine Semikolons, keine Typdeklarationen). Wichtig: präzise genug, dass die Übersetzung in echten Code eindeutig ist (siehe Beispiel).

Ein Flowchart (Programmablaufplan, DIN 66001 / ISO 5807) stellt denselben Ablauf grafisch dar (): Oval für Start/Ende, Rechteck für eine Operation, Raute für eine Entscheidung (mit ja/nein-Ausgängen) und Parallelogramm für Ein-/Ausgabe, verbunden durch Ablaufpfeile.

Flowchart-Symbole (ISO 5807)

Abb. 3Die genormten Symbole eines Programmablaufplans und ihre Bedeutung.

Für Korrektheitsbeweise ist die Schleifeninvariante das zentrale Werkzeug: eine Aussage, die vor und nach jeder Iteration gilt. Zeigt man Initialisierung (gilt zu Beginn), Erhalt (bleibt pro Durchlauf) und Terminierung (liefert am Ende das Gewünschte), ist die Schleife bewiesen korrekt (siehe Beispiel: Maximum-Suche).

Verifikation, Tests und Code Reviews ergänzen einander: Tests zeigen die Anwesenheit von Fehlern an Beispielen, eine formale Verifikation kann ihre Abwesenheit beweisen (aber nur bei begrenztem Umfang), Reviews fangen Verständnis- und Designfehler. Kein einzelnes Mittel genügt allein.

In der Prüfung lautet die Aufgabe oft „Pseudocode angeben + Trace + Komplexität". Häufige Fehler: Pseudocode zu sprachspezifisch (wie fertiges Python) schreiben, Flowchart-Symbole falsch verwenden (eine Operation in eine Raute setzen), oder die Schleifeninvariante mit der Schleifenbedingung verwechseln.

Musterbeispiel

Pseudocode + Invariante: Maximum in Liste

Finde das größte Element einer nicht-leeren Liste $a[0..n-1]$ .

Pseudocode
``` max := a[0] for i from 1 to n-1 do if a[i] > max then max := a[i] return max ```
Schleifeninvariante
Vor jedem Schleifendurchlauf gilt: `max` ist das größte Element von $a[0..i-1]$ .
Initialisierung
Vor $i=1$ : max = a[0] = größtes von a[0..0] - Invariante gilt.
Erhalt
In jedem Schritt wird max ggf. auf a[i] erhöht - Invariante bleibt.
Terminierung
Nach $i=n$ : max ist größtes von a[0..n-1] - Korrektheit folgt.

Ergebnis: Beweis über Schleifeninvariante zeigt: Algorithmus liefert tatsächlich das Maximum. Laufzeit $O(n)$ .

Schritt-für-Schritt Erklärung3 Schritte

1
Pseudocode ist die Lingua Franca der Algorithmen - sprachunabhaengig, aber präzise.
2
Schleifeninvarianten sind das Fundament jeder Korrektheitsuessage.
3
Flowcharts helfen, Kontrollflusss visuell zu prüfen - besonders bei verschachtelten Bedingungen.

SRDP-Aufgaben

SelbsttestAus der Fragenbank6 Punkte

Aufgabenstellung

Schreibe Pseudocode für den Algorithmus, der die Summe aller geraden Zahlen in einer Liste berechnet. Skizziere zusätzlich das Flowchart und gib die Laufzeit an.

Deine Antwortwird nicht automatisch bewertet

Typische Fehler

Pseudocode mit Python verwechselt (zu sprachspezifisch).
Flowchart-Symbole falsch verwendet (Operation in Raute).
Schleifeninvariante als Schleifenbedingung wiederholt.

Aktive Wiederholung

Schreibe Pseudocode für "Finde das Maximum in einer Liste". Notiere die Schleifeninvariante.

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Quellen: Knuth: TAOCP Volume 1 - Fundamental Algorithms (Addison-Wesley)