AG Algorithmen und Komplexität
>

Entwurf und Analyse von Algorithmen (WS 13/14)

Die Vorlesung Entwurf und Analyse von Algorithmen hat am Fachbereich Informatik der TU Kaiserslautern eine lange Tradition, war sie doch bereits für die Diplomstudiengänge Informatik und Angewandte Informatik eine Pflichtveranstaltung im Grundstudium. Sie vermittelt grundlegende Kenntnisse und Fähigkeiten der Algorithmik, also

Ineffective sorts Wie würden Sie es machen?
  • mathematische Grundlagen der Algorithmenanalyse,
  • elementare Datenstrukturen und Algorithmen,
  • Analyse von iterativen und rekursiven Algorithmen,
  • Entwurfsmuster für Algorithmen und
  • Grundlagen der Komplexitätstheorie.

Als Arbeitsbeispiele werden Wörterbuchdatenstrukturen sowie Sortier- und Graphalgorithmen verwendet, die zum Werkzeugkasten eines jeden Informatikers gehören. Neben algorithmischer Intuition und der Fähigkeit, die Inhalte der Vorlesung auf neue Probleme anwenden zu können, legen wir außerdem Wert auf formal sauberes Arbeiten.

Die Vorlesung richtet sich an Studierende in Bachelorstudiengängen der Informatik (Inf), Angewandte Informatik (AI), Mathematik (Math) und Wirtschaftsingenieurwesen Fachrichtung Informatik (WII). Den unterschiedlichen Lernzielen wird durch unterschiedliche Schwerpunktsetzung in Übungen und Klausur Rechnung getragen. Studierende aus AI und WII besuchen außerdem Beweistechniken, um fehlende Übung im Umgang mit Formalismen auszugleichen.

Für die Formalitäten sei auf die entsprechenden Modulhandbucheinträge INF-00-06-V-2 (Inf), INF-00-06AI-M-2 (AI, WII) und MAT-INF-10-M-4 (Math) verwiesen.

Die Vorlesung wird im Wintersemester 2013/14 von Prof. Dr. Markus Nebel gehalten und von Raphael Reitzig betreut.

Weitere Informationen zu

erhalten Sie auf den entsprechenden Unterseiten.

Mitteilungen und Neuigkeiten finden Sie in OLAT.

Termine

Die Vorlesung findet während der Vorlesungszeit zwei Mal pro Woche statt, nämlich am

  • Montag, 13:45 – 15:15 in 46-220, und
  • Donnerstag, 13:45 – 15:15 in 46-210.

Ausnahmen sowie etwaige Zusatztermine entnehmen Sie bitte dem Kalender im KIS (Vorlesung, Übung).

Die Übungstermine entnehmen Sie bitte der entsprechenden Seite.

Die Prüfungstermine entnehmen Sie bitte der entsprechenden Seite.

Programmierkurs in C für Mathematiker

Für Mathematikstudenten bietet Herr Schürmann einen Auffrischkurs Programmierung in C an. Dieser findet an drei Terminen je Montags, 28.10., 04.11., 11.11. um 17:15 Uhr in 46-110 statt.

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.

In früheren Jahren