AG Algorithmen und Komplexität
>

Literatur

Alle für die Vorlesung wichtigen Inhalte werden umfänglich im Buch Entwurf und Analyse von Algorithmen von Prof. Nebel (L INF 160, INF 335/178, online) behandelt, das im Teubner-Springer Verlag erschienen ist. Wer die verschiedenen Inhalte vertiefen möchte oder nach einer alternativen Abhandlung sucht, sei auf folgende Werke verwiesen:

  • Aho, Hopcroft, Ullman: The Design and Analysis of Computer Algorithms
    INF 335/001, L INF 181, MAT Aho
  • Ottmann, Widmayer: Algorithmen und Datenstrukturen
    INF 335/105, L INF 690

Tipps zur Vorbereitung

Die Einstiegsvorlesungen in Mathematik sind lange her? Sie haben Sorge, mit Formalismen nicht zurecht zu kommen? Programmieren hört für Sie beim Festplattenrecorder auf? Dann möchten Sie vielleicht schon vor Beginn der Vorlesung Ihr Wissen auffrischen bzw. ergänzen, denn

  • sowohl Vorlesung als auch Übungen erfordern Umgang mit Mathematik und
  • etwas Programmiererfahrung hilft erfahrungsgemäß beim Verstehen und Verfassen von Algorithmen in Pseudocode.

Wir wollen Sie dabei nicht alleine lassen und empfehlen Ihnen die folgenden Ressourcen:

  • Das (kosten)freie Book of Proof von Richard Hammack behandelt Grundkonzepte des mathematischen Beweises ausführlich und zugänglich. Besonders hervorzuheben sind die vielen Übungsaufgaben mit Lösungen, die Sie zur Selbstkontrolle nutzen können.
  • Wem das zu langweilig ist, der möchte vielleicht durch Concrete Mathematics von Graham, Knuth und Pathashnik blättern. Neben vielen in der theoretischen Informatik relevanten mathematischen Konzepten und Methoden finden Sie auch hier etliche Übungsaufgaben mit Lösungen.
  • Es gibt für einige Programmiersprachen gut verdauliche, interaktive Tutorials wie zum Beispiel RubyMonk oder Try Haskell. Während die konkrete Syntax oder auch Semantik natürlich keine Verwendung in unserem Pseudocode findet, können Sie doch ein Gefühl für beides und eine gewisse algorithmische Intuition entwickeln, wenn Sie ein paar Dinge selbst implementieren. Übersichtliche Aufgaben zum Üben finden Sie etwa bei Project Euler.
  • Einführende Texte über Programmierung – und zahlreiche Aufgaben – finden Sie etwa in Introduction to Programming in Java von Sedgewick und Wayne.
  • Abschließend sei erwähnt, dass es auf Plattformen wie Coursera oder MIT OpenCourseWare zahlreiche thematisch verwandte Kurse gibt. Da der Zeitaufwand dieser durchaus hoch sein kann, ist ihr Konsum nur zu empfehlen, wenn Sie große Bedenken bezüglich Ihrer Vorkenntnisse haben.

Weiterführende Literatur

Mathematische Grundlagen

Berechnungsmodelle

  • Uwe Schöning: Theoretische Informatik, kurz gefasst
    L INF 114

Algorithmenanalyse

Komplexitätstheorie

  • Garey, Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness
    INF 370/004, L INF 188, MAT Gare

Algorithmik, Datenstrukturen, Entwurfsmethoden

  • Brassard, Bratley: Algorithmik
    INF 335/130
  • Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms
    INF 335/097; INF 335/161, L INF 87, MAT Algo
  • Robert Sedgewick, Kevin Wayne: Algorithms
    INF 335/062
  • Uwe Schöning: Algorithmik
    INF 335/154, L INF 111

Einführung in Java