so, nachdem die Site jetzt endlich wieder online ist (was für ein Gedöööns ...) ein kurzes Update was so passiert ist die letzten 2 Monate: das 4. Semester hat angefangen, welches den Fächern nach zu urteilen sehr interessant werden wird. Da wäre zum Beispiel das Software-Praktikum, bei dem wir in 5er-Teams die neue Website für die Kinderuni Augsburg entwickeln werden. So komplett mit Ticketbestell-Funktion, Userverwaltung, CMS und den ganzen Geschichten. Das Team mit der besten Website gewinnt und deren Ergebnis wird live geschalten. Ich hatte Glück bei der Teamverlosung und arbeite mit sehr fähigen Leuten zusammen, wir malen uns gute Chancen auf Platz 1 aus. Natürlich ist es bis dahin noch ein weiter Weg, keiner von uns hat bisher ernsthaft mit den verwendeten Technologien gearbeitet.
Dann wäre da noch Suchmaschinen, bei dem es wie der Name schon sagt um die Funktionsweise von Google + Friends geht. Ein sehr interessantes Thema, wenn ich mir auch Sorgen mache ob mein Vorwissen ausreicht, offiziell wird dafür nämlich Datenbanken I vorausgesetzt was ich nicht belegt habe, mal schauen, bis jetzt komm ich noch mit.
Mein drittes Hauptfach Systemnahe Informatik interessiert mich jetzt nicht sonderlich, allerdings ist der Stoff definitiv "nice to know", so dass ich mich auch da reinhängen werde. Nebenbei fungiere ich noch als (hochmotivierter) Informatik II-Tutor und tauche mit interessierten Studenten in die Java-Welt ein. Mal sehen ob ich den Ansprüchen eines "Lehrers" gerecht werde, bis jetzt bin ich zuversichtlich.
Ich hatte mit dem Gedanken gespielt aus Zeitgründen meinen heiß geliebten Job bei Vogel an den Nagel zu hängen, aber da ich jetzt mit meinem Vorgesetzten ausgemacht habe viel weniger zu arbeiten als bisher, bleib ich erstmal dabei. Meine Woche ist VOLL, allerdings VOLL mit coolem Zeugs, das macht es wieder erträglich ;)

Achja, ich bin jetzt am twittern, so ne Mischung zwischen chatten und bloggen, ein neuer Kommunikations-Trend der natürlich nicht an mir vorbei ziehen darf - follow Me

... where zeros and ones turn into billions ...

...so lautete einer der Teaser-Sprüche der diesjährigen CeBIT, der weltgrößten Computer-Messe in Hannover. Ich fand den Spruch so dermaßen geil, dass ich ihn direkt mal zu meinem (beruflichen) Lebensmotto deklariert habe (auch wenn ich mich für den Anfang mit millions zufrieden geben würde ^^).
Meine Aufgabe auf der Messe bestand im Wesentlichen darin, "Promotiongirl" für unsere tollen neuen Websites (siehe letzten Post) zu spielen und interessierte Leute dazu zu bringen sich bei uns zu registrieren. Wir hatten zwei Terminals auf einem Gemeinschaftsstand verschiedener Hersteller von Virtualisierungs-Software, darunter namhafte Firmen wie Platespin und VMware (was manchen ein Begriff sein könnte). Am ersten Tag war ich nicht sonderlich erfolgreich. Das lag daran dass ich schlichtweg zu schüchtern war wild-fremde Leute anzuquatschen und vollzulabern ihre Daten preiszugeben, zumal ich auch thematisch üerhaupt keine Ahnung hatte. Mein Selbstbewusstsein stärkte sich aber dann in den darauffolgenden Tagen, nachdem ich ein paar Erfolgserlebnisse für mich verbuchen konnte. Am Ende hat es sogar teilweise Spaß gemacht mit den Leuten zu reden. Mir ist aufgefallen dass unsere Websites wirklich verdammt gut sind, vorausgesetzt man ist Zielgruppe. Ein Zitat einer Kollegin bringt das ganz gut auf den Punkt: "Der Wurm muss dem Fisch schmecken nicht dem Angler."
Ich hatte leider wenig Zeit mir die riesige Messe anzugucken. Ich bin nur einmal rumgelatscht, als mich der Tim freundlicherweise Samstag-Nachmittag besucht hatte. Aber da konnt ich nicht viel Spektakuläres entdecken. Eigentlich wollt ich mir die Intel Extreme Masters Finals reinziehen, die Kiddie-Schlange vor dem Pavillon war allerdings ca. 3 km lang, so dass ich mich mit nem WC3-Match im Rahmen der World Cyber Games Euro Championship zufrieden gab. E-Sport made in Germany, war recht imposant.

Es folgen visuelle Eindrücke der CeBIT-Woche, aufgenommen mit meiner Handy-Cam. Eventuelle Unschärfe bitte ich zu entschuldigen.

Unsere neuen Websites sind da !!! Ladies and Gentlemen, hier das Ergebnis von monatelangem Anhäufen von Überstuden, zahlreichen Nervenzusammenbrüchen, tausenden E-Mails und Telefonaten, Diskussionen und Meetings, schlaflosen Nächten und Wochenenden im Büro. Zwar trifft keines von den oben beschriebenen Strapazien auf mich zu, da ich an der konkreten Umsetzung nur in der letzten Woche ernsthaft beteiligt war, es sei dennoch vermerkt was für eine immense Arbeit hinter solchen auf den ersten Blick "harmlosen" Web-Portalen steckt. Mein Respekt gilt allen Beteiligten die sich für dieses Projekt so aufgeopfert haben. Und wie es sich für einen ordentlichen SEO gehört, widme ich unseren neuen Babies gleich mal 4 optimierte Backlinks:

• SearchSecurity.de: IT-Security, Trojaner, Firewall, Antivirus, Netzwerksicherheit
• SearchNetworking.de: Networking, WLAN, VoIP, VPN, Router | Entscheiderwissen für Networking-Professionals
• SearchStorage.de: Storage, Festplatte, Speichernetze, SAN, NAS, RAID, Datensicherung
• SearchDataCenter.de: Virtualisierung, Green-IT, Energie-Effizienz, Server Konsolidierung, IT-Infrastruktur

Registrieren, rumklicken, bewundern, Feed abonnieren, Lesen, Bugs melden, downloaden, mit den JQueries spielen, Suchen, social bookmarken, Backlinks auf eure Website setzen oder tut was euch sonst so einfällt. Hauptsache WÜRDIGEN :P

Ich bin gerade dabei für die erfahrungsgemäß wichtigste / schwierigste Klausur meines Bachelor-Studiums zu pauken. Sie trägt den weniger aussagekräftigen Namen "Informatik III". Grob gesagt geht es in der Vorlesung um grundlegende Algorithmen (= Verfahren, Probleme zu lösen) und die dazugehörigen Datenstrukturen. Die wichtigste Kennziffer um Algorithmen zu bewerten ist die Laufzeit. Man bedient sich dabei einigen Tricks um die Darstellung zu vereinfachen. So werden Konstanten, die von der jeweiligen Architektur des zugrunde liegenden Systems abhängen, einfach weggelassen und nur die Worst-Case Laufzeit asymptotisch angegeben. Ein kleines Beispiel zur Veranschaulichung: Ein Algorithmus erhält eine Eingabe der Länge n (z.B. eine Folge von n ganzen Zahlen). In dem Programm gibt es eine Schleife, die die Eingabe durchläuft und erst abbricht, wenn etwas bestimmtes gefunden wurde. Es könnte sein, dass die komplette Folge durchlaufen werden muss, bis die Abbruchbedingung erreicht wird (= worst-case) oder der Algorithmus schon bei der ersten Zahl anhält (= best-case). Die Laufzeit dieses Programms wäre damit O(n). Die O-Notation hier bedeutet, n-mal durchlaufen oder eben besser.

Wieso erzähle ich das ganze? Ich will auf das Thema der NP-Vollständigkeit eingehen, ein sehr interessantes Kapitel der Vorlesung, das mich fasziniert. Es geht um die Frage "P = NP?". Was ist P und was ist NP?

Um das zu erklären, muss ich erstmal weiter ausholen. Wichtig ist zu wissen, dass nur Algorithmen mit polynomieller Laufzeit für die Praxis interessant sind. Polynomiell heißt, dass nur konstante Zahlen in der Potenz der Laufzeit stehen dürfen. Also Laufzeiten wie O(n²) oder O(n³) sind polynomiell. Alles was langsamer läuft (exponentiell) ist äußerst ineffizient und für die Praxis unbrauchbar. Hier eine Grafik, die das sehr gut veranschaulicht. Darauf seht ihr, wie verschiedene Laufzeiten die Dauer eines Programms beeinflussen. Wie unschwer zu sehen ist, sind exponentielle Laufzeiten völlig inakzeptabel. So benötigt beispielsweise ein exponentieller Algorithmus bei Eingabelänge n = 60 (was nicht viel ist) 366 Jahrhunderte bis die Berechnung beendet ist, während ein 2-polynomieller dafür gerade einmal 36 Tausendsel Sekunden benötigt:

Nun gibt es ein Modell aus der theoretischen Informatik, das es ermöglicht, Probleme, dessen Lösung in der Praxis nur exponentiell berechnet werden können, polynomiell zu lösen. Dieses Modell trägt den netten Namen "nichtdeterministische Turing-Maschine" (NTM) und geht zurück auf Alan Turing, der dieses Modell 1936 erfunden hat. Es handelt sich bei einer NTM um eine sehr abgespeckte Version eines Computers mit einer besonderen Fähigkeit: sie kann raten. Da reale Computer das leider nicht können, ist dieses Modell für die Praxis relativ unbrauchbar. Eine deterministische Turing-Maschine (DTM) dagegen, ist ein Berechnungsmodell, das laut der Churchschen These genauso mächtig ist, wie jeder reale Computer. Man benutzt diese einfachen Rechenmodelle um Verfahren für komplexe Probleme auf eine verhältnismäßig einfache, gemeinsame Grundlage zu stellen. Wenn es um Turing-Maschinen geht, redet man nicht mehr von durchführbaren Berechnungen, sondern von akzeptierten Sprachen. Wieso das so ist, ist jetzt uninteressant. Die Menge der Sprachen, die von einer NTM in polynomieller Laufzeit akzeptiert werden, heißt NP. Und die Sprachen, die von DTMs polynomiell akzeptiert werden P. Zusammenfassend ist also P die Menge der Probleme, für die es einen effizienten, praxistauglichen Algorithmus gibt und NP die Menge der Probleme, für die es nur einen tauglichen Algorithmus gibt, wenn Computer die Lösung "erraten" könnten. Bis hierhin noch relativ unspektakulär. Nun gibt es aber unter den Sprachen in NP eine winzig-kleine Teilmenge, die Menge der NP-vollständigen Sprachen, mit einer zauberhaften Eigenschaft:

Gibt es einen polynomiellen Algorithmus für eine NP-vollständige Sprache, gilt P = NP.

Was bedeutet das? Das bedeutet, wenn man einen effizienten Algorithmus für eine NP-vollständige Sprache findet, hat man damit bewiesen, dass es für alle bisher ungelösten NP-Probleme einen effizienten Algorithmus gibt und das sind verdammt viele. Das liegt daran, dass NP-vollständige Sprachen gewissermaßen so "schwierig" sind, dass man alle anderen NP-Sprachen darauf reduzieren kann (Stichwort polynomieller Reduktionsbeweis). Um NP = P zu beweisen genügt also die effiziente Lösung einer einzigen NP-vollständigen Sprache. Wo gibts schon sowas? Um tausende Probleme zu lösen, genügt die Lösung für ein einziges zu finden. Krass oder? Und jetzt kommt der nächste Knaller: Das P-NP-Problems gehört zu den Clay Mathematics Institute Millenium-Problemen . Mit anderen Worten, wer das Problem löst, kassiert 1 Millionen Dollar. Wie schaut also so ein NP-vollständiges Problem aus, dessen Lösung einen zum Millionär macht und mit Einstein gleichstellt?

Die erste NP-vollständige Sprache wurde von Stephen A. Cook in den 70ern gefunden, das sogenannte Erfüllbarkeitsproblem der Aussagenlogik (engl. satisfiability): Jeder kennt logische Ausdrücke. Beispielsweise ist die Aussage "A und B" nur wahr, wenn A = wahr und B = wahr gilt. Es gibt also eine Belegung, für die die Aussage "A und B" wahr ist, die Aussage ist damit erfüllbar. Nun schauen die meisten formalen logischen Aussagen ein bisschen komplizierter aus (neben "und" gibt es noch zahlreiche andere logischen Verknüpfungen wie "oder", "impliziert", "ist äquivalent", etc..) und man kann sich denken, es wäre nützlich, wenn es ein Programm gäbe, das mir für beliebig lange logische Ausdrücke sagt, ob die Aussage überhaupt für irgend eine Belegung erfüllbar ist. Intuitiv könnte man einfach einen Algorithmus schreiben, der in alle Elementaraussagen (Atome) "wahr" oder "falsch" einsetzt und guckt ob irgendwann mal die Gesamtaussage wahr wird. Wie wäre die Laufzeit eines solchen Algorithmus? Bei Eingabelänge n müsste man im worst-case in alle Atome zwei Werte einsetzen (wahr oder falsch). Also eine Laufzeit von O(2^n) -> exponentiell -> inakzeptabel. Dass diese Sprache in NP liegt, sieht man leicht. Die NTM rät einfach eine Belegung und prüft ob die Gesamtaussage wahr wird. Das kann sie in polynomieller Zeit. Der Beweis, dass dieses Problem NP-vollständig ist, ist unglaublich kompliziert und eine geistige Meisterleisung von Cook. Laut unserem Prof zählt dieser Beweis (den ich absolut nicht checke) zu den größten Meilensteine der Informatik.

Bis heute wurde weder bewiesen noch wiederlegt, dass P = NP gilt. Wem es also gelingt, einen Algorithmus zu finden, der das oben beschriebene Problem in polynomieller Laufzeit löst, kassiert eine Millionen Dollar, verändert die Menschheit (Computer würden noch viel viel viel viel mächtiger werden) und kriegt neben massig Anerkennung bestimmt noch den Nobel-Preis. Also Leute, macht euch ran und findet eine polynomielle Lösung. Wenn euch das obige Problem nicht gefällt, sucht euch ein anderes NP-vollständiges Problem. Es gibt mittlerweile über 1000 davon. Für den Anfang: hier eine Liste von 21 weiteren Problemen, dessen polynomielle Lösung euch berühmt machen wird. Der Vollständigkeit halber, hier noch die offizielle Beschreibung des NP-P-Problems von Stephen Cook persönlich. Ein Ausschnitt:

The importance of the P vs NP question stems from the successful theories of NP-completeness and complexity-based cryptography, as well as the potentially stunning practical consequences of a constructive proof of P = NP.

Ich hoffe die Lösung eines solchen Problems wird keine Klausur-Aufgabe, zutrauen würde ichs unserem Prof ;)

Wie hier bereits angekündigt arbeite ich an einer Blender-Animation für die Uni. Die finale Version hab ich soeben fertig gerendert und steht nun zum Download bereit. Hier die youtube-Version:

Ganz zufrieden mit dem Ergebnis bin ich nicht. Es gibt einige Punkte die man verbessern könnte. Allerdings hatte ich gegen Ende keine Lust mehr mich damit großartig weiter zu beschäftigen, zumal die Zeit auch knapp wurde. Ich hoffe es gefällt euch trotzdem und bin gespannt auf eure Kommentare!