|
Di, 12:00-13:30 Uhr, HS 11 The lecture will be in English. The learning goal is to develop basic skills and techniques which are relevant to problem solving when dealing with formulas related to enumeration, in particular, for the analysis of algorithms. Many
of the topics discussed in the lecture can be found in the book
"Concrete Mathematics - A Foundation for Computer Science" by
R.L.Graham, D.E.Knuth und O.Patashnik (Addison-Wesley, 1994). A
citation from its preface:
"...But what exactly is Concrete Mathematics? It is a blend of CONtinuous and disCRETE mathematics. Moreconcretely,
it is the controlled manipulation of mathematical formulae, using a
collection of techniques for solving problems. Once you ... have
learned the material in this book, all you will need is a cool head, a
large sheet of paper, and fairly decent handwriting in order to
evaluate horrendous-looking sums, to solve complex recurrence
relations, and to discover subtle patterns in data. You will be so
fluent in algebraic techniques that you will often find it easier to
obtain exact results than to settle for approximate answers that are
valid only in a limiting sense.The
major topics in this book include sums, recurrences, elementary number
theory, binomial coefficients, generating functions, discrete
probability, and asymptotic methods. The emphasis is on manipulativetechnique
rather than on existence theorems or combinatorial reasoning; the goal
is for each reader to become as familiar with discrete operations (like
the greatest-integer function and finite summation) as a student of
calculus is familiar with continuous operations (like the
absolute-value function andinfinite integration)."A
major emphasis of the lecture is on putting computer algebra into
action. Recently developed algorithms will be discussed, for instance,
the Steele-prized summation algorithm by Zeilberger. Requirements: Basic knowledge from analysis and linear algebra. Note: Within the frame of this lecture various topics for a diploma thesis are offered.
| |