In der LVA Formale Grundlagen 2 behandeln wir den formalen
Berechenbarkeitsbegriff anhand von rekursiven Funktionen und
Turingmaschinen. Aufbauend darauf befassen wir uns mit der
Entscheidbarkeit bzw. Unentscheidbarkeit von Problemen, mit
Komplexitätsklassen und vollständigen Problemen.

Es wird vorausgesetzt, daß die Teilnehmer die mathematischen
Voraussetzungen, wie sie in den LVAen Mathematik für
Informatiker I und II geboten werden, mitbringen.
Weiters werden Grundkenntnisse über Programmierung und
Programmiersprachen vorausgesetzt.

erste Vorlesung: 7. Oktober
erste Übung: 14. Oktober

Am Ende des Semesters (27.1.2006) findet eine Klausur statt.

The purpose of the meetings is to discuss progress made in diploma or PhD theses advised by the lecturer.

The overall goal of this seminar is to study aspects of recent algorithmic developments, and to discuss progress
made in various research projects. Major topics of interest are: symbolic summation and integration, special
functions, and related themes like difference equations, generating functions, etc. The main focus is on the design
of new computer algebra algorithms.
Despite its research character, the structure of the seminar is such that ambitious students, being new to the area,
have a chance to contribute in an active manner. Usually this happens in the form of approx. 120 minutes talks.
Requirements: Active knowledge from "Analytische Kombinatorik" and "Computer Algebra I".

The lecture is directed to an audience with strong interest in methods for symbolic summation. 
Requirements: Active knowledge from "Analytische Kombinatorik" and "Computer Algebra I".

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, and 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 this 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)."
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.