12412 - Effiziente Algorithmen II Modulübersicht
| Modulnummer: | 12412 - Modul nicht mehr im Angebot ab WS 2008/9 |
| Modultitel: | Effiziente Algorithmen II |
| Efficient Algorithms II | |
| Einrichtung: | Fakultät 1 - Mathematik, Naturwissenschaften und Informatik |
| Verantwortlich: |
|
| Lehr- und Prüfungssprache: | Deutsch |
| Dauer: | 1 Semester |
| Angebotsturnus: | sporadisch nach Ankündigung |
| Leistungspunkte: | 8 |
| 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. |
| 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. |
| Empfohlene Voraussetzungen: | keine |
| Zwingende Voraussetzungen: | keine |
| Lehrformen und Arbeitsumfang: |
|
| Unterrichtsmaterialien und Literaturhinweise: | - 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. |
| Modulprüfung: | Keine Angabe - Angabe ab Wintersemester 2016/17 erforderlich! |
| Prüfungsleistung/en für Modulprüfung: | Prüfungsgespräch benotet |
| Bewertung der Modulprüfung: | Prüfungsleistung - benotet |
| Teilnehmerbeschränkung: | keine |
| Zuordnung zu Studiengängen: |
|
| Bemerkungen: | keine |
| Veranstaltungen zum Modul: | keine |
| Veranstaltungen im aktuellen Semester: |
|