BA-INF032 - Algorithmen und Berechnungskomplexität I

Termine

Art Wann Wo Beginn LP Dozent und Übungsleitung
V4 Dienstag 12:30 - 14:00
Donnerstag 12:30 - 14:00
AVZ III / HS 1
AVZ III / HS 1
20. Oktober 2015 5,5 Prof. Rolf Klein
Barbara Schwarzwald, David Kübel
Ü2 Übungstermine 26. Oktober 2015 3,5 Philipp Bruckschen, Sergio Chumachero, Jens Harder,
Martin Kretschmer, Pascal Mueller

Prüfungen

Die Klausureinsicht für die Nachklausur findet am Freitag, dem 8.4., zwischen 14:00 und 16:00 im Raum E.08 in der Friedrich-Ebert-Allee 144 statt. Wer zu diesem Termin keine Zeit hat, kann auch Donnerstag, 7.4. zwischen 14:00 und 15:00 kommen, muss sich aber spätestens bis Mittwoch, dem 6.4., per Email anmelden.

Die Prüfung findet am Samstag (!), dem 20.2.2016 ab 9:30 im Hauptgebäude der Universität (Regina-Pacis-Weg) statt. Bitte seien Sie schon ein paar Minuten früher da, damit wir möglichst pünktlich anfangen können. Die Dauer der Klausur wird 120 Minuten betragen.

Die Klausur wird in Hörsaal 10 (X) und Hörsaal 1 (I) stattfinden. Die Verteilung der Studenten auf die Hörsäle erfolgt nach dem Anfangsbuchstaben des Nachnamens wie folgt:

A-Q: Hörsaal 10 (Hörsaal X)
R-Z: Hörsaal 1 (Hörsaal I)

Bitte denken Sie daran, einen aktuellen Lichtbildausweis (z.B. Personalausweis) und ihren Studentenausweis mitzubringen.

Die Nachprüfung findet am Dienstag, den 29.3.2016 zwischen 8:30 und 11:00 im Hauptgebäude in Hörsaal X statt.

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, das den gesamten Semesterstoff abdeckt.
Änderung 1 (13.11.2015): Geringfügige Ausbesserung von Fehlern im ersten Teil und Ergänzung von Kapitel 6 (ab Seite 51).
Änderung 2 (18.12.2015): Klarifizerung des Löschens aus Binärbäumen (jetzt immer aus dem linken Teilbaum), geringfügiges Ausbessern von kleineren Fehlern und Ergänzung von Kapitel 7 und 8.
Änderung 3 (21.12.2015): Vereinfachungen im Beweis zu Theorem 20 und Herausnehmen von Kapitel 8 (vorübergehend).
Änderung 4 (19.1.2016): Ergänzung von Kapitel 8.

Als zusätzliche Hilfestellung gibt es die Formelsammlung, die einige gängige Formeln und Umformungen, die im Skript verwendet werden, auflistet.

Eine grafische Übersicht über die bisher vorgestellten Werkzeuge und die damit gelösten Probleme findet sich in Suchen und Sortieren, Geometrische Probleme, Graphenprobleme und Andere Probleme.

Übungen

Information: Zwischen dem 21.12.15 und dem 8.1.16 finden keine Übungen statt.

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. Die Aufgaben dürfen in festen Gruppen von bis zu drei Studenten bearbeitet werden. Voraussetzung für die Zulassung zur Prüfung ist ein Erreichen von mindestens 50% der Übungspunkte und das Vorrechnen zweier Übungsaufgaben.

Wann Wo Tutor
1 Montag 8:15 - 9:45 AVZ III / A301 Jens Harder
2 Montag 12:15 - 13:45 AVZ III / A6c Sergio Chumachero
3 Montag 12:15 - 13:45 AVZ III / A7a Pascal Müller
4 Montag 14:15 - 15:45 AVZ III / A7a Pascal Müller
5 Mittwoch 12:15 - 13:45 AVZ III / A7a Sergio Chumachero
6 Mittwoch 12:15 - 13:45 AVZ III / A301 Philipp Bruckschen
7 Mittwoch 14:15 - 15:45 AVZ III / A301a Philipp Bruckschen
8 Donnerstag 10:15 - 11:45AVZ III / A301 Jens Harder
9 Freitag 10:15 - 11:45 AVZ III / A7a Martin Kretschmer
10 Freitag 12:15 - 13:45 AVZ III / A301 Martin Kretschmer
11 Montag 12:15 - 13:45 AVZ III / A7b Barbara Schwarzwald
12 Donnnerstag 8:15 - 9:45 AVZ III / A7a David Kübel

Übungszettel

  • Präsenzzettel (keine Abgabe, Besprechung 26.-30.10.)
  • Übungszettel 1 (Abgabe bis Dienstag, 27.10., 12:30 im Postkasten in der Römerstraße, Besprechung 02.11. - 06.11.)
  • Übungszettel 2 (Abgabe bis Dienstag, 03.11., 12:30 im Postkasten in der Römerstraße, Besprechung 09.11. - 13.11.)
  • Übungszettel 3 (Abgabe bis Dienstag, 10.11., 12:30 im Postkasten in der Römerstraße, Besprechung 16.11. - 20.11.)
  • Übungszettel 4 (Abgabe bis Dienstag, 17.11., 12:30 im Postkasten in der Römerstraße, Besprechung 23.11. - 27.11.)
  • Übungszettel 5 (Abgabe bis Dienstag, 24.11., 12:30 im Postkasten in der Römerstraße, Besprechung 30.11. - 04.12.)
  • Übungszettel 6 (Abgabe bis Dienstag, 01.12., 12:30 im Postkasten in der Römerstraße, Besprechung 07.12. - 11.12.)
  • Übungszettel 7 (Abgabe bis Dienstag, 08.12., 12:30 im Postkasten in der Römerstraße, Besprechung 14.12. - 18.12.)
  • Übungszettel 8 (Abgabe bis Dienstag, 15.12., 12:30 im Postkasten in der Römerstraße, Besprechung 11.01. - 15.01.)
  • Übungszettel 9 (Abgabe bis Dienstag, 12.01., 12:30 im Postkasten in der Römerstraße, Besprechung 18.01. - 22.01.)
  • Übungszettel 10 (Abgabe bis Dienstag, 19.01., 12:30 im Postkasten in der Römerstraße, Besprechung 25.01. - 29.01.)
  • Übungszettel 11 (Abgabe bis Dienstag, 26.01., 12:30 im Postkasten in der Römerstraße, Besprechung 01.02. - 05.02.)
  • Übungszettel 12 (Abgabe bis Dienstag, 02.02., 12:30 im Postkasten in der Römerstraße, Besprechung 08.02. - 12.02.)
  • Übungszettel 13 (keine Abgabe, dieser Zettel dient nur zur selbständigen Wiederholung des Stoffes aus Kapitel 8)

Abgabe der Übungszettel

Bitte den vollständigen Namen sowie die Nummer der Übungsgruppe (s.o.) gut lesbar oben aufs erste Blatt schreiben. Bei gemeinsamer Abgabe bitte die Namen jedes Gruppenmitglieds notieren. Gruppen dürfen nur aus Teilnehmern derselben Übungsgruppe gebildet werden. Sorgt bitte bei mehrblättrigen Abgaben dafür, dass zusammengehörige Blätter zusammenhalten, damit keine losen Zettel im großen Stapel untergehen.

Anmeldung zu den Übungen:

Die Anmeldung zu den Übungsgruppen erfolgte über das Tutorienvergabesystem (TVS) und ist abgeschlossen. Wer noch keine Übungsgruppe oder terminliche Probleme mit dem zugeteilten Termin hat, meldet sich bitte zeitnah bei Barbara Schwarzwald.

Anrechnung des Übungserfolges:

Übungserfolg aus dem Vorsemester sollte automatisch von basis übertragen worden sein. Im Zweifel bitte selbst in basis nachprüfen und bei Problemen wie unten beschrieben bei uns per Beleg eintragen lassen.

Wer die Übungen zu diesem Modul bereits in einem vorigen Semester bestanden hat, kann sich den Übungserfolg anrechnen lassen und damit die Prüfungszulassung erhalten. Dazu benötigen wir aber als Beleg einen Ausdruck der Leistungsübersicht aus basis, auf der diese bestandene Leistung eingetragen ist. Dieser kann über den Postkasten oder persönlich abgegeben werden.

lehre/ws1516/algorithmen-und-berechnungskomplexitaeti.txt · Zuletzt geändert: 2016/04/05 11:58 von schwarzwald

Benutzer-Werkzeuge