Lehrstuhl fürFormale Sprachen und Theoretische Informatik
Angebote
Angebote

Hier eine Liste von Arbeiten und Aufgabenstellungen, für Studienarbeiter, Diplomanden, sowie Abschlußarbeiten für Bachelor- und Masterstudenten.

Auch Hiwi-Stellen werden hier annonciert. 



 

Dense Completeness

Eine Sprache heißt vollständig für eine Komplexitätsklasse, wenn sie in der Komplexitätsklasse liegt und sich alle Sprachen in der Komplextitäsklasse auf diese Sprache reduzieren lassen. Beispielsweise ist das Problem SAT für NP vollständig.

Read more...
 

Wahlsysteme

Es gibt viele alltägliche Situationen, in denen Gruppen von Menschen zwischen verschiedenen Alternativen entscheiden müssen - bekannte Beispiele sind etwa politische Wahlen, Wählen eines Klassensprechers/einer Kommission, Auswahl eines gemeinsamen Reiseziels, Aufgabenverteilungen, Preisverleihungen. Ziel ist es, einen Konsens zu finden, der die unterschiedlichen, individuellen Wünsche und Präferenzen der einzelnen Teilnehmer ("Wähler") möglichst gut respektiert - man spricht hier von Präferenzenaggregation. Oftmals müssen nicht nur die Präferenzen von Menschen aggregiert werden, sondern beispielsweise auch die von autonomen Software-Agenten, die kollektive Entscheidungen treffen sollen.

Read more...
 

Logic vs. Sprachkalküle

In der Aussagenlogik gibt es neben den klassischen Kalkülen auch die intuitionistischen Kalküle. In der Komplexitätstheorie führen diese auf die Klassen NP und PSPACE. Das formalsprachliche Problem der Äquivalenz regulärer Ausdrücke in verschiedenen Varianten führt ebenfalls auf diese Klassen. Salomaa führte für die formalsprachliche Fragestellung vollständige Kalküle ein. Ihre Aufgabe ist es die Kalküle auf den beiden Seiten gegenüber zu stellen.
 

D+-Gleichungen

Wir betrachten folgendes Problem: Gegeben ein Binärbaum, an dessen Blätter der Wert True und an dessen inneren Knoten die Nand-Funktion steht. Frage: Wertet dieser Baum zu True aus?

Read more...
 

TüC

TüC ist ein Programmpaket zum Arbeiten mit Sprachen, Automaten und Monoiden. Das Programmpaket ist sehr Modular aufgebaut, es fehlen aber noch etliche Module. Ihre Aufgabe wäre es Datenstrukturen und Algorithmen zu entwerfen und zu implementieren.

Read more...
 
  • «
  •  Start 
  •  Prev 
  •  1 
  •  2 
  •  Next 
  •  End 
  • »