BA-INF 032 - Algorithmen und Berechnungskomplexität I

Termine

Art Uhrzeit Wo Datum LP Dozent und Übungsleitung
V4 Dienstag 12:15 - 13:45
Donnerstag 12:15 - 13:45
AVZ III / HS 1 10. Oktober 2017
- 25.01.2018
5,5 PD Dr. Elmar Langetepe
David Kübel, Clemens Rösner
Ü2 Übungstermine
keine Übungen in KW44
16. Oktober 2017
- 02.01.2018
3,5 Lukas Drexler, Florian Glaesser, Jan Höckendorff,
Moritz Wiemker, Christian Winkler
1. Klausurtermin Mo. 12:00 - 15:00 HSZ / HS 1 + 2 05. Februar 2018
2. Klausurtermin Mi. 09:00 - 12:00 HSZ / HS 1 + 2 04. April 2018
Fragestunde Di. 12:15 - 13:45 AVZ III / HS 1 30. Januar 2018

Inhalt

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

Prüfungen und Klausureinsicht

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

Fragestunde

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

Übungen

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!

Abgabe in Teams:

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

Wann Wo Tutor
1 Montag 12:00 - 13:30 AVZ III / A6c Lukas Drexler
2 Montag 12:15 - 13:45 AVZ III / A7a Moritz Wiemker
3 Montag 14:15 - 15:45 AVZ III / A7a Moritz Wiemker
4 Dienstag 08:15 - 09:45 AVZ III / A301 Lukas Drexler
5 Mittwoch 12:15 - 13:45 AVZ III / A301 Christian Winkler
6 Mittwoch 14:15 - 15:45 AVZ III / A301a Christian Winkler
7 Donnerstag 08:15 - 09:45AVZ III / A7a Florian Glaesser
8 Donnerstag 10:15 - 11:45AVZ III / A301 Florian Glaesser
9 Freitag 10:15 - 11:45 AVZ III / A7a Jan Höckendorff
10 Freitag 12:15 - 13:45 AVZ III / A301 Jan Höckendorff

Übungsblätter

  • 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)

Abgabe der Übungsblätter

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.

Anmeldung zu den Übungen:

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

Anrechnung des Übungserfolges:

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

lehre/ws1718/algorithmen-und-berechnungskomplexitaet-1.txt · Zuletzt geändert: 2018/04/09 11:01 von kuebel

Benutzer-Werkzeuge