Inhaltlich werden wir uns eng an die u.g. Bücher halten. Einführende Information findet sich auch im WWW, z.B. unter den untenstehenden Adressen:
http://www.cs.cmu.edu/
http://www.cis.ohio-state.edu/
Literatur:
Inhalt:
Die
algorithmische Geometrie beschäftigt sich mit der Verarbeitung geometrischer
Daten auf dem Computer. Probleme der konstruktiven Geometrie waren bereits
im griechischen Altertum von Interesse. Effiziente Datenstrukturen und
Algorithmen zur maschinellen Lösung von geometrischen Problemen haben
sich in den letzten 20 Jahren zu einer wichtigen Thematik der Informatik
entwickelt.
Die Vorlesung behandelt grundlegende Methodiken und Problemstellungen in diesem Bereich. Diese sind Grundlagen in der grafischen Datenverarbeitung und finden neuerdings auch vermehrt Anwendung in intelligenten Informationssystemen. Konkrete Fragestellungen werden sein: die Berechnung der konvexen Hülle, Voronoi Diagramme, geometrisches Suchen, Schnitt- und Sichtbarkeitsprobleme.
Literaturhinweise:
Erkennen verschiedener Begriffe
trotz unterschiedlicher Wortbildungen und -beugungen (Morphologie).
Vorstellung von Begriffsystemen
vornehmlich aus der Medizin (etwa zur Modellierung der Anatomie)
Techniken zur Speicherung
von "Wissen". Hier sollen Hypertexttechniken und speziell grammatikbasierte
Systeme
(XML und SGML) vorgestellt
werden.
Auf unserer Web-Seite gibt es detailierte Informationen zu den einzelnen Problemkreisen und Vortragsthemen.
Vorbesprechung: 11. Oktober 1999, Uhr 16 ct im Hörsaal 1
der Seefahrtschule
Interessenten können auch gerne schon vorher ihr Interesse an
einem Vortrag bei einem der Veranstalter bekunden.
Unsere Einstiegsseite:
http://www.medinf.mu-luebeck.de/SeminarWS9900.html
In
diesem Seminar diskutieren wir die wichtigsten Konzepte und Methoden der
Quanteninformationsverarbeitung, einschließlich der fundamentalen
Ideen für Quantencomputer von David Deutsch und des berühmten
Algorithmus
von Peter Shor für die schnelle Faktorisierung. Außerdem
werden wir Quantennetzwerke, Kommunikationsprobleme für Quanteninformationsverarbeitung,
Quantenkryptographie und Suche in Datenbanken (einschließlich Algorithmus
von Grover) betrachten.
Es sind noch nicht alle Schwierigkeiten überwunden, einen wirklichen
Quantencomputer zu bauen, dennoch sind die Fortschritte in dieser Richtung
wesentlich. So wurde z. B. im Los Alamos National Laboratory - einem
führenden Forschungsinstitut für experimentelle Quantenberechnungen
in der Welt - im Winter 1998 ein 3-qubit Quantencomputer (mit Hilfe
von Nuclear Magnetic Resonance) konstruiert.
Graph-Algorithmen:
Ein Standardproblem bei
der Planung von Netzwerken ist die Berechnung eines
minimal erzeugenden
Baumes (minimal spanning tree) für gewichtete Graphen. Durch Randomisierung
kann dieses Problem auf einfache Weise gelöst werden. ([MR95], Kapitel
10.3)
Ein weiteres Thema sind
Irrfahrten
(random walks) in Graphen, bei denen durch eine zufällige Auswahl
von Kanten ein unbekannter Graph möglichst schnell durchsucht werden
soll. Eine Erweiterung in Richtung auf schnell mischende Markov-Ketten,
eine elegante Technik um große Zustandsräume zu untersuchen,
ist möglich. ([MR95], Kapitel 6)
Online-Algorithmen:
Beim Paging-Problem
geht es darum, Datenblöcke so in der Speicherhierarchie eines Prozessors
abzulegen, daß er möglichst schnell auf sie zugreifen kann.
Wir betrachten den Fall eines großen Hauptspeichers mit langsamem
Zugriff kombiniert mit einem schnellen Cache, der allerdings nur Platz
für höchstens k Blöcke bietet. Eine Caching-Strategie
legt fest, welche Datenblöcke zu jedem Zeitpunkt im Cache gehalten
werden. Dabei unterscheidet man zwischen off-line-Verfahren, die
die gesamte Datenzugriffssequenz vorab benötigen, und on-line-Verfahren,
die jeweils auf eine neue Datenanfrage hin entscheiden, was im Cache gehalten
wird, ohne nachfolgende Anfragen zu kennen. Für den on-line Fall gibt
es keine deterministischen Paging-Strategien mit einem guten worst-case
Verhalten. Randomisiert kann man dieses Problem jedoch nachweisbar besser
lösen. ([MR95], Kapitel 13.1-3)
(II) Je nach Teilnehmerzahl und Interesse können noch weitere Aspekte und Beispiele von Algorithmen und Randomisierung behandelt werden, etwa die Frage, wie sich Lösungen bestimmter Optimierungsprobleme verhalten, wenn die Eingabedaten zufällig sind. Ein Beispiel ist das
Bin Packing-Problem:
Gegeben sei eine Menge gleicher Behälter mit einer gewissen Kapazität
und eine Menge von n Elementen mit Volumen X1,
X2,
..., Xn. Aufgabe ist es, diese Elemente in möglichst
wenigen Behältern unterzubringen. Die exakte Berechnung der Minimalzahl
L
ist NP-schwierig, aber es gibt verschiedene Approximationsalgorithmen (offline
und online), welche eine Einteilung in L' Gruppen liefern, so daß
der Quotient
L'/L bestimmte Schranken nicht überschreitet.
([H97], Kapitel 2.1-2)
Schließlich betrachten
wir die Zahlen L und L' im Falle von zufälligen und
unabhängigen Eingabedaten Xi. Mithilfe einer
sehr eleganten Methode von M. Talagrand kann man zeigen, daß L/n
und L'/n bei großem n nahezu konstant sind. Talagrands
Methode kann man auf viele Probleme der kombinatorischen Optimierung anwenden.
([H97], Kapitel 2.3; [S97], Kapitel 6; [D96]).
sowie verschiedene Zeitschriftenartikel.
Vortrag: The Digital Library and Future Technologies, Judith Klavans, Columbia University
Lecture Summary: The concept of the digital library is both intuitive and complex. On the intuitive and complex. On the intuitive side, as more and more information becomes available in digital format, the digital library is playing a major role in organizing and delivering this information, much in the same way that it has played for centuries. Electronic books, journals, images, music, and video are now becoming a standard resource, and thus from part of the information pool to which libraries traditionally provide access. In contrast, on the complex side, both the quantity and format of this new digital information presents technical and user-related problems never before encountered by libraries. .
Speaker Information: Judith Klavans is the director of the Center for Research on Information Access (CRIA) at Columbia University. She won a post-doctoral research appointment at MIT, followed by a position in 1983 at the IBM T.J. Watson Research Center. She joined the Columbia University Department of Computer Science in 1992. Klavans was appointed the first director of the newly formed CRIA in 1995. The purpose of CRIA is to foster technical collaboration between research and working applications in the creation of the digital library. Her combined background in linguistics and computer science has provided her with the broad perspective required to lead this innovative interdisciplinary research center. KlavanÇs research focuses on natural language processing, emphasizing the use of large semantic lexicon for extracting and structuring information in monolingual and multilingual texts. She has published more than 40 technical articles and two books..
Contents:
This
class will deal with a variety of central topics in computer science. We
will have various guest speakers, all experts in their fields who present
their material in a well prepared and profound way. The lectures are given
in English, video-taped and distributed by Stanford University Video Communications.
The following list ernumerates the speakers and topis:
Bell, Gordon The Computer Museum, The First Computers
Dijkstra, Edsger W. Reasoning About Programs
Agerwala, Tilak K. Parallel Processing
Allen, Frances E.
Optimizing Compilers for Parallel Computers
Graham, Ronald L. The Shortest
Network Problem
Karlin, Anna R.
On Online Computation
Stroustrup, Bjarne The Design
of C++
Oehler/Blasgen
Evolution of Power PC Architecture
Ditzel, David R.
SPARC Version 9: Adding 64-Bit Adressing and
Robustness to an Existing RISC Architecture
Hillis, Daniel
Architecture of the CM-5
Watanabe, Tadashi Toward the Ultra
High-Speed Computing System
Sun Microsystems Sunergy
22: The Future of Computing Architectures
Lenoski, Daniel E. Scalable
Shared-Memory Multiprocessing and the
Silicon Graphics S2MP Architekture
Fisher, Joseph A.
Instruction-Level Parallelism (ILP)
Forster, James
Multiprotocol Routing in Large Networks
Fraser, A.G.
The Origins of ATM
Feigenbaum, Joan
Security and Privacy in the Information Economy
Pfitzmann, Birgit
Digital Cash
Klavans, Judith
The Digital Library and Future Technologies
Lee, Kai-Fu
Automatic Speech Recognition
In the first meeting we will select those topics we want to discuss. Each presentation lasts between 45 and 60 minutes. The remaining time will be used to discuss the subjects in more detail and to answer questions that are left open. The discussion may be in German or English depending on the preferences of the participants.