Berichte 19/20

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!