By Klaus W. Wagner
Diese kompakte Einführung in die Theoretische Informatik stellt die wichtigsten Modelle für zentrale Probleme der Informatik vor. Dabei werden u.a. folgende Fragestellungen behandelt:
Welche Probleme sind algorithmisch lösbar? (Theorie der Berechenbarkeit und Entscheidbarkeit)
Wie schwierig ist es algorithmische Probleme zu lösen? (Theorie der Berechnungskomplexität, NP-Theorie)
Wie sind informationsverarbeitende Systeme prinzipiell aufgebaut? (Theorie der endlichen Automaten)
Welche Strukturen besitzen Programmiersprachen? (Theorie der formalen Sprachen)
In der Erarbeitung dieser Themen wird der Abstraktionsprozeß von den realen Gegenständen der Informatik zu den in der Theoretischen Infromatik etabliertern Modellen, wie z.B. Random-Access-Maschinen, Turingmaschinen und endlichen Automaten, nachvollzogen und umgekehrt verdeutlicht, used to be diese Modelle aufgrund der über sie gewonnenen Erkenntnisse für die Praxis leisten können.
Der vorliegende textual content stellt reichhaltiges fabric für die Gestaltung einer einsemestrigen vierstündigen Vorlesung bereit. Viele Beispiele und Aufgaben erleichtern das Verständnis und ermöglichen die Aneignung des Stoffes auch im Selbststudium. Zum Testen selbstgeschriebener Programme kann ein Compiler vom Server des Autors heruntergeladen werden.
Read or Download Theoretische Informatik: Eine kompakte Einführung PDF
Similar machine theory books
Data Integration: The Relational Logic Approach
Facts integration is a severe challenge in our more and more interconnected yet unavoidably heterogeneous international. there are lots of info assets to be had in organizational databases and on public info platforms just like the world-wide-web. now not unusually, the assets usually use diverse vocabularies and diverse info buildings, being created, as they're, via various humans, at assorted instances, for various reasons.
This publication constitutes the joint refereed complaints of the 4th overseas Workshop on Approximation Algorithms for Optimization difficulties, APPROX 2001 and of the fifth overseas Workshop on Ranomization and Approximation thoughts in computing device technological know-how, RANDOM 2001, held in Berkeley, California, united states in August 2001.
This ebook constitutes the complaints of the fifteenth foreign convention on Relational and Algebraic equipment in machine technological know-how, RAMiCS 2015, held in Braga, Portugal, in September/October 2015. The 20 revised complete papers and three invited papers offered have been conscientiously chosen from 25 submissions. The papers take care of the idea of relation algebras and Kleene algebras, procedure algebras; mounted element calculi; idempotent semirings; quantales, allegories, and dynamic algebras; cylindric algebras, and approximately their software in components resembling verification, research and improvement of courses and algorithms, algebraic techniques to logics of courses, modal and dynamic logics, period and temporal logics.
Biometrics in a Data Driven World: Trends, Technologies, and Challenges
Biometrics in an information pushed global: developments, applied sciences, and demanding situations goals to notify readers concerning the smooth purposes of biometrics within the context of a data-driven society, to familiarize them with the wealthy background of biometrics, and to supply them with a glimpse into the way forward for biometrics.
Additional info for Theoretische Informatik: Eine kompakte Einführung
Example text
Weiter nahm man auch an, daß es für viele wichtige mathematische Theorien einen Entscheidungsalgorithmus gebe. Eine mathematische Theorie ist dabei, etwas vereinfacht ausgedrückt, die Menge aller wahren Aussagen, die sich über Objekte einer gegebenen Menge mit vorgegebenen formalen Mitteln formulieren lassen. Zum Beispiel bilden alle mit Hilfe der Addition und der Multiplikation formulierbaren wahren Aussagen wie VaVb:3c((a+ c = b) V (b + c = a)) eine arithmetische Theorie. Ein Entscheidungalgorithmus für eine Theorie ist ein Algorithmus, der für jede mit den formalen Mitteln der Theorie formulierbare Aussage nach endlich vielen Schritten feststellt, ob diese wahr oder falsch ist.
Um zu vermeiden, daß dabei ein hier nicht zulässiger negativer Wert entsteht, verwenden wir die modifizierte Subtraktion -'-. Im folgenden beschreiben wir die Menge der neben dem Stoppbefehl STOP bei einer RAM zulässigen Befehle (links) und ihre Wirkung (rechts). 1 Random-Access-Maschinen 23 Die Verwendung von Registern RRi, deren Adresse durch das Programm nicht fest vorgegeben, sondern durch den Inhalt eines Registers Ri bestimmt ist, nennen wir indirekte Adressierung. Bei den Sprungbefehlen unterscheiden wir zwischen dem unbedingten Sprung der Form GOTO m und den anderen beiden Typen des bedingten Sprungs.
2. Ist a [] eine Feldvariable, und sind b, eWertausdrücke, so ist a[e] := b eine Wertzuweisung. (IS) Zusammengesetzte Anweisungen 1. Hintereinandemusführung. Sind 81, 82, ... , so ist auch begin 81; 82; ... ; eine Anweisung. 2 Die Programmiersprache RIES 29 2. Bedingte Anweisungen. Ist b eine Bedingung und sind 81, 82 Anweisungen, so sind auch i f b then 81 e18e 82 und i f b then 81 Anweisungen. 3. for -Schleifen. Ist i eine Wertvariable, sind a1 und a2 Wertausdrücke und ist 8 eine Anweisung, in der i:= nicht auftritt, so ist for i := a1 to a2 do 8 eine Anweisung.