Preprints und Diskussionspapiere

On the rank of a random binary matrix with independently chosen rows of constant weight

In Vorbereitung.


A linearized DPLL calculus with clause learning

Oktober 2007, aktualisiert im Januar 2010.

Viele formale Beschreibungen DPLL-basierter SAT-Algorithmen enthalten entweder nicht alle wesentlichen Beweistechniken, die in modernen SAT-Solvern implementiert sind, oder hängen von bestimmten Heuristiken oder Datenstrukturen ab. Dies erschwert die Analyse beweistheoretischer Eigenschaften oder der Suchkomplexität derartiger Algorithmen. Mit diesem Artikel versuchen wir, diese Situation durch die Entwicklung eines nichtdeterministischen Beweiskalküls zu verbessern, der die Arbeitsweise von SAT-Algorithmen modelliert, die auf dem um das Lernen von Konfliktklauseln erweiterten DPLL-Kalkül basieren. Unser Kalkül ist unabhängig von Implementierungsdetails, aber dennoch präzise genug, um eine formale Analyse realistischer DPLL-basierter SAT-Algorithmen zu ermöglichen.

PDF herunterladen


Konferenzbeiträge

Codegenerierung für anwendungsspezifische Prozessoren mit evolutionären Algorithmen

Informatiktage 2001, 213–215, Konradin-Verlag, November 2001.
Außerdem präsentiert auf dem Fachbereichstag Informatik, Oktober 2002.

Dieser Artikel beschreibt ein Verfahren zur Codegenerierung für Prozessoren mit Befehlsparallelismus und komplexen Befehlen. Beispiele für derartige Architekturen sind digitale Signalprozessoren (DSPs), Multimediaprozessoren mit speziellen Befehlssätzen zur Verarbeitung von Audio- oder Videodaten und andere anwendungsspezifische Prozessoren (ASIPs). Unser Verfahren basiert auf zwei gekoppelten evolutionären Algorithmen, von denen einer die Befehlsauswahl vornimmt und der andere Registerzuordnung und Befehlsplanung optimiert. Die Optimierung erfolgt dabei vollständig auf einer Graphendarstellung des Eingabeprogramms.

PDF herunterladen


Forschungsberichte

Mapping IEC 1131-3 to the ECMA-335 Common Language Infrastructure and the Real-Time Operating System QNX

(mit Uwe Petermann) Forschungsbericht, HTWK Leipzig, März 2003, überarbeitet im Februar 2005.

Dieser Bericht fasst die Ergebnisse und Erfahrungen aus dem Projekt CommonCtrl zusammen. Ziel dieses Projektes war die Integration eines auf der SPS-Programmiersprache IEC 1131-3 basierenden Prozessleitsystems in eine auf der Common Language Infrastructure nach dem ECMA-335-Standard basierende dynamische objektorientierte Umgebung unter dem Echtzeit-Betriebssystem QNX. Dieses Vorhaben war motiviert von dem Wunsch, die standardisierte Programmiersprache IEC 1131-3, mit der viele Entwicklungsingenieure vertraut sind und die sich als solide Basis für Prozessleitsysteme bewährt hat, mit einer Plattform zu kombinieren, die eine umfangreiche Klassenbibliothek, dynamisch ladbare Komponenten und Interoperabilität zu gängigen Betriebssystemen und Kommunikationsstandards bietet.

PDF herunterladen


Mapping IEC 1131-3 to the ECMA-335 Common Language Infrastructure and the Real-Time Operating System QNX

(mit Uwe Petermann) Forschungsbericht, BitCtrl Systems, Januar 2003.

Dieser Bericht beschreibt die Ergebnisse des Projektes CommonCtrl im Detail.

(Nicht öffentlich verfügbar.)


Abschlussarbeiten

A Recurrent Neural Network Model for Pattern Recognition

Masterarbeit, Max-Planck-Institut für Mathematik in den Naturwissenschaften und HTWK Leipzig, Dezember 2003.

Viele neuronale Modelle des visuellen Systems von Säugetieren sind im wesentlichen Feed-Forward-Modelle, die entweder überhaupt keine Rückkopplungen beinhalten oder diese nur als untergeordneten Teil nutzen. Dies steht im Widerspruch zu neuroanatomischen Fakten und den Ergebnissen zahlreicher neuropsychologischer Experimente, die Indizien dafür liefern, dass Rückkopplungen eine wesentliche Rolle bei der Verarbeitung visueller Signale spielen. In meiner Masterarbeit entwickle ich ein rückgekoppeltes neuronales Netzwerkmodell, dass diese Ergebnisse berücksichtigt. Dieses Modell basiert auf der Idee, dass es insbesondere bei verrauschten Daten von Vorteil ist, nicht die gesamten Eingangssignale auf einmal auszuwerten, sondern nur die Merkmale, die zu einem bestimmten Zeitpunkt den größten Informationsgewinn erwarten lassen. Das Netzwerk verwendet die Rückverbindungen, um die auszuwertenden Merkmale auszuwählen. Dies macht die Rückkopplungen im Netzwerk zu einem zentralen Kontrollelement, was besser mit biologischen Erkenntnissen übereinstimmt als traditionelle Modelle.

PDF herunterladen


Codegenerierung für variable Zielarchitekturen mit evolutionären Algorithmen

Diplomarbeit, HTWK Leipzig, Oktober 2001. Diese Arbeit wurde vom Fachbereichstag Informatik 2002 als hervorragende Diplomarbeit im Fachgebiet Technische Informatik prämiert.

Hardware-Software-Codesign, also der integrierte Entwurf von Hardware- und Softwareteilen eines Systems, ist insbesondere für den Entwurf komplexer eingebetteter System ein wichtiges Entwurfsparadigma. Ein wesentlicher Bestandteil jedes Codesign-Systems ist ein Codegenerator, der in der Lage ist, für unterschiedliche Zielarchitekturen Code zu erzeuge, der die speziellen Eigenschaften der jeweiligen Architektur, wie Befehlsparallelismus und komplexe Befehle, möglichst gut ausnutzt. Klassische, auf Heuristiken basierende Algorithmen zur Codegenerierung sind dafür oft nicht geeignet, weil ihr Prozessormodell diese Eigenschaften nicht adäquat abbilden kann. In meiner Diplomarbeit entwickle ich deshalb ein neues, auf evolutionären Algorithmen basierendes generisches Verfahren zur Codegenerierung, das automatisch optimierten Code für verschiedene Zielarchitekturen erzeugen kann.

PDF herunterladen


Notizen

Kolmogorov Complexity and the Incompressibility Method

Oktober 2011.

Die Inkomprimierbarkeitsmethode ist eine einfache und trotzdem leistungsfähige Beweismethode, die sich aus dem Begriff der Kolmogorov-Komplexität ableiten lässt. Dieser Artikel erklärt die Konzepte, auf denen diese Beweistechnik basiert, und bietet nebenbei eine knappe und präzise Einführung in die Kolmogorov-Komplexitätstheorie. Die einzige Voraussetzung für diesen Text ist ein grundlegendes Verständnis berechenbarer Funktionen.

PDF herunterladen


Die Unentscheidbarkeit extensionaler Eigenschaften von Turingmaschinen: der Satz von Rice

Juli 2008, aktualisiert im Januar 2010.

Dieser einführende Text behandelt die Beweistechnik der funktionalen Reduktion als Werkzeug zum Beweis der Unentscheidbarkeit oder Nichtaufzählbarkeit einer Sprache. Es wird erklärt, wie mit dieser Technik das Akzeptanzproblem für Turingmaschinen – die universelle Sprache – auf jede nichttriviale Menge von Turingmaschinen-Beschreibungen oder deren Komplement reduziert werden kann. Dieses Ergebnis, das als Satz von Rice bekannt ist, zeigt, dass jede nichttriviale extensionale Eigenschaft von Turingmaschinen (oder mit anderen Worten: jede nichttriviale Menge partiell berechenbarer Funktionen) unentscheidbar ist. Das bedeutet, dass sich prinzipiell kein Programm konstruieren lässt, welches automatisch prüft, ob ein beliebiges Programm ein bestimmtes extensionales Verhalten besitzt.

PDF herunterladen


Information maximization in a network of linear neurons

Mai 2005.

Seit den Arbeiten von Hubel und Wiesel ist bekannt, dass viele Neuronen in den unteren visuellen Arealen der Gehirne von Säugetieren ein charakteristisches Antwortverhalten besitzen. Beispielsweise gibt es Zellen, die auf hell-dunkel-Kontraste reagieren, während andere auf Kanten einer bestimmten Ausrichtung ansprechen. In einer Serie von Artikeln hat Linsker experimentell gezeigt, wie sich derartige Antworteigenschaften in einem einfachen Feed-Forward-Netzwerk aus linearen Neuronen mittels einer Hebbschen Lernregel entwickeln können, ohne dass das Netzwerk strukturierte Eingaben erhält. Später zeigte Linsker theoretisch, dass der Selbstorganisationsprozess, der zu diesen rezeptiven Feldern führt, mit dem Prinzip der maximalen Informationserhaltung beim Übergang vom Stimulus zur Antwort konsistent ist. Dieser Text enthält eine Einführung in Linskers Analyse.

PDF herunterladen


Einige Untersuchungen zu einem Neuronenmodell auf der Basis von dendritischen Spine-Clustern

Juni 2002.

Übliche abstrakte Neuronenmodelle betrachten Neuronen als (mehr oder weniger einfache) Integrations-Schwellwert-Einheiten, deren Erregung als gewichtete Summe ihrer Eingaben berechnet wird. Dabei bleibt aber unberücksichtigt, dass die Eingangspfade natürlicher Neuronen eigentlich aus Dendritenbäumen mit einer sehr aufwändigen Struktur bestehen. Eine einfache Summierung der an den Dendriten ankommenden Signale ignoriert die komplexen Wechselwirkungen zwischen den dendritischen Synapsen. In diesem Artikel untersuchen wir ein alternatives Neuronenmodell für assoziatives Lernen von Alkon, Blackwell und Vogl. Dieses Modell ist aus der Annahme abgeleitet, dass die Fähigkeit natürlicher Neuronen, eingehende Signale zu verbinden, und somit auch ihre Fähigkeit, lernende Systeme zu bilden, auf der Wechselwirkung räumlich benachbarter Synapsen beruht.

PDF herunterladen

Design und Programmierung: Holger Arnold