Das Frühjahrssemester 2021 findet grundsätzlich online statt. Neue Präsenzelemente ab 26. April werden von den Dozierenden mitgeteilt.

252-0026-00L  Algorithmen und Datenstrukturen

SemesterHerbstsemester 2020
DozierendeM. Püschel, D. Steurer
Periodizitätjährlich wiederkehrende Veranstaltung
LehrspracheDeutsch



Katalogdaten

KurzbeschreibungThe Kurs behandelt die Grundlagen des Entwurfs und der Analyse von Algorithmen und Datenstrukturen. Diese werden anhand von klassischen algorithmischen Problemen einschliesslich Graphenproblemen studiert. Die dazu nötige Einführung in die Graphentheorie ist ebenfalls Teil dieses Kurses.
LernzielVerständnis des Entwurfs und der Analyse grundlegender Algorithmen und Datenstrukturen. Verständnis der Grundlagen der Graphentheorie und einiger ihrere grundlegenden Algorithmen,
InhaltDer Kurs ist eine Einführung in die Grundlagen des Designs and der Analyse von Algorithmen. Dazu gehören zum einen klassische Entwurfsmuster für Algorithmen wie Induktion, Divide-and-Conquer und dynamische Programmierung. Diese werden anhand von klassischen Problemen wie zum Beispiel Suchen und Sortieren studiert. Zum anderen geht es um das Zusammenspiel von Algorithmen und Datenstrukturen wie verkettete Listen, Suchbäumen, Heaps und Union-Find Strukturen. Ein besondere Fokus sind Graphenalgorithmen für Probleme wie kürzeste Wege und minimale Spannbäume. Die dazu notwendige erste Einführung in die Graphentheorie ist ebenfalls Teil der Vorlesung.
SkriptEin vollständiges Skript in Deutsch ist in der Entwicklung und bereits als vollständiger Entwurf auf der Vorlesungswebseite verfügbar.
LiteraturAbgesehen vom Skript und Vorlesungsunterlagen empfehlen wir die folgenden Bücher als zusätzliches Nachschlagewerk.

Th. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen, Spektrum-Verlag, 5. Auflage, Heidelberg, Berlin, Oxford, 2011

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: An Introduction to Algorithms, 3rd edition, MIT Press, 2009

Leistungskontrolle

Information zur Leistungskontrolle (gültig bis die Lerneinheit neu gelesen wird)
Leistungskontrolle als Semesterkurs
Im Prüfungsblock fürBachelor-Studiengang Informatik 2016; Ausgabe 25.02.2020 (Basisprüfungsblock 1)
ECTS Kreditpunkte7 KP
PrüfendeM. Püschel, D. Steurer
FormSessionsprüfung
PrüfungsspracheDeutsch
RepetitionDie Leistungskontrolle wird in jeder Session angeboten. Die Repetition ist ohne erneute Belegung der Lerneinheit möglich.
Prüfungsmodusschriftlich 120 Minuten und 180 Minuten
Zusatzinformation zum PrüfungsmodusWährend des Semesters können durch aktive Mitarbeit Bonuspunkte erarbeitet werden. Die Veranstaltung bietet als "Leistungselement" (im Sinne der WEISUNG: Anwendung von Leistungselementen in der Lehre vom 22.12.2017) zwei Arten von Lernelementen an.
Die einen Lernelemente sind Bonusaufgaben und klar markierter Teil der wöchentlichen Aufgabensammlung. In maximal 13 Wochen wird es Bonusaufgaben geben. Das andere Lernelement ist Peer Feedback, d.h., die Korrektur der Bonusaufgaben von Kommilitonen in den wöchentlichen Übungen. Die durch die Lernelemente erworbenen Punkte verbessern das Ergebnis der schriftlichen Prüfung um maximal 0.25 Notenpunkte, wobei für dieses Maximum nicht die Maximalpunktzahl erforderlich ist.

Unehrliches Verhalten bei der Bearbeitung der Lernelemente (z.B., Kopieren der Lösungen von Kommilitonen oder anderen Quellen, zur Verfügung stellen der eigenen Lösungen zum Kopieren) haben ernste Konsequenzen inklusive der Aberkennung aller Bonuspunkte dieser Veranstaltung.

Die Prüfung wird an zwei verschiedenen Daten stattfinden: 1) Schriftliche Prüfung auf Papier: 120 Min. und 2) Computerbasierte Online-Prüfung: 180 Min.
Hilfsmittel schriftlichkeine
Online-PrüfungDie Prüfung kann am Computer stattfinden.
Falls die Lerneinheit innerhalb eines Prüfungsblockes geprüft wird, werden die Kreditpunkte für den gesamten bestandenen Block erteilt.
Diese Angaben können noch zu Semesterbeginn aktualisiert werden; verbindlich sind die Angaben auf dem Prüfungsplan.

Lernmaterialien

 
HauptlinkWebseite zur Vorlesung
Es werden nur die öffentlichen Lernmaterialien aufgeführt.

Lehrveranstaltungen

NummerTitelUmfangDozierende
252-0026-00 VAlgorithmen und Datenstrukturen
Die Vorlesungen finden im Hybrid-Modus statt. Ein Teil der Studierenden besucht die Vorlesung im aufgeführten Hörsaal, und der andere Teil der Studierenden verfolgt den Live-Stream im Video-Portal der ETH. Details und Belegungsplan: https://www.basisjahr.inf.ethz.ch/
3 Std.
Do14-17ML D 28 »
M. Püschel, D. Steurer
252-0026-00 UAlgorithmen und Datenstrukturen
Gruppeneinteilung erfolgt über myStudies.
plus jeweils eine Stunde Nachbearbeitungszeit (montags 11-12)
2 Std.
Mo09-11CAB G 52 »
09-11CAB G 59 »
09-11CHN D 42 »
09-11CHN D 44 »
09-11CHN D 46 »
09-11CHN D 48 »
09-11CHN F 42 »
09-11ETZ E 7 »
09-11ETZ F 91 »
09-11ETZ H 91 »
09-11ETZ J 91 »
09-11ETZ K 91 »
09-11HG D 5.1 »
09-11HG D 5.3 »
09-11IFW A 34 »
09-11IFW B 42 »
09-11IFW C 31 »
09-11IFW C 33 »
09-11LEE C 104 »
09-11LEE C 114 »
09-11LFW C 11 »
09-11ML J 34.1 »
09-11ML J 34.3 »
M. Püschel, D. Steurer
252-0026-00 AAlgorithmen und Datenstrukturen1 Std.M. Püschel, D. Steurer

Gruppen

252-0026-00 UAlgorithmen und Datenstrukturen
GruppenINFK-ON 01
nur für  Informatik BSc (252000)
INFK-Rest 01
Mo09-11CHN F 42 »
nicht für  Informatik BSc (252000)
INFK-01
Mo09-11ML J 34.3 »
nur für  Informatik BSc (252000)
INFK-02
Mo09-11LFW C 11 »
nur für  Informatik BSc (252000)
INFK-03
Mo09-11ML J 34.1 »
nur für  Informatik BSc (252000)
INFK-04
Mo09-11CHN D 46 »
nur für  Informatik BSc (252000)
INFK-05
Mo09-11CHN D 48 »
nur für  Informatik BSc (252000)
INFK-06
Mo09-11CAB G 52 »
nur für  Informatik BSc (252000)
INFK-07
Mo09-11CAB G 59 »
nur für  Informatik BSc (252000)
INFK-08
Mo09-11CHN D 44 »
nur für  Informatik BSc (252000)
INFK-09
Mo09-11ETZ H 91 »
nur für  Informatik BSc (252000)
INFK-10
Mo09-11ETZ J 91 »
nur für  Informatik BSc (252000)
INFK-11
Mo09-11ETZ K 91 »
nur für  Informatik BSc (252000)
INFK-12
Mo09-11HG D 5.3 »
nur für  Informatik BSc (252000)
INFK-13
Mo09-11HG D 5.1 »
nur für  Informatik BSc (252000)
INFK-14
Mo09-11IFW A 34 »
nur für  Informatik BSc (252000)
INFK-15
Mo09-11IFW B 42 »
nur für  Informatik BSc (252000)
INFK-16
Mo09-11IFW C 31 »
nur für  Informatik BSc (252000)
INFK-17
Mo09-11IFW C 33 »
nur für  Informatik BSc (252000)
INFK-18
Mo09-11CHN D 42 »
nur für  Informatik BSc (252000)
INFK-19
Mo09-11LEE C 104 »
nur für  Informatik BSc (252000)
INFK-20
Mo09-11LEE C 114 »
nur für  Informatik BSc (252000)
INFK-21
Mo09-11ETZ F 91 »
nur für  Informatik BSc (252000)
INFK-22
Mo09-11ETZ E 7 »
nur für  Informatik BSc (252000)

Einschränkungen

GruppenEinschränkungen sind unter Gruppen aufgeführt

Angeboten in

StudiengangBereichTyp
Informatik BachelorBasisprüfungsblock 1OInformation
Informatik LehrdiplomTeil 1OInformation