Thesis

Seit fast zwei Monaten schreibe ich jetzt am Lehrstuhl für Betriebssysteme meine Bachelorarbeit:

Eine generische Speicherverwaltung mit Hilfe von Seitentabellen für ein
minimalistisches Betriebssystem

oder auf Englisch

A generic memory management with paging for a minimalistic operating
system

Huh?! Was ist das? Was machst du da?“ Da dies häufig die erste Reaktion von Freunden und Familie ist, möchte ich versuchen das Thema meiner Arbeit hier kurz und verständlich vorzustellen. Wer Interesse an einem tieferem Verständnis und technischen Details hat, lade ich gerne zu meinem Abschlussvortrag Ende Mai ein. Zu dem „Was machst du da?“ kann ich schon einmal sagen, dass ich viel am Programmieren bin und dabei unheimlich viel praktische Erfahrung sammele. Und es nen riesen Spaß macht 😀

Meine Arbeit dreht sich also um Betriebssysteme. Die Aufgabe von Betriebssystemen ist es verfügbare Ressourcen zu verwalten und diese mit einer einheitlichen Schnittstelle dem Nutzer zu Verfügung zu stellen. In meinem Fall arbeite ich an der Verwaltung des Arbeitsspeichers.
Arbeitsspeicher (engl. RAM für Random Access Memory) findet man in Handys, TVs, MP3 Playern, Laptops und vor allem in Server und Hochleistungsrechnern. Es ist einer recht schneller dafür auch leicht flüchtiger Speicher, den man gut mit dem menschlichen Kurzeitgedächtnis vergleichen kann. „Random Access“ steht für einen wahlfreien Zugriff, also dass man alle Informtionen ohne vorheriges „Spulen“ oder „Nadel umsetzen“ abfragen kann – um mal in nostalgischen Analogien zu sprechen.

quote-Bill-Gates-640k-ought-to-be-enough-for-anybody-89027

Dieses Zitat, das gerne dem Microsoft Gründer Bill Gates zugeschrieben wird, dürfte vielleicht einigen von euch bekannt sein. Waren im Jahr 1981 noch 640 KB das Maß der Dinge haben heutige Server 64 GB und mehr. Dies entspricht verblüffend genau einer Verdopplung der Kapazität alle zwei Jahre wie es Gordon Moore bereits schon 1965 postuliert hat.

Aber nun mal wieder zurück zu meiner Arbeit: diese rasante Entwicklung der Speicherkapazität hat Betriebssysteme vor einigen Jahre vor wesentliche Probleme gestellt.
Stellen wir uns vor – ähnlich wie die Größe des Speichers, hätte sich die Anzahl der Autohalter in Deutschland entwickelt. Den Zulassungsstellen wären recht schnell die Nummernschilder ausgegangen, da es einfach nicht genügend unterschiedliche Kombinationen von Landkreis und Buchstaben/Zahlen gäbe. Und wer möchte schon das gleiche Nummernschild wie sein Nachbar haben. Jedes Auto muss also eindeutig identifizierbar und jeder Speicherplatz eindeutig adressierbar sein. Mit zunehmender Anzahl an Autohaltern, bzw. der Speicherkapazität, steigt daher auch Komplexität der Verwaltung.

In meinem Beispiel könnte man dieses Problem beispielsweise durch einen zusätzlichen Buchstaben für das Bundesland auf jedem Nummernschild lösen. Man denke an die Einführung der EU-Kennzeichen.
Und damit bin ich auch schon beim Ziel meiner Arbeit: Ich möchte dieses Verwaltungsproblem für beliebe große Speicherkapazitäten und beliebig viele Verwaltungsinstanzen lösen ohne die Kompexität dadurch zu steigern.

Puh, das soll erst einmal reichen. Ende Mai werde ich diese, meine erste wissenschaftliche, Arbeit abschließen. So lange behalte ich meine Lösung noch für mich :p

Informatik Präsentation: Künstliche Intelligenz

Die Natur als Vorbild der KI?
Die Natur als Vorbild der KI?

Im letzten Halbjahr haben wir unserer komplette Informatiknote durch eine Präsentationsprüfung ersetzt. Die Themen konnten wir uns weitestgehend selbst aussuchen. Die sechs Schüler aus unserem Kurs teilten sich in drei Zweiergruppen auf, die jeweils 20 Minuten Zeit hatten ihr Thema vorzustellen. Mit dem anschließenden Kolloquium war die Zeit für uns also alle knapp bemessen. So musste ich mich mit meinem Teil wirklich ranhalten.

Unsere Präsentation kann mal wirklich als sehr allgemeine und kurze Einführung in die KI verstehen. Nach einer kurzen Definition der Begriffe Intelligenz und künstliche Intelligenz berichten wir kurz über die Geschichte der KI Forschung und deren Anwendungsgebiete. Anhand von einem Beipspiel, der Particle Swarm Optimization, wollen wir einen kurzen Einblick in die vielfältigen Anwendungen von KI geben. Ein kurzer philosophischer Ausblick in die Zukunft schließt die Präsenation ab.

Hier ist wie gewohnt der Link zur PDF Version

TSP: Das Travelling Salesman Problem

Vor einigen Wochen beschäftigten wir uns im Informatikunterricht mit dem Travelling salesman problem. Ohne näher auf die existierenden Algorithmen zum Lösen dieses Problems einzugehen lernten wir, dass es sich bei diesem Problem um ein NP-Vollständiges Problem handelt. Das TSP ist also eine Problemstellung die sich nicht in polynomieller Zeit lösen lässt. Anders ausgedrückt, lässt sich die Laufzeitkomplexität dieses Problems in Abhängigkeit von der Problemgröße n (Anzahl der Knoten bzw. Städte) nicht ausschließlich mit einem Polynom beschreiben.

Es existieren zwar einige Algorithmen die die perfekte Lösung mehr oder weniger gut annähern können und dafür nur eine zu n quadratische Komplexität besitzen (O(n²)).

Eine perfekte Lösung lässt sich bis heute praktisch aber noch nicht exakt bestimmen. TSP: Das Travelling Salesman Problem weiterlesen

n-Damen Problem

Für meine morgige Informatik-Klausur habe ich mich mal wieder an C++ gewagt um einen Algorithmus zu implementieren. Die Hauptthemen der Klausur werden das n-Dame Problem und das Josephus Problem sein.

JS, PHP & CSS Frontend

Für das n-Damen-Problem habe ich eine iterative Backtracking-Implementation in C++ geschrieben. Gleichzeitig ist es mein erstes funktionsfähiges und komplexeres C++ Programm 😉

Um euch meine Ergebnisse zeigen zu können, habe ich mich bei der PHP, JS & CSS Version meines Freundes Micha bedient und sie leicht angepasst.

Das PHP-Script ruft über den Backtick-Operator das C++ Programm auf und stellt es anschließen mit JS und CSS dar.

Um den Server zu schonen habe ich die maximale Feldgröße auf 13 beschränkt. Das sind zu mindestens schon mal 5 Damen mehr als bei der PHP-Version.

Ohne die Beschränkung sind auch Problemgrößen bis 16 in einem angemessenen Zeitrahmen zu bewältigen. An den Weltrekord (25 Damen) komme ich jedoch noch nicht 😉

Wer interesse an dem Quellcode hat, kann sich einfach per Mail melden.