Prof. Dr. Kurt-Ulrich Witt
Refine
H-BRS Bibliography
- yes (21)
Departments, institutes and facilities
Document Type
- Book (monograph, edited volume) (15)
- Report (4)
- Article (1)
- Preprint (1)
Year of publication
Keywords
- Lehrbuch (6)
- Cutting sticks-Problem (3)
- Teilsummenaufteilung (3)
- Theoretische Informatik (3)
- Algebra (2)
- Cutting sticks problem (2)
- Mengenpartitionsproblem (2)
- Set partition problem (2)
- Algorithmen (1)
- Algorithmische Informationstheorie (1)
Bei der Übertragung und Speicherung von Daten ist es eine wesentliche Frage, inwieweit die Daten komprimiert werden können, ohne dass deren Informationsgehalt verloren geht.
Ein Maß für den Informationsgehalt von Daten ist also von grundlegender Bedeutung. Vor etwa siebzig Jahren hat C. E. Shannon ein solches Maß eingeführt und damit das Lehr- und Forschungsgebiet der Informationstheorie begründet, welches seit dem bis heute hin wesentlich zur Konzeption und Realisierung von Informationsund Kommunikationstechnologien beigetragen hat. Etwa zwanzig Jahre später hat A. N. Kolmogorov ein anderes Maß für den Informationsgehalt von Daten eingeführt. Während die Shannonsche Informationstheorie zum Curriculum von mathematischen, informatischen und elektrotechnischen Studiengängen gehört, ist die Algorithmische Informationstheorie von Kolmogorov weit weniger bekannt und eher Gegenstand von speziellen Lehrveranstaltungen.
Seit einigen Jahren nimmt allerdings die Beschäftigung mit dieser Theorie zu, zumal in der einschlägigen Literatur von erfolgreichen praktischen Anwendungen der Theorie berichtet wird. Die vorliegende Arbeit gibt eine Einführung in grundlegende Ideen dieser Theorie und beschreibt deren Anwendungsmöglichkeiten bei einigen ausgewählten Problemstellungen der Theoretischen Informatik.
Die Ausarbeitung kann als Skript für einführende Lehrveranstaltungen in die Algorithmische Informationstheorie sowie als Lektüre zur Einarbeitung in die Thematik als Ausgangspunkt für Forschungs- und Entwicklungsarbeiten verwendet werden.
Das Cutting sticks-Problem ist in seiner allgemeinen Formulierung ein NP-vollständiges Problem mit Anwendungspotenzialen im Bereich der Logistik. Unter der Annahme, dass P ungleich NP (P != NP) ist, existieren keine effizienten, d.h. polynomiellen Algorithmen zur Lösung des allgemeinen Problems.
In diesem Papier werden Ansätze aufgezeigt, mit denen bestimmte Instanzen des Problems effizient berechnet werden können. Für die Berechnung wichtige Parameter werden charakterisiert und deren Beziehung untereinander analysiert.
Das Cutting sticks-Problem ist in seiner allgemeinen Formulierung ein NP-vollständiges Problem mit Anwendungspotenzialen im Bereich der Logistik. Unter der Annahme, dass P ungleich NP (P != NP) ist, existieren keine effizienten, d.h. polynomiellen Algorithmen zur Lösung des allgemeinen Problems.
In diesem Papier werden für eine Reihe von Instanzen effiziente Lösungen angegeben.
Das Cutting sticks-Problem ist ein NP-vollständiges Problem mit Anwendungspotenzialen im Bereich der Logistik. Es werden grundlegende Definitionen für die Behandlung sowie bisherige Ansätze zur Lösung des Problems aufgearbeitet und durch einige neue Aussagen ergänzt. Insbesondere stehen Ideen für eine algorithmische Lösung des Problems bzw. von Varianten des Problems im Fokus.
Diese Theorie-Einführung hat konsequent praktische Anwendungen im Blick. Seien es Workflow-Systeme, Web Services, Verschlüsselung von Informationen, Authentifizierungsprotokolle oder selbstfahrende Autos - all diese Technologien haben enge Bezüge zu den theoretischen Grundlagen der Informatik. So trägt das Buch dazu bei, dass Studierende die Grundlagen der Theoretischen Informatik nicht nur verstehen, sondern auch anwenden können, um effektiv und produktiv an informationstechnischen Problemlösungen mitwirken zu können. Wegen seiner speziellen inhaltlichen und didaktischen Qualität ist das Buch neben dem Einsatz in der Lehre auch für das Selbststudium geeignet.
Informatikerinnen und Informatiker aller Fachrichtungen müssen die grundlegenden Konzepte, Methoden und Verfahren, die der Entwicklung und dem Einsatz von Informations- und Kommunikationstechnologien zugrunde liegen, verstehen und bei der Lösung von Problemen anwenden können. Das Buch stellt die algebraischen und zahlentheoretischen Grundlagen dafür vor und wendet diese bei der Lösung praktischer Problemstellungen, wie modulare Arithmetik, Primzahltests und Verschlüsselung an. Das Verständnis der Begriffe und deren Zusammenhänge und Zusammenwirken wird u.a. durch Lernziele, integrierte Übungsaufgaben mit Musterlösungen und Marginalien unterstützt. Das Buch ist zum Selbststudium gut geeignet.