BA-INF 032 - Algorithmen und Berechnungskomplexität I

In dieser Vorlesung werden wir uns mit dem Entwurf und der Analyse von Algorithmen beschäftigen. Ein Algorithmus ist eine Handlungsvorschrift zur Lösung eines Problems, die so präzise formuliert ist, dass sie von einem Computer ausgeführt werden kann. Algorithmen sind heute so allgegenwärtig, dass sie kaum wahrgenommen oder gewürdigt werden. Wie selbstverständlich nutzen wir Navigationsgeräte, um den besten Weg vom Start zum Ziel zu bestimmen, oder Suchmaschinen, um innerhalb kürzester Zeit riesengroße Datenmengen zu durchsuchen. Dass dies überhaupt möglich ist, liegt zum Teil an der immer besseren Hardware, zu einem viel größeren Teil liegt es aber an den cleveren Algorithmen, die für diese Anwendungen entwickelt wurden. In dieser Vorlesung werden wir Techniken zum Entwurf und zur Analyse von Algorithmen kennenlernen und diese nutzen, um effiziente Algorithmen für zahlreiche grundlegende Probleme zu entwerfen.

Die Vorlesung basiert auf folgendem Skript. Bitte beachten Sie, dass wir im Laufe des Semesters Änderungen und Erweiterungen vornehmen.
Änderung 1 (7.11.2017): Abschnitt Greedy-Algorithmen ergänzt, Abschnitt Sweep hinzugefügt.
Änderung 2 (4.12.2017): Abschnitt Datenstrukturen, kleinere Typos beseitigt.
Änderung 3 (10.1.2018): Abschnitt Lineare Programmierung.
Änderung 4 (16.1.2018): Abschnitt Lineare Programmierung, (Simplex Alg./Dictionaries/Initialisierung).
Änderung 5 (17.1.2018): Abschnitt Lineare Programmierung, (Initialisierung/Iteration/Terminierung/Beispiele).
Änderung 6 (26.1.2018): Tippfehler korrigiert

Die Klausureinsichten sind abgeschlossen. Bitte wenden Sie sich ab sofort zur Einsichtnahme an das Prüfungsamt.

Zu Ihrer Unterstützung in der Vorbereitung auf die Klausur werden in einer Fragestunde am 30.01.2018 konkrete Fragen zu Vorlesungs- und Übungsinhalten beantwortet. Folgende Fragen wurden eingesendet und werden auf jeden Fall behandelt.

Allgemeine Fragen:

• Struktur der Klausur: Gibt es ein festes Verhältnis zwischen Anwendungsaufgaben, Wissensteil/Beweisaufgaben, etc.?
• Anwendung des Mastertheorems mit Beispielen
• Sind die nicht im Skript behandelten Definitionen (o(n) „klein O“ und Rot-Schwarz-Baum) relevant?
• Wenn eine Aufgabe sagt, man solle einen Algorithmus angeben, soll man dann auch seine Korrektheit beweisen? Und wie sieht es da mit Laufzeit und Speicherbedarf aus?
• Übersicht zu Laufzeiten und Speicherbedarf aller Algorithmen
• Wenn in der Klausur Definitionen abgefragt werden wie genau muss die Antwort gegeben werden?

Datenstrukturen:

• Definition Höhe und Tiefe im Binärbaum. Dabei bitte auch was ist die Höhe null? Ist es ein Knoten ist es ein Blatt ist es ein Knoten mit zwei Blättern?
• Löschungen im AVL Baum. Welches Objekt wird verwendet um das gelöschte zu ersetzen? Nächst kleineres / nächst größeres.
• Muss man im AVL Baum die leeren Blätter malen?
• Wie viele Elemente hat ein B-Baum Knoten der Ordnung k?
• Höhe und Ordnung im B-Baum. Welche Höhe hat ein B-Baum der Ordnung k mit n Elementen?
• Schwarztiefe von Rot-Schwarz-Bäumen.
• Was ist bei der Kollisionsbehandlung von Hashtabellen mit dem Belegungsfaktor alpha gemeint und was sagt das in der Formel (1+alpha/2)?

Graphenalgorithmen

• Warum gilt im Kruskal Algorithmus die Laufzeit von O(|E| * log(|V|^2) = O(|E| * log(|V|)? Wohin verschwindet die hoch 2?

Lineare Programmierung

• Anwendung des Simplex-Algorithmus mit relevanten Pivotregeln und prüfungsrelevanten Variationen

Voraussetzung für die Zulassung zur Prüfung ist das Erreichen von mindestens 50% der Übungspunkte und das Präsentieren zweier Übungsaufgaben. Die Übungen finden einmal pro Woche statt. Die Übungsaufgaben werden dienstags zum Download bereitgestellt und in der darauffolgenden Woche am Dienstag vor der Vorlesung im Postfach abgegeben. Eine weitere Woche später sind diese korrigiert und werden in den Übungen besprochen. Da es voraussichtlich 12 Übungsblätter mit je 24 regulären Punkten gibt, hat man mit 144 Übungspunkten die 50% Hürde auf jeden Fall geschafft!

Die Aufgaben dürfen in festen Teams von bis zu drei Studierenden der gleichen Übungsgruppe bearbeitet werden.

• Präsenzblatt (keine Abgabe, Besprechung KW 42)
• Übungsblatt 1 (Abgabe bis Dienstag, 17.10., 12:00 im Postkasten in der Römerstraße, Besprechung KW 43)
• Übungsblatt 2 (Abgabe bis Dienstag, 24.10., 12:00 im Postkasten in der Römerstraße, Besprechung KW 45)
• Übungsblatt 3 (Abgabe bis Dienstag, 07.11., 12:00 im Postkasten in der Römerstraße, Besprechung KW 46)
• Übungsblatt 4 (keine Abgabe, keine Besprechung)
• Übungsblatt 5 (Abgabe bis Dienstag, 14.11., 12:00 im Postkasten in der Römerstraße, Besprechung KW 47)
• Übungsblatt 6 (Abgabe bis Dienstag, 21.11., 12:00 im Postkasten in der Römerstraße, Besprechung KW 48)
• Übungsblatt 7 (Abgabe bis Dienstag, 28.11., 12:00 im Postkasten in der Römerstraße, Besprechung KW 49)
• Übungsblatt 8 (Abgabe bis Dienstag, 05.12., 12:00 im Postkasten in der Römerstraße, Besprechung KW 50)
• Übungsblatt 9 (Abgabe bis Dienstag, 12.12., 12:00 im Postkasten in der Römerstraße, Besprechung KW 51)
• Übungsblatt 10 (Abgabe bis Dienstag, 19.12., 12:00 im Postkasten in der Römerstraße, Besprechung KW 2)
• Übungsblatt 11 / Probeklausur (Abgabe bis Dienstag, 09.01., 12:00 im Postkasten in der Römerstraße, Besprechung KW 3)
• Übungsblatt 12 (Abgabe bis Dienstag, 16.01., 12:00 im Postkasten in der Römerstraße, Besprechung KW 4)
• Übungsblatt 13 (Abgabe bis Dienstag, 23.01., 12:00 im Postkasten in der Römerstraße, Besprechung KW 5)

Auf die Abgabe sind oben rechts auf dem ersten Blatt die vollständigen Namen aller Gruppenmitglieder und die Nummer der Übungsgruppe gut lesbar zu notieren. Abgaben aus mehreren Blättern sind zu heften. Abgaben, die diese Voraussetzungen nicht erfüllen werden von Korrektur und Wertung ausgeschlossen.

Die Anmeldung zu den Übungsgruppen erfolgte über das Tutorienvergabesystem (TVS) und ist abgeschlossen.

Übungserfolg aus vorherigen Semestern wird automatisch in BASIS übernommen, bitte überprüfen Sie das zusätzlich selbst.