1. Hauptnavigation
  2. Navigation des Hauptbereiches
  3. Inhalt der Seite

Lehrveranstaltungen im WS

Grundlagen der Informatik

Inhalte:

  • Aussagenlogik
  • Beweistechniken
  • Kombinatorik
  • O-Notation und Laufzeitanalyse von Algorithmen
  • Relationen und Graphen, Graphalgorithmen
  • Such- und Sortieralgorithmen
  • Codierungstheorie

Materialien

Regelung zur PVL: In den schriftlichen Lernkontrollen muss die Hälfte der Punktzahl erreicht werden. Die Lernkontrollen finden statt am 6.11., 26.11., 17.12., 21.1., jeweils in der Vorlesung. Unterlagen sind nicht zugelassen.

Die Übungen finden ab dem 17.10. statt.

Verlegung von Vorlesungen in 2019:

  • Vom 14.1. auf den 15.1. um 13:20 in S 216.

Programmierung 1

Inhalt:

  1. Einführung

  2. Variablen und Datentypen

  3. Funktionen

  4. Kontrollstrukturen

  5. Datenstrukturen

  6. Ein- und Ausgabe

  7. Weitere Programmbeispiele

 

Es wird die Programmiersprache C verwendet.

Aufgabe für die APL:

  • Implementierung eines Linksbaums
  • Damit Implementierung eines Min-Heaps
  • Damit Implementierung des Algorithmus Heapsort
  • Implementierung von Unit-Tests

Abgabe: Bis 13. 1. 2019 in OPAL. Die Abnahme findet in den KW 4 und 5 in den Praktika statt.

Aufgaben und Programme

Algorithmen und Lernverfahren

Inhalte:

  • Landau-Symbole, Laufzeitanalyse.
  • Suchverfahren: Binäre Suche, Suchbäume, Hashing, Skipliste.
  • Sortierverfahren: Theoretische Laufzeitschranke, Quicksort, Mergesort, Heapsort, Bucketsort.
  • Dynamische Programmierung: Editierdistanz, längste gemeinsame Teilfolge, Rucksackproblem, TSP, Viterbi-Algorithmus.
  • Greedy-Algorithmen: Bruchteil-Rucksackproblem, Aktivitäten-Auswahlproblem, Huffman-Kompression, Union-Find-Datenstruktur, Kruskal-Algorithmus.
  • Logistische Regression.

Literatur:

  • Schöning: Algorithmik.
  • Cormen, Leiserson, Rivest, Stein: Algorithmen - Eine Einführung.
  • Jurafsky, Martin: Speech and Language Processing.
Aktualisiert: 08.02.2019