Informatik
Formale Sprachen
Was eine formale Sprache, ein Alphabet und ein Wort sind. Grundbegriffe der Theorie der formalen Sprachen, erklärt im Vergleich mit der Alltagssprache und an Beispielen.
Endliche Automaten
Der endliche Automat als Rechenmodell mit Zuständen und Übergängen. Definition, Zustandsdiagramm, Formalisierung der Berechnung und Beispiele akzeptierter Wörter.
Reduktion endlicher Automaten
Unerreichbare Zustände eines endlichen Automaten, in die man vom Startzustand aus nicht gelangen kann. Definition und Vorgehen, wie man sie sicher aus dem Automaten entfernt.
Abgeschlossenheit regulärer Sprachen
Reguläre Sprachen sind abgeschlossen unter Vereinigung, Schnitt, Konkatenation und Kleene-Stern. Was Abgeschlossenheit unter einer Operation bedeutet und warum sie für reguläre Sprachen gilt.
Reguläre Ausdrücke
Was ein regulärer Ausdruck ist und wie er eine Menge von Wörtern beschreibt. Definition, Vergleich mit arithmetischen Termen und Zusammenhang mit endlichen Automaten.
Schätzung eindeutiger Werte
Linear Counting: Wie du die Anzahl eindeutiger Werte in großen Datenmengen schätzt. Hashfunktionen, Bitmaps und warum der naive Ansatz nicht ausreicht.
Bloomfilter: Ist ein Element in der Menge enthalten?
Der Bloomfilter ist eine probabilistische Datenstruktur, die schnell beantwortet, ob ein Element in der Menge enthalten ist. Prinzip, Hashfunktionen und praktische Anwendung.
Caesar-Verschlüsselung
Wie die Caesar-Verschlüsselung funktioniert, eine der ältesten Methoden, Text zu verschlüsseln. Das Prinzip der Buchstabenverschiebung, die Verallgemeinerung des Verfahrens und ein Online-Werkzeug zum Verschlüsseln.
Vigenère-Chiffre
Die Vigenère-Chiffre verwendet mehrere Alphabete und widersteht deshalb der Häufigkeitsanalyse. Das Prinzip der Verschlüsselung, das Vigenère-Quadrat, die Wahl des Schlüssels und ein Online-Werkzeug.
