Structural complexity of algorithms

At the beginning, the lecture compares Von Neumann’s computer model with today’s architecture. The story continues with mathematical discoveries that have influenced the theory of algorithms…


Introduction themes

  • real computers: Von Neumann’s and today’s architecture
  • some mathematical discoveries that preceded (and influenced) the theory of algorithms / (formal) languages / grammar / automats

Structural complexity of algorithms / problems / language / grammar / automate

Time and memory complexity of algorithms / problems / acceptance languages