Eine kleine Übersicht über die Basismodule

Im folgenden werden die drei Pflichtveranstaltungen, die jeder Bachelor-Student absolvieren muss vorgestellt: Im Alltag eines Informatikers gibt es für sie oder ihn immer und immer wieder Aufträge, die sie/er zu bearbeiten hat. Hierbei handelt es sich um Probleme, die aus der ''realen'' Welt stammen und welche in Software oder sogar als Softwareprojekt umgesetzt werden sollen. Eine zentrale Frage hierbei ist: Wie machen wir das? Die ''typische'' Vorgehensweise ist: Wir betrachten hierzu mal ein Beispiel:
Die strenge Ordnungsbeamtin Helga von San Theoretika möchte möglichst alle Falschparker in ihrer Stadt erwischen und ordentlich Knöllchen verteilen. Da wäre es doch ganz geschickt, wenn sie durch jede Straße einmal durchläuft und alle dort parkenden PKWs überprüft. Leider hat der Tag nur 24 Stunden und Helga möchte pünktlich Feierabend machen! Es wäre daher sinnvoll, wenn sie keine Straße doppelt durchlaufen muss.
Wir können uns nun überlegen: Wie kann Helga einmal durch alle Straßen laufen ohne diese doppelt zu besuchen? Welchen Weg muss sie laufen? Antworten für dieses Problem und sehr viele weitere Probleme aus dem Alltag finden wir schon in den Basisveranstaltungen der Theoretischen Informatik.

Diskrete Modellierung

Wie wir schon in der Einleitung gesehen haben benötigen wir zuerst zur Lösung der Probleme ein ''Modell''. Ein Modell ist hier eine mathematische Abstraktion eines Sachverhalts, die sich nur auf die zur Problemlösung wesentlichen Tatsachen beschränkt. Um erstmals so ein Problem modellieren zu können benötigen wir zunächst das Wissen, wie wir diese Probleme überhaupt modellieren können. Dazu werden in dieser Veranstaltungen die wichtigen grundlegenden Modellierungstechniken vorgestellt (wie z.B. Aussagenlogik, Graphen, Logik erster Stufe, Automaten, kontextfreie Grammatiken). Wir gehen kurz beispielhaft auf einige der Modellierungstechniken ein:

Informationen zur Veranstaltung

Empfohlene Vorkenntnisse: Stoff aus dem Vorsemesterkurs Informatik zum Wintersemester
Benötige Module: Keine
CP: 8 CP (3 Vorlesungsstunden, 2 Übungsstunden, 1 Fragestunde pro Woche)
Rhythmus: jedes WiSe
Empfehlung: 1. Semester (Start im WiSe), 2. Semester (Start im SoSe)
Wann findet die Vorlesung statt? Di 8-10 c.t., Do 8-9 c.t. (und Do 9-10 c.t. gibt es eine Fragestunde)
Link zur Veranstaltung

Datenstrukturen

Nachdem wir in der Diskreten Modellierung gelernt haben, wie wir aus einem realen Problem heraus ein Modell bauen können, stellen sich nun berechtigt die Fragen: Dazu müssen wir uns einen Algorithmus, also eine Handlungsvorschrift überlegen, der das Problem knackt. Um den Algorithmus effizient zu implementieren führt man Datenstrukturen ein, die auch in der Modellbildung eine Rolle spielen können. Beispielsweise lässt sich ein Graph darstellen durch eine Liste
Knoten Nachbar
Franz Otto, Bernd
Otto Franz
Bernd Franz
So haben wir die Möglichkeit den Graphen von oben darzustellen. Für jeden Knoten merken wir uns eine Liste von Knoten, zu der wir eine Kante haben. Der fertige Programmcode könnte dann so aussehen:

struct Knoten {
int name;
Knoten * next;}
AListe = Knoten[];

Um einem Algorithmus anzusehen, wann er effizient ist, wird das Konzept der Laufzeitanalyse eingeführt. Damit sind wir in der Lage für große Eingaben zu messen, welche Algorithmen ''besser'' als andere Algorithmen hinsichtlich ihrer Laufzeit sind. Kann ein Algorithmus ein Problem innerhalb von drei Stunden lösen oder wird er mehrere Jahre brauchen? Mit der Laufzeitanalyse sind wir in der Lage abzuschätzen, welche Datenstrukturen für bestimmte Algorithmen geeignet sind und welche nicht.

Informationen zur Veranstaltung

Empfohlene Vorkenntnisse: Diskrete Modellierung, Programmierkenntnisse einer imperativen Programmiersprache (z.B. Python, Java, ...)
Benötige Module: Keine
CP: 5 CP (2 Vorlesungsstunden pro Woche und 2 Übungsstunden alle zwei Wochen)
Rhythmus: jedes SoSe
Empfehlung: 2. Semester (Start im WiSe), 1. Semester (Start im SoSe)
Wann findet die Vorlesung statt? Di 8-10 c.t.

Theoretische Informatik 1

Es bleibt in unserem ganzen Konstrukt noch eine Frage zu klären: Wir haben nun unser Modell gebaut und implementiert. Was ist aber mit der ''eigentlichen Arbeit''? In der Vorlesung ''Theoretische Informatik 1'' werden hier Ansätze für die Antwort dieser Fragen gegeben. Zunächst werden Algorithmen angeschaut, die eine Liste von Zahlen sortieren können, sogenannte Sortieralgorithmen. Die nächste Überlegung wäre die Umsetzung von Algorithmen auf Graphen. Hier werden klassische Beispiele für Graphalgorithmen vorgestellt. Außerdem wird noch auf die verschiedenen Methoden eingegangen, wie man Algorithmen entwerfen kann. Weitere sehr spannende Fragen sind:

Informationen zur Veranstaltung

Empfohlene Vorkenntnisse: Diskrete Modellierung, Datenstrukturen, Programmierkenntnisse einer imperativen Programmiersprache (z.B. Python, Java, ...)
Benötige Module: Keine
CP: 10 CP (4 Vorlesungsstunden, 2 Übungsstunden, 0.5 Ergänzungsstunden pro Woche)
Rhythmus: jedes WiSe
Empfehlung: 3. Semester (Start im WiSe), 4. Semester (Start im SoSe)
Wann findet die Vorlesung statt? Di 8-10 c.t., Do 8-10 c.t.

... zurück zum Beispiel

Wir greifen noch einmal das Beispiel von oben auf. Wir möchten jetzt ein Programm entwerfen, das der Ordnungsbeamtin Helga hilft einen optimalen Weg zu finden.

Überblick über die Module im Bereich "Grundlagen der Informatik" im Bachelor-Studiengang: