This book assembles some of the most important problems and solutions in theoretical computer science-from computability, logic, circuit theory, and complexity. The book presents these important results with complete proofs in an understandable form. It also presents previously open problems that have found (perhaps unexpected) solutions, and challenges the reader to pursue further active research in computer science.

This book introduces the notions and methods of formal logic from a computer science standpoint, covering propositional logic, predicate logic, and foundations of logic programming. It presents applications and themes of computer science research such as resolution, automated deduction, and logic programming in a rigorous but readable way.

The style and scope of the work, rounded out by the inclusion of exercises, make this an excellent textbook for an advanced undergraduate course in logic for computer scientists.

This is a short introductory book on the topic of propositional and first-order logic, with a bias towards computer scientistsa ]. SchAning decides to concentrate on computational issues, and gives us a short book (less than 170 pages) with a tight storylinea ]. I found this a nicely written book with many examples and exercises (126 of them). The presentation is natural and easy to followa ]. This book seems suitable for a short course, a seminar series, or part of a larger course on Prolog and logic programming, probably at the advanced undergraduate level. a" SIGACT News

Contains examples and 126 interesting exercises which put the student in an active reading mode.... Would provide a good university short course introducing computer science students to theorem proving and logic programming. a" Mathematical Reviews

This book concentrates on those aspects of mathematical logic which have strong connections with different topics in computer science, especially automated deduction, logic programming, program verification and semantics of programming languages.... The numerous exercises and illustrative examples contribute a great extent to a betterunderstanding of different concepts and results. The book can be successfully used as a handbook for an introductory course in artificial intelligence. a" Zentralblatt MATH

Dieses in der 5. Auflage vorliegende Standardwerk macht Sie in kompakter Form mit den wesentlichen GrundzA1/4gen der Theoretischen Informatik vertraut. Der erste und grAAte Teil behandelt Formale Sprachen, Grammatiken und Automaten. Prof. SchAning gelingt durch seinen verstAndlichen Beweisstil und viele Beispiele eine A1/4bersichtliche und im Detail gut nachvollziehbare Darstellung dieses grundlegenden Gebietes der Theoretischen Informatik. Es schlieAt sich die Behandlung der Berechenbarkeitstheorie an. Hier werden beginnend mit dem intuitiven Berechenbarkeitsbegriff und der Churchschen These die wichtigsten Theoreme bis hin zum GAdelschen UnvollstAndigkeitssatz bewiesen. Der dritte Teil fA1/4hrt in die KomplexitAtstheorie ein und legt hierbei den Schwerpunkt auf die Theorie der NP-VollstAndigkeit. Zahlreiche QuerbezA1/4ge und Bemerkungen erleichtern das VerstAndnis und vertiefen das Gelernte.

Leserstimmen auf amazon.de:

a žMir gefAllt besonders, dass er dabei mehr die Ideen betont als das Formale. Daher liest sich das Buch sehr gut und flA1/4ssig."

a žAlles in allem das kompakteste und beste Buch dieses Themengebietes."

Dieses Lehrbuch der Algorithmik stellt die grundlegenden Algorithmen dar und vermittelt die Prinzipien von Algorithmusanalyse und -entwurf. In einem einfuhrenden Kapitel werden die benoetigten Grundbegriffe aus der Theoretischen Informatik, der Stochastik und der Komplexitatsanalyse bereitgestellt. Die folgenden Kapiteln behandeln die Gebiete Sortieren und Selektion, Hashing, Dynamisches Programmieren, Greedy-Algorithmen, Algorithmen auf Graphen, Optimiertes Suchen in Baumen, Datenkompression sowie algebraische Algorithmen, String Matching und Heuristiken. Im abschliessenden Kapitel werden die effizientesten Algorithmen fur das Erfullbarkeitsproblem der Aussagenlogik diskutiert. Prof. Schoening gelingt durch seinen verstandlichen Stil, viele Beispiele und das Aufzeigen von Querverbindungen eine lebendige und gut verstandliche Gesamtdarstellung der Algorithmik.

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 Bedurfnissen 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. Schoening gelingt eine kompakte und verstandliche Darstellung der Aussagen- und Pradikatenlogik, bei der die benoetigten Begriffe prazise eingefuhrt 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 UEbungsaufgaben mit ausfuhrlichen Loesungshinweisen erleichtern die Vertiefung des Lernstoffes.