\( \newcommand{\data}{\textnormal{data}} \newcommand{\lower}{\textnormal{lower}} \newcommand{\upper}{\textnormal{upper}} \newcommand{\array}{\textnormal{array}} \newcommand{\depth}{\textnormal{depth}} \newcommand{\height}{\textnormal{height}} \newcommand{\BST}{\textnormal{BST}} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\lognpone}{\ceil{\log_2(n+1)}} \newcommand{\bitsize}{\textnormal{bitSize}} \newcommand{\mult}{\textnormal{mult}} \newcommand{\inneighbors}{\textnormal{inNeighbors}} \newcommand{\outneighbors}{\textnormal{outNeighbors}} \newcommand{\neighbors}{\textnormal{neighbors}} \newcommand{\indeg}{\textnormal{indeg}} \newcommand{\outdeg}{\textnormal{outdeg}} \newcommand{\scc}{\textnormal{scc}} \newcommand{\R}{\mathbb{R}} \newcommand{\val}{\textnormal{val}} \newcommand{\dist}{\textnormal{dist}} \newcommand{\flows}{\textnormal{flows}} \)

1. Einführung

Schöne Einleitung schreiben. Wie es sich in PP und TI einfügt.

Dieses Vorlesungsskript ist der zentrale "Landeplatz" für alle Materialien, Beispiele, Code, Übungsaufgaben. Ich gebe keine separaten Übungsblätter aus, sondern verweise auf die Übungsaufgaben in diesem Skript. Hier ist eine Liste der Dinge, die Sie sich für diesen Kurs besorgen sollten:

Literatur und Software

  • Das Buch Algorithmen und Komplexität. Wagenknecht, Christian. Leipzig: Fachbuchverlag im Hanser Verlag München, 2003.
  • Das Buch Introduction to Algorithms bzw. Algorithmen - eine Einführung von Cormen, Leiserson, Rivest und Stein (im Volksmund einfach CLRS genannt). Wenn Sie sich im Hochschulnetz befinden, können Sie bei de Gruyter auf eine pdf-Version zugreifen. .
  • Java. Wenn wir kompliziertere Algorithmen implementieren, dann vorzugsweise in Java.
  • Python. Sie sollten auf Ihrem Rechner oder auf einem Hochschulrechner mit Python programmieren können. Gerade, wenn wir Algorithmen schreiben, die mit sehr großen Zahlen arbeiten müssen, dann ist Python bequemer als Java.
  • Gerade am Anfang werden wir manche Datenstrukturen (Suchbäume) in Elm implementieren.

Überschneidung mit Theoretischer Informatik und Unterschiede

Wenn Sie meine Vorlesung Theoretische Informatik (TI) besucht haben, dann werden Sie sicherlich ein paar Überschneidungen feststellen. Gerade am Anfang werden wir Sortieralgorithmen und Suchbäume untersuchen. Nun allerdings mit einem stärkeren Fokus auf Laufzeitkomplexität. In TI haben Sie ja auch bereits einige Algorithmen kennengelernt, nur dass wir sie vielleicht nicht exakt so benannt haben. LL-Parser, LR-Parser, Methoden zur Umwandlung einer regulären Grammatik in einen endlichen Automaten; oder in einen regulären Ausdruck: all dies sind Algorithmen. Ein wesentlicher Unterschied zur TI-Vorlesung ist, dass die Algorithmen in dieser Vorlesung vielfältiger sind, also nicht wie in TI auf formale Sprachen fokussiert; und dass unser Augenmerk sehr stark auf der Laufzeitkomplexität liegen wird. Uns wird es nun also darum gehen, zu untersuchen, wie sich die Laufzeit des Algorithmus in Abhängigkeit zur Größe des Inpust verhält. Der Fokus auf die Implementierung wird schwächer ausfallen. Ging es in Programmierparadigmen und Theoretischer Informatik mit der Programmierung in Elm auch viel darum, sich über sauberes Programmieren, gute Typensysteme etc. Gedanken zu machen, so werden wir bei der Implementierung hier nur eins zum Ziel haben: den Algorithmus zum Laufen zu bringen. Daher werden wir bei der Implementierung von Algorithmen vorzugsweise mit Java arbeiten.