Dozent: Prof. Dr. Christian Scheideler

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

PAUL

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

Vorlesung

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

Zentralübung

• Montags, 13.00 Uhr, Hörsaal L1, 

Erste Vorlesung: Montag, 11. April 2016 

Übungsgruppen

Die Anmeldung zu den Übungsgruppen erfolgt über 

PAUL. 

1. Mo  09:00 - 11:00 Uhr, (D1.312 Tutor: Lars Kleinemeier)  
2. Mo  09:00 - 11:00 Uhr, (01.252 Tutor: Linghui Luo)
3. Mo  14:00 - 16:00 Uhr, (D1.312 Tutor: Anna Droege)  
4. Mo  14:00 - 16:00 Uhr, (01.252 Tutor: Till Knollmann)  
5. Mo  16:00 - 18:00 Uhr, (D1.312 Tutor: Karlson Pfannschmidt)  
6. Di   09:00 - 11:00 Uhr, (D1.312 Tutor: Zun Wang)
7. Di   16:00 - 18:00 Uhr, (J2.220 Tutor: Robert Gmyr)
8. Mi   09:00 - 11:00 Uhr, (D1.312 Tutor: Stephanie Freitag)  
9. Mi   16:00 - 18:00 Uhr, (D1.312 Tutor: Stephanie Freitag)   
10. Do   09:00 - 11:00 Uhr, (D1.312 Tutor: Jannik Sundermeier) 
11. Do   14:00 - 16:00 Uhr, (D1.312 Tutor: Oliver Otte) 
12. Do   14:00 - 16:00 Uhr, (01.252 Tutor: Michael Feldmann)  
13. Do   16:00 - 18:00 Uhr, (D1.312 Tutor: Oliver Otte)
14. Fr    09:00 - 11:00 Uhr, (D1.312 Tutor: Jannik Sundermeier)
15. Fr    09:00 - 11:00 Uhr, (01.252 Tutor: Thim Strothmann) 

Inhalt der Vorlesung:

Modulinformation:

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

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 and Conquer - Mergesort
• Kapitel 5: Rekursionen
• Kapitel 6: Divide and Conquer - 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 (Version vom 23.05.)
  
• Kapitel 12: Balancierte binäre Suchbäume (Version vom 27.05.)
• Kapitel 13: Hashing (Version vom 03.06.)
• Kapitel 14: Elementare Graphalgorithmen
• Kapitel 15: Kürzeste Wege (Version vom 16.6.)
  
• Kapitel 16: Minimale Spannbäume (Version vom 17.6.)
• Kapitel 17: All Pairs Shortest Paths
• Kapitel 18: Divide and Conquer
• Kapitel 19: Gierige Algorithmen
  
• Kapitel 20: Dynamische Programmierung
• Kapitel 21: Verschiedenes (auch in ppt)

Ü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.

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 montags in das koaLa-System eingestellt. Die Abgabefrist ist jeweils der darauffolgende Freitag um 11.00 Uhr (Zettelkästen auf D3).

Zusätzlich zu den schriftlichen Hausaufgaben wird es in zweiwöchigen Abstand Programmieraufgaben geben (ingesamt 4 Zettel). Die Lösungen von Programmieraufgaben geben Sie bitte per koaLA ab.

Sie erhalten einen weiteren Bonusnotenschritt, wenn Sie 75% der Programmieraufgaben erfolgreich gelöst haben (also 6 Aufgaben von 8).

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. Die erste Klausur wird voraussichtlich am 05.08.2016 stattfinden.
2. Die zweite Klausur wird voraussichtlich am 15.09.2016 stattfinden.

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.