Einfü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.
Lernziel
Nach 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.
Inhalt
Die 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.
Skript
Ja. Wird zu Beginn des Semesters verteilt.
Leistungskontrolle
Information zur Leistungskontrolle (gültig bis die Lerneinheit neu gelesen wird)
Die Leistungskontrolle wird in jeder Session angeboten. Die Repetition ist ohne erneute Belegung der Lerneinheit möglich.
Prüfungsmodus
schriftlich 120 Minuten
Hilfsmittel schriftlich
10 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.