Lernen Sie den Entwurf und die Analyse von Algorithmen
Techniken zur Optimierung von eingebetteten Systemen - Entwurf und Analyse von Algorithmen, logisches Schließen & Automatentheorie
Inhalte des Kurses
Im erstem Teil (Entwurf und Analyse von Algorithmen; ca. 60%) wird auf folgende Inhalte eingegangen: Messung der Komplexität von Algorithmen, Das D&C-Prinzip (Beispiele: Closest Pair und FFT), Dynamische Programmierung (Beispiele: Fibonacci Zahlen und Editierdistanz), Randomisierung (Beispiele: Closest Pair und Primzahltest, RSA-Verfahren), Scheduling Algorithmen (Beispiele: Verfahren von Jackson und Horn), Online Algorithmen und Kompetivität, Graphen (Adjazenzmatrix, Adjazenzlisten, Durchlaufordnungen, Tiefensuche, Breitensuche, kürzeste Wege, Dijkstra Algorithmus)
Im zweiten Teil (Formalisierung und logisches Schließen; ca. 20%) die Aussagenlogik als Mittel zur Formalisierung behandelt und der Unterschied zwischen Syntax und Semantik sowie zwischen Folgerung und Ableitbarkeit erläutert. Es wird auf folgende Inhalte eingegangen: Wohlgeformte Ausdrücke, Wahrheitstafeln, Interpretationen, Modelle, Äquivalenzbegriff und Normalformen, Erfüllbarkeit, Folgerungsbegriff, Ableitbarkeit, Resolution
Im dritten Teil (Automatentheorie; ca. 20%) werden formale Modelle von Rechnern und ihre Mächtigkeit diskutiert. Es wird auf folgende Inhalte eingegangen: Alphabete, Wörter und Sprachen, Operationen auf Wörtern und auf Sprachen, Deterministische und Nicht-deterministische Endliche Automaten (DEA & NEA), Reguläre Ausdrücke und Reguläre Sprachen, Abschlusseigenschaften, Minimale Automaten, Entscheidbarkeit- und Komplexitätsfragen
Unsere Dozenten
Prof. Dr. Thomas Ottmann
Institut für Informatik
E-Mail: ottmann(at)informatik.uni-freiburg.de
Telefon: +49 (0) 761 203-8161
Dr. Andreas Karwath
Institut für Informatik
E-Mail: karwath(at)informatik.uni-freiburg.de
Telefon: +49 (0) 761 203-8029
Haben Sie Interesse an diesem Kurs?
Hier gehts zur Anmeldung.
Oder kontaktieren Sie uns einfach bei weiteren Fragen.
Wofür können die Inhalte verwendet werden?
- Für den Entwurf und die Analyse von eingebetteten Systemen ist häufig das Beachten von Echtzeitbedingungen wichtig. Sie lernen verschiedene Verfahren zur Ablaufplanung von Aufgaben kennen, die unterschiedliche Vorgaben, wie z.B. harte und weiche Zeitbedingungen, und unterschiedliche Optimierungsziele, wie z.B. die Minimierung der maximalen Verspätung, berücksichtigen.
- Mittel Aussagenlogik lassen sich zum Beispiel digitale Schaltungen analysieren und entwerfen oder auch Verschlusspläne für Weichen und Signale erstellen.
- Kellerautomaten werden verwendet um Eigenschaften von Problemen und Algorithmen zu beweisen. So werden Kellerautomaten und kontextfreie Grammatiken dazu verwendet, um zum Beispiel Compiler oder Interpreter für Programmiersprachen zu entwickeln.
