Comprehensive Mathematics for Computer Scientists 2nd ed [Vol 1] - G. Mazzola, et al., (Springer, 2006) WW.pdf

(3777 KB) Pobierz
642530448 UNPDF
Guerino Mazzola • Gérard Milmeister •
Jody Weissmann
Comprehensive Mathematics
for Computer Scientists 1
Sets and Numbers, Graphs and Algebra,
Logic and Machines, Linear Geometry
(Second Edition)
With 118 Figures
642530448.001.png
Guerino Mazzola
Gérard Milmeister
Jody Weissmann
Department of Informatics
University Zurich
Winterthurerstr. 190
8057 Zurich, Switzerland
. The graphics were drawn using Dia, an
open-source diagramming software. The main text has been set in the Y&Y Lucida
Bright type family, the headings in Bitstream Zapf Humanist 601.
L A T E X2 ε
Library of Congress Control Number: 2006929906
Mathematics Subject Classification (2000): 00A06
ISBN (First Edition) 3-540-20835-6
ISBN 3-540-36873-6 Springer-Verlag Berlin Heidelberg New York
This work is subject to copyright. All rights are reserved, whether the whole or part of the
material is concerned, specifically the rights of translation, reprinting, reuse of illustrations,
recitation, broadcasting, reproduction on microfilm or in any other way, and storage in data
banks. Duplication of this publication or parts thereof is permitted only under the
provisions of the German Copyright Law of September 9, 1965, in its current version, and
permission for use must always be obtained from Springer-Verlag. Violations are liable for
prosecution under the German Copyright Law.
Springer-Verlag is a part of Springer Science+Business Media
springer.com
© Springer-Verlag Berlin Heidelberg 2006
The use of general descriptive names, trademarks, etc. in this publication does not imply,
even in the absence of a specific statement, that such names are exempt from the relevant
protective laws and regulations and therefore free for general use.
Cover Design: Erich Kirchner, Heidelberg
Typesetting: Camera ready by the authors
The text has been created using
Printed on acid-free paper SPIN: 11803911 40/3142/SPi - 543210
Preface to the Second Edition
A second edition of a book is a success and an obligation at the same
time. We are satised that a number of university courses have been orga­
nized on the basis of the rst volume of Comprehensive Mathematics for
Computer Scientists . The instructors recognized that the self­contained
presentation of a broad specturm of mathematical core topics is a rm
point of departure for a sustainable formal education in computer sci­
ence.
We feel obliged to meet the valuable feedback of the responsible in­
structors of such courses, in particular of Joel Young (Computer Science
Department, Brown University) who has provided us with numerous re­
marks on misprints, errors, or obscurities. We would like to express our
gratitude for these collaborative contributions. We have reread the entire
text and not only eliminated identied errors, but also given some addi­
tional examples and explications to statements and proofs which were
exposed in a too shorthand style.
A second edition of the second volume will be published as soon as the
errata, the suggestions for improvements, and the publisher's strategy
are in harmony.
Zurich,
Guerino Mazzola
June 2006
Gérard Milmeister
Jody Weissmann
Preface
The need for better formal competence as it is generated by a sound
mathematical education has been conrmed by recent investigations by
professional associations, but also by IT opinion leaders such as Niklaus
Wirth or Peter Wegner. It is rightly argued that programming skills are a
necessary but by far not sucient qualication for designing and control­
ling the conceptual architecture of valid software. Often, the deciency in
formal competence is compensated by trial and error programming. This
strategy may lead to uncontrolled code which neither formally nor ef­
fectively meets the given objectives. According to the global view such
bad engineering practice leads to massive quality breakdowns with cor­
responding economical consequences.
Improved formal competence is also urged by the object­oriented para­
digm which progressively requires a programming style and a design
strategy of high abstraction level in conceptual engineering. In this con­
text, the arsenal of formal tools must apply to completely dierent prob­
lem situations. Moreover, the dynamics and life cycle of hard­ and soft­
ware projects enforce high exibility of theorists and executives on all
levels of the computer science academia and IT industry. This exibil­
ity can only be guaranteed by a propaedeutical training in a number of
typical styles of mathematical argumentation.
With this in mind, writing an introductory book on mathematics for com­
puter scientists is a somewhat delicate task. On the one hand, computer
science delves into the most basic machinery of human thought, such
as it is traced in the theory of Turing machines, rewriting systems and
grammars, languages, and formal logic. On the other hand, numerous ap­
plications of core mathematics, such as the theory of Galois elds (e.g.,
for coding theory), linear geometry (e.g., for computer graphics), or dif­
ferential equations (e.g., for simulation of dynamic systems) arise in any
VIII
Preface
relevant topic of computational science. In view of this wide eld of math­
ematical subjects the common practice is to focus one's attention on
a particular bundle of issues and to presuppose acquaintance with the
background theory, or else to give a short summary thereof without any
further details.
In this book, we have chosen a dierent presentation. The idea was to set
forth and prove the entire core theory, from axiomatic set theory to num­
bers, graphs, algebraic and logical structures, linear geometryin the
present rst volume, and then, in the second volume, topology and cal­
culus, dierential equations, and more specialized and current subjects
such as neural networks, fractals, numerics, Fourier theory, wavelets,
probability and statistics, manifolds, and categories.
There is a price to pay for this comprehensive journey through the over­
whelmingly extended landscape of mathematics: We decided to omit
any not absolutely necessary ramication in mathematical theorization.
Rather it was essential to keep the global development in mind and to
avoid an unnecessarily broad approach. We have therefore limited ex­
plicit proofs to a length which is reasonable for the non­mathematician.
In the case of lengthy and more involved proofs, we refer to further read­
ings. For a more profound reading we included a list of references to
original publications. After all, the student should realize as early as pos­
sible in his or her career that science is vitally built upon a network of
links to further knowledge resources.
We have, however, chosen a a modern presentation: We introduce the
language of commutative diagrams, universal properties and intuitionis­
tic logic as advanced by contemporary theoretical computer science in
its topos­theoretic aspect. This presentation serves the economy and el­
egance of abstraction so urgently requested by opinion leaders in com­
puter science. It also shows some original restatements of well­known
facts, for example in the theory of graphs or automata. In addition, our
presentation oers a glimpse of the unity of science: Machines, formal
concept architectures, and mathematical structures are intimately related
with each other.
Beyond a traditional standalone textbook, this text is part of a larger
formal training project hosted by the Department of Informatics at the
University of Zurich. The online counterpart of the text can be found
on http://math.ifi.unizh.ch . It oers access to this material and in­
cludes interactive tools for examples and exercises implemented by Java
 

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin