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)
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.
Internet, Soziale Netzwerke, Spiele, Smartphones, DVDs, digitaler Rundfunk und digitales Fernsehen funktionieren nur deshalb, weil zu ihrer Entwicklung und Anwendung mathematisch abgesicherte Verfahren zur Verfügung stehen. Dieses Buch vermittelt Einsichten in grundlegende Konzepte und Methoden der Linearen Algebra, auf denen diese Verfahren beruhen. Am Beispiel fehlertoleranter Codierung wird einführend gezeigt, wie diese Konzepte und Methoden in der Praxis eingesetzt werden, und am Beispiel von Quantenalgorithmen, die möglicherweise in Zukunft eine Rolle spielen, wird deutlich, dass die Lineare Algebra zeitinvariante Konzepte, Methoden und Verfahren bereitstellt, mit denen IT-Technologien konzipiert, implementiert, angewendet und weiterentwickelt werden können. Wegen seiner didaktischen Elemente wie Vorgabe von Lernzielen, Zusammenfassungen, Marginalien und einer Vielzahl von Übungen mit Musterlösungen eignet sich das Buch nicht nur als Begleitlektüre zu entsprechenden Informatik- und Mathematik-Lehrveranstaltungen, sondern insbesondere auch zum Selbststudium.
Logiken, Mengen, Relationen, Funktionen, Induktion und Rekursion sind grundlegende mathematische Konzepte und Methoden, die in allen Bereichen der Informatik für die Beschreibung von Problemen und deren Lösung benötigt werden. Das Beherrschen dieser Konzepte und Methoden ist Voraussetzung für das Studium fast aller weiteren Informatik-Module, nicht nur in Bereichen der Mathematik und der Theoretischen Informatik, sondern auch in Bereichen der Praktischen Informatik, wie z.B. Programmierung, Datenstrukturen, Algorithmen und Datenbanken. Das Buch stellt die grundlegenden Begriffe, ihre Eigenschaften und Anwendungsmöglichkeiten schrittweise vor. Das Verständnis der Begriffe und deren Zusammenhang und Zusammenwirken wird u.a. durch Lernziele, integrierte Übungsaufgaben mit Musterlösungen und Marginalien unterstützt; das Buch ist zum 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.
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.
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.
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.