Dozent: Prof. Dr. Christian Scheideler

Modulinformation

• Modul I.2.2 (MuA)
• V4+ZÜ1+Ü2 SWS
• 8 ECTS

Vorlesung

• Montags 11.00 Uhr - 13.00 Uhr, Hörsaal L1
   
• Freitags, 11.00 Uhr - 13.00 Uhr, Hörsaal L1

Zentralübung

• Freitags, 13.00 Uhr, Hörsaal L1

Übungsgruppen

Die Anmeldung zu den Übungsgruppen erfolgt über PAUL. 

1. Mo  09:00 - 11:00 Uhr   Raum D1.312 (Tutor: Lars Werneke)
2. Mo  09:00 - 11:00 Uhr   Raum O1.252 (Tutor: Sascha Brauer)
3. Mo  14:00 - 16:00 Uhr   Raum D1.312 (Tutor: Stephanie Freitag)
4. Mo  14:00 - 16:00 Uhr   Raum O1.252 (Tutor: Karlson Pfannschmidt)
5. Di   09:00 - 11:00 Uhr   Raum N4.232 (Tutor: Oliver Otte)
6. Di   09:00 - 11:00 Uhr   Raum D1.312 (Tutor: Christina Kolb)
7. Di   16:00 - 18:00 Uhr   Raum D1.312 (Tutor: Lukas Arendt)
8. Mi   09:00 - 11:00 Uhr   Raum D1.312 (Tutor: Simon Pokrup)
9. Mi   16:00 - 18:00 Uhr   Raum D1.312 (Tutor: Jörn Köpe)
10. Do   09:00 - 11:00 Uhr  Raum D1.312 (Tutor: David Georgi)
11. Do   14:00 - 16:00 Uhr  Raum D1.312 (Tutor: Stephanie Freitag)
12. Do   14:00 - 16:00 Uhr  Raum O1.252 (Tutor: Lars Kleinemeier)
13. Do   16:00 - 18:00 Uhr  Raum D1.312 (Tutor: Jörn Köpe)
14. Fr    09:00 - 11:00 Uhr  Raum D1.312 (Tutor: Thim Strothmann)
15. Fr    09:00 - 11:00 Uhr  Raum O1.252 (Tutor: Oliver Otte)

Die Veranstaltung wird über die koaLA-Plattform organisiert. Dort finden sich sämtliche Informationen und Materialien. Melden Sie sich in PAUL für die Veranstaltung an.

Hinweis: Wenn Sie keine Übungsgruppe besuchen wollen melden Sie sich bitte in PAUL in der ersten Übungsgruppe (KEINE ÜBUNG) an. Somit wird vermieden, dass Sie Übungsgruppenplätze für Ihre Kommilitonen blockieren

• Erste Vorlesung: Freitag, 21. April 2017
• Erste Zentralübung: 12. Mai 2017
• Übungsbeginn: 2. Mai 2017

Inhalt der Vorlesung:

Algorithmen bilden die Grundlage jeder Hardware und Software: ein Schaltkreis setzt einen Algorithmus in Hardware um, ein Programm macht einen Algorithmus für den Rechner verstehbar. Algorithmen spielen daher eine zentrale Rolle in der Informatik. Wesentliches Ziel des Algorithmenentwurfs ist die (Ressourcen-)Effizienz, d.h. die Entwicklung von Algorithmen, die ein gegebenes Problem möglichst schnell und mit möglichst geringem Speicherplatz lösen.

Untrennbar verbunden mit effizienten Algorithmen sind effiziente Datenstrukturen, also Methoden, große Datenmengen im Rechner so zu organisieren, dass Anfragen wie Suchen, Einfügen und Löschen, aber auch komplexere Anfragen effizient beantworten werden können.

Die in dieser Veranstaltung vorgeschlagenen Entwurfs- und Analysemethoden für effiziente Algorithmen und Datenstrukturen sowie die grundlegenden Beispiele wie Sortierverfahren, dynamische Datenstrukturen und Graphenalgorithmen gehören zu den Grundlagen für die Algorithmenentwicklung und Programmierung in weiten Bereichen der Informatik.

Inhaltliche Gliederung: (zuletzt aktualisiert am 13.04.)

1. Einführung (Rechenmodelle, Effizienzmaße, Beispiele)
2. Analysetechniken (Invarianten, Rekurrenzgleichungen)
3. Sortierverfahren (Insertionsort, Mergesort, Quicksort, Heapsort, Countingsort)
4. Datenstrukturen (Verkettete Listen, Bäume, Graphen, dynamische Suchstrukturen, Hashing)
5. Graphenalgorithmen (Tiefen- und Breitensuche, kürzeste Wege, minimale Spannbäume)
6. Entwurfsparadigmen (inkrementelle Entwicklung, Teile-und-Herrsche, Greedy Algorithmen, dynamische Programmierung)

Folien:

• Kapitel 1: Einleitung
• Kapitel 2: Grundlagen
• Kapitel 3: Inkrementelle Algorithmen
• Kapitel 4: Divide & Conquer - Merge-Sort
• Kapitel 5: Rekursionen
• Kapitel 6: Quicksort
• Kapitel 7: Heapsort
• Kapitel 8: Untere Schranken für Sortieren
• Kapitel 9: Sortieren in linearer Zeit
• Kapitel 10: Elementare Datenstrukturen
• Kapitel 11: Binäre Suchbäume
• Kapitel 12: Balancierte binäre Suchbäume
• Kapitel 13: Hashing
• Kapitel 14: Elementare Graphalgorithmen
• Kapitel 15: Kürzeste Wege
• Kapitel 16: Minimale Spannbäume
• Kapitel 17: All Pairs Shortest Path Problem
• Kapitel 18: Divide & Conquer
• Kapitel 19: Gierige Algorithmen
• Kapitel 20: Dynamische Programmierung

Übungen:

Um die Inhalte der Vorlesung zu vertiefen, bieten wir Präsenzübungen und auch Heimübungen an. Heimübungen lösen Sie in Kleingruppen bis maximal 3 Personen und geben Ihre Lösung einmal pro Woche ab. Durch diese Punkte können Sie in der Klausur einen Bonus erreichen, sofern Sie die Klausur bestehen.

Zusätzlich haben Sie die Möglichkeit, in den wöchentlich stattfindenden Übungsgruppen Präsenzübungen zu bearbeiten. Dabei steht Ihnen ein Tutor als Ansprechpartner zur Verfügung.

Um zur Klausur zugelassen zu werden, müssen Sie in mindestens 75% der Hausübungen mindestens 20% der Punkte holen. Sie erhalten einen Bonusnotenschritt, wenn Sie 60% der Punkte auf den Hausübungen erreicht haben UND einmal in der Präsenzübung vorgerechnet haben.

Die Übungsaufgaben werden Freitags in das koaLa-System eingestellt. Die Abgabefrist ist jeweils der übernächste Montag vor der Vorlesung (Zettelkästen auf D3). Bei verspäteter Abgabe erfolgt keine Bewertung!

Bei weiteren Fragen wenden Sie sich an Ihren Tutor.

Klausur:

Die Vorlesung ist nur dann bestanden, wenn die Klausur mit mindestens 4,0 bestanden ist. 

Klaurtermine:

1. Erste Klausur: 07.08.2017, 15:00-18:00 Uhr, SP 2.
2. Zweite Klausur: 18.09.2017, 14:00-17:00 Uhr, AM.

Sie dürfen in der Klausur keine Hilfsmittel benutzen außer einem beidseitig handbeschriebenen DINA4 Zettel.

Materialien:

Generell finden Sie alle Materialien im koaLA-System.