Vorige Seite (Elektronik, Labor T1) Nächste Seite (Gesellschaftliche Aspekte der Telematik)
Entwurf und Analyse von Algorithmen

LV-Nummer:
 508.061
508.062 Stunden:
 2 Vo + 1 Ue (Vorlesung + Übung) Semester:
 6. Sem. Institut:
 508 (``IGI'' ) ECTS-Punkte:
 3.0 + 2.0 credits Vortragender:
 Dipl.-Ing. Dr.techn. Oswin Aichholzer () Lehrinhalt:
 Entwurfsprinzipien anhand von Beispielen: Teilsummenproblem (Scan-line Prinzip), Multiplizieren langer Zahlen (Divide & Conquer), randomisierte Suchbäume (Randomisierung), String-Matching (probabilistische Algorithmen). Geometrische Algorithmen: Dreieckszerlegung von Polygonen (Dynamisches Programmieren), Schnitt von Liniensegmenten, konvexe Hüllen, Algorithmen auf Graphen: Suchen in die Tiefe bzw. Breite, minimale Spannbäume, kürzeste Wege, Distanzmatrix, NP-vollständige Probleme (P, NP, Reduzierbarkeit), Approximationsalgorithmen (Rundreiseproblem, Rucksackproblem). Lehrziel:
 Vermittlung und Vertiefung von Kenntnissen über effiziente Computerverfahren und Datenstrukturen. Darstellung der wesentlichsten Entwurfsprinzipien und Anleitung zum selbständigen Anwenden dieser Methoden zum Entwerfen und Analysieren von Algorithmen. Lehrmethode:
 Vortrag, Übungen unter Beteiligung der Studierenden Voraussetzungen:
 Vorkenntnisse: Datenstrukturen und Algorithmen, grundlegende Kenntnisse aus Mathematik und diskreten Strukturen, einfache Programmierkenntnisse Studienbehelfe:
 Cormen, Leiserson, Rivest: Introduction to Algorithms, MIT Press London, 1990
Mehlhorn: Data Structures & Algorithms 1-3, Teubner Stuttgart
Ottmann, Widmayer: Algorithmen und Datenstrukturen, BI-Verlag
Sedgewick: Algorithms, Addison-Wesley
Mulmuley: Computational Geometry, An Introduction Through Randomized Algorithms, Prentice Hall
Preparata, Shamos: Computational Geometry - An Introduction, Springer
Edelsbrunner: Algorithms in Combinatorial Geometry, Springer
Garey, Johnson: Computers and Intractability - A Guide to the Theory of NP-Completeness, Freeman and Company;
Fallweise Referenz auf Originalarbeiten. Anmeldung zur LV:
 Zu den Übungen (über das Anmeldesystem) Prüfungsmodus:
 Schriftlich Newsgroup:
 news:tu-graz.algorithmen Webpage:
 http://www.cis.tu-graz.ac.at/igi/oaich

© 1997-2002: Dieter LUTZMAYR
Letzte Änderung am 27. Dezember 2001