252-0851-00L  Algorithmen und Komplexität

SemesterHerbstsemester 2019
DozierendeJ. Lengler, A. Steger
Periodizitätjährlich wiederkehrende Veranstaltung
LehrspracheDeutsch



Lehrveranstaltungen

NummerTitelUmfangDozierende
252-0851-00 VAlgorithmen und Komplexität2 Std.
Di08:15-10:00HG D 1.2 »
J. Lengler, A. Steger
252-0851-00 UAlgorithmen und Komplexität1 Std.
Do16:15-17:00CAB G 52 »
16:15-17:00CAB G 56 »
16:15-17:00IFW C 35 »
16:15-17:00LEE C 114 »
16:15-17:00LEE D 105 »
J. Lengler, A. Steger

Katalogdaten

KurzbeschreibungEinführung: RAM-Maschine, Datenstrukturen; Algorithmen: Sortieren, Medianbest., Matrixmultiplikation, kürzeste Pfade, min. spann. Bäume; Paradigmen: Divide&Conquer, dynam. Programmierung, Greedy; Datenstrukturen: Suchbäume, Wörterbücher, Priority Queues; Komplexitätstheorie: Klassen P und NP, NP-vollständig, Satz von Cook, Beispiele für Reduktionen.
LernzielNach dieser Vorlesung kennen die Studierenden einige Algorithmen und übliche Werkzeuge. Sie kennen die Grundlagen der Komplexitätstheorie und können diese verwenden um Probleme zu klassifizieren.
InhaltDie Vorlesung behandelt den Entwurf und die Analyse von Algorithmen und Datenstrukturen. Die zentralen Themengebiete sind: Sortieralgorithmen, Effiziente Datenstrukturen, Algorithmen für Graphen und Netzwerke, Paradigmen des Algorithmenentwurfs, Klassen P und NP, NP-Vollständigkeit, Approximationsalgorithmen.
SkriptJa. Wird zu Beginn des Semesters verteilt.

Leistungskontrolle

Information zur Leistungskontrolle (gültig bis die Lerneinheit neu gelesen wird)
Leistungskontrolle als Semesterkurs
Im Prüfungsblock fürBachelor-Studiengang Mathematik 2010; Ausgabe 24.02.2016 (Prüfungsblock 1)
Bachelor-Studiengang Mathematik 2016; Ausgabe 25.02.2020 (Prüfungsblock 1)
ECTS Kreditpunkte4 KP
PrüfendeJ. Lengler, A. Steger
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
Hilfsmittel schriftlich10 handgeschriebene Din A4 Blätter
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

Keine öffentlichen Lernmaterialien verfügbar.
Es werden nur die öffentlichen Lernmaterialien aufgeführt.

Gruppen

Keine Informationen zu Gruppen vorhanden.

Einschränkungen

Keine zusätzlichen Belegungseinschränkungen vorhanden.

Angeboten in

StudiengangBereichTyp
Informatik (Allgemeines Angebot)Informatik für NichtinformatikerZInformation
Mathematik BachelorPrüfungsblock IOInformation