Informatik

Following a general discussion of formal languages, their descriptions, and borderline cases of recognizability, the chapter covers regular languages—which find their most important application in the lexical definition of programming languages—as well as context-free languages, which are used to define the syntax of programming languages. From a theoretical perspective, the clear correspondence between language description and language recognition is satisfying—finite automata correspond to regular languages, and pushdown automata correspond to context-free languages. Further levels of the Chomsky hierarchy are only briefly covered, as they are of lesser practical importance. Instead, a separate chapter on compiler design highlights additional techniques for deriving a parser—that is, the complete "front end" of a compiler—from a language description. The concept of an "algorithm" is explained using various machine models, and Church’s thesis—that every reasonable definition of "computability" leads to the same class of functions—is also confirmed. The limits of what is algorithmically feasible are clearly delineated using the halting problem and Rice’s theorem. The concluding chapter on complexity theory explores, among solvable problems, the boundary between those that can be solved with reasonable (polynomial) effort and those whose solution is not significantly more efficient than systematically trying out candidate solutions. This chapter leads the reader to the most famous unsolved problem in theoretical computer science: P = NP? The first volume of Computer Science explains the fundamental concepts: programming, algorithms, and data structures. The second volume is devoted to technical topics—in particular, computer architecture, operating systems, computer networks, and specifically the Internet. The book is intended for all beginners who wish to seriously engage with computer science, whether for self-study or to accompany lectures. The subsequent volumes of this book explore the topics of computer architecture, operating systems, computer networks, the Internet, compiler design, and theoretical computer science in greater depth. Prof. Dr. Heinz-Peter Gumm is a professor of theoretical computer science in Marburg. After completing his studies in Darmstadt and Winnipeg (Canada) from 1970 to 1975 and earning his habilitation in 1981, he held professorships in Hawaii, California, and New York. His research areas include formal methods, general algebras, and coalgebras. Prof. Dr. Manfred Sommer is Professor Emeritus of Practical Computer Science in Marburg. After completing his studies in Göttingen and Munich from 1964 to 1969, he served as an assistant at Germany’s first computer science institute at the Technical University of Munich. This was followed by ten years at Siemens in Munich, and from 1984 to 2014 he was a professor of computer science in Marburg.
Nach einer allgemeinen Diskussion formaler Sprachen, deren Beschreibungen und Grenzfällen der Erkennbarkeit werden die regulären Sprachen behandelt, welche in der lexikalischen Defi nition von Programmiersprachen ihre wichtigste Anwendung finden sowie die kontextfreien Sprachen, mit denen man die Syntax von Programmiersprachen definiert. Aus theoretischer Sicht befriedigend ist die eindeutige Entsprechung zwischen Sprachbeschreibung und Spracherkennung den regulären Sprachen entsprechen die endlichen Automaten und den kontextfreien Sprachen die Stackmaschinen. Weitere Stufen der Chomsky-Hierarchie werden nur kurz behandelt, da sie in der Praxis von geringerer Bedeutung sind. Stattdessen zeigt ein eigenes Kapitel zum Thema Compilerbau weitere Techniken auf, die aus einer Sprachbeschreibung einen Parser, also das komplette »front-end« eines Compilers, entstehen lassen. Der Begriff des »Algorithmus« wird anhand verschiedener Maschinenmodelle erklärt und bestätigt wird auch die Churchsche These, dass jede vernünftige Defi nition von »Berechenbarkeit« auf die gleiche Klasse von Funktionen führt. Die Grenzen des algorithmisch Machbaren werden anhand des Halteproblems und des Satzes von Rice klar abgesteckt. Das abschließende Kapitel zur Komplexitätstheorie erkundet unter den lösbaren Problemen die Grenze zwischen denen, die mit einem vertretbaren (polynomiellen) Aufwand lösbar sind und solchen, deren Lösung nicht wesentlich effi zienter ist, als ein systematisches Ausprobieren von Lösungskandidaten. Dieses Kapitel führt den Leser zu dem bekanntesten noch ungelösten Problem der Theoretischen Informatik: P = NP? Der erste Band der Informatik erklärt die grundlegenden Konzepte: Programmierung, Algorithmen und Datenstrukturen. Der zweite Band ist technischen Themen gewidmet – insbesondere der Rechnerarchitektur, Betriebssystemen, Rechnernetzen und speziell dem Internet. Das Buch richtet sich an alle Einsteiger, die sich ernsthaft mit Informatik beschäftigen wollen, sei es zum Selbststudium oder zur Begleitung von Vorlesungen. In den folgenden Bänden dieses Buches werden die Themen, Rechnerarchitektur, Betriebssysteme, Rechnernetze, Internet, Compilerbau und Theoretische Informatik vertieft. Prof. Dr. Heinz-Peter Gumm ist Professor für Theoretische Informatik in Marburg. Nach dem Studium in Darmstadt und Winnipeg (Kanada) von 1970 bis 1975 und der Habilitation 1981 folgten Professuren in Hawaii, Kalifornien und New York. Seine Forschungsgebiete sind Formale Methoden, Allgemeine Algebren und Coalgebren. Prof. Dr. Manfred Sommer ist emeritierter Professor für Praktische Informatik in Marburg. Nach dem Studium in Göttingen und München von 1964 bis 1969, war er Assistent am ersten Informatik-Institut in Deutschland an der TU München. Es folgten zehn Jahre bei Siemens in München und von 1984 bis 2014 war er Informatik-Professor in Marburg.