Inhalte der Übungen

Im Rahmen der zur Lehrveranstaltung gehörenden Übungen wenden wir das in der Vorlesung erlernte Wissen an und versuchen mit vielen Beispielen eine anschauliche Sicht auf die Thematik zu werfen. Dabei beschäftigen wir uns mit Grundlagen der formalen Sprachtheorie und wenden diese an. Dazu gehören zum Beispiel Syntaxdiagramme, der Rücksprungalgorithmus, EBNF und Fixpunktsemantik. Die Kenntnisse nutzen wir anschließend um uns mit der Programmiersprache C vertraut zu machen und in dieser einfache Datenstrukturen kennenzulernen. Thematisiert werden schlussendlich auch verkettete Listen und Bäume.

Im zweiten Teil behandeln wir grundlegende Algorithmen aus dem Themenbereichen

• Sortieren (Quicksort und Heapsort)
• Suchen und Ersetzen (KMP-Algorithmus und Levenshtein-Dinstanz)
• Graphalgorithmen (Breiten- und Tiefensuche, topologisches Sortieren, kürzeste Wege, algebraisches Pfadproblem).
• EM-Algorithmus

Hinweis: In diesem Semester wurden die Themen Topologisches Sortieren und der Algorithmus von Dijkstra ausgelassen.

Informationen

Im Folgenden sind meine in den Übungen erarbeiteten Lösungsvorschläge zu finden. Diese Lösungen wurden nicht vom Lehrstuhl erstellt und können damit trotz gründlicher Arbeit noch Fehler enthalten. Die Slides und den zugehörigen Latex-Code dazu findet ihr in meinem entsprechenden Github-Repository. Findet ihr einen Fehler in meinen Lösungen, dann fühlt euch eingeladen mir dies mitzuteilen oder direkt selbst mit einem Request zu beheben.

Bitte beachtet stets die aktuellen Informationen auf der Website der Lehrveranstaltung. Bei Fragen oder Problemen könnt ihr euch an mich oder an Thomas Ruprecht wenden.

Informationen zu Übungsverlegungen infolge von Feiertagen oder anderen Ursachen werden auf der Lehrveranstaltungswebsite und hier veröffentlicht.

Übungsmaterial

Die folgenden Materialien habe ich größtenteils in meiner Freizeit erstellt. Damit sind auch (Tipp-) Fehler keinesfalls ausgeschlossen. Die zur Verfügung gestellten Folien sollen keineswegs den aktiven Besuch der Übungen ersetzen, sondern vielmehr eine Hilfestellung sein um sich während der Übung auf das Verständnis konzentrieren zu können.

Teil 1: Formale Sprachen

Teil 2: Programmieren in C

Leider haben wir in den Übungen nicht die Zeit um allen einen funktionsfähigen Compiler und ein optimales Setup zu garantieren. Daher bitte ich euch die Informationen auf der Lehrveranstaltungswebsite zu beachten. Außerdem habe ich unter dem folgenden Button einige Hinweise zusammengetragen. Wie immer sind natürliche auch Google und YouTube sehr gute Quellen für weitere Hilfe. Im Zweifelsfall hilft euch sicher auch der iFSR.

Hinweise zum Programmieren mit C

Teil 3: Algorithmen