Formale Sprachen:
Formale Grammatiken, Normalformen, kontextfreie und kontextsensitive
Sprachen, Comsky Hierarchie, reguläre Sprachen, reguläre
Ausdrücke, endliche Automaten, Pumping Lemma, Wortprobleme
Komplexität algorithmischer Probleme:
Zeit- und Platzmasse, Programmierung von TM, Simulation, Reduktion,
Komplexitätsabschätzungen, Beschleunigung, untere Schranken,
Zeit- und Platzhierarchien, Nichtdeterminismus sequentielle Komplexitätsklassen,
NP-Vollständigkeit Erfüllbarkeitsproblem für Boolesche Formeln,
Optimierungsprobleme
Auswahl Lehrbücher
In general any function from {0,1}n to {0,1}m is called a Boolean function. Clearly, these functions are the basics in informatics. We can model with them computing circuits, formal reasoning, and last but not least we model with them the string-to-string functions, which represent the functions that our computers are computing. In detail we will discuss in this course the following topics:
1. Foundations on Boolean functions:
1.1.Post's Theorem on characterizing complete bases for the set of
Boolean functions.
1.2.Computing special representations of Boolean functions.
2. Circuits for arithmetic functions:
2.1.Circuits for addition.
2.2.Circuits for multiplication.
2.3.Circuits for devision.
2.4.Computing with matrices.
3. Some complexity aspects of VLSI design:
3.1.Basics in lower bound arguments.
3.2.Layout of planar graphs for wire routing.
Mostly we will use for our topics the following books: [W87, U84, G97] Note, in this course we communicate in English, only.
First meeting: ??. April 2001
Here we will find out the participants who will enjoy us with talks on the topics above. Also it will be possible to arrange further lectures.
Please feel free to use my e-mail for any questions. It is also possible to arrange a meeting before the run starts. G. Buntrock
Wir behandeln die Beschleunigung und Effizienz der vorgestellten Algorithmen. Darüber hinaus führen wir Modelle für paralleles Rechnen ein und untersuchen die grundlegenden parallelen Komplexitätsklassen.
Im zweiten Teil der Vorlesung studieren wir asynchrone bzw. verteilte Berechnungen. Wir exemplifizieren die grundlegend neuen Fragenstellungen (neu in Bezug auf den synchronen Fall) und stellen mathematische Modelle zur Beschreibung von verteilten Systemen vor.
Abschliessend studieren wir temporale Logiken für konkurrente Systeme.
Es wird von Woche zu Woche ein Übungsblatt geben, das dann in der Übung besprochen wird. Die Bearbeitung der Aufgaben ist zum Scheinerwerb obligatorisch. Am Semesterende wird eine Rücksprache über die Aufgaben stattfinden.
- Effiziente Algorithmen für algebraische Funktionen
- Grundlagen der Computeralgebra
- Parallelverarbeitung bei rechenintensiven Aufgabenstellungen
In der Vorlesung werden wir die wichtigsten grundlegenden Entwicklungen und Erkenntnisse, die zur Umsetzung dieses anspruchsvollen Zieles in den vergangenen 50 Jahren verfolgt bzw. gewonnen wurden, unter einem einheitlichen Gesichtspunkt behandeln und aktuelle Anwendungen im Data Mining aufzeigen.
Im ersten Teil der Vorlesung spezifizieren wir zunächst allgemeinste
Anforderungen an die Modellierung des intuitiven Begriffes ``Lernen''.
Danach stellen wir die wichtigsten Lernmodelle exemplarisch vor. Es folgen
vertiefende Untersuchungen, die insbesondere die Frage klären, unter
welchen Bedingungen ein angestrebtes Lernziel erreicht werden kann. Abschließend
wird das Problem der Wissensentdeckung in großen Datenbanken behandelt
(Data Mining).
In Ähnlicher Weise stellen wir auch formale Modellbildungen aus den Bereichen Proteinfaltung und Phylogenie vor. Schließlich gehen wir auf die schon klassisch gewordenen und in der modernen Bildverarbeitung oft eingesetzten Methoden des Abbildens von Wachstumsmechanismen in Formale Text-, Bild- und 3-D-Daten ein: die Lindenmayer-Systeme. Wir benutzen hier unter anderem [Fer94,RS80].
Literaturhinweise:
In dieser Vorlesung werden algemeine Techniken für Approximationsverfahren und Strategien zum Entwurf von Approximationsalgorithmen für konkrete ausgewählte Optimierungsprobleme vorgestellt. Anschließend werden Methoden zur Klassifizierung von Optimierungsproblemen nach dem Grad ihrer Approximierbarkeit behandelt.
Empfohlene Literatur
Literatur:
Anschliessend werden grundlegende Eigenschaften rekursiver Funktionen beleuchtet.
Im dritten Teil wenden wir uns der von Manuel Blum begründeten axiomatischen Komplexitätstheorie rekursiver Funktionen zu. Wir untersuchen die rekursive Aufzählbarkeit von abstrakten Komplexitätsklassen, eine sehr allgemeine Form des GAP-Theorems, das Speed-up Phänomen, das Compression Theorem, sowie weitere Sätze.
Sollte es die Zeit erlauben, werden wir auch Anwendungen der Theorie rekursiver Funktionen in verschiedenen Bereichen der Informatik untersuchen (Semantik, Lerntheorie, ...)
Empfohlene Literatur
Trotz intesiver Forschung sind noch nicht alle Schwierigkeiten überwunden, einen wirklichen Quantencomputer zu bauen, dennoch sind die Fortschritte in dieser Richtung wesentlich. Zwei Meilensteine in Richtung der Verwirklichung eines Quantenrechners überraschten in den letzten drei Jahren die Fachpresse. So wurde im Los Alamos National Laboratory - einem führenden Forschungsinstitut für experimentelle Quantenberechnungen in der Welt - im Winter 98 ein 3-qubit Quantencomputer konstruiert. Anfangs dieses Jahres stoppten Wissenschaftler zweier verschiedener Laboratorien (Harvard und Cambridge, Massachusetts) das erste Mal effektiv einen Lichtsimpuls:
AT LAST! LIGHT BROUGHT TO A HALT. For the first time, physicists in two separate laboratories have effectively brought a light pulse to a stop. In the process, physicists have accomplished another first: the non-destructive and reversible conversion of the information carried by light into a coherent atomic form. Sending a light pulse into specially prepared rubidium (Rb) vapor, a group at the Harvard-Smithsonian Center for Astrophysics led by Ron Walsworth and Mikhail Lukin has (1) slowed the pulse's `group velocity' to zero and (2) stored its information in the form of an atomic `spin wave', a collective excitation in the Rb atoms. [...] The atomic spin wave is coherent and long-lived, which enables the researchers to store the light pulse's information and then convert it back into a light pulse with the same properties as the original pulse. This new accomplishment in a simple system increases the promise for quantum communication, which may someday be used to connect potentially ultrafast quantum computers in a large network analogous to the Internet. [From: The American Institute of Physics Bulletin of Physics News, Number 521, January 18, 2001]
In diesem Seminar diskutieren wir die wichtigsten Konzepte und Methoden der Quanteninformationsverarbeitung, Quantennetzwerke, Quantenkryptographie und Suche in Datenbanken. Bekannte Ergebnisse aus diesen Gebieten sind die fundamentalen Ideen über den Quantencomputer von David Deutsch und der berühmten Algorithmus von Peter Shor für die schnelle Faktorisierung.
Aus technischer Hinsicht sind diese Tools durchaus anspruchstvoll und setzen zum Teil einen erheblichen Entwicklungsaufwand voraus. Aus theoreitischer Sicht vermissen wir jedoch in der Regel eine gewisse Intelligenz und Eigendynamik dieser Tools. XML bietet die Möglichkeit vollständig neue Abstraktionen zu unseren Daten in den Daten selbst unterzubringen, die wir dann nutzbringend verwenden können. Hier geht es nicht um bunte Darstellungen und faszinierende Darstellungen sondern um die Entwicklung von selbsttätig operierenden Optimierern, die z. B. äquivalente Tags bestimmen, so dass XML-Dokumente vergleichbarer Typen zusammengefasst werden werden können - auch geht es darum Linkstrukturen zu erweitern und somit das Auffinden von Daten generell zu erleichtern.
In dem Projekt sollen exemplarische XML-Daten aus dem Bereich Maschinenbau
verarbeitet werden. Mit Algorithmen aus den Bereichen Lerntheorie und Künstlicher
Intelligenz sollen Beispielhafte Programme erstellt werden, die solche
Optimierungen bewirken. Die Programme sollen vorzugsweise in ML, C, C++
oder Java erstellt werden. Im Bereich Wissensreprðsentation soll eine
Inklusionsdatenbank aufgebaut werden. Diese kann z. B. genutzt werden,
um Inklusionen von Komplexitätsklassen darzustellen. In diesem weiteren
Vorhaben geht es darum, abstrakte Graphen, die Verbandsstrukturen repräsentieren,
in einer active map abzubilden, so dass Informationen zu den Knoten und
Kanten durch Anklicken angezeigt werden können. Vorzugsweise sind
hier gute HTML- und Java-Kenntnisse hilfreich. Eine in Java programmierte
Schnittstelle an MYSQL zusammen mit einer einfache Graphrepräsentation
sind bereits vorhanden.
Diverse Implementierungen von Algorithmen für grundlegende
kombinatorische Probleme wie z.B. Wegeprobleme in Graphen, Pattern Matching
oder geometrische Probleme wie konvexe Hüllen bilden die Basisbausteine.
Die Teilnehmer üben anschliessend an konkreten Aufgabenstellungen,
siehe dazu Beispiel
Literatur:
