Notes in TI

To Subscribe, use this Key

Status	Last Update	Fields
Published	11/10/2024	Problem
Published	11/04/2024	Die 3 Grundstrukturen der Informatik
Published	11/04/2024	Definition von Alphabet
Published	11/04/2024	Definition von Wort
Published	11/04/2024	Definition der Verkettung (Konkatenation)
Published	11/04/2024	Definition der Umkehrung (Reversal)
Published	11/04/2024	Definition von Iteration
Published	11/04/2024	Was sind die Teile eines Wortes
Published	11/04/2024	Was ist die kanonische Ordnung von Wörtern
Published	11/04/2024	Definition von Sprache
Published	11/04/2024	Definition von Program [TI]
Published	11/04/2024	Definition eines Homomorphismus von Alphabeten
Published	11/04/2024	Definition des Entscheidungsproblems
Published	11/04/2024	Definition einer Funktion über endlich abgeschlossene Alphabete
Published	11/04/2024	Was bedeutet es ein Wort mit einem Algorithmus zu generieren?
Published	11/04/2024	Definition eines Aufzählungsalgorithmus
Published	11/10/2024	Definition eines Relationsproblems
Published	12/03/2024	Definition eines Optimierungsproblem
Published	11/04/2024	Definition der Shannon-Entropy
Published	11/04/2024	Definition der Kolmogorov-Komplexität
Published	11/10/2024	Upper-bound für $K(x)$
Published	11/04/2024	Definition der Kolmogorov-Komplexität einer natürlichen Zahl
Published	11/04/2024	Wie löst man das Entscheidungsproblem und für welche Sprachen geht das?
Published	11/04/2024	Definition von Algorithmus (Semi-Formal) [TI]
Published	11/04/2024	Was ist die Konkatenation von Sprachen?
Published	12/03/2024	Was ist $L^*$?
Published	11/04/2024	Wie wird ein Optimierungsproblem gelöst?
Published	12/03/2024	Wie können wir eine Sequenz natürlicher Zahlen komprimieren?
Published	11/04/2024	Definition eines endlichen Automaten (deterministisch).
Published	11/04/2024	Was ist eine Konfiguration von einem endlichen Automaten Quintupel $M$?
Published	12/03/2024	Was ist eine (akzeptierende/verwerfende) Berechnung eines $EA$?
Published	11/04/2024	Was ist eine reguläre Sprache?
Published	12/03/2024	Was ist die Bedeutung von $\vdash_M^*$?
Published	12/03/2024	Was ist die Bedeutung von $\hat\delta$?
Published	11/04/2024	Was ist $Kl[p]$?
Published	11/04/2024	Was kann mensch mit endlichen Automaten erkennen?
Published	12/03/2024	Wie verhalten sich Vereinigungen regulärer Sprachen?
Published	11/10/2024	Nenne die drei Varianten um Beweise der Nichtregularität zu führen.
Published	11/10/2024	Lemma 3.3
Published	11/10/2024	Pumping-Lemma für reguläre Sprachen
Published	11/04/2024	Nichtregularität mithilfe von Kolmogorov-Komplexität (Satz)
Published	11/04/2024	Wie konstruiert man einen EA $M$, der eine Mengenoperation $\odot(\cup,\cap, -)$ auf zwei andere EA's simuliert?
Published	11/04/2024	Was ist ein Nichtdeterministischer Endlicher Automat?
Published	11/04/2024	Was ist ein Schritt in einem $NEA$?
Published	11/04/2024	Wann gilt ein Wort als akzeptiert in einem $NEA$?
Published	11/10/2024	Was ist die von einem $NEA\ M$ akzeptierte Sprache $L$?
Published	11/04/2024	Was ist $\hat\delta$ für ein $NEA$?
Published	11/10/2024	Was ist die Definition der Turingmaschine
Published	11/10/2024	Was ist die Konfiguration einer Turingmaschine $M$?
Published	12/03/2024	Was ist ein Schritt einer Turingmaschine?
Published	11/10/2024	Was ist eine Berechnung (auf $x$) auf einer Turingmaschine?
Published	11/10/2024	Was sind Resultate von Berechnungen auf Turingmaschinen?
Published	11/10/2024	Was ist eine berechenbare Funktion?
Published	11/10/2024	Was ist eine von einer Turingmaschine $M$ akzeptierte Sprache?
Published	11/10/2024	Was ist die Klasse der rekursive aufzählbaren Sprachen?
Published	11/10/2024	Was ist die Klasse der rekursiven (entscheidbaren) Sprachen?
Published	11/10/2024	Was ist die Potenzmengenkonstruktion?
Published	11/10/2024	Nenne eine Sprache $L_k$ welche mindestens $2^k$ viele zustände haben muss.
Published	12/03/2024	Was ist eine Mehrband Turing Maschine der Grösse $k$? (informell)
Published	11/10/2024	Wann sind zwei $TM$ äquivalent?
Published	12/03/2024	Kann man eine $MTM$ zu einer $TM$ umwandeln?
Published	11/10/2024	Was sind die (4) Sprachmodelle, die wir kennen?
Published	11/22/2024	Wann sind zwei Maschinenmodelle (Maschinenklassen) $\mathcal{A}$ und $\mathcal{B}$ äquivalent?
Published	11/22/2024	Sind TM oder MTM aussagekräftiger?
Published	11/22/2024	Was sagt die Church'sche These aus?
Published	11/22/2024	Wie funktioniert ein NTM?
Published	11/22/2024	Was ist ein Berechnungsbaum?
Published	11/22/2024	Wie kann men eine NTM in eine TM umwandeln?
Published	12/03/2024	Was können wir über die Grössen der Menge der Wörter eines Alphabetes $\Sigma$ sagen?
Published	12/06/2024	Wie definieren wir $\|A\| \le \|B\|$, $\|A\|=\|B\|$ und $\|A\|<\|B\|$?
Published	12/03/2024	Wann ist eine Menge abzählbar?
Published	12/03/2024	Was können wir über die Grösse der Menge $KodTM$ der Turingmaschinenkodierungen sagen?
Published	12/03/2024	Was können wir über die Grösse von $(\mathbb{N}-\{0\})\times (\mathbb{N}-\{0\})$ sagen, und wie können wir das zeigen?
Published	12/03/2024	Was können wir über die Grösse von $[0,1]$ sagen?
Published	12/03/2024	Was können wir über die Grösse von $\mathcal{P}((\Sigma_\text{bool})^*)$ sagen und wie können wir das zeigen?
Published	12/03/2024	Was ist die Menge $KodTM$?
Published	12/03/2024	Wie definieren wir die Kodierung der $i$-ten TM?
Published	12/03/2024	Können wir die TM $M_i$ generieren?
Published	12/03/2024	Wie zeigen wir, dass es unendlich viele nicht rekursive Sprachen gibt?
Published	12/03/2024	Wie ist die Diagonalsprache definiert?
Published	12/03/2024	Was giltet für $L_\text{diag}?$
Published	12/03/2024	Was sagt uns $(L_\text{diag})^C$ über $\mathcal{L}_R$und $\mathcal{L}_{RE}$ aus?
Published	12/03/2024	Definition der universellen Sprache
Published	12/03/2024	Was können wir über $L_U$ sagen?
Published	12/06/2024	Definition des Halteproblems
Published	12/06/2024	Was können wir über $L_H$ sagen?
Published	12/03/2024	Definition einer R-Reduktion
Published	12/03/2024	Definition einer EE-Reduktion
Published	12/03/2024	Was sind die Relationen zwischen den Verschiedenen Reduktionen?
Published	12/03/2024	Was giltet für das Komplement einer Sprache im Bezug auf die R-Reduktion?
Published	12/06/2024	Was ist die Definition von $L_\text{empty}$ und was können wir über die Sprache und ihr Komplement sagen?
Published	12/03/2024	Können wir generell entscheiden ob zwei TM die gleiche Sprache haben?
Published	12/03/2024	Was ist ein semantisch nichttriviales Entscheidungsproblem?
Published	12/03/2024	Was ist der Satz von Rice?
Published	12/06/2024	Was ist die Speicherplatzkomplexität einer Berechnung $C$?
Published	12/06/2024	Was ist die Speicherplatzkomplexität von $M$ auf $x$?
Published	12/06/2024	Was ist die Speicherplatzkomplexität einer TM $M$?
Published	12/06/2024	Was ist die Zeitkomplexität einer TM $M$ und die Zeitkomplexität der Berechnung von $M$ auf $x$?
Status	Last Update	Fields