Theoretische Informatik
B1 1. Sem.
B1 1. Sem.
\(2^{11}\)
2048
Was ist ein Algorithmus?
Was bedeutet ein rekursiver Aufruf einer Funktion?
Bei der rekursiven Programmierung ruft sich eine Prozedur, Funktion oder Methode in einem Computerprogramm selbst wieder auf. Auch der gegenseitige Aufruf stellt eine Rekursion dar.
Wichtig bei der rekursiven Programmierung ist eine Abbruchbedingung in dieser Funktion, weil sich das rekursive Programm sonst (theoretisch) unendlich oft selbst aufrufen würde.
Was ist eine Menge?
Unter einer Menge verstehen wir jede Zusammenfassung M von bestimmten wohl unterschiedenen Objekten unserer Anschauungen oder unseres Denkens (welche die Elemente von M genannt werden) zu einem Ganzen.
Wie lassen sich Mengen beschreiben?
Mengen lassen sich
aufzählend/deskriptiv
beschreiben.
Was besagt die Axiomatisierung von ℕ / Peano-Axiome?
Zahl 0
- 1
- 2
- 3
natürliche Zahlen
- 1
- 2
Zahl 0
- 0 ist eine natürliche Zahl: 0EN
- 0 ist kein Nachfolger einer natürlichen Zahl
- Enthält eine Teilmenge M von N die Zahl 0 und zu jedem Element n auch den Nachfolger, so gilt M = N
Natürliche Zahlen
- Jede natürliche Zahl n hat genau einen Nachfolger: nEN -> succ(n) E N
- Die Nachfolger zweier verschiedener natürlicher Zahlen sind auch verschieden.
Was entsteht bei einer Relation?
Es entsteht ein Wahrheitswert
Was entsteht bei einer Operation?
Eine neue Menge.
Wie ist die Abschlusseigenschaft ℕ definiert?
ℕ ist abgeschlossen bzgl. Addition u. Multiplikation, nicht aber bezüglich Subtraktion und Division.
Was bedeuten diese Zeichen?
echte Teilmengen
Teilmenge
Injektivität
s.u.
Surjektivität
Alle Elemente der Zielmenge werden getroffen.
Bijektivität
s.u.
Definition: Mächtigkeit
Mit M1 und M2 seien zwei beliebige Mengen gegeben.
M1 und M2 heißen gleichmächtig, geschrieben als
|M1| = |M2|
wenn eine bijektive Abbildung f: M1 → M2 existiert.
Wir schreiben |M1| \(\leq\) |M2|
wenn eine injektive Abbildung f: M1 → M2 existiert.
Abzählbarkeit, Überabzählbarkeit
Eine Menge M heißt
– abzählbar unendlich, falls |M| = |\(\mathbb{N}\)|
– höchstens abzählbar, falls |M| ≤ |\(\mathbb{N}\)|
– überabzählbar unendlich, falls |M|>|\(\mathbb{N}\)|
Satz von Cantor
Für jede Menge M ist die Potenzmenge 2M mächtiger
als M selbst.
Relation
s.u.
transitiv
s.u.
-
- 1 / 18
-
Flashcards
\(2^{11}\)
2048
Was ist ein Algorithmus?
Was bedeutet ein rekursiver Aufruf einer Funktion?
Bei der rekursiven Programmierung ruft sich eine Prozedur, Funktion oder Methode in einem Computerprogramm selbst wieder auf. Auch der gegenseitige Aufruf stellt eine Rekursion dar.
Wichtig bei der rekursiven Programmierung ist eine Abbruchbedingung in dieser Funktion, weil sich das rekursive Programm sonst (theoretisch) unendlich oft selbst aufrufen würde.
Was ist eine Menge?
Unter einer Menge verstehen wir jede Zusammenfassung M von bestimmten wohl unterschiedenen Objekten unserer Anschauungen oder unseres Denkens (welche die Elemente von M genannt werden) zu einem Ganzen.
Wie lassen sich Mengen beschreiben?
Mengen lassen sich
aufzählend/deskriptiv
beschreiben.
Was besagt die Axiomatisierung von ℕ / Peano-Axiome?
Zahl 0
- 1
- 2
- 3
natürliche Zahlen
- 1
- 2
Zahl 0
- 0 ist eine natürliche Zahl: 0EN
- 0 ist kein Nachfolger einer natürlichen Zahl
- Enthält eine Teilmenge M von N die Zahl 0 und zu jedem Element n auch den Nachfolger, so gilt M = N
Natürliche Zahlen
- Jede natürliche Zahl n hat genau einen Nachfolger: nEN -> succ(n) E N
- Die Nachfolger zweier verschiedener natürlicher Zahlen sind auch verschieden.
Was entsteht bei einer Relation?
Es entsteht ein Wahrheitswert
Was entsteht bei einer Operation?
Eine neue Menge.
Wie ist die Abschlusseigenschaft ℕ definiert?
ℕ ist abgeschlossen bzgl. Addition u. Multiplikation, nicht aber bezüglich Subtraktion und Division.
Was bedeuten diese Zeichen?
echte Teilmengen
Teilmenge
Injektivität
s.u.
Surjektivität
Alle Elemente der Zielmenge werden getroffen.
Bijektivität
s.u.
Definition: Mächtigkeit
Mit M1 und M2 seien zwei beliebige Mengen gegeben.
M1 und M2 heißen gleichmächtig, geschrieben als
|M1| = |M2|
wenn eine bijektive Abbildung f: M1 → M2 existiert.
Wir schreiben |M1| \(\leq\) |M2|
wenn eine injektive Abbildung f: M1 → M2 existiert.
Abzählbarkeit, Überabzählbarkeit
Eine Menge M heißt
– abzählbar unendlich, falls |M| = |\(\mathbb{N}\)|
– höchstens abzählbar, falls |M| ≤ |\(\mathbb{N}\)|
– überabzählbar unendlich, falls |M|>|\(\mathbb{N}\)|
Satz von Cantor
Für jede Menge M ist die Potenzmenge 2M mächtiger
als M selbst.
Relation
s.u.
transitiv
s.u.
