Ebook: Grundbegriffe der Theoretischen Informatik
Author: Prof.Dr. Franz Stetter (auth.)
- Tags: Computation by Abstract Devices, Algorithm Analysis and Problem Complexity, Logics and Meanings of Programs
- Series: Studienreihe Informatik
- Year: 1988
- Publisher: Springer-Verlag Berlin Heidelberg
- Edition: 1
- Language: German
- pdf
In diesem Lehrbuch werden die grundlegenden Begriffe der Theoretischen Informatik - Berechenbarkeit, Entscheidbarkeit, rekursive Funktionen, Regelsprachen, Turingmaschinen, Komplexität - auf der Basis 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 8 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 Problem, da für ein bestimmtes Problem 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 war 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 Analysis und Lineare Algebra voraus. Um den Leser mit der Terminologie in diesem Buch vertraut zu machen, sind im Anhang diese mathematischen Grundlagen in knapper Form zusammengestellt.
In diesem Lehrbuch werden die grundlegenden Begriffe der Theoretischen Informatik - Berechenbarkeit, Entscheidbarkeit, rekursive Funktionen, Regelsprachen, Turingmaschinen, Komplexit?t - auf der Basis 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 8 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 Problem, da f?r ein bestimmtes Problem 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 war 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 Analysis und Lineare Algebra voraus. Um den Leser mit der Terminologie in diesem Buch vertraut zu machen, sind im Anhang diese mathematischen Grundlagen in knapper Form zusammengestellt.
In diesem Lehrbuch werden die grundlegenden Begriffe der Theoretischen Informatik - Berechenbarkeit, Entscheidbarkeit, rekursive Funktionen, Regelsprachen, Turingmaschinen, Komplexit?t - auf der Basis 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 8 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 Problem, da f?r ein bestimmtes Problem 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 war 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 Analysis und Lineare Algebra voraus. Um den Leser mit der Terminologie in diesem Buch vertraut zu machen, sind im Anhang diese mathematischen Grundlagen in knapper Form zusammengestellt.
Content:
Front Matter....Pages I-VIII
Grundlagen....Pages 1-22
Programme....Pages 23-46
Funktionen....Pages 47-69
Regelsprachen....Pages 70-90
Regul?re Sprachen und Automaten....Pages 91-127
Kontextfreie Sprachen....Pages 128-155
Berechenbarkeit....Pages 156-183
Komplexit?tsklassen....Pages 184-217
Back Matter....Pages 218-236
In diesem Lehrbuch werden die grundlegenden Begriffe der Theoretischen Informatik - Berechenbarkeit, Entscheidbarkeit, rekursive Funktionen, Regelsprachen, Turingmaschinen, Komplexit?t - auf der Basis 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 8 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 Problem, da f?r ein bestimmtes Problem 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 war 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 Analysis und Lineare Algebra voraus. Um den Leser mit der Terminologie in diesem Buch vertraut zu machen, sind im Anhang diese mathematischen Grundlagen in knapper Form zusammengestellt.
Content:
Front Matter....Pages I-VIII
Grundlagen....Pages 1-22
Programme....Pages 23-46
Funktionen....Pages 47-69
Regelsprachen....Pages 70-90
Regul?re Sprachen und Automaten....Pages 91-127
Kontextfreie Sprachen....Pages 128-155
Berechenbarkeit....Pages 156-183
Komplexit?tsklassen....Pages 184-217
Back Matter....Pages 218-236
....