Benjamins Blog

Ich denke nicht, dass es übertrieben ist zu sagen, dieses Seminar gehört mit zu den Höhepunkten meines bisherigen Studiums an der Uni Ulm. Ein einfaches Seminar haben die Jungs vom Institut für Medieninformatik zu einer vollständig konferenzähnlichen Veranstaltung aufgebohrt – und es hat sich für alle gelohnt. Die Seminarthemen orientierten sich an aktuellen Forschungstrends aus dem Bereich der Medieninformatik und insbesondere aus den Bereichen des Ubiquitous Computings. Allerdings waren die Themen allgemein genug, um mehr als nur punktuelle Forschungsergebnisse anderer zu beschreiben. Vielmehr bot jeder einzelne Vortrag einen guten Einblick in den jeweiligen Themenkomplex ohne all zu spezifisch für die anderen Teilnehmer zu werden. Dies sorgte insbesondere für rege Diskussionen am Ende jeden Vortrags. Die vier Sessions teilten sich in die Bereiche Ubiquitous Computing, Devices and Games, Networking Trends sowie Social Computing ein.
Verschiedene Beiträge werden in Kürze auf IOException vorgestellt.

Doch der Ablauf unterschied sich von dem üblichen Abläufen: Ausarbeitung schreiben, Überarbeitung mit einem Betreuer, Powerpoint Folien erstellen und letztendlich die typischen Präsentationen.



Zunächst wurden wir dazu motiviert, unsere Paper auf Englisch zu verfassen. Der Review-Prozess wurde um ein Peer-Reviewing erweitert, bei dem die Teilnehmer Arbeiten anderer mitbegutachteten. Bei den Vorträgen legten die Betreuer Wert auf ansprechende Präsentationen abseits von Powerpoint und Bullet Points.
Dieser Mehraufwand wurde letztendlich mit einem wirklich sehr konferenznahen Blockseminar belohnt. Es gab Badges für alle Teilnehmer, gedruckte(!) 130-seitige Proceedings mit allen Papern und sogar zwei Keynotes Speeches – darunter ein Forscher aus den Niederlanden
Selbst ein Social Event am Ende hat es gegeben, es war echt noch nett im Barfüsser!

Nochmal großes Lob an Boto, Stefan, Flo, Elmar, Basti und Björn für die besondere Betreuung des Seminars!

Und irgendwie hat dieses Seminar Lust auf mehr gemacht – kurze und interessante Vorträge, die einen Blick über den Tellerrand ermöglichen, gerne auch noch interdisziplinärer. Mal sehen, ob wir da noch etwas weiteres auf die Reihe bekommen.

Aus meiner Seminararbeit zum Thema Semantic Mashups aus dem vergangenen Sommersemester ist nun ein kleiner Technical Report geworden. Im Paper werden Mashups – also Anwendungen, die Informationen verschiedener Webseiten vermischen – analysiert und verschiedene technische Grundlagen, die hierfür nötig sind erläutert. Desweiteren werden existierende Mashup-Engines und Architekturen vorgestellt, sowie Herausforderungen und Probleme beim Erstellen von Mashups aufgezeigt.


Abstract:

Nowadays, the World Wide Web has become the most important source of information for many people and is nearly indispensable. However, the information is spread on billions of web pages. So there is an increasing demand to combine the data of different web pages for an acquisition of information. Mashup applications assist the user at this task. This paper will give an overview about how to extract structured and semantical data out of web pages using different technologies and also shows, what types of mashup applications already exist. Furthermore we take a look at mashup architectures and engines and unresolved issues for mashup applications.

Benjamin Erb, Jan-Patrick Elsholz, Franz J. Hauck: Semantic Mashup: Mashing up Information in the Todays World Wide Web – An Overview. VS-R08-2009, 2009. [pdf] [bib]

Vor etwa einem Monat habe ich zusammen mit Raimar und David die Seite www.IOException.de ins Leben gerufen, auf der wir unsere technischeren und Informatik bezogenen Beiträge aggregieren möchten.
Gerne nehmen wir auch noch weiter Mit-Blogger auf oder freuen uns auf Gastbeiträge, bei Interesse einfach melden.

Für die Wahl eines Informatikstudiums sollte es völlig irrelevant sein, ob man bereits erste Programmiererfahrungen besitzt oder noch nie eine Zeile Code geschrieben hat. Analytisches und logisches Denkvermögen sowie fehlende Berührungsängste mit Mathematik sind um einiges wichtiger als Wissen zu aktuellen Programmiersprachen, denn Programmierung ist selbst eher ein Werkzeug der Informatik, als zentraler Lehrinhalt eines universitären Studiums. Genauso wenig ist ein sonderlich profundes Vorwissen über Computer notwendig, wie bereits ein bekannter niederländischer Informatiker sagte:

„Computer science is no more about computers than astronomy is about telescopes."
Edsger Dijkstra

Trotzdem muss man natürlich lernen, seine Werkzeuge beherrschen zu können. Und leider haben erfahrungsgemäß Studierende im ersten Semester ohne Programmiererfahrungen einen zusätzlichen Aufwand dadurch, parallel zu den Vorlesungen, die eben keinen Programmierkurs darstellen, sondern eher abstrakte Konzepte vermitteln, auch noch das ganz praktische und angewandte Programmieren zu erlernen.

Aus diesem Grund wurde an der Uni Ulm vor einem Jahr auf Initiative von uns, der Fachschaft Informatik, ein aus Studiengebühren finanzierter Kurs eingeführt, der in die Java-Programmierung einführt und wirklich im wahrsten Sinne des Wortes bei null anfängt. Bei diesem freiwilligen Kurs werden Studierende intensiv bei ihren ersten Programmierschritten begleitet, was vor allem durch ein hohes Betreuungsverhältnis mit vielen Tutoren möglich ist. Neben Übungsblättern entstand nun bei der zweiten Durchführung der sogenannten „Programmierstarthilfe“ auch ein Skript als Einführung in die Java-Programmierung. Da ich als Tutor diese Veranstaltung in ihrem ersten Jahr mitbetreut habe, war ich auch an der Entstehung dieses Skripts beteilgt, an dem ansonsten vor allem Guido und Marcus gearbeitet haben, aber auch die übrige Team. Wir haben uns dazu entschlossen, das entstandene Werk unter einer Creative Commons-Lizenz der Öffentlichkeit zugänglich zu machen. Es entstand zwar in oben genanntem Kontext, kann aber auch völlig losgelöst zum Selbststudium gelesen werden. Es richtet sich weder ausschließlich an InformatikerInnen, noch sind irgendwelche Vorkenntnisse notwendig. Somit sollte es mit diesem Skript für quasi jeden möglich sein, erste Erfahrungen mit der Programmierung und dem Programmieren in Java zu machen

Auf 90 Seiten werden unter anderem grundlegende Konzepte wie Datentypen, Kontrollstrukturen, Schleifen, Arrays, Methoden, Rekursion oder einfache Objektorientierung erklärt. Ein weiteres Kapitel zeigt außerdem auf, in welche Richtungen es noch weitergeht. Hier werden Themen wie Vererbung, Interfaces, Autoboxing, Enum-Typen, Generics, Collections, Multithreading und GUI-Programmierung angerissen. Dieses weiterführende Kapitel sowie die Kapiel über abstrakte Datenstrukturen und über API-Dokumentation stammen übrigens von mir.

Download: Skript: Java Grundlagen - Programmierstarthilfe (PDF)

Das Skript steht unter der Creative Commons Attribution-NonCommercial-ShareAlike 2.0 Lizenz und kann in der Version vom April 2009 heruntergeladen werden.

Automaten sind nicht nur in der theoretischen Informatik ein wichtiges Werkzeug im Bereich der formalen Sprachen zur Überprüfung von Sprachzugehörigkeiten. Eine davon abgeleitete Anwendung ist die Mustererkennung in Zeichenketten mithilfe regulärer Ausdrücke. Aber auch viele Protokolle verteilter Systeme (z.B. TCP) greifen das Konzept von Zustandsautomaten auf, um abhängig von verschiedenen internen Zuständen auf Ereignisse differenziert zu reagieren. Natürlich müssen diese Zustandsautomaten bei der Implementierung von Protokollen auch in Software abgebildet werden. In diesem Artikel möchte ich anhand eines einfachen DFAs aufzeigen, wie solche Zustandsautomaten unter Anwendung des State Patterns in Java realisierbar sind.

In diesem Beispiel soll ein DFA konstruiert werden, der aus allen möglichen Zeichenfolgen bestehend aus Einsen und Nullen genau diejenigen akzeptiert, in denen die Teilworte 01 und 10 gleich oft vorkommen. Der nebenstehende Graph verdeutlicht die Funktionsweise des Automaten. Neben dem Startzustand (S) gibt es zwei gültige Endzustände (A,X) mit gleicher Anzahl von Vorkommen, sowie zwei Zustände (B,Y) die keinen gültigen Endzustand darstellen.

Möchte man nun eine solche Konstruktion implementieren, so muss man Zustände, Übergänge und gültige Kombinationen abbilden. Das State Pattern der GoF als Verhaltensmuster bietet sich bei objektorientierten Sprachen an, da es übersichtlicher, sauberer und erweiterbarer ist als Kaskaden von If-Abfragen oder Switch-Statements-Konstrukten. Die Grundidee hierbei ist, Zustände mit zugehörigen Übergängen in eigene Objekte auszulagern und dem zustandsbehafteten Objekt die entsprechende Referenz auf seinen aktuellen Zustand zu übergeben. Änderungen delegiert dieses zustandsbehaftete Objekt dann an sein aktuelles Zustandsobjekt, welches eventuell nach dem Übergang ersetzt wird. In Java bietet es sich an, die Zustände als Enum-Instanzen zu realisieren und diese ein Interface implementieren zu lassen, welches die Übergange definiert. Zusätzlich lassen sich die Zustände, also Enum-Instanzen, darauf hin abfragen, ob sie einen gülitgen finalen Zustand darstellen.
Die Automaton-Klasse stellt nun das eigentliche Objekt dar, was zustandsbehaftet ist, jedoch mit ausgelagerter Behandlung der Zustände:

Transitions.java - Auflistung der Übergänge als Interface

/**
 * Interface listing possible transitions to be implemented by states
 */
public interface Transitions
{
	public void readZero(Automaton a);

	public void readOne(Automaton a);
}

State.java - Zustände als Enum-Typen

/**
 * Enum type for states
 */
public enum State implements Transitions
{
	/**
	 * Initial State - S
	 */
	S
	{
		@Override
		public void readOne(Automaton a)
		{
			a.setState(X);
		}

		@Override
		public void readZero(Automaton a)
		{
			a.setState(A);
		}

		@Override
		public boolean isFinal()
		{
			return true;
		}
	},

	/**
	 * Final State - A
	 */
	A
	{
		@Override
		public void readOne(Automaton a)
		{
			a.setState(B);
		}

		@Override
		public void readZero(Automaton a)
		{
			a.setState(A);
		}

		@Override
		public boolean isFinal()
		{
			return true;
		}
	},

	/**
	 * State -B
	 */
	B
	{
		@Override
		public void readOne(Automaton a)
		{
			a.setState(B);
		}

		@Override
		public void readZero(Automaton a)
		{
			a.setState(A);
		}

		@Override
		public boolean isFinal()
		{
			return false;
		}
	},

	/**
	 * Final State - X
	 */
	X
	{
		@Override
		public void readOne(Automaton a)
		{
			a.setState(X);
		}

		@Override
		public void readZero(Automaton a)
		{
			a.setState(Y);
		}

		@Override
		public boolean isFinal()
		{
			return true;
		}
	},

	/**
	 * State -Y
	 */
	Y
	{
		@Override
		public void readOne(Automaton a)
		{
			a.setState(X);
		}

		@Override
		public void readZero(Automaton a)
		{
			a.setState(Y);
		}

		@Override
		public boolean isFinal()
		{
			return false;
		}
	};

	/**
	 * Is state final?
	 * @return true if final
	 */
	abstract public boolean isFinal();
}

Automaton.java - Das zustandsbehaftete Objekt inklusive Test in der Main-Methode.

/**
 * Automaton class
 */
public class Automaton
{
	//Initial state
	private State state = State.S;

	public void setState(State s)
	{
		this.state = s;
	}

	public void readZero()
	{
		//Delegate...
		state.readZero(this);
	}

	public void readOne()
	{
		//Delegate...
		state.readOne(this);
	}

	public boolean isInFinalState()
	{
		//Delegate...
		return state.isFinal();
	}

	public static void main(String[] args)
	{
		Automaton a = new Automaton();
		String s1 = "11010101";
		for (char c : s1.toCharArray())
		{
			switch (c)
			{
				case '1':
					a.readOne();
					break;
				case '0':
					a.readZero();
					break;
			}
		}
		System.out.println(a.isInFinalState()); //true...
	}
}

Dieses Beispielprogramm mit einem DFA habe ich zum leichteren Verständis gewählt, natürlich lassen sich mit diesem Pattern weit aus komplexere Abläufe modellieren. So könnte der Automat zum Beispiel ein Buch-Objekt einer Bücherei sein und die Übergänge Aktionen wie das Ausleihen, Verlängeren oder Zurückgeben des Buches. Die Zustände als Enum-Typen würden dann auch mehr Geschäftslogik enthalten als das bloße Verändern das Zustands wie hier in diesem Beispiel.

Unter einem Heap (im Deutschen gelegentlich auch als Halde bezeichnet) versteht man eine baumartige Datenstrukur mir einer besonderen Eigenschaft: Die Nachfolgeknoten jedes Knotens besitzen immer kleinere (oder immere größere) Schlüsselwerte als der Knoten selbst. Somit entsteht ein partiell geordneter Baum. Ein Heap wird vor allem für zwei Dinge eingesetzt: Zur Realisierung von gewichteten Prioritätswarteschlangen und zur Sortierung (Heap Sort).

Bei der Sortierung wird eine nicht geordnete Liste in einen binären Heap eingelesen und dabei entsprechend der Heapeigenschaft umstrukturiert. Danach ist die Wurzel genau der Knoten mit dem maximalen Wert, und alle Knoten jeweils kleiner als ihre Elternknoten, aber größer als ihre Kindknoten. Nun beginnt der eigentliche Sortierschritt. Iterativ wird immer der aktuelle Wurzelknoten aus dem Heap entnommen und an den sortieren Bereich angefügt. Danach wird der Heap wieder erneuert und ein neuer Knoten mit dem Maximalwert der übrigen Knoten wandert an die Stelle der Wurzel. Meistens wird diese Datenstruktur auf einem Array realisiert. Das Array wird zunächst in eine gültige Heap-Ordnung überführt. Danach wird jeweils der erste Werte als verbliebenes Maximun in den hinteren Bereich des Arrays einsortiert, wo schrittweise die Ordnung aufgebaut wird. Dabei wird einfach das Wurzelelement mit dem Element an der richtigen Stelle am Ende des Arrays getauscht. Nun wird erneuert der Heap korrigiert.

In der Visualisierung ist der binäre Heap als sogenannter Sunburst Tree dargestellt. Die Wurzel entspricht dem inneren Kreis, die Kindknoten jeweils den konzentrisch abstehenden Kreisbogensegmenten. Die Ordnung entspricht der farblichen Sortierung von Schwarz zu Rot. Im Video sind die einzelnen Phasen gut sichtbar. Zunächst wird die chaotische Ordnung durch eine Ordnung entsprechend des Heaps angepasst. Hier wandern die dunklen Felder nach innen und die roten Felder nach außen. Anschließend beginnt die Sortierung. Im Falle des ersten Elements bedeutet dies das Tauschen des dunkelsten schwarzen Feldes (Kreismitte) mit dem Ende des Arrays. Anschließend wird wieder die Heapstruktur hergestellt. Somit ensteht schrittweise die Ordnung - im Uhrzeigersinn und von außen nach innen.

Realisiert habe ich die animierte Visualisierung mithilfe von Java (zur Grafikgenerierung) und mencoder (Stopmotion). Auf vimeo gibt es außerdem das Video in hoher Qualität.

Weihnachten in einer Informatiker-WG: Oh Tanenbaum!

Im Rahmen der Vorlesung "Medienpädagogik, -didaktik und -psychologie" wurden empirische Studien zu medienpsychologischen Themen durchgeführt. Unsere Arbeitsgruppe entschied sich für das Thema "Geschlechtsspezfisches Flirtverhalten in sozialen Netzwerken am Beispiel der Onlineplattform StudiVZ". Hierfür führten wir eine Onlineumfrage durch und stellten unsere Ergebnisse in Form eines Posters (PDF-Datei, Din A0: 1,9 MB) dar:

Eine mit Processing realisierte Visualiserung zwölf verschiedener Sortieralgorithmen. Auf den Grafiken werden deutlich die Charakteristika der einzelnen Algorithmen sichtbar. Die normierte Zeitachse gibt jedoch keine Auskunft über die Zeitkomplexität der Algorithmen.

Neben den unten stehen Vorschaufotos gibt es außerdem große Grafiken:
Sorting Algorithm Visualization Poster I
(PNG, 1280 x 3691 px, 970 kB)
Sorting Algorithm Visualization Poster II
(PNG, 3072 x 2170 px, 1120 kB)

Außerdem eine Posterversion zum Drucken:
Sorting Algorithm Visualization Poster
(PDF, Din A1, 8885 kB)

...mit Processing: