Refine
H-BRS Bibliography
- yes (20)
Departments, institutes and facilities
Document Type
- Book (monograph, edited volume) (14)
- 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)
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 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.
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.
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.
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.
Warum beeinträchtigen bestimmte Kratzer auf einer CD nicht die Wiedergabequalität? Wie können Datenübertragungen gegen Informationsverlust gesichert werden? Warum und wie funktionieren öffentliche Verschlüsselungssysteme? Worin ist deren Sicherheit begründet? Auf welcher Grundlage werden Routing-Tabellen in Netzwerkknoten erstellt? Wie wird eine optimale Kompression von Daten erreicht?
Diese und viele andere Fragen müssen zufriedenstellend beantwortet werden können, um bestimmte Qualitäten von Informations- und Kommunikationstechnologien zu erreichen. Informatikerinnen und Informatiker aller Studienrichtungen müssen in der Lage sein, diese Technologien erfolgreich einzusetzen und weiterzuentwickeln. Dazu müssen sie die Grundlagen kennen, auf denen diese Technologien basieren.