By Franz Stetter
In diesem Lehrbuch werden die grundlegenden Begriffe der Theoretischen Informatik - Berechenbarkeit, Entscheidbarkeit, rekursive Funktionen, Regelsprachen, Turingmaschinen, Komplexität - auf der foundation der Programmiersprache PASCAL motiviert, abgeleitet und in einer einheitlichen Betrachtungsweise dargestellt. Ferner wird die Äquivalenz verschiedener Ansätze zu einer Theorie der Berechenbarkeit - Programme, rekursive Funktionen, Regelsprachen und Turingmaschinen - als weiteres zentrales Konzept herausgestellt. Während in den Kapiteln 1-7 qualitative Aspekte der Berechenbarkeit behandelt werden, ist Kapitel eight den quantitativen Aspekten gewidmet. Die Komplexität, d.h. Zeit- bzw. Speicheraufwand für eine Berechnung, ist sowohl abhängig von dem zugrundeliegenden Berechnungsmodell als auch von dem zu lösenden challenge, da für ein bestimmtes challenge gewisse Schranken nicht unterschritten werden können. Bei einem so weitgespannten Gebiet wie der Theoretischen Informatik müssen zwangsläufig manche Einschränkungen bei der Stoffauswahl gemacht werden. So wird z.B. Semantik nur informell behandelt, Parallelität nur ansatzweise betrachtet oder Automatentheorie nur am Rand gestreift. Ziel der Stoffauswahl struggle es, ein möglichst umfassendes Bild der Theoretischen Informatik zu bieten und ein Fundament für weitergehende Studien zu legen. Das Buch setzt Grundkenntnisse aus den Anfängervorlesungen über research und Lineare Algebra voraus. Um den Leser mit der Terminologie in diesem Buch vertraut zu machen, sind im Anhang diese mathematischen Grundlagen in knapper shape zusammengestellt.
Read or Download Grundbegriffe der Theoretischen Informatik PDF
Similar german_5 books
Relationale Datenbanken: Eine Einführung für die Praxis
Die Fachbrosch}re gibt eine umfassende Einf}hrung in das Gebiet der relationalen Datenbanken. Bei der Datenmodellierung werden Abbildungsregeln zum ]berf}hren eines Entit{ten-Beziehungsmodells in ein relationales Datenbankschema behandelt, Normalformen diskutiert und ein unternehmensweites Datenmodell veranschaulicht.
- Handbuch der Verkehrslogistik
- Datenübertragung Technik der Daten- und Textkommunikation: Band I · Grundlagen
- Einführung in die Umwelttechnik: Grundlagen und Anwendungen aus Technik und Recht
- Einführung in die Mechanik, Akustik und Wärmelehre
Extra resources for Grundbegriffe der Theoretischen Informatik
Example text
M r ) mit f( nl, ... , n q ) = (ml, ... , m r ) liefert. f heißt berechenbar, f unter P berechenbar ist. Die Berechenbarf sichert also die Existenz eines Programms P, mit dessen Hilfe f berechnet wenn es ein Programm P gibt, so daß keit von werden kann. Das Programm program N100 (input,output); var N : in teger; begin read( N); if N> 100 then write( N) end. liefert für N für N > ~ 100 keine Ausgabe, also f(N) 100. 1 für N ~ 100 und f(N) =N für alle N E 7Z wird durch folgendes Programm "erzeugt": program leer (input,output); var N : in teger; begin read( N); while true do end.
No zu finden, der bei jedem Durchlauf der Schleife bzw. bei jedem rekursiven Aufruf der Prozedur echt kleiner wird und der insgesamt nach unten beschränkt ist. Terminiert ein Programm nur für bestimmte Eingab ewerte , so ist die zugeordnete Funktion partiell. 1 Berechenbarkeit Eine partielle Funktion f heißt berechenbar unter einem Programm P , wenn P für alle definierten Eingabetupel (nl' n2, ... , n q ) terminiert und das entsprechende Ausgabetupel (ml' m2, ... , m r ) mit f( nl, ... , n q ) = (ml, ...
Ein solches Ergebnis ist auch zu erwarten, wenn man bedenkt, daß die Zahl der Programme abzählbar ist, jedoch die Zahl der Funktionen nicht abzählbar ist. 47 3. Funktionen 3. Funktionen Jedes Programm berechnet eine bestimmte Funktion. No erklärt ist, und daß f im Wertebereich einstellig ist. No. Die Funktion f hat das r -tupel (nI, n2, ... , n r ) als Argument. Zur Abkürzung werde N für das r-tupelgesetzt,also f(N) statt f(nl,n2, ... ,n r ). Im Sinne von PASCAL ist N ein Feld mit r Komponenten.