Algorithmen und Berechnungskomplexität II

Termine

	Wann	Beginn	Dozent
Vorlesung	Mittwoch 12:15-13:45	22. April 2020	Röglin
Übungen	Montag 12:15-13:45	27. April 2020	Sophie Duong
	Montag 14:15-15:45	27. April 2020	Vincent Schönbach
	Dienstag 10:15-11:45	28. April 2020	Vincent Schönbach
	Dienstag 16:15-17:45	28. April 2020	Ken Berkpinar
	Mittwoch 08:15-09:45	29. April 2020	Sophie Duong
	Mittwoch 10:15-11:45	29. April 2020	Andreas Hene
	Mittwoch 14:15-15:45	29. April 2020	Andreas Hene
	Donnerstag 10:15-11:45	30. April 2020	Joshua Könen/Jan Eube
	Donnerstag 12:15-13:45	30. April 2020	Joshua Könen/Jan Eube
	Freitag 12:15-13:45	08. Mai 2020	Ken Bergpinar

Inhalt

In dieser Vorlesung werden wir uns mit der Berechenbarkeit und Komplexität von Problemen beschäftigen. Es gibt viele verschiedene Probleme. Wir werden formalisieren, was wir unter einem Problem verstehen und Rechnermodelle angeben, die bestimmen, was für Operationen wir zur Bestimmung von Lösungen benutzen dürfen. Wir haben im vergangenen Semester effiziente Algorithmen zur Lösung einer Vielzahl von Problemen entworfen. In dieser Vorlesung werden wir die Grenzen der Algorithmik kennenlernen und uns damit beschäftigen, für welche Probleme es keine effizienten Algorithmen gibt und welche überhaupt nicht algorithmisch gelöst werden können.

eCampus

Die Vorlesung und die zugehörigen Übungen werden auf eCampus unter folgendem Link stattfinden (https://ecampus.uni-bonn.de/goto_ecampus_crs_1665299.html). Bitte melden Sie sich bis zum 8. Mai für die Vorlesung und eine Übungsgruppe an.

Übungen

Zu Übungszwecken werden wöchentliche Übungsblätter zum Download bereitgestellt. Die Aufgaben können schriftlich bearbeitet werden und dem/der Tutor/in zur Korrektur bis zum Montag der darauf folgenden Woche elektronisch übermittelt werden. In der darauf folgenden Woche werden die Inhalte in den Tutorien besprochen. Für die Zulassung zur Prüfung gelten keine Voraussetzungen.

Übungsblatt 1 (Besprechung in KW 18, Abgabe bis 27.04., 12:00 Uhr, per Mail an den/die Tutor(in))
Übungsblatt 2 (Besprechung in KW 19, Abgabe bis 04.05., 12:00 Uhr, per Mail an den/die Tutor(in))
Übungsblatt 3 (Besprechung in KW 20, Abgabe bis 11.05., 12:00 Uhr, per Mail an den/die Tutor(in))
Übungsblatt 4 (Besprechung in KW 21, Abgabe bis 18.05., 12:00 Uhr, per Mail an den/die Tutor(in))
Übungsblatt 5 (Besprechung in KW 22, Abgabe bis 25.05., 12:00 Uhr, per Mail an den/die Tutor(in))
Übungsblatt 6 (Besprechung in KW 23, Abgabe bis 01.06., 12:00 Uhr, per Mail an den/die Tutor(in))
Übungsblatt 7 (Besprechung in KW 24, Abgabe bis 08.06., 12:00 Uhr, per Mail an den/die Tutor(in))
Übungsblatt 8 (Besprechung in KW 25, Abgabe bis 15.06., 12:00 Uhr, per Mail an den/die Tutor(in))
Übungsblatt 9 (Besprechung in KW 26, Abgabe bis 22.06., 12:00 Uhr, per Mail an den/die Tutor(in))
Übungsblatt 10 (Besprechung in KW 27, Abgabe bis 29.06., 12:00 Uhr, per Mail an den/die Tutor(in))
Übungsblatt 11 (Besprechung in KW 28, Abgabe bis 06.07., 12:00 Uhr, per Mail an den/die Tutor(in))
Übungsblatt 12 (Besprechung in KW 29, Abgabe bis 13.07., 12:00 Uhr, per Mail an den/die Tutor(in))

Klausur

Die Klausur findet am 22.07.2020 von 11:00 Uhr bis 12:30 Uhr statt.

Nachklausur

Die Nachklausur findet am 22.09.2020 von 13:00 Uhr bis 14:30 Uhr verteilt auf 3 Hörsäle statt. Falls Sie sich zur Klausur angemeldet haben und an der Klausur teilnehmen wollen, finden Sie sich bitte spätestens um 12:50 Uhr entsprechend Ihrem Nachnamen (ausgenommen Sonderabsprachen) am ausgewiesenen Eingang des jeweiligen Hörsaales ein. Achten Sie bitte bereits im Eingangsbereich darauf, einen Mindestabstand von 1,50 Meter einzuhalten, und setzen Sie eine Mund-Nasen-Bedeckung (MNB) auf. Die Verteilung der Teilnehmer auf die Hörsäle ist wie folgt vorgesehen: CP 1 (Hörsaalzentrum): Nachnamen beginnend mit A-H CP 2 (Hörsaalzentrum): Nachnamen beginnend mit J-R WPHS (Wolfgang Paul Hörsaal): Nachnamen beginnend mit S-Z

Um 12:50 Uhr erhalten Sie Einlass. Bitte gehen Sie der Reihe nach mit einem Abstand von jeweils mindestens 1,50 Meter nacheinander in den Hörsaal. Desinfizieren Sie sich unbedingt auf dem Weg die Hände am bereitstehenden Spender. Treten Sie dann der Reihe nach in den jeweiligen Hörsaal ein und besetzen die gekennzeichneten Sitzplätze von hinten nach vorne von links nach rechts. Legen Sie Stifte und einen Lichtbildausweis bereit und stellen Sie dann Ihre Tasche zwei Plätze weiter rechts von sich ab.

Sobald Sie das Gebäude betreten, sind Sie verpflichtet einen Mund-Nase-Schutz zu tragen. Wir bitten Sie, diesen nach Möglichkeit während der Klausur aufzubehalten, mindestens jedoch, bis die Mitarbeiter mit der Identitätsprüfung fertig sind. Bei jedem näheren Kontakt als 1,50 Meter ist der Mund-Nase-Schutz in jedem Fall aufzusetzen.

Um an der Klausur teilzunehmen, füllen Sie bitte die bereitliegende Erklärung zur Rückverfolgung von Kontakten aus. Diese wird bei Kontrolle Ihres Ausweises eingesammelt. Beachten Sie auch, dass ein Betreten der Räume der Universität Bonn mit Krankheitszeichen, welche nicht vom Arzt abgeklärt wurden, verboten ist.

Zum Ende der Klausur bleiben Sie bitte an Ihrem Platz sitzen und verlassen bei Aufforderung in umgekehrter Eingangsreihenfolge nacheinander den Hörsaal.

Unter dem Link https://www.uni-bonn.de/die-universitaet/informationen-zum-coronavirus/handreichung-prasenzprufungen-studierende-final.pdf befindet sich noch eine allgemeine Anweisung der Universität Bonn zum Verhalten während der Klausur. Bitte lesen Sie auch diese Hinweise aufmerksam durch.

Bitte seien Sie auf jeden Fall pünktlich und kommen Sie nur, wenn Sie wirklich gesund sind.

Wir bedanken uns für Ihre Mithilfe und wünschen Ihnen viel Erfolg für die Klausur.

Literatur

Die Inhalte der Vorlesung finden sich in diesem Skript.