E-Book Overview
Diese Einführung umfasst die Theorie der formalen Sprachen, die Theorie der Berechenbarkeit und einen Überblick über die Komplexitätstheorie. Alle Beweise werden ausführlich behandelt. Schwierige Beweise werden nicht etwa abgekürzt, sondern eingehender behandelt. Damit bietet dieses Buch zugleich eine Einführung in die Technik des Beweisens und ist somit sowohl für Anfänger als auch Dozenten geeignet. Ein größeres Kapitel behandelt alternative Rechenmodelle, unter anderem Zwei-Register-Maschinen, Tag-Systeme, Wang-Maschinen, Rödding-Netze, Splicing und reversible Rechnungen.
E-Book Content
eXamen.press eXamen.press ist eine Reihe, die Theorie und Praxis aus allen Bereichen der Informatik für die Hochschulausbildung vermittelt. Katrin Erk · Lutz Priese Theoretische Informatik Eine umfassende Einführung 3., erweiterte Auflage 123 Dr. Katrin Erk University of Texas at Austin Linguistics Department 1 University Station B5100 Austin, TX 78712 USA Prof. Dr. Lutz Priese Universtät Koblenz-Landau Institut für Computervisualistik Universitätsstr. 1 56070 Koblenz Bis zur 2. Auflage erschienen in der Reihe Springer-Lehrbuch. ISBN 978-3-540-76319-2 e-ISBN 978-3-540-76320-8 DOI 10.1007/978-3-540-76320-8 ISSN 1614-5216 Bibliografische Information der Deutschen Nationalbibliothek Die Deutsche Bibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über http://dnb.d-nb.de abrufbar. © 2008 Springer-Verlag Berlin Heidelberg Dieses Werk ist urheberrechtlich geschützt. Die dadurch begründeten Rechte, insbesondere die der Übersetzung, des Nachdrucks, des Vortrags, der Entnahme von Abbildungen und Tabellen, der Funksendung, der Mikroverfilmung oder der Vervielfältigung auf anderen Wegen und der Speicherung in Datenverarbeitungsanlagen, bleiben, auch bei nur auszugsweiser Verwertung, vorbehalten. Eine Vervielfältigung dieses Werkes oder von Teilen dieses Werkes ist auch im Einzelfall nur in den Grenzen der gesetzlichen Bestimmungen des Urheberrechtsgesetzes der Bundesrepublik Deutschland vom 9. September 1965 in der jeweils geltenden Fassung zulässig. Sie ist grundsätzlich vergütungspflichtig. Zuwiderhandlungen unterliegen den Strafbestimmungen des Urheberrechtsgesetzes. Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten wären und daher von jedermann benutzt werden dürften. Herstellung: LE-TEX Jelonek, Schmidt & Vöckler GbR, Leipzig Einbandgestaltung: KünkelLopka Werbeagentur, Heidelberg Gedruckt auf säurefreiem Papier 987654321 springer.com Vorwort zur 1. Auflage Dieses Buch umfasst den Inhalt der Theoretischen Informatik, wie er in etwa an der Universit¨ at Koblenz-Landau im Grundstudium des Diplomstudienganges Informatik gelehrt wird. Es ist aus verschiedenen Vorlesungen von Lutz Priese und zwei Skripten von Sven Hartrumpf und Katrin Erk entstanden. Zum Zeitpunkt der Erstellung dieses Buches war Frau Erk noch Studentin. Das Buch ist das Ergebnis eines Ringens beider Autoren aus zwei unterschiedlichen Warten: Die professorale Sichtweise von Priese auf formale Korrektheit und die studentische Sichtweise von Erk auf Klarheit und Vermittelbarkeit der Inhalte sind hier eine Symbiose eingegangen. Das Resultat ist ein (hoffentlich) formal korrektes und doch relativ leicht lesbares Buch, in dem der gesamte relevante Stoff der Grundstudiumsvorlesungen mit allen Beweisen dargestellt ist. Wir haben nicht den leichten (modernen?) Weg beschritten, Beweise u ¨berall dort, wo sie anspruchsvoll werden, zu u ¨bergehen oder nur noch zu skizzieren. Im Gegenteil, je anspruchsvol