Jugendforum Informatik

Anfang Februar hatten unsere beiden Schüler Lukas Kesch (Jahrgangsstufe 11) und Florian Pallas (Jahrgangsstufe 12) im Rahmen der zweiten Runde des Bundeswettbewerbs Informatik die Möglichkeit, am alljährlichen Jugendforum Informatik auf Burg Liebenzell teilzunehmen. Die Veranstaltung soll erfolgreiche Teilnehmer der ersten Runde aus Baden-Württemberg auf die zweite Runde vorbereiten und spannende Einblicke in die Informatik bieten. Das insgesamt viertägige Programm besteht aus Vorträgen sowie Arbeits- und Projektphasen. Nachfolgend der Bericht von Florian Pallas:

Die Teilnehmer waren bunt gemischt: Von Neulingen bis hin zu “Veteranen”, welche das Jugendforum bereits mehrfach besucht hatten, war alles anzutreffen. Zu den Betreuern gehörte dieses Jahr unter anderem Johannes Häring, welcher erst vor zwei Jahren sein Abitur am HGG geschrieben und an der Endrunde des Wettbewerbs teilgenommen hat. Er studiert mittlerweile am Karlsruher Institut für Technologie Informatik im dritten Semester.

Bereits der Ankunftstag hatte ein volles Programm. Wir lernten verschiedene Möglichkeiten kennen, Zeichenketten auf ihre Ähnlichkeit hin zu prüfen. Hierbei gab es simplere Herangehensweisen, welche schlichtweg die verwendeten Buchstaben verglichen, aber auch komplexere Algorithmen, welche Tippfehler oder die deutsche Aussprache in Betracht zogen. Auf diese Weise können beispielsweise Dubletten in großen Datensätzen schnell gefunden und entfernt werden. Fehler sind schließlich menschlich, eine hohe Qualität und Integrität von Daten jedoch unverzichtbar.

Am Tag darauf wurde uns in einem weiteren Vortrag eine Art der Indexierung gezeigt, welche eine effiziente Suche in gigantischen Datenmengen ermöglichte. Die Ergebnisse der Suche enthalten dabei bewusst Fehler, sind deswegen aber erst effizient berechenbar. Der Algorithmus stellt sicher, dass kein Treffer übersehen wird. Es gibt also höchstens zusätzliche falsche Treffer. Nur deswegen ist dieser Ansatz überhaupt sinnvoll nutzbar. Eine Anwendung war das Durchsuchen von DNA-Datenbanken, welche Petabyte an Datenmengen umfassen. Trotzdem darf bei einer Suche natürlich nichts übersehen werden.

Die erste Programmieraufgabe gab es in Form des bekannten Vertex-Cover-Problems. Hier muss ein Netz von Knoten und Verbindungen möglichst effizient abgedeckt werden. Dazu können Knoten markiert werden, um deren direkte Verbindungen für die Abdeckung zu verwenden. Ziel ist es nun, ein gegebenes Netz mit möglichst wenig markierten Knoten komplett abzudecken.

Dieses Problem ist eines der schwersten der Informatik und kann in vielen Fällen immer noch nicht effizient gelöst werden. Unser Algorithmus suchte daher nur eine Annäherung an die perfekte Lösung. So gelang es uns, mit einer Abweichung von rund 1% von der exakten Lösung alle uns gegebenen Beispiele in wenigen Sekunden zu lösen.
(Code: https://github.com/lukaskesch/FakeNews)

Das Studententeam, welches die Aufgabe in einem Vortrag vorgestellt hatte, präsentierte im Anschluss eine Kombination von Algorithmen, welche letztendlich die perfekte Lösung in nur wenigen Nanosekunden berechnete. Von uns konnte natürlich keiner mithalten, schließlich hatten wir nur wenige Stunden für unser Programm zur Verfügung gehabt.

Am meisten Zeit nahmen jedoch die Projektphasen ein. Aus drei verschiedenen Projekten wählten wir den Bau eines Compilers aus.

Doch was genau ist ein Compiler? Der Prozessor im Computer versteht letztendlich nur einfachste Befehle (Maschinencode), in einer für den Menschen besser lesbaren Variante auch Assembler genannt. Diese direkten Anweisungen zu schreiben bietet zwar auch Vorteile, ist aber in den meisten Fällen schlichtweg zu aufwendig und abstrakt.

Deswegen wird heute nur noch selten mit Maschinencode programmiert, stattdessen nutzt man für den Menschen besser verständliche höhere Programmiersprachen. Hier kommt nun der Compiler ins Spiel. Dieser agiert als Übersetzer zwischen den höheren Programmiersprachen und dem Maschinencode. Moderne Compiler optimieren dabei zusätzlich den Code oder bieten andere Erweiterungen, um beste Performance zu garantieren oder das Programmieren schlichtweg zu erleichtern.

Unsere Aufgabe war es nun, innerhalb eines knappen Tages Ansätze eines solchen Compilers zu programmieren.

Ein Compiler besteht dabei aus drei großen Teilen. Zuerst wird der Code in Blöcke unterteilt, und diese werden entsprechend bezeichnet. Diese Aufgabe übernimmt der sogenannte “Tokenizer”. Festgelegte Schlüsselwörter werden also beispielsweise als “Schlüsselwort-Block” bezeichnet und weitergegeben. Im nächsten Schritt werden diese Blöcke interpretiert und in eine Baumstruktur gegliedert. Dieses Gliedern (engl. “parsen”) der Blöcke übernimmt der “Parser”. Die Baumstruktur enthält eine abstrahierte Form der Anweisungen und kann vielseitig weiterverwendet werden. Mittels dieser Baumstruktur wird dann im letzten Schritt der finale Maschinencode generiert. Der “Generator” kennt den Maschinencode der einzelnen Teile des Baums und arbeitet diesen nun schrittweise ab. So entsteht der ausführbare Maschinencode.

Mittels unseres Compilers konnten wir nun bereits ein kleines Programm zur Multiplikation von Ganzzahlen schreiben und in Maschinencode übersetzen lassen. Besonders schwierig stellte sich dabei die Verwaltung des Speichers dar, da dieser im Maschinencode manuell verwaltet werden muss. Der Compiler muss also eine Menge zusätzliche Arbeit leisten, um den Code korrekt umzusetzen. Der Programmierer macht sich hingegen in einer höheren Programmiersprache keine Gedanken über solche Aspekte.
(Code: https://github.com/FlorianPallas/JFI-Compiler)

Innerhalb dieser vier Tage haben wir beide eine Menge gelernt und vieles vertieft. Zudem ist es immer spannend, Gleichgesinnte kennenzulernen und zusammen zu arbeiten. Bei einer erneuten Teilnahme am Wettbewerb würden wir diese Möglichkeit definitiv wieder ergreifen!