Informatik

My point is that a good programmer in this time does not just write programs, a good programmer builds a working vocabulary - in other word, a good programmer does language design, though not from scratch, but building on the frame of a base language.

Willkommen in der Zukunft. Durch Quantencomputer ist Primfaktorzerlegung kein Problem mehr, RSA und andere Verfahren sind nutzlos geworden. Das unheimlich wichtige Dokument D=(1,1,0) soll aber trotzdem signiert werden, also braucht es dafür ein anderes Verfahren mit einer anderen Sicherheitsbedingung. Das Lamport-Diffie Einmail-Signaturverfahren (LD-OTS) eilt zur Rettung.

LD-OTS braucht nur eine funktionierende Hashfunktion, dass eine solche noch existiert ist Mindestvoraussetzung. Und dann ist es ganz einfach, der Signierer bietet schlicht die passenden Urbilder zu den vorher veröffentlichten und durchs Dokument ausgewählten Hashs an.

Also so: Für jedes Bit im Dokument hat der Signierer zwei Werte, die geheim bleiben, den Signaturschlüssel, hier: x = (x01, x11; x02, x12; x03, x13).

Veröffentlicht wird vorher der Verifizierungsschlüssel: y = (y01, y11; y02, y12; y03, y13) = (H(x01), H(x11); H(x02), H(x12); H(x03), H(x13))

Zum Signieren des Dokuments D = (1, 1, 0) veröffentlicht der Signierer dann je nach Bit an der jeweiligen Stelle seinen Teil des Signaturschlüssels und damit die Urbilder der Hashfunktion als Signatur, hier also: (x11, x12, x03). Der Verifizierer braucht dann dann nur zu schauen, ob die veröffentlichten Signaturschlüsselteile mit dem vorher veröffentlichten Verifizierungsschlüssel übereinstimmen, also H(x11) = y11, H(x12)=y12 und H(x03)=y03 ist.

Angestoßen von dieser Diskussion über die Performance des Bayes-Plugins schreibe ich hier mal die theoretische Grundlage des Plugins und damit auch eines generischen Bayes-Spamfilters auf, damit man sich bei einer eventuellen Überarbeitung hierdran orientieren kann.

Bayes-Formel

Das Bayes-Theorem wurde entdeckt, verworfen und schließlich wiederentdeckt. Ich glaube, die mathematischen Einwände gegen die Formel finden sich manchmal noch in der Kritik an solchen Filtern wieder, deshalb sei ihr Vorhandensein erwähnt.

Die allgemeine Formal lautet:

P(A) ist die Wahrscheinlichkeit für A, P(A|B) ist die Wahrscheinlichkeit für A unter der Bedingung B, also wenn B eingetreten ist.

Wie sieht das nun für Spam aus? So:

Zu beachten ist, dass wir diese Spamwahrscheinlichkeit für jedes Wort im Kommentar wissen wollen, daher am Ende mehrere Wahrscheinlichkeiten aufaddieren und normalisieren müssen.

Aufdröselung

Es gibt also genau drei Variabeln zu berechnen: Die Inverse Wahrscheinlichkeit, die Wahrscheinlichkeit von Spam und die Wahrscheinlichkeit für das Auftreten solcher Wörter. Das für jedes Wort. Was genau bedeuten die Formeln jeweils?

P(Wort|Spam)

Dies ist die Wahrscheinlichkeit, dass in einem Spamkommentar dieses Wort vorkommt: Spamkommentare mit diesem Wort / Spamkommentare

P(Spam)

Die Gesamtwahrscheinlichkeit, dass ein Kommentar Spam ist: Spamkommentare / Kommentare.

P(Wort)

Die Wahrscheinlichkeit, dass dieses Wort überhaupt in einem Kommentar vorkommt: Kommentare mit diesem Wort / Kommentare

Programmiertechnische Konsequenzen

Es ist völlig klar, dass eine Datenbank gebraucht wird und die Bewertung größtenteils aus dem Heraussuchen der richtigen Daten zu den Worten besteht. Zuerst muss ein sogenannter Tokenizer den Kommentar in seine Einzelwörter zerlegen. Im Wesentlichen ist das ein:

tokenize(text) {
    tokens = split("\W", text )
    return unique(tokens)
}

Das Lernen eines Kommentars als Ham oder Spam ist nun nichts anderes, als diese Tokens in diese Datenbank namens "tokens" zu schreiben:

token (text) | ham (number) | spam (number)

Ist das Token schon vorhanden, wird der zugehörige Ham- bzw Spamwert um eins erhöht. Gleichzeitig wird der Gesamtzähler Hamkommentare bzw Spamkommentare um eins erhöht.

Diese Datenbank zusammen mit den Gesamtzählern gibt uns nun alle nötigen Werte:

P(Wort|Spam)

spam = sql_query("Select spam from tokens where token = Wort")
spam / (Spamkommentare)

P(Spam)

Spamkommentare / (Spamkommentare + Hamkommentare)

P(Wort)

ham, spam = sql_query("Select ham, spam from tokens where token = Wort)"
(ham + spam) / (Spamkommentare + Hamkommentare)

Formelveränderungen

Schaut man sich nun die Bewertungsfunktion im Bayes-Plugin an wird man feststellen, dass der PHP-Code nicht nur wesentlich unschöner als mein Pseudocode aussieht, sondern auch anders funktioniert. Das liegt daran, dass das Plugin auf b8 aufbaute, und b8 nicht simpel das Bayes-Theorem benutzt, die Wahrscheinlichkeiten addiert und dann durch ihre Anzahl teilt. Diese Änderungen basieren auf Tests und anderen theoretischen Annahmen als den hier gezeigten. Insbesondere die folgenden Änderungen sind enthalten oder denkbar.

Law of total probability

Wer Vorkenntnisse hat oder nachrecherchierte, dem könnte aufgefallen sein, dass Wikipedias Bayes-Spamfilterformel anders aussieht:

P(Wort) wird hier gemäß dem Law of total probability umgeformt. Ohne das gerade nachgerechnet zu haben vermute ich, dass die Werte gleich sein sollten und diese Formel nur P(Wort) anders betrachtet.

Häufigkeit von Tokens im Kommentar

Wie oft ein Wort im Kommentar auftaucht sollte die Wahrscheinlichkeit beeinflussen. Dieser Artikel hier ist kein Spam, obwohl nun Viagra auftaucht, aber wäre jedes Wort Viagra, wäre er durchaus Spam. Deshalb beachtet b8 die Häufigkeit eines Tokens.

Wichtigkeit

Eine beliebte Spammertaktik ist, Kommentare mit ewig langem Fülltext auszustaffieren und den Spammerinhalt so zu verstecken. Der Gedanke dabei ist, dass die vielen harmlosen Worte den ganzen Kommentar harmlos erscheinen lassen. Die auch von b8 genutzte Taktik dagegen ist die Einführung eines Wichtigkeitsfaktors: Beziehe nur die Tokens in die Schlussrechnung ein, die eine Tendenz zu Spam oder Ham haben, also um einen bestimmten Faktor von der Mitte 0,5 abweichen. Der Gedanke dahinter ist, dass die vielen Füllwörter die Bewertung sonst gegen 0,5 tendieren lassen würden.

Optimierungsmöglichkeiten

Ich schrieb oben, dass dieser Artikel die theoretischen Grundlagen zwecks einer späteren Optimierung des Filters deutlich machen soll.

Diese Optimierungsmöglichkeiten sehe ich bis jetzt:

Ham-Spam-Faktor

Der Anstoßgeber dieses Eintrags ist diese Diskussion. Grischa schlug vor, über irgendeinen Faktor auszugleichen, dass ein typischer Blog sehr viel mehr Spam als Ham bekommt und daher der Filter zu streng werden würde. Meiner Meinung nach ist das nicht wirklich ein Problem, da diese Verteilung elementar für den Filter ist, und nicht automatisch neuer Spam eingelernt wird, wenn man das nicht will.

Wikipedia erwähnt, dass P(Spam) generell 0,8 sei. Vielleicht würde es helfen, diesen Wert festzusetzen statt ihn empirisch zu bestimmen?

Häufigkeit von Tokens

Wie oben beschrieben ist die Häufigkeit von Wörtern innerhalb eines Kommentars ein wichtiger Faktor. Zur Zeit fließt das aber nur indirekt in die Bewertung ein, indem es bei der Bewertung selbst ignoriert wird, beim Einlernen aber beachtet wird. Statt in der Tabelle den Ham- bzw Spamwert um eins zu erhöhen, wird er um die Anzahl der Tokens erhöht. Bei der Bewertung aber wird jedes Token nur einmal beachtet, selbst wenn es mehrmals vorkommt. Das könnte man ändern.

Es ist auch ein kritischer Punkt, weil man sich hier leicht mit Anzahl der Tokens und Anzahl der Kommentare verheddern kann. Die Formel müsste genau geprüft werden.

Konstanten

Bei der Übernahme von b8 wurde die Klassifizierungsberechnung blind übernommen. In ihr enthalten sind einige Konstanten, die auf den Testergebnissen beruhen. Es geht um diese Zeile:

$ratings[$word] = (0.15 + (($stored_tokens[$word]['ham'] + $stored_tokens[$word]['spam']) * $rating)) / (0.3 + $stored_tokens[$word]['ham'] + $stored_tokens[$word]['spam']);

0,15 und 0,3 sind die Konstanten, die hier direkt die Bewertung beeinflussen und entfernt bzw verändert werden könnten.

Schlusswort

Es ist nunmal Mathematik. Ich hoffe, die Erklärung macht die Funktionsweise des Filters trotzdem klarer. Die Optimierung des Filters könnte ein sehr interessantes Projekt sein, aber auch sehr zeitaufwändig.

Hinweise zu Fehler in den Formeln nehme ich dankend entgegen

Vll tritt da eine Schwäche von mir bei den formalen Grundlagen zutage, aber sowohl Currying als auch Monads sind so Begriffe, die ich (z.B. bei Hackernews) öfter mal lese, die mir aber schlicht nichts sagen. Kann mich nicht erinnern, darüber je was gelernt zu haben. Dabei hatte ich ja funktionale Programmierung, mochte sie schlußendlich sogar, und da wird wohl beides genutzt.

Nach meiner Faustregel hat es niemand verstanden, den ich bis jetzt gelesen habe, denn ich finde keine einfache Erklärung. Vielleicht kann hier jemand helfen? Ich beschreibe mal, was ich bisher habe.

Currying

Abgeleitet aus der comp.lang.functional-FAQ: Das scheint total unspannend zu sein. Hat man nur einen Parameter zur Verfügung, dann kann man um

 f(x,y)

auszudrücken, x durch eine Funktion ersetzen, also:

(f'(x))(y) = f (x,y)

Das solls sein?

Gut, mir ist klar, dass man das gebrauchen kann, wenn man in einer seltsamen Sprache zwar lambda zur Verfügung hat, aber nur einparametrige Funktionen. Das wäre dann ein theoretisches Konstrukt ohne Praxisrelevanz, das höchstens dann gut ist, wenn eine solche Sprache zu leichteren Beweisen führt und man sie nutzt, weil man bewiesen richtigen Programmcode braucht.

Monads

Hier geht mein im Studium gestählter Bullshit-Sensor an. Und zwar, weil hier die FAQ jede Antwort darüber verweigert, was es ist, und nur darüber schreibt, wofür es gut ist:

What is a "monad", and what are they used for?

The concept of a monad comes from category theory; full details can be found in any standard textbook on the subject. Much of the interest ...

Was mich wieder zu meiner Frage führt, ob es wirklich Dinge gibt, die so kompliziert und trotzdem wichtig sind, dass man sie nicht mehr mit einfachen Worten ausdrücken kann (siehe die Sprachbarriere bei FGdI).

Wie auch immer, aus diesem Paper und Wikipedia wird die Essenz des Begriffs nicht wirklich klar. Laut dem Paper: Ein Monad ist ein Ding M, das Seiteneffekte darstellt, und das man deswegen vor den normalen Typ stellt? Das Divisionsbeispiel aus der Wikipedia ist für mich an sich einleuchtend (abgesehen von der grauenhaften Syntax):

(//) :: Maybe a -> Maybe a -> Maybe a
_ // Nothing = Nothing
Nothing // _  = Nothing
_ // Just 0 = Nothing
Just x // Just y = Just (x / y)

Statt eine Division / zu definieren, die Zahlen zurückgibt (und dann Sonderfälle wie die Division durch 0 fangen zu dürfen), definiere ich eine Division //, die entweder Zahlen oder einen Ausweichtyp ausgibt. Ähnlich wie Listen, die entweder Elemente oder ein Schlußsymbol beinhalten. Und wieder: Ist das alles?

Ich muss es bezweifeln, sonst könnte man es einfach erklären.

Das Konzept von Salts ist eigentlich ein sehr einfaches. Da ich jetzt aber ein paarmal über Menschen gestolpert bin, denen das Konzept nicht klar wurde (und es auch selbst am Anfang für etwas hoch-komplexes hielt), versuche ich mich mal an einer einfachen Erklärung.

Funktionsweise

Angenommen, man hat eine Webanwendung, in die sich Leute mit einem Passwort einloggen können (sie könnte Serendipity heißen). Selbstverständlich speichert man das Passwort dieser Nutzer nicht im Klartext ab, weil dann ein einfacher Blick in die Datenbank genügen würde, um das Passwort zu verraten. Stattdessen speichert man den Hash H des Passworts, der durch eine beliebige kryptographische Hashfunktion generiert wird:

H = hash(Passwort)

hash() ist im wesentlichen eine Einwegfunktion, also kann aus H nicht direkt Passwort rekonstruiert werden. Es existiert kein unhash(H) == Passwort.

Bei einem Loginversuch mit dem Passwort wird dann das Hashen wiederholt und mit dem gespeicherten H in der Datenbank verglichen:

bool loginCorrect?(passwort) {
    return (hash(passwort) == H)
}

Nur wenn die beiden Hashes übereinstimmen, stimmen die durch die Hashes repräsentierten Passwörter und der Nutzer kann sich erfolgreich einloggen.

Nun kommt der Salt dazu. Der wird zufällig gewählt, ist also eine zufällige Zeichenfolge, und wird dem Passwort angehängt:

hash(Passwort + Salt) = salted_H

Das wird nun bei jeder Passworterstellung gemacht, also insbesondere jedes Mal ein neuer Salt berechnet. Vom Prinzip her ist das alles.

Der Salt wird natürlich mit dem salted_H in der Datenbank gespeichert. Das ist notwendig, denn bei einem Loginversuch wird ja wieder ein Hash berechnet und mit dem gespeicherten verglichen:

bool loginCorrect?(passwort) {
    return (hash(passwort + Salt) == salted_H)
}

Warum?

Bleibt die Frage, warum man einen solchen Salt nutzen sollte. Die Antwort: Sicherheit. Es soll verhindert werden, dass aus den Hashes indirekt das Passwort berechnet werden kann. In der Konsequenz geht es um ein Gegenmittel gegen Rainbow-Tables.

Die Datenbank der Webanwendung könnte gestohlen werden, wie das ja in letzter Zeit reihenweise passierte. Ziel des Angreifers ist es danach, das Passwort im Klartext herauszufinden. Aus zwei Gründen:

1. Wenn er nur die Datenbank hat, könnte er sich dann in der Webanwendung einloggen und Aktionen durchführen
2. Viele Nutzer verwenden Passwörter mehrfach, sodass der Angreifer bei vielen anderen Diensten gültige Logins und Passwörter bekommen würden

Im Idealfall hat der Angreifer bisher nur die Datenbank mit dem Nutzernamen (der natürlich auch gehasht werden könnte), dem salted_H und dem Salt jedes Nutzers. Schon dank des Hashens reicht das nicht, um sich einzuloggen. Denn die Loginfunktion hasht ja wieder, gibt man den salted_H da ein entsteht also:

return (hash(salted_H + Salt) == salted_H))

Auch ohne den Salt wäre das false, denn man kann davon ausgehen, dass hash(hash(X)) != hash(X).

Ohne den Salt würde der Angreifer jetzt versuchen, eine Rainbow-Table aufzubauen. Dafür nutzt er seinen privaten Rechencluster in etwa so:

1000000000.times {
    passwort = guess_password()
    rainbow_table[hash(passwort)] = passwort
}

Er erstellt also eine Liste von gehashten Passwörtern und ihrem Klartext. Danach braucht er nur in der Datenbank zu schauen, ob der Hash verwendet wurde, und weiß deswegen, welches Passwort verwendet wurde um den Hash zu erstellen. Schon hat er das Passwort im Klartext.

Genau das verhindert der Salt. Da zwei Datenbanken oder sogar zwei Nutzer in einer Datenbank unterschiedliche Salts benutzen, unterscheidet sich ihr salted_H, selbst wenn sie das gleiche Passwort benutzen. Wird also eine Datenbank gestohlen, muss zwingend für jeden einzelnen Nutzer geguckt werden, ob

hash(guess_password() + Salt) == salted_H 

gilt. Eine Rainbow-Table, die die Salts mitspeichert würde absurd groß werden:

for salt in salts {
    1000000000.times {
        passwort = guess_password()
        rainbow_table[salt][hash(passwort +salt)] = passwort
    }
}

Daher kommt auch die Bewegung, teure Hashfunktionen wie bcrypt zu nutzen und sie möglichst noch mehrmals durchlaufen zu lassen. Bei einem Login ist die benötigte Zusatzzeit kaum bemerkbar, aber bei einem Knacken der Hashes tut jede ms weh.

Kurz

Ein Hash mit Salt ist einfach hash(X + Salt). Er schützt nicht generell vor schwachen Passwörtern, aber er erschwert es, dass Passwörter aus dem Hash rekonstruiert werden können.

Stanford bietet von September bis Dezember eine KI-Vorlesung als offene Online-Version an (via). Das Video zeigt ein paar der Inhalte:

Mich erinnerte es sehr an meine KI-Vorlesung. Klar, wir sind nicht mit Robotern durch die Stadt gefahren, aber die gezeigten Inhalte hatten wir größtenteils. Und er basierte auf dem gleichen Buch, was wohl wirklich das Standardwerk ist (Artificial Intelligence: A Modern Approach).

Was mir wieder klar machte, wie toll ich das Thema finde. KI ist nicht einfach eine simple Untermenge der Informatik. Wenn Informatik das Beherrschen von Informationen, das algorithmische Lösen von Problemen ist, dann ist das genau die Definition der KI. Die Algorithmen der schwachen KI haben mehr als andere den Ansatz, ein Problem generisch zu lösen statt es direkt lösen zu lassen, oder sind eher das Zusammenspiel von Algorithmen zur generischen Lösung eines Problems.

Beispiel Schach. Um dafür eine Lehrbuch-KI zu schreiben ist zwar Unmengen an Können notwendig, doch eigentlich braucht man "nur" eine eine performante Min-Max-Variante, plus den nötigen Optimierungen um der Komplexität beizukommen. In denen liegt dann die Schwierigkeit, aber Min-Max selbst ist ein sehr simpler Algorithmus, der einfach alle möglichen Varianten durchgeht und dann den Zug wählt, der für den Spieler das beste Ergebnis hat. Der Pseudocode hat 5 Zeilen.

Daher sah ich KI als praktisches Anwenden des Algorithmik-Kurses (der selbst schon ziemlich praxisbezogen war) und als Versuch, Probleme geschickt zu lösen. Da wird kein Data erschaffen, sondern Spiele gespielt, was nichts anderes als Problemlösen ist.

Und Problemlösen, darum geht es doch immer. Deshalb ist das Ansehen des Stanford-Kurs für die meisten Informatiker und Programmierer, die einen solchen Kurs noch nicht gehört haben, wahrscheinlich eine gute Idee.

Eines der neun von Turing vorweggenommenen Argumente gegen die Möglichkeit einer starken KI bezieht sich auf Ada Lovelaces Zitat:

It has no pretensions to originate anything. It can do whatever we know how to order it to perform.

Bei uns in der Diskussion darüber fiel der folgende Satz:

Ein Flugzeug kann auch besser fliegen als sein Ingenieur.

Fand ich treffend.

Bei dem Würfelspiel-KI-Wettbewerb vom Linuxmagazin hatte ich angekündigt, später mehr über meinen Ansatz zu schreiben. Denn der ist an sich simpel, funktionierte aber ganz gut - bis zu einer gewissen Grenze.

Statt auszurechnen, was die beste Lösung für das Problem ist, habe ich ein sehr simples Botmodell gebaut. Nochmal vereinfacht sah das so aus:

class DiceClient():
    def __init__(self, maxPoints, sprint, enemySprint):
        self.enemySprint = enemySprint
        self.maxPoints = maxPoints
        self.sprint = sprint

Er würfelte also und hatte zur Entscheidung, ob er weiterwürfelt, drei Merkmale bzw Grenzen. Wieviele Punkte ...

1. ... haben ich bereits in diesem Versuch erwürfelt
2. ... hat der Gegner insgesamt
3. ... habe ich insgesamt

Bei Erreichen der ersten Grenze speicherte er, bei Erreichen der anderen beiden versucht er, durchzuwürfeln um doch noch zu gewinnen.

Statt also nun diese Grenzen selbst möglichst optimal zu wählen, erstellte ich 20 solcher Bots mit zufälligen Werten und ließ sie spielen - gegen sich selbst, gegen andere Bots (von mir und von Freunden), gegen die Bots auf den Servern. Die Bots wurden nach ihrem Erfolg geordnet. Waren ein paar Spiele zusammen, ersetzte ein Kind der gewinnenden Bots einen der verlierenden. Dazu wurde die mutate() aufgerufen:

def mutate(self):
        random.seed()
        self.maxPoints = self.maxPoints + random.randint(-1,1)
        self.sprint = self.sprint + random.randint(-1,1)
        self.enemySprint = self.enemySprint + random.randint(-1,1)

Das Kind eines Bots war also eher kein identisches Abbild, sondern hatte leicht andere Werte. So sollte die Gesamtpopulation sich schrittweise den optimalen Grenzen annähern.

maxPoints: 30, sprint: 46, enemySprint: 48, generation: 23

Dieser Auszug aus der Speicherdatei beschreibt mein Endergebnis bei ungefähr 10000 Spielen mit diesem Botmodell, dabei habe ich es dann auch gelassen. Mit dem simplen, wobei schon erweiterten, Botmodell sind ein paar Konstrukte nicht ohne weiteren Umbau möglich gewesen die ich gerne als manuellen Startwert ausprobiert hätte, z.B. erst bis 16 würfeln, speichern, danach durchsprinten. Und dafür fehlte mir dann die Zeit.

Vor kurzem hat noch das Linuxmagazin seinen Würfelwettbewerb veranstaltet, jetzt richtet auch Google einen KI-Wettbwerb aus. Das Thema ist etwas anspruchsvoller (und attraktiver): Planetwars. Jeder Spieler hat Planeten, dort wachsen Schiffe, diese können losgeschickt und so neue Planeten erobert werden.

Die Auswertungreihenfolge bei (funktionalen) Programmiersprachen wie Scheme ist nicht automatisch gegeben. Beide Methoden im Titel haben Vorteile und Scheme z.B. nutzt im Standard die Applikative. Was bedeutet das überhaupt?

Applikative Reihenfolge: Erst Parameter auswerten, dann die Funktion ausführen.

Normale Reihenfolge: Die Funktion mit den unausgewerteten Parametern ausführen, dann die Parameter auswerten.

Applikativ

Im Klartext meint das folgendes: Eine Funktion wie + wird üblicherweise applikativ ausgewertet. Also würde ein Aufruf von

(2 + (5 - 3))

dazu führen, dass im nächsten Schritt dort

(2 + 2)

steht und dann mit diesen Parametern das gemacht wird, was die Funktion + damit nunmal machen will.

Normal

Bei einer bedingten Operation wäre das problematisch: Würden erst die Parameter ausgewertet, könnte es sein, dass die Prozedur überhaupt nicht mehr terminiert, z.B. dann, wenn eine Funktion sich selbst rekursiv aufruft - denn wie soll der Rekursionsanker getroffen werden, die Rekursion also zurücklaufen, wenn immer erst der Parameter ausgewertet wird? Ein Beispiel dafür wäre (die fiktive Funktion f in pseudo-Pseudocode)

f(n) {
if ( ( n  = 0 ) then 100 else f(n - 1) )
}

Hier sorgt die normale Auswertungsreihenfolge dafür, dass sobald n=0 ist die 100 ausgegeben wird, ohne dass der folgende elseteil ausgeführt wird, wodurch die Rekursion über die Parameterauswertung des if eben doch weiterliefe (weitere Beispiele).

Auswirkungen

Die normale Auswertungsreihenfolge ist immer dann notwendig, wenn mit Konstrukten wie Streams gearbeitet werden soll, die eben nicht immer vor der eigentlichen Betrachtung zuende aufgelöst werden können.

PS: Wikipedia nennt die Systeme strikte und verzögerte Auswertung.

Ein PDA ist ein Kellerautomat. Aus einer kontextfreien Grammatik kann man problemlos einen PDA erstellen. Dabei kommt man mit einem einzigen Zustand aus.

Ein Beispiel aus einer Grammatik:

S -> AX | BY | a

Um aus der Grammatik den PDA zu bilden geht man die Liste von oben nach unten durch und setzt sie in eine PDA-Zeile ein. Normalerweise hat man ja noch mehr zu übersetzen als nur das S, da A, X, Y und B auch noch zugeordnet werden müssen. Als Beispiel deckt das S aber jeden Fall ab.

Die Syntax:

(Zustand, Kellersymbol, Eingabe, Folgekellersymbol, Folgezustand)

Zuallererst wird ein Einstieg benötigt:

(q0, #, ?, S, q0)

Nun können die Zeilen der Grammatik angehängt werden, hier die S-Zeile von oben:

(q0, S, ?, AX, q0)
(q0, S, ?, BY, q0)
(q0, S, a, ?, q0)

An der Übersetzung kann man schon das ganze Schema ablesen. Die beiden q0 bleiben immer gleich. S ist das S von vor dem Pfeil.

An die dritte Stelle, die Eingabe, kommt das ?, wenn das betrachtete Zeichen noch weiter aufgelöst werden kann, dann kommt das Zeichen als Folgekellersymbol selbst in die vierte (so beim AX und beim BY gemacht).

Genau andersrum funktioniert es bei dem a: das kommt direkt in die Eingabe. Das ? füllt dann die vierte Stelle, ein echtes Folgekellersymbol gibt es in dem Fall ja nicht.

Diesem Schema folgend geht man nun die ganze Grammatik durch. Der Einstieg muss natürlich nur einmal gesetzt werden, ganz am Anfang.

Zusatz: Die so gebildeten Transitionen sind nur ein Teil des PDAs. Die Zustandsmenge Q und die akzeptierende Zustandsmenge A beinhalten aber nur {q0} - andere Zustände werden ja nicht angelegt. Das Kelleralphabet besteht aus den Zeichen vor den Pfeilen, hier also dem S.

Hornklauseln sind Klauseln wie {Q,¬A,¬B} mit jeweils maximal einem positiven Bestandteil. Mit dem Markierungsalgorithmus kann man in einfachen Schritten ihre minimale Belegung erhalten.

Schritt 1: Umformen

Dieser Schritt ist nicht unbedingt nötig, vereinfacht die Sache aber. Die Klauseln werden umgeformt in Implikationsform.

Dies funktioniert nach folgenden Regeln:

Bei negativen und positiven Elementen wird das positive gefolgert:

{Q,¬A,¬B} := ((A & B)->Q)

Nur negative Elemente folgern !T (wird ausgewertet zu 0):

{¬Q, ¬A,¬B}:=((A & B & Q)-> !T)

Ein positives Element folgert sich aus T (wird ausgewertet zu 1):

{Q}:=(T->Q)

Ein Beispiel:

Aus

M:= { {a,¬c}, {c}, {¬a, b, ¬c} } {¬b, ¬c, a, ¬d)

wird

(c -> a) & (T -> c) & ((a & c) -> b) & ((b & c & d) -> a)

Schritt 2: Initialmarkierung

Nun werden die Element markiert, die aus einem T gefolgert werden:

M1: (c¹ -> a) & (T -> c¹) & ((a & c¹) -> b) & ((b & c¹ & d) -> a)

Schritt 3: Whilemarkierung

Schritt für Schritt werden alle bisher unmarkierten Elemente markiert, die aus Elementen gefolgert werden, die schon alle(!) markiert sind.

Abbruchbedingungen:

1. Es gibt nichts mehr zu markieren: erfüllbar

2. Es wäre !T zu markieren: unerfüllbar.

Dem Beispiel von oben folgend:

M2: (c¹ -> a²) & (T -> c¹) & ((a² & c¹) -> b) & ((b & c¹ & d) -> a²)
M3: (c¹ -> a²) & (T -> c¹) & ((a² & c¹) -> b³) & ((b³ & c¹ & d) -> a²)
=> erfüllbar.

Schritt 4: Auswertung

Teil der Minimalbelegung sind nun die markierten Elemente. In diesem Fall sind das alle außer d:

   a   

   b   

   c   

   d   

   1   

   1   

   1   

   0   

Quelle

Der Quicksort ist vom Prinzip schon sehr effektiv. Trotzdem kann er in natürlich optimiert werden, um den Wort-Case seltener eintreten zu lassen und die reale Performance zu erhöhen - nur wie? Welche Verfahren sind praktikabel, welche Kleinigkeiten kann man beachten?

Ich muss da selbst noch einiges lernen. Was mir aber bei meinen Versuchen bisher aufgefallen ist:

1. Kleinigkeiten nützen schon etwas. Wenn man nicht das mittlere Element als Pivot, sondern das linke oder das rechte wählt, dann kann man den jeweiligen Cursor auch links bzw. rechts vom Pivot ansetzen.

2. Noch eine Kleinigkeit: Beim Tauschen darauf achten, dass die zu tauschenden Elemente nicht sowieso schon gleich sind (evtl. ist das auch schlecht: kostet die Abfrage mehr Leistung als das unnötige Tauschen?)

3. Es gibt eine (relativ) naive Implementierung, bei der das linke, das mittlere und das rechte Element verglichen werden und der Mittelwert als Pivot gewählt wird. Wenn man die sowieso manuell betrachtet, kann man sie auch sortiert zurückschreiben: das kleinste nach links, das größte nach rechts, das Pivot in die Mitte.

Meinen bisherigen Tests nach hilft das enorm bei halbwegs geordneten Listen, schadet aber ein kleines bißchen bei komplett ungeordneten Zahlenabfolgen.

4. Wenn nur noch zwei Elemente in der zu sortierenden Liste sind, sollte das linke zum Pivot werden. Das kann aber natürlich auch eine Macke in meiner Implementation sein.

Noch testen will ich, wie es sich auswirkt, wenn man mehrere Threads nutzt und wie man das am besten anstellt.

Und sowieso: Ist es in der Realität nicht eher besser, auf die Kleinigkeiten zu verzichten und sich auf die Wahl eines guten Pivots zu beschränken, weil so Abfragen gespart werden - oder wiegen die gesparten Arrayzugriffe das wieder auf?

Auch wenn es mindestens die Hälfte meiner Leserschaft nicht wirklich interessieren wird, zeige ich hier mal wie man einen DFA per Hand (auch) minimieren kann. Das ist nämlich eigentlich recht einfach, solange der DFA simpel genug ist, wird aber oft genug kompliziert erklärt.

Nehmen wir folgenden DFA als zu minimierenden:

Minimieren kann nur funktionieren, wenn man überflüssige Zustände entfernt bzw. zusammenfasst. Am Anfang haben wir kein weiteres Unterscheidungsmerkmal als die Frage, ob die Zustände final sind (im Bild oben dargestellt durch die Doppelkreise) oder nicht. Grafisch betrachtet sieht das dann so aus (die Linien stellen die Übergänge dar, a ist blau, b braun, ab türkis)

Der Doppelpunkt markiert das nächste Unterscheidungskriterium: Zustand 1 und 2 gehen über a bzw. b in die linke Gruppe, Zustand 5 geht jeweils in sich selbst, also in die rechte Gruppe: Hier kann innerhalb der Gruppe "125" nochmal unterschieden werden zwischen "12" (gehen beide in die linke Gruppe) und "5" (geht in die rechte Gruppe).

Nun sieht der nächste Schritt so aus:

Da 3 und 4 nun auf eine andere Gruppe als 0 zeigen, kann jetzt auch in der linken Gruppe unterschieden werden.

Führt man das Verfahren nun nochmal aus, zeigt jedes Gruppenmitglied auf die gleiche Gruppe, ein weiteres Unterscheiden ist also nicht möglich.

Der fertig minimiert DFA sieht also wie folgt aus:

PS: Die DFAs wurden mit dem Automaton Simulator gezeichnet.