Help on query formulation
Mathematics for computer scientists. Explained thoroughly with many program examples and exercises. (Mathematik für Informatiker. Ausführlich erklärt mit vielen Programmbeispielen und Aufgaben.) (German)
Studium. Wiesbaden: Vieweg+Teubner (ISBN 978-3-8351-0157-9/pbk). 798~p. (2009).
This volume gives a thorough and mathematically precise foundation of those parts of mathematics which are really needed by computer scientists. It is divided into 24 chapters, which cover the material of roughly the first three semesters of mathematical instruction. The first part for the first semester is concerned with propositional logic, set theory and number systems from $\Bbb N$ to $\Bbb C$. It also lays the ground for algebraic structures from groups to fields, both finite and infinite. The integers and rational numbers are accurately constructed from the natural numbers. Quite from the beginning many algorithms, e.g. for converting numbers to different bases or for the euclidean algorithm are given as complete C++-programs. The correctness of programs is proven by program verification. Proofs are complete with exhausting detail, e.g. for the fundamental theorem of number theory, litte Fermat and many others. There are lots of applications, e.g. equivalence relations for databases, hashing, error checking numbers and RSA encryption. Some highlights are programs for solving quadratic equations within $\Bbb C$ or plotting the mandelbrot set, a simple iteration for $\sqrt2$ (not Heron’s) and a nice example for a set having itself as an element. The second part for the second semester covers the two topics boolean algebra and graph theory. Of course logical gates, minterm and maxterm representation and karnaugh diagrams for finding minimal representations of boolean expressions are treated in extension with many examples exhibiting nearly every possible special case. Graph theory is concerned with eulerian paths, spanning trees, Dijkstra’s algorithm for shortest paths, recursion, binary trees and matching ‒ for undirected as well as for directed graphs. Here again many complete programs are found, by the way aquainting the reader with the principles of object oriented programming: a complete set of classes for binary trees is designed. Applications are parsing of arithmetic terms, bipartite graphs, the marriage theorem and hungarian algorithm. The runtimes of algorithms, leading ultimately to the P/NP-Problem, are also discussed here. The third part treats probability theory and statistics, starting not with abstract definitions, but with motivating examples from daily life. It then gives very careful definitions of terms, e.g. of quantils, giving formal proofs of there properties. Of course probability theory is founded on $σ$-algebras. There are many examples from combinatorics. The realm of distributions is restricted to the most important, namely binomial, hypergeometrical, normal and $χ^2$, but for these the reader gets a very explicit description of confidence intervals, parameter- and distribution-tests, again with complete proofs. This part differs from the other two however since the connection to computer science is not as close as before. Throughout the book the exposition is always elementary and requires no prerequisites. It is especially well suited for self-study by the motivating and humorous style and its wealth of examples and exercises, the latter are well accessible. An appendix with the most needed parts of calculus helps remember forgotten college stuff.
Reviewer: Dieter Riebesehl (Lüneburg)
Classification: N50 K15 E15 M55 A15
Valid XHTML 1.0 Transitional Valid CSS!