Efficient Algorithms II
Effiziente Algorithmen II
8 LPunregelmäßigDEwird nicht mehr angeboten
Inhalte
Union-Find-Algorithmus (Beispiel für untere Schranke). Arithmetische Algorithmen: schnelle Matrizenmultiplikation und -inversion, schnelle diskrete Fouriertransformation, Polynom- und Integermultiplikation, Primzahltest. Approximationsalgorithmen, Parallele Algorithmen, Probabilistische Algorithmen (Monte Carlo, Las Vegas). Lineare Optimierung.
Lernziele
Auf dem Weg vom Problem zum Programm ist das Finden eines effizienten Algorithmus der erste Schritt. So ist ein wichtiger Aspekt der Mathematik das Finden von Verfahren zur Lösung von Problemen. Oft geht es darum ineffiziente Verfahren, die sich nahelegen, zu ersetzen durch Verfahren, die kostengünstiger sind. Dies muß dann allerdings nachgewiesen werden. Darum werden Algorithmen auf ihre Effizienz untersucht, analysiert. Auch ist es nicht immer offensichtlich, daß ein Verfahren in allen Fällen korrekt arbeitet. Auch dies muß gezeigt werden. Ziel der Veranstaltung ist es, einen Einblick in die Methoden der Erstellung, Verifikation und Analyse von Algorithmen zu geben.
Prüfungsleistung
Prüfungsgespräch benotet
Literatur (1)
- - Donald E. Knuth: The Art of Computer Programming 1 - 3 , Addison-Wesley 1973. - Kurt Mehlhorn: Effiziente Algorithmen, Teubner Studienbücher Informatik 1977. - Ellis Horowitz, Sartaj Sahni: Fundamentals of Computer Algorithms, Computer Sciences Press, 1978 - Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: Data Structures and Algorithms, Addison-Wesley 1983. - Kurt Mehlhorn: Data Structures and Algorithms 1 - 3, Springer 1984. - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Introduction to Algorithms, MIT-Press, McGraw-Hill 1989. - Thomas Ottman, Peter Widmayer: Algorithmen und Datenstrukturen, BI Wissenschaftsverlag 1993.
Quelle: Modulbeschreibung der BTU · abgerufen 20.10.2026Original