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

Show description

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

Best machine theory books

Mathematics for Computer Graphics

John Vince explains quite a lot of mathematical innovations and problem-solving techniques linked to computing device video games, laptop animation, digital fact, CAD and different parts of special effects during this up-to-date and multiplied fourth version. the 1st 4 chapters revise quantity units, algebra, trigonometry and coordinate structures, that are hired within the following chapters on vectors, transforms, interpolation, 3D curves and patches, analytic geometry and barycentric coordinates.

Topology and Category Theory in Computer Science

This quantity displays the starting to be use of concepts from topology and class thought within the box of theoretical desktop technology. In so doing it deals a resource of recent issues of a pragmatic taste whereas stimulating unique rules and suggestions. Reflecting the most recent options on the interface among arithmetic and machine technology, the paintings will curiosity researchers and complex scholars in either fields.

Cognitive robotics

The kimono-clad android robotic that lately made its debut because the new greeter on the front of Tokyos Mitsukoshi division shop is only one instance of the fast developments being made within the box of robotics. Cognitive robotics is an method of growing man made intelligence in robots by way of allowing them to benefit from and reply to real-world occasions, rather than pre-programming the robotic with particular responses to each achievable stimulus.

Mathematical Software – ICMS 2016: 5th International Conference, Berlin, Germany, July 11-14, 2016, Proceedings

This booklet constitutes the court cases of the fifth foreign convention on Mathematical software program, ICMS 2015, held in Berlin, Germany, in July 2016. The sixty eight papers incorporated during this quantity have been conscientiously reviewed and chosen from various submissions. The papers are prepared in topical sections named: univalent foundations and facts assistants; software program for mathematical reasoning and purposes; algebraic and toric geometry; algebraic geometry in functions; software program of polynomial platforms; software program for numerically fixing polynomial structures; high-precision mathematics, potent research, and unique services; mathematical optimization; interactive operation to clinical art and mathematical reasoning; details providers for arithmetic: software program, companies, versions, and knowledge; semDML: in the direction of a semantic layer of a global electronic mathematical library; miscellanea.

Extra resources for Theoretische Informatik: Eine kompakte Einführung

Example text

C n )) als beg in if (sr< w(d := fCco, ... ,c n ))) then begin rs [i] := w( d := f (co, ... ,c n )); l[i] := p; t [p] := i; bo[p]:=(co); ... ;bn[p] (c n rs [p] := 0; sr:= (r + 1) end; if (sr = w(d := fCco, ... ,c n ))) then begin d [i] := f [1 [i]]; sr := 0 end ); end Im ersten if-Fall ist die I(i)-te Berechnung an einem Funktionsaufruf angelangt. Es wird die neue Berechnung mit der Nummer I(p) vorbereitet, die diesen Funktionsaufruf realisieren soll, und mit sr := (r + 1) wird dafür gesorgt, daß der Rest der I(i)-ten Berechnung zunächst einmal übersprungen wird.

Besitzt eine Anweisung S gleichzeitig die Form i f b then SI else S2 und die Form i f b then S3 (das ist bei S = i f b then if b' then SI else S2 der Fall), so wird S gemäß der zweiten Form interpretiert. Mit anderen Worten: Im Zweifelsfalle wird ein else dem letzten i f zugeordnet. 3. Ist i eine Wertvariable, sind al, a2 Wertausdrücke und ist S eine Anwei- sung, in der i:= nicht auftritt, so wird festgelegt, daß die Anweisung for i := al to a2 do S die Wirkung der Anweisung begin i := al; j := a2; while (i ::; j) do begin s; i j := 0 end (i + 1) end; besitzt, wobei j eine neue, sonst im Programm nicht verwendete Wertvariable ist.

Damit ist die Se- mantik von RIES festgelegt. 2 RIES-Berechenbarkeit Nachdem wir definiert haben, welche Funktion von einem RIES-Programm berechnet wird, ist folgende Definition der RIES-Berechenbarkeit naheliegend. p berechnet. 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.

Download PDF sample

Rated 4.16 of 5 – based on 38 votes