Arbeiten, die während meines Studiums entstanden:
- Studienarbeit "Der minimale euklidische Algorithmus im Ring der ganzen Gaußschen Zahlen"
- Seminararbeit "Parsing natürlicher Sprache"
- Diplomarbeit "Die Pell'sche Gleichung über Funktionenkörpern"
Vorlesungsskript, aktuelle Version: 25.08.2004
Inhalt:
- Endliche Automaten
- Formale Sprachen
- Reguläre Sprachen und endliche Automaten
- Kontextfreie Sprachen
Graphentheorie
Vorlesungsskript, aktuelle Version: 19.10.2004
Inhalt:
- Graphen: Definition, Kantenzüge und Zusammenhangskomponenten
- Bäume
- Algorithmen: Breitensuche, topologische Anordnung, Netzwerke
Berechenbarkeit
Vorlesungsskript, aktuelle Version: 30.03.2004
Inhalt:
- Abstrakte Maschinen
- LOOP- und WHILE-Berechenbarkeit
- Partiell-rekursive und primitiv rekursive Funktionen
- Rekursive, semirekursive und rekursiv aufzählbare Relationen
- Grundlagen der Komplexitätstheorie
Automatisches Beweisen
Vorlesungsskript, aktuelle Version: 08.12.2004
Inhalt:
- Aussagenlogik (Sequenzenkalkül, Tableaux, Resolution, Davis-Putnam-Verfahren)
- Prädikatenlogik
- Sequenzenkalkül
- Resolution
- Logikprogrammierung
Studienarbeit "Der minimale euklidische Algorithmus im Ring der ganzen Gaußschen Zahlen"
Ein Ring R heißt euklidischer Ring, falls eine Abbildung g von R in die natürlichen Zahlen existiert, so dass es für je zwei Elemente x, y aus R (y verschieden von 0) Elemente q, r aus R gibt mit x=qy+r, wobei entweder r=0 oder g(r) < g(y) ist.
Die Abbildung g heißt dabei euklidischer Algorithmus (euklidische Normfunktion).
Es lässt sich zeigen, dass jeder euklidische Ring einen minimalen euklidischen Algorithmus besitzt.
In dieser Studienarbeit wird am Beispiel des Ringes der ganzen Gaußschen Zahlen ein Verfahren zur Konstruktion des minimalen euklidischen Algorithmus vorgestellt und implementiert.
Download der kompletten Studienarbeit (PDF-Datei, 360 kb)
Download der Implementierung (ausführbare JAR-Datei, 30 kb)
Für das Ausführen des Programmes ist eine installierte JAVA-Runtime in einer Version >=1.4 notwendig, erhältlich bei http://java.sun.com/.
Seminararbeit "Parsing natürlicher Sprache"
In der Seminararbeit wird ein grober Überblick über das Gebiet des Parsings natürlicher Sprache gegeben. Im ersten Teil werden einige Möglichkeiten der formalen Repräsentation natürlicher Sprache erörtert, im zweiten Teil werden Algorithmen zum Parsing natürlicher Sprache besprochen. Die Arbeit schließt mit der kurzen Vorstellung zweier existierender Systeme zur Zerlegung natürlichsprachlicher Sätze in ihre syntaktischen Bestandteile.
Download der kompletten Seminararbeit (PDF-Datei, 285 kb)
Diplomarbeit "Die Pell'sche Gleichung über Funktionenkörpern"
Schon seit langer Zeit ist in der Mathematik die sogenannte Pell'sche Gleichung bekannt; für eine natürliche Zahl d, die kein Quadrat ist, sucht man nach ganzzahligen Lösungen x, y der Gleichung x^2-dy^2=1.
Die Pell'sche Gleichung im Zahlkörperfall ist gut untersucht, die gebräuchlichste Lösungsmethode verwendet Kettenbruchentwicklungen.
In der Diplomarbeit wird jedoch die Pell'sche Gleichung über Funktionenkörpern untersucht. Dabei betrachtet man die Gleichung
A^2 - MB^2 = 1, wobei M ein Polynom über einem endlichen Körper K von ungerader Charakteristik ist und sucht Polynome A und B aus K[X], welche die Gleichung erfüllen.
Es wird gezeigt, dass die Gleichung für nichtquadratische, normierte Polynome M von geradem Grad stets unendlich viele nichttriviale Lösungen besitzt, die sich - analog zum Zahlkörperfall - durch Kettenbruchentwicklungen gewinnen lassen.
Download der kompletten Diplomarbeit (PDF-Datei, 455 kb)
Download der Implementierung in KANT/KASH (17 kb)
Anleitung zur KANT-Implementierung (ASCII, 6 kb)
Download der Implementierung in PARI-GP (15 kb)
Anleitung zur PARI-Implementierung (ASCII, 5 kb)
Für die Benutzung der Implementierung ist entweder das Algebra-Paket KANT mit interaktivem Interpreter KASH (http://www.math.tu-berlin.de/~kant/) oder das Algebra-System PARI mit Interpreter GP ( http://pari.math.u-bordeaux.fr/) notwendig, beide sind frei verfügbar.