Kategorien Preise Unternehmen
Kostenloses Lehrbuch

Grundlagen der Theoretischen Informatik

0 Bewertungen
140
Sprache:  German
In der Theoretische Informatik wird, hautpsächlich mit mathematischen Methoden und Instrumenten, eine Begründung für viele in der Praxis der Informatik auftretenden Phänomene gegeben.
Kostenlose PDF-Lehrbücher herunterladen oder online lesen. Weniger als 15 % Werbeeinblendungen
Business Abonnement kostenlos für die ersten 30 Tage , dann $5.99/mo
Beschreibung
Inhalt

In der Theoretische Informatik wird, hautpsächlich mit mathematischen Methoden und Instrumenten, eine Begründung für viele in der Praxis der Informatik auftretenden Phänomene gegeben. Grob kann man folgende Teilgebiete unterscheiden:

  • Die Automatentheorie, die eine Formalisierung des Begriffs des Automaten vornimmt und untersucht, was die unterschiedlichen Typen von Automaten zu leisten imstande sind.
  • Die Algorithmentheorie, in der untersucht wird, was und mit welchem Aufwand berechenbar ist.
  • Die Theorie formaler Sprachen, die sich mit der Klassifikation von formalen, das heisst künstlichen, Sprachen und deren Eigenschaften wie die zur Beschreibung erforderlichen Grammatiken beschäftigt.

Diese drei Komplexe sind in den universitären Studiengängen zur Informatik meist im Rahmen einer Vorlesung ''Theoretische Informatik'' abgehandelt. Das Buch verfolgt das Anliegen, den Studierenden für diese Vorlesung zusätzlich Material zur Verfügung zu stellen. Es geht primär darum, durch auch verbale Erläuterungen und Beispiele Schwierigkeiten im Verständnis des Vorlesungsstoffes zu beheben. Vertiefende Betrachtungen sind nicht angestrebt. Dadurch wird der Umfang auf eine für das begleitende Studium erträglichen Größe gehalten.

Dabei werden aber die engen Zusammenhänge, die zwischen den einzelnen Gebieten existieren und für das Verständnis wichtig sind gebührend berücksichtigt. Im Buch werden die Beziehungen zwischen Automaten und Sprachen beziehungsweise deren Grammatiken und den Algorithmen besonders betont. Das erfolgt unter Verzicht auf gewisse spezielle Eigenschaften der einzelnen Teilgebiete, zum Beipiel der Komplezität von Algorithmen.

Die der theoretischen Informatik mathematische Vorgehensweise, verbunden mit einer strengen Formalisierung kann auch im Buch nicht umgangen werden. Für ein besseres Verständnis wird aber zum Formalismus der Inhalt informal erläutert. Wo möglich und sinnvoll, werden Beispiele zur Demonstration hinzugezogen. Notwendige mathematische Vorkenntnisse können in einem Anhang nachgeschlagen werden.

  1. Ein Vorwort
  2. Abstrakte Automaten
    1. Das allgemeine Modell
    2. Endliche Akzeptoren
    3. Reguläre Wortmengen
    4. Deterministische endliche Akzeptoren
    5. Minimisierung reduzierter, totaler deterministischer endlicher Akzeptoren
  3. Berechenbarkeit, Entscheidbarkeit und Aufzählbarkeit
    1. Intuitive Anforderungen an Algorithmen
    2. Programme, Programmgesteuerte Rechenautomaten und berechenbare Funktionen
    3. Erweiterung des Standardbefehlssatzes
    4. Wohlstrukturierte Programme
    5. Entscheidbare und aufzählbare Mengen
  4. Rekursionstheorie
    1. Partiell-rekursive Funktionen
    2. Beziehung zu den berechenbaren Funktionen
    3. Mehr über partiell rekursive Funktionen
    4. Mehr über aufzählbare und nicht aufzählbare Mengen
  5. Grammatiken
    1. Typ 0: Der allgemeine Fall
    2. Typ 1: Nichtverkürzende und kontextsensitive Grammatiken
    3. Typ 2: Kontextfreie Grammatiken
    4. Typ 3: Einseitig lineare Grammatiken
  6. Noch mehr Automaten
    1. Turing-Automaten
    2. Linear-Bounded Automaten
    3. Push-Down Automaten
    4. Finite-State Automaten
  7. Weitere Eigenschaften formaler Sprachen
    1. Abschlusseigenschaften
    2. Entscheidbarkeitseigenschaften
home.book.about_author

Peter Bachmann

Peter Bachmann wurde 1942 in Freital, einer kleinen Stadt nahe Dresden, geboren. Dort besuchte er die Gundschule von 1949 bis 1957, anschließend die Erweiterte Oberschule bis zum Erwerb des Abiturs. Erfolgreich nahm er an den Mathematikolympiaden der DDR teil, bei denen er 1961 in Berlin einen ersten Preis erringen konnte. Von 1961 bis 1966 folgte das Studium der Mathematik an der Universität Rostock. Dabei spezialisierte er sich bereits in Richtung Informatik. In der Diplomarbeit 1966 entwickelte er einen Compiler für einen Subset von Algol 60.

Es folgte eine Tätigkeit als Programmierer, später Chefprogrammierer im Kombinat Robotron, bei der Probleme der Betriebssystementwicklung, der Compilertechnik und von Datenbanken bearbeitet wurden. Neben dieser Tätigkeit promovierte Peter Bachmann 1972 an der Technischen Universität Dresden mit einer Arbeit zur Programmoptimierung. Die Resultate dieser Dissertationsschrift wurden auf einen Vortrag zum IFIP-Welt- Kongress 1971 vorgestellt. Ab 1975 wurde Peter Bachmann als Bereichsleiter an der Akademie der Wissenschaften der DDR in Berlin, Zentrum für Rechentechnik tätig. In seinem Bereich wurden sowohl Anwendungen der Rechentechnik in der Kosmosforschung und der Kristallographie als auch Grundlagenuntersuchungen zur numerischen Verfahrenstechnik und zur Softwaretechnologie durchgeführt. Die persönlichen Forschungsgebiete dieser Zeit war die Softwaretechnologie, die Compilertechnik und die theoretische Informatik, speziell die Theorie der Programmschemata. Es entstanden Arbeiten zu formalen Sprachen, zur automatischen Fehlerdiagnose in Compilern und zur Datenflußanalyse. Letzterem Thema war die Habilitationsschrift gewidmet. Auch diese Ergebnisse wurden auf dem IFIP-Kongreß 1977 in Toronto als Vortrag angenommen.

Im Februar 1980 folgte er einem Ruf als Dozent an die Technische Universität Dresden, Sektion Mathematik. 1982 wurde er dann dort als ordentlicher Professor berufen, wo er auf der in Dresden traditionell engen Verbindung zwischen Mathematik und Informatik wissenschaftlich tätig war. Das betraf insbesondere die mathematischen Grundlagen der Informatik, wobei die algebraischen und logischen Methoden eine Hauptrolle spielten. Neben theoretischen Arbeiten zu Terminationsbeweisen wurde ein experimentelles Softwaresystem zur algebraischen Spezifikation unter Einbindung von Beweistechniken geschaffen.

Von 1992 bis 1995 war Peter Bachmann als Full Professor am Departement of Mathematics and Computer Science an der Universität in Kuwait beschäftigt. Hier war er sowohl im Grundstudium als auch in Graduate-Kursen und bei der Betreuung von Master-Arbeiten eingesetzt. In Forschungsprojekten setzte er die Bearbeitung von Fragen der algebraischen Spezifikation, der Termersetzung und des Narrowing fort.

Ab 1995 übernahm er dann als Universitätsprofessor die Leitung des Lehrstuhls ''Programmiersprachen und Compilertechnik'' an der Brandenburgischen Technischen Universität Cottbus. Die Forschungsarbeiten dort betrafen sowohl theoretische Grundlagen als auch praktische Aspekte der Programmierung.

Das Vorlesungsspektrum von Peter Bachmann ist breit gefächert. Neben Mathematik- und Informatik-Grundkursen für Ingenieure hat er Grund- und Spezialvorlesungen vor Mathematik- und Informatikstudenten gelesen, unter anderem Lineare Algebra, Höhere Algebra, Mengenlehre und Logik, Zahlentheorie, Berechnungstheorie, Formale Sprachen und Automaten, Compilertechnik, Mathematische Modelle paralleler Prozesse, Formale Semantik, Programmierung, Nichtnumerische Algorithmen.

Er hat zahlreiche Diplom- und Masterarbeiten sowie Dissertationen betreut und begutachtet.

Die Publikationsliste von Peter Bachmann umfaßt fünf Bücher und mehr als 60 wissenschaftliche Arbeiten.

1997 trat Peter Bachmann in den Ruhestand, hat aber nach wie vor enge Kontakte zu seinem früheren Lehrstuhl.

Peter Bachmann ist verheiratet und hat einen Sohn.

Kolkwitz, September 2015