9th Estonian Winter School in Computer Science (EWSCS)
IX Eesti Arvutiteaduse Talvekool (EATTK)
Palmse, Estonia
February 29 - March 5, 2004
Rusins Freivalds
Institute of Mathematics and Computer Science
University of Latvia
Riga, Latvia
UNREASONABLE EFFECTIVENESS OF CLASSICAL MATHEMATICS IN COMPUTER SCIENCE
Abstract
There is no wonder when elementary mathematics is used in Computer Science. However many examples show that some results of the mathematics of 19th and 20th century originally belonging to the "pure mathematics" later become crucially important for extremely practical problems of Computer Science. The most well-known example is the usage of Number Theory in Cryptography. However there are many more such examples. We consider:
- Riemann hypothesis and its impact to Theoretical Computer Science;
- Hilbert's theorem on basis, and decidability of equivalence problem for deterministic Lindenmayer systems;
- Fourier transform and its usage to prove lower bounds of complexity;
- p-adic numbers and factorisation of polynomials.
Course materials
Riemann hypothesis
Invariants, Hilbert and Lindenmayer
Hilbert's Nullstellensatz
Fourier transform
p-adic numbers