Download Theoretische Informatik: Eine kompakte Einführung by Klaus W. Wagner PDF

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, was once 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.

Show description

Read or Download Theoretische Informatik: Eine kompakte Einführung PDF

Similar machine theory books

Numerical computing with IEEE floating point arithmetic: including one theorem, one rule of thumb, and one hundred and one exercises

Are you acquainted with the IEEE floating aspect mathematics ordinary? do you want to appreciate it higher? This publication offers a vast evaluation of numerical computing, in a ancient context, with a distinct specialize in the IEEE general for binary floating element mathematics. Key principles are built step-by-step, taking the reader from floating aspect illustration, competently rounded mathematics, and the IEEE philosophy on exceptions, to an figuring out of the the most important innovations of conditioning and balance, defined in an easy but rigorous context.

Robustness in Statistical Pattern Recognition

This ebook is worried with very important difficulties of strong (stable) statistical pat­ tern popularity whilst hypothetical version assumptions approximately experimental facts are violated (disturbed). development reputation concept is the sector of utilized arithmetic within which prin­ ciples and strategies are built for class and identity of items, phenomena, procedures, events, and signs, i.

Bridging Constraint Satisfaction and Boolean Satisfiability

This e-book offers an important step in the direction of bridging the parts of Boolean satisfiability and constraint pride by means of answering the query why SAT-solvers are effective on sure sessions of CSP cases that are difficult to resolve for normal constraint solvers. the writer additionally offers theoretical purposes for selecting a specific SAT encoding for numerous very important sessions of CSP circumstances.

A primer on pseudorandom generators

A clean examine the query of randomness was once taken within the concept of computing: A distribution is pseudorandom if it can't be special from the uniform distribution via any effective technique. This paradigm, initially associating effective strategies with polynomial-time algorithms, has been utilized with admire to a number of usual periods of distinguishing strategies.

Extra info for Theoretische Informatik: Eine kompakte Einführung

Example text

Mit RIES bezeichnen wir die Menge aller RIES-berechenbaren Funktionen. 7 Ein RIES-Programm, das nicht bei jeder Eingabe hält. 8 Ein RIES-Programm mit mehreren Funktionsdeklarationen. In diesem Programm werden die Funktionen prim, teil und mod deklariert, die für n, m, i 2': 0 wie folgt definiert sind: prim(n) teil( m) mod(m,i) n-te Primzahl (wobei 2 als die O-te Primzahl gilt) { Anzahl der Teiler von m, falls m 2': 0 o sonst { Rest beim Dividieren von m durch i, falls i m sonst >0 Das Programm berechnet die zuerst deklarierte Funktion, nämlich prim.

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. Es sei erwähnt, daß die zulässigen RAM-Befehle etwa den Befehlen entsprechen, die in Assemblersprachen realer Rechner verwendet werden.

Sind a, b Wertvariable und ist c [] eine Feldvariable, so sind c [a] := b und b := c [a] Anweisungen. 38 2 Berechenbarkeit 3. Sind gen. a, b, c Wertvariable, so sind a := (b + c) und a := (b - c) Anweisun- (IS) Zusammengesetzte Anweisungen 1. Sind SI, S2, ... ,Sn begin Anweisungen, so ist auch SI; S2; ... ; Sn end eine Anweisung. 2. Ist S eine Anweisung und ist a eine Wertvariable, so ist auch while (a -::f- 0) do S eine Anweisung. Die Funktionsdeklarationen sind wie bei RIES definiert, und ein MINI-RIESProgramm besteht aus genau einer Funktionsdeklaration.

Download PDF sample

Rated 4.15 of 5 – based on 22 votes