Vorlesungen über Informatik: Berechenbarkeit, Formale Sprachen, Spezifikationen (springer-lehrbuch) (german Edition)

Dieses Lehrbuch baut auf den Themen "Grundlagen und funktionales Programmieren" und "Objektorientiertes Programmieren und Algorithmen" der ersten beiden Bände auf und vermittelt wesentliche Fundamente aus der theoretischen Informatik wie Grundlagen der Berechenbarkeits- und Komplexitätstheorie, formale Sprachen und Automaten. Danach werden Transformation von Programmen und die Spezifikationstechnik einführend behandelt. Der Verfasser stellt den Zusammenhang zwischen der Algorithmenentwicklung und der Theorie her. Er zeigt, wie man durch Transformation Programme gleichen Inhalts unterschiedlich formulieren kann. Anhand der Z-Notation und der Technik der Statecharts wird erörtert, wie man Systemaufgaben analysiert und spezifiziert. This book provides a comprehensive introduction to the modern study of computer algorithms. It presents many algorithms and covers them in considerable depth, yet makes their design and analysis accessible to all levels of readers. We have tried to keep explanations elementary without sacrificing depth of coverage or mathematical rigor. Each chapter presents an algorithm, a design technique, an application area, or a related topic. Algorithms are described in English and in a "pseudocode" designed to be readable by anyone who has done a little programming. The book contains over 260 figrues illustrating how the algorithms work. Since we emphasize efficiency as a design criterion, we include careful analyses of the running times of all our algorithms. The text is intended primarily for use in undergraduate or graduate courses in algorithms or data structures. Because it discusses engineering issues in algorithm design, as well as mathematical aspects, it is equally well suited for self-study by technical professionals. -- Preface Growth of functions Summations Recurrences Sets, etc. Counting and probability Heapsort Quicksort Sorting in linear time Medians and order statistics Elementary data structures Hash tables Binary search trees Red-black trees Augmenting data structures Dynamic programming Greedy algorithms Amortized analysis B-trees Binomial heaps Fibonacci heaps Data structures for disjoint sets Elementary graph algorithms Minimum spanning trees Single-source shortest paths All-pairs shortest paths Maximum flow Sorting networks Arithmetic circuits Algorithms for parallel computers Matrix operations Polynomials and the FFT Number-theoretic algorithms String matching Computational geometry NP-completeness Approximation algorithms. Front Matter....Pages i-xii Berechenbarkeit....Pages 1-50 Komplexitätstheorie....Pages 51-76 Formale Sprachen....Pages 77-144 Programmtransformationen....Pages 145-172 Spezifikationstechniken: Die Z Notation....Pages 173-216 Ablaufspezifikationen, Synchronisierung und Kommunikation....Pages 217-272 Back Matter....Pages 273-284 Dieses Lehrbuch baut auf den Themen "Grundlagen und funktionales Programmieren" und "Objektorientiertes Programmieren und Algorithmen" der ersten beiden Bande auf und vermittelt wesentliche Fundamente aus der theoretischen Informatik wie Grundlagen der Berechenbarkeits- und Komplexitatstheorie, formale Sprachen und Automaten.