Arbeiten und Papers

Hier gibt es die Papers die ich so geschrieben habe, und zwar in chronologisch absteigender Reihenfolge.

Diese Liste wird nicht mehr upgedatet. Bitte hier schauen.

Implementierung und Visualisierung des Planar-Separator-Algorithmus

Dirk Achenbach, Thomas Pajor, Jonida Saqe

Im Rahmen des Praktikums „Algorithm Engineering“ im Wintersemester 2006/2007 an der Universität Karlsruhe haben wir den Algorithmus zum Planar-Separator-Theorem in Java implementiert und mit Hilfe von Java3D visualisiert. Das Planar-Separator-Theorem besagt, dass jeder planare Graph mit n≥5n \geq 5 Knoten durch Wegnahme einer Separatormenge, die weniger als 4⋅n4\cdot\sqrt{n} Knoten enthält, so in zwei nicht-zusammenhängende Komponenten zerteilt werden kann, dass jede höchstens 2n/32n/3 Knoten enthält. In dieser Ausarbeitung präsentieren wir unsere Implementierung des Algorithmus und möchten besonders auf die zum Teil nicht offensichtlichen Schwierigkeiten eingehen, die während der Implementierung aufgetreten sind. Abschließend stellen wir einige Ergebnisse von Experimenten bezüglich der Qualität des Algorithmus vor, die wir an drei Graphklassen durchgeführt haben.

Download [512 KiB] (Update: 18 Apr 2007)

Triangulierung eines Planaren Graphen

Thomas Pajor

Das Triangulieren eines Graphen ist eine Grundoperation, die von vielen Algorithmen, die auf planaren Graphen operieren, benötigt wird. Der hier vorgestellte Algorithmus trianguliert einen Graphen mit nn Knoten in O(n)\mathcal{O}(n) Zeit durch geeignetes Einfügen von Kanten.

Download [54 KiB] (Update: 18 Apr 2007)

Einige Kalküle der Logik

Thomas Pajor

Dieses Dokument soll eine Zusammenfassung einiger Kalküle aus der Aussagenlogik und Prädikatenlogik erster Stufe sein. Kalküle dienen dazu innerhalb eines formalen Systems, beispielsweise eines Logiksystems, Aussagen zu beweisen oder zu widerlegen. Da dies ein wichtiger Bestandteil der Vorlesung „Formale Systeme“ an der Universität Karlsruhe ist, erhoffe ich mir durch die Erstellung des Papiers einen kleinen Lerneffekt für mich. Aber vielleicht hilft es auch dem einen oder anderen beim Verständnis. Ich setze hier die Grundbegriffe der Logik wie „erfüllbar“, „allgemeingültig“ usw. voraus. Genauso sollte man wissen wie die Aussagenlogik und Prädikatenlogik syntaktisch definiert sind und was eine Interpretation bzw. ein Modell ist.

Download [149 KiB] (Update: 27 Feb 2006)

Das Symbol für Hochgradigkeit

Dirk Achenbach und Thomas Pajor

Hochgradigkeit tritt im Alltag in vielen Situationen auf. Besonders oft wird man jedoch in mathematischen Beweisen oder Aussagen mit ihr konfrontiert. Folgende Symbole können (zum Beispiel als Randnotiz) in LaTeX\LaTeX{} dazu benutzt werden, um dem geneigten Leser zu verdeutlichen – bzw. ihn zu warnen – dass eine hochgradige Stelle folgt.

Download [37 KiB] (Update: 02 Feb 2006)

Das Mysterium der Koordinatenvektoren bei Linearen Abbildungen

Thomas Pajor

Teil der Vorlesung „Lineare Algebra und Analytische Geometrie“ an der Universität Karlsruhe (TH) ist die Darstellung linearer Abbildungen durch Matrizen. Diese setzen ein Verständnis des Begriffs Koordinatenvektor voraus. Da dieses Thema extremst grundlegend und wichtig ist, und es meist nicht richtig verstanden wird, habe ich dieses kleine Paper geschrieben, um vielleicht ein wenig für Aufklärung zu sorgen…

Download [111 KiB] (Update: 17 Sep 2005)

Der Minus-Eins-Zeilen-Trick

Thomas Pajor

Das Lösen von homogenen linearen Gleichungssystemen (LGS) ist in der linearen Algebra von zentraler Bedeutung. Als Standardverfahren wird dabei die Gauß-Elimination verwendet, bei der man das LGS als Matrix A∈Km×nA \in \mathbb{K}^{m \times n} auffast und dann diese durch elementare Zeilenumformungen in Gaußnormalform (GNF) bringt.

Hat man als Endprodukt die GNF hergeleitet, und gilt rang(A)<n\text{rang}(A) < n, so hat man nun das Problem den Lösungsraum irgendwie abzulesen. Dieses Dokument soll dazu einen höchst geheimen Trick vorstellen, und zwar den sogenannten „Minus-Eins Zeilen-Trick“, mit dem das Ablesen der Lösung in einem Bruchteil einer Sekunde möglich ist.

Download [63 KiB] (Update: 01 Jun 2005)

Der Mysteriöse Grenzwert

Thomas Pajor

Ich möchte hier einen Beweis liefern, dass die Funktion f(n)=log⁡(n!)nlog⁡nf(n) = \frac{\log (n!)}{n \log n} für nn gegen unendlich gerade gegen 11 strebt. Daraus folgt nämlich dass für sehr große nn gilt dass log⁡(n!)≈nlog⁡n\log(n!) \approx n \log n. Dies ist unter anderem beim Beweis der unteren Schranke für Sortieren relevant.

Download [41 KiB] (Update: 31 May 2005)