Uwe Schöning Bücher

Dieses Buch beschreitet einen neuen Weg. Inhalte vor allem der Theoretischen Informatik werden hier für ein breiteres Publikum aufbereitet und verfügbar gemacht. Der Autor verdeutlicht, dass der Zugang zur Informatik über die formale Methode, die Grundideen und die Algorithmik viel Spaß machen kann. Effiziente, praxisrelevante Lösungsansätze stehen im Vordergrund, was Verständlichkeit und Anwendbarkeit der Ideen fördert.

Dieses Lehrbuch der Algorithmik stellt die grundlegenden Algorithmen dar und vermittelt die Prinzipien von Algorithmusanalyse und -entwurf. In einem einführenden Kapitel werden die benötigten Grundbegriffe aus der Theoretischen Informatik, der Stochastik und der Komplexitätsanalyse bereitgestellt. Die folgenden Kapiteln behandeln die Gebiete Sortieren und Selektion, Hashing, Dynamisches Programmieren, Greedy-Algorithmen, Algorithmen auf Graphen, Optimiertes Suchen in Bäumen, Datenkompression sowie algebraische Algorithmen, String Matching und Heuristiken. Im abschließenden Kapitel werden die effizientesten Algorithmen für das Erfüllbarkeitsproblem der Aussagenlogik diskutiert. Prof. Schöning gelingt durch seinen verständlichen Stil, viele Beispiele und das Aufzeigen von Querverbindungen eine lebendige und gut verständliche Gesamtdarstellung der Algorithmik.

Das Buch macht den Leser in kompakter Form mit den wesentlichen GrundzA1/4gen der Theoretischen Informatik vertraut. Es fA1/4hrt in die Thematik Formale Sprachen, Grammatiken und Automaten ein. An eine Diskussion des Berechenbarkeitsbegriffs und unentscheidbarer Probleme schlieAt sich eine EinfA1/4hrung in die Komplexi-tAtstheorie, speziell die Theorie der NP-VollstAndigkeit, an. QuerbezA1/4ge zwischen den Fachgebieten werden aufgezeigt. In der 3. Auflage wurden Erweiterungen eingearbeitet, wie zum Beispiel der KomplementabschluA der kontext-sensitiven Sprachen, die Greibach- und Kuroda-Normalform, weitere Unentscheidbarkeitsergebnisse fA1/4r kontextfreie Sprachen, ein Beweis fA1/4r die A"quivalenz von LOOP-Berechenbarkeit und primitiver RekursivitAt, ein Hinweis auf das 10. Hilbertsche Problem, weitere NP-VollstAndigkeitsresultate, sowie eine etwas anders gestaltete Darstellung der Ackermann-Funktion.

Das Buch macht den Leser mit den wesentlichen Teilgebieten der formalen Logik vertraut, die Bestandteil der Ausbildung in Theoretischer Informatik sind. Die Darstellung orientiert sich an den Bedürfnissen von Informatikstudierenden. Insbesondere werden viele mehr auf das Prinzipielle ausgerichtete Resultate der formalen Logik unter einem algorithmischen Gesichtspunkt behandelt. Diese Vorgehensweise erleichtert entscheidend den Zugang zu dem abstrakten Themengebiet. Prof. Schöning gelingt eine kompakte und verständliche Darstellung der Aussagen- und Prädikatenlogik, bei der die benötigten Begriffe präzise eingeführt und durch Beispiele veranschaulicht werden. Darauf beruhend werden Anwendungen der Logik in der Informatik, wie z. B. Resolution, Automatisches Beweisen und Logik-Programmierung behandelt. Zahlreiche Übungsaufgaben mit ausführlichen Lösungshinweisen erleichtern die Vertiefung des Lernstoffes.

Das Kompendium – im Rahmen einer Vorlesung an der Universität Ulm entstanden – ist kein Vorlesungsskript im eigentlichen Sinne; das heißt, man findet hier nicht den Ablauf der Vorlesung chronologisch wiedergegeben. Vielmehr war es die Intention des Autors, in diesem Kompendium die wesentlichen Begriffe, Definitionen und Sätze aus dem Kontext der Kryptologie vorzufinden – angeordnet nach Sachgebieten wie Komplexitätstheorie, Informationstheorie, Zahlentheorie sowie den entsprechenden kryptographischen Algorithmen und Protokollen. Und das alles in kompakter Form.

SAT (für satisfiability) ist das bekannteste NP-vollständige Problem, das sich mit der Erfüllbarkeit von Aussagenlogik beschäftigt. Bei diesem Problem wird eine Formel mit Boole’schen Variablen und Verknüpfungen gegeben, und es wird eine Wertezuweisung gesucht, die die Formel wahr macht. Dieses algorithmische Problem ist zentral für NP-Vollständigkeitsnachweise und wird oft als „Drosophila“ der Algorithmik bezeichnet. In den letzten Jahren wurden leistungsstarke Algorithmen entwickelt, die in der Lage sind, Formeln mit Hunderten oder Tausenden von Variablen zu lösen. Besonders herausfordernd sind Formeln mit wenigen Lösungen, was der Suche nach einer Nadel im Heuhaufen gleicht. In diesem Buch wird detailliert erklärt, wie solche Algorithmen funktionieren und wie logische Kalküle sowie heuristische Suchmethoden eingesetzt werden. Es ist die erste deutschsprachige Veröffentlichung zu diesem Thema und erscheint als Band 1 der Reihe Mathematik für Anwendungen. Diese Reihe zeigt, dass Mathematik mehr ist als nur Theoreme und Definitionen – sie bietet die Möglichkeit, anwendungsnahe Probleme der realen Welt zu lösen. Die Bände sind für Vorlesungen und Seminare in Ingenieurwissenschaften und Informatik gedacht und zielen darauf ab, Themen kompakt und didaktisch durchdacht zu präsentieren. Sie sind wertvoll für Studierende, Praktiker aus der Industrie sowie Lehrer und Schüler in mathematischen Fächern.

Der größte Stolperstein in den ersten Semestern eines Informatik- oder Ingenieurstudiums ist für viele Studienanfänger die Mathematik. Die zunächst ungewohnte mathematische Notation sowie die konsequente Art, eine Behauptung durch einen Beweis zu begründen, stellt sich oft wie ein Eintreten in eine neue, bisher nicht bekannte Welt dar. Hier will dieser Leitfaden helfen und die Studierenden während der ersten Semester begleiten. Die Darstellung orientiert sich an den Grundbedürfnissen der neuen Bachelor-/Master-Studiengänge und schlägt eine Brücke quer über die eigentlichen Fachvorlesungen. Insbesondere soll es die Quervernetzung des Wissens - in Bezug auf spezi? sche Informatikthemen - erleichtern.

In kompakter Form macht das Buch mit den wesentlichen Themen vertraut, die in einer Vorlesung über Algorithmen behandelt werden. Im Mittelpunkt stehen dabei die verschiedensten sequentiellen Algorithmen, deren Komplexitätsanalyse und allgemeine Algoithmen-Paradigma. Prof. Schöning gelingt es, kurz, konkret und verständlich die wichtigsten algorithmischen Aufgabenstellungen (Selektion, Sortieren, Hashing), Algorithmen auf Graphen, algebraische und zahlentheoretische Verfahren zu behandeln. Hinzu kommen heuristische Algorithmenprinzipien wie z. B. genetisches Programmieren.