Refine
Document Type
- Doctoral Thesis (3) (remove)
Language
- German (3) (remove)
Has Fulltext
- yes (3)
Is part of the Bibliography
- no (3)
Keywords
- Approximability (1)
- Approximationsgüte (1)
- Approximierbarkeit (1)
- Bedienstrategie (1)
- Berechnungskomplexität (1)
- Formale Sprache (1)
- Heuristik (1)
- Kommunikationsprotokoll ; Komplexitätstheorie ; Stochastischer Automat ; Nichtdeterministischer Automat ; Quantencomputer (1)
- Maschinelles Lernen (1)
- Problem kürzester Superstrings (1)
Institute
- Informatik (3)
Im Gegensatz zur Minimierung von DFAs ist die exakte Minimierung von NFAs oder regulären Ausdrücken nachweislich schwierig, im allgemeinen Fall PSpace-schwer. Wir zeigen, dass selbst schwache Approximationen zur Minimierung von NFAs und regulären Ausdrücken wahrscheinlich nicht effizient möglich sind. Falls als Eingabe ein NFA oder regulärer Ausdruck der Größe n gegeben ist, löst ein Approximationsalgorithmus für das Minimierungsproblem mit Approximationsfaktor o(n) bereits ein PSpace-vollständiges Problem. Wenn wir uns auf NFAs oder reguläre Ausdrücke über einem unären - also einelementigen - Alphabet beschränken, so ist das Problem der exakten Minimierung NP-vollständig. Wir weisen nach, dass effiziente Approximationen für das unäre Minimierungsproblem mit Approximationsfaktor n^(1-delta) für jedes delta>0 nicht möglich sind, sofern P != NP gilt. Liegt die Eingabe als DFA mit n Zuständen vor, kann sie exponentiell größer sein als ein äquivalenter NFA oder regulärer Ausdruck. Dennoch bleibt das Minimierungsproblem PSpace-schwer, wenn die Anzahl der Übergänge oder Zustände in einem äquivalenten NFA oder die Länge eines äquivalenten regulären Ausdrucks zu bestimmen ist. Wir zeigen, dass auch hierfür keine guten Approximationen zu erwarten sind. Unter der Annahme der Existenz von Pseudozufallsfunktionen, die wiederum auf der Annahme basiert, dass Faktorisierung schwierig ist, zeigen wir, dass kein effizienter Algorithmus einen Approximationsfaktor n/(poly(log n)) für die Zahl der Übergänge im NFA oder die Länge des regulären Ausdrucks garantieren kann. Für die Zahl der Zustände im NFA weisen wir nach, dass effiziente Approximationen mit Approximationsfaktor (n^(1/2))/(poly(log n)) ausgeschlossen sind. Wir betrachten dann Lernprobleme für reguläre Sprachen als Konzeptklasse. Mit den entwickelten Methoden, die auf der Annahme der Existenz von Pseudozufallsfunktionen beruhen, zeigen wir auch, dass es für das Problem des minimalen konsistenten DFAs keine effizienten Approximationen mit Approximationsfaktor n/(poly(log n)) gibt. Für den unären Fall hingegen weisen wir nach, dass es einen effizienten Algorithmus gibt, der einen minimalen konsistenten DFA konstruiert und erhalten somit auch einen effizienten PAC-Algorithmus für unäre reguläre Sprachen, die von DFAs mit n Zuständen akzeptiert werden. Für unäre Beispielmengen weisen wir außerdem nach, dass es keine effizienten Algorithmen gibt, die minimale konsistente NFAs konstruieren, falls NP-vollständige Probleme nicht in Zeit (n^(O(log n)) gelöst werden können. Andererseits geben wir einen effizienten Algorithmus an, der zu unären Beispielmengen einen konsistenten NFA mit höchstens O(opt^2) Zuständen konstruiert, wenn ein minimaler konsistenter NFA opt Zustände hat. Abschließend betrachten wir das Lernen von DFAs durch Äquivalenzfragen. Für den nicht-unären Fall ist bekannt, dass exponentiell viele Fragen für DFAs mit n Zuständen benötigt werden. Für unäre zyklische DFAs mit primer Zykluslänge und höchstens n Zuständen zeigen wir, dass Theta((n^2)/(ln n)) Äquivalenzfragen hinreichend und notwendig sind. Erlauben wir größere zyklische DFAs als Hypothesen, kommen wir mit weniger Fragen aus: Um zyklische DFAs mit höchstens n Zuständen durch Äquivalenzfragen mit zyklischen DFAs mit höchstens n^d Zuständen für d <= n als Hypothesen zu lernen, sind O((n^2)/d) Fragen hinreichend und Omega((n^2 ln d)/(d (ln n)^2)) Fragen nötig.
Wir haben Interaktion in der Kommunikationskomplexität untersucht und dabei die drei Modi probabilistische, (beschränkt) nichtdeterministische und quantenmechanische Kommunikation betrachtet. Bei allen drei Modi haben wir herausgefunden, dass Interaktion für Effzienz oft unerlässlich ist, im nichtdeterministischen Fall gibt es eine Abhängigkeit zwischen dem Einfluss der Interaktion und der erlaubten Anzahl der nichtdeterministischen Ratebits. Abgesehen von dem erreichten besseren Verständnis des Kommunikationsmodells haben wir verschiedene Anwendungen auf andere Berechnungsmodelle beschrieben, bei denen untere Schranken der Kommunikation zu unteren Schranken für andere Ressourcen in diesen Modellen geführt haben. Ein Beispiel eines kommunikations- und interaktionsbeschränkten Modells sind endliche Automaten, welche wir in allen drei Modi untersucht haben. Ein weiteres Beispiel sind Formeln, für die wir eine Verbindung zwischen Einweg Kommunikation und Formellänge herstellen konnten. Diese Verbindung führte zu unteren Schranken für probabilistische, nichtdeterministische und Quanten Formeln. Dabei sind die unteren Schranken für Quanten Formeln und probabilistische Formeln im wesentlichen gleich. Für monotone Schaltkreise haben wir gezeigt, wie nichtdeterministisches Raten die Tiefe drastisch reduzieren kann, und wie eine geringfügige Einschränkung der nichtdeterministischen Ratebits zu einer Tiefenhierarchie führt. Insgesamt lässt sich feststellen, dass die Schwäche interaktionsbeschränkter Kommunikation mathematisch nachvollziehbar ist. Außerdem scheint ein solches Verhalten in der Welt einfacher Berechnungsmodelle häufig aufzutreten. Oder anders gesagt, viele Berechnungsmodelle sind deshalb einfacher zu verstehen, weil sie durch interaktionsbeschränkte Kommunikation analysierbar sind.
Analyse von Heuristiken
(2006)
Heuristiken treten insbesondere im Zusammenhang mit Optimierungsproblemen in Erscheinung, bei solchen Problemen also, bei denen nicht nur eine Lösung zu finden ist, sondern unter mehreren möglichen Lösungen eine in einem objektiven Sinne beste Lösung ausfindig gemacht werden soll. Beim Problem kürzester Superstrings werden Heuristiken herangezogen, da mit exakten Algorithmen in Anbetracht der APX-Vollständigkeit des Problems nicht zu rechnen ist. Gegeben ist eine Menge S von Strings. Gesucht ist ein String s, so dass jeder String aus S Teilstring von s ist. Die Länge von s ist dabei zu minimieren. Die prominenteste Heuristik für das Problem kürzester Superstrings ist die Greedy-Heuristik, deren Approximationsfaktor derzeit jedoch nur unzureichend beschränkt werden kann. Es wird vermutet (die sogenannte Greedy-Conjecture), dass der Approximationsfaktor genau 2 beträgt, bewiesen werden kann aber nur, dass er nicht unter 2 und nicht über 3,5 liegt. Die Greedy-Conjecture ist das zentrale Thema des zweiten Kapitels. Die erzielten Ergebnisse sind im Wesentlichen: * Durch die Betrachtung von Greedyordnungen können bedingte lineare Ungleichungen nutzbar gemacht werden. Dieser Ansatz ermöglicht den Einsatz linearer Programmierung zum Auffinden interessanter Instanzen und eine Vertiefung des Verständnisses solcher schwerer Instanzen. Dieser Ansatz wird eingeführt und eine Interpretation des dualen Problems wird dargestellt. * Für die nichttriviale, große Teilklasse der bilinearen Greedyordnungen wird gezeigt, dass die Länge des von der Greedy-Heuristik gefundenen Superstrings und die des optimalen Superstrings sich höchstens um die Größe einer optimalen Kreisüberdeckung der Strings unterscheiden. Da eine optimale Kreisüberdeckung einer Menge von Strings stets höchstens so groß ist wie ein optimaler Superstring (man schließe einen Superstring zu einem einzelnen Kreis), ist das erzielte Ergebnis für die betrachtete Teilklasse der Greedyordnungen stärker als die klassische Greedy-Conjecture. * Es wird eine neue bedingte lineare Ungleichung auf Strings -- die Tripelungleichung -- gezeigt, die für das eben genannte Hauptergebnis wesentlich ist. * Schließlich wird gezeigt, dass die zum Nachweis der oberen Schranke von 3,5 für den Approximationsfaktor herangezogenen bedingten Ungleichungen (etwa die Monge-Ungleichung) inhärent zu schwach sind, um die Greedy-Conjecture selbst für lineare Greedyordnungen zu beweisen. Also ist die neue Tripelungleichung auch notwendig. Zuletzt wird gezeigt, dass das um die Tripelungleichung erweiterte System bedingter linearer Ungleichungen inhärent zu schwach ist, um die klassische Greedy-Conjecture für beliebige Greedyordnungen zu beweisen. Mit der Analyse von Queueing Strategien im Adversarial Queueing Modell wird auch ein Fall betrachtet, in dem Heuristiken auf Grund von anwendungsspezifischen Forderungen wie Online-Setup und Lokalität eingesetzt werden. Pakete sollen in einem Netzwerk verschickt werden, wobei jeder Rechner nur begrenzte Information über den Zustand des Netzwerks hat. Es werden Klassen von Queueing Strategien untersucht und insbesondere untersucht, wovon Queueing Strategien ihre lokalen Entscheidungen abhängig machen sollten, um ein gewisses Qualitätsmerkmal zu erreichen. Die hier erzielten Ergebnisse sind: * Jede Queueing Strategie, die ohne Zeitstempel arbeitet, kann zu einer exponentiell großen Queue und damit zu exponentiell großer Verzögerung (im Durchmesser und der Knotenzahl des Netzwerks) gezwungen werden. Dies war bisher nur für konkrete prominente Strategien bekannt. * Es wird eine neue Technik zur Feststellung der Stabilität von Queueing Strategien ohne Zeitnahme vorgestellt, die Aufschichtungskreise. Mit ihrer Hilfe können bekannte Stabilitätsbeweise prominenter Strategien vereinheitlicht werden und weitere Stabilitätsergebnisse erzielt werden. * Für die große Teilklasse distanzbasierter Queueing Strategien gelingt eine vollständige Klassifizierung aller 1-stabilen und universell stabilen Strategien.