|
|
|
|
|
Mon, 15:30-17:00, S2 046
The lecture will be held 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.
The final exam is scheduled on Monday, June 27, 2022 from 15:30-17:00 in S2 046 S3 HS19. It is an open book exam. If no exam is handed in before the time expires, there is no grade. Every submitted exam will be graded. The second exam is scheduled on Thursday, September 15, 2022 from 15:15-16:45 in HS15.
The course follows the book "The Concrete Tetrahedron - Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates" by Manuel Kauers and Peter Paule. Its preface starts with
There are problems in mathematics which are so hard that they remain open for centuries. But many problems are not of this type. Often, being able to solve a problem just depends on knowing the right technique. This book is a book on techniques. More precisely, it is a book on techniques for solving problems about infinite sequences. Some of these techniques have belonged already to the repertoire of Euler and Gauss, others have been invented only a couple of years ago and are best suited for being executed in a computer algebra system.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. Many of the topics discussed in the lecture can also 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. More concretely, 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 these book include sums, recurrences, elementary number theory, binomial coefficients, generating functions, discrete probability, and asymptotic methods. The emphasis is on manipulative technique 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 and infinite integration)."
Requirements: Basic knowledge from analysis and linear algebra.
Note: Within the frame of this lecture various topics for a diploma thesis are offered.
The lecture notes of the previous year can be found here. The content of the course this year may differ from these lecture notes. Further material for download
Mon, 17:15-18:00, S2 046
The assignments for the exercises will be posted here.| Discussion | Exercise sheet |
| 14.03.2022 | exercises-01.pdf |
| 21.03.2022 | exercises-02.pdf |
| 28.03.2022 | exercises-03.pdf |
| 04.04.2022 | exercises-04.pdf |
| 25.04.2022 | exercises-05.pdf |
| 02.05.2022 | exercises-06.pdf |
| 09.05.2022 | exercises-07.pdf |
| 16.05.2022 | exercises-08.pdf |
| 23.05.2022 | exercises-09.pdf testcase.txt |
| 30.05.2022 | exercises-10.pdf |
| 20.06.2022 | exercises-11.pdf |