Handy-Programmierung für ein Verschlüsselungssystem

Das Foto-PIN Verfahren fuer Symbian Handys

 

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.

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.

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.

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?

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.