AG Algorithmen und Komplexität
>

Sommersemester 2017

Sebastian bietet im Sommersemester 2017 die Vorlesungen Advanced Algorithmics an.


 

Entwurf und Analyse von Algorithmen

Die über mehrere Jahre hinweg gewachsenen Materialien zur gleichnamigen Vorlesung wurden erneut überarbeitet, um interessante Inhalt ergänzt und im Springer Vieweg Verlag als Studienbuch veröffentlicht. Das Werk deckt entsprechend alle Inhalte der Vorlesung ab und gestattet es, verschiedenste Aspekte über den Stoff der Vorlesung hinaus zu vertiefen.

Aus dem Inhalt

2012. VIII, 392 S. mit 149 Abb.
ISBN: 978-3-8348-1949-9
  1. Einleitung
    1. Ziele und Überblick
    2. Algorithmentheorie - eine kurze Einführung
    3. Grundlagen der Analyse von Algorithmen
    4. Abstrakte Datentypen
    5. Quellenangaben und Literaturhinweise
    6. Aufgaben
  2. Elementare Datenstrukturen
    1. Lineare Listen
    2. Stacks und Queues
    3. Mengen
    4. Graphen und Bäume
    5. Partitionen
    6. Quellenangaben und Literaturhinweise
    7. Aufgaben
  3. Das Wörterbuchproblem
    1. Binäre Suchbäume
    2. Balancierte Bäume
    3. Digitale Suchbäume und Tries
    4. Hashing
    5. Datenstrukturen für das Information Retrieval
    6. Quellenangaben und Literaturhinweise
    7. Aufgaben
  4. Graph-Algorithmen
    1. Kürzeste Wege
    2. Minimale Spannbäume
    3. Quellenangaben und Literaturhinweise
    4. Aufgaben
  5. Sortieren
    1. Primitive Sortier-Algorithmen
    2. Quicksort
    3. Heapsort
    4. Mergesort
    5. Distribution Counting, Radix-Exchange und Radixsort
    6. Sortiernetzwerke
    7. Quellenangaben und Literaturhinweise
    8. Aufgaben
  6. String-Algorithmen
    1. String-Matching
    2. Suffix-Bäume
    3. Quellenangaben und Literaturhinweise
    4. Aufgaben
  7. Entwurfsmethoden für Algorithmen
    1. Divide and Conquer
    2. Dynamisches Programmieren
    3. Greedy Algorithmen
    4. Lineares Programmieren
    5. Transformationen
    6. Quellenangaben und Literaturhinweise
    7. Aufgaben
  8. Komplexitätstheorie
    1. NP-Vollständigkeit
    2. Wichtige NP-vollständige Probleme
    3. Quellenangaben und Literaturhinweise
    4. Aufgaben
  9. Entwurfsmethoden für schwere Optimierungsprobleme
    1. Backtracking und Branch&Bound
    2. Approximations-Algorithmen und Heuristiken
    3. Randomisierte Algorithmen
    4. Quellenangaben und Literaturhinweise
    5. Aufgaben

Anhang

  1. Notationsverzeichnis
  2. Formelsammlung
  3. Syntax der Modell-Programmiersprache

Für Dozenten

Die Inhalte des Buches werden in über 100 Aufgaben vertieft, für die ich auf Anfrage gerne Lösungsvorschläge zur Verfügung stelle. Alternative können diese auch über das Dozenten-Portal des Springer Teubner Verlages bezogen werden.

Downloads

An Invitation To Generating Functions Featuring a Derivation of the Explicit Formula of the Fibonacci Numbers.

Errata zum Buch Entwurf und Analyse von Algorithmen.

 

Formale Grundlagen der Programmierung

Auch zur Vorlesung Formale Grundlagen der Programmierung gibt es ein Lehrbuch, das deren Inhalte (Syntax, Semantik, Berechenbarkeit) behandelt. Über den Inhalt des Buches hinaus stehen unten (sowie auf dem Studierenden-Portal des Springer Vieweg Verlages) den Stoff vertiefende Dokumente zum download bereit.

Aus dem Inhalt

2012. VIII, 194 S. Br.
ISBN: 978-3-8348-1889-8
  1. Syntax von Programmiersprachen
    1. Grundlegende Definitionen
    2. Das Wort- und Analyseproblem
    3. Eigenschaften formaler Sprachen
    4. Quellenangaben und Literaturhinweise
    5. Aufgaben
  2. Semantik von Programmiersprachen
    1. Operationelle Semantik
    2. Denotationelle Semantik
    3. Programmverifikation
    4. Quellenangaben und Literaturhinweise
    5. Aufgaben
  3. Die Grenzen des Berechenbaren
    1. Registermaschinen und primitive Rekursion
    2. Partiell rekursive Funktionen
    3. Berechnebare Mengen
    4. Turingmaschinen revisited
    5. Loop-, While- und Goto-Berechenbarkeit
    6. Chursche These
    7. Schlussbemerkungen
    8. Quellenangaben und Literaturhinweise
    9. Aufgaben

Anhang

  1. Notationsverzeichnis
  2. Beweistechniken
  3. Literaturverzeichnis

 Downloads

Sebastian Wild und Markus E. Nebel -- Ausführliches Beispiel zur Minimierung eines DEA (deterministischer endlicher Automat).

Sebastian Wild und Markus E. Nebel -- Vertiefende Betrachtung und ausführliche Beispiele zu den genannten Beweistechniken.

Raphael Reitzig, Sebastian Wild und Markus E. Nebel -- Eine im Vergleich zum Buch erweiterte Version des Satzes von Rice und sein Beweis.

Sebastian Wild und Markus E. Nebel -- Ein ausführliches Beispiel und vertiefende Gedanken zum Gebrauch der Hoare-Logik.

Sebastian Wild und Markus E. Nebel -- Ausführliches Beispiel (in alternativer Darstellung) zur Umwandlung eines NEA in einen DEA.

Sebastian Wild und Markus E. Nebel -- Vielfältige Beispiele primitiv rekursiver Funktionen.

Sebastian Wild und Markus E. Nebel -- Studium eines Beispiels, für das der (erweiterte) Satz von Rice nicht angewandt werden kann.

Sebsation Wild und Markus E. Nebel -- Ausführliches Beispiel für die Anwendung des Satzes von Rice.