We study intermediate sums, interpolating between integrals and discrete sums, which were introduced by A. Barvinok [Computing the Ehrhart quasi-polynomial of a rational simplex, Math. Comp. 75 (2006), 1449--1466]. For a given polytope P with facets parallel to rational hyperplanes and a rational subspace L, we integrate a given polynomial function h over all lattice slices of the polytope P parallel to the subspace L and sum up the integrals. We first develop an algorithmic theory of parametric intermediate generating functions. Then we study the Ehrhart theory of these intermediate sums, that is, the dependence of the result as a function of a dilation of the polytope. We provide an algorithm to compute the resulting Ehrhart quasi-polynomials in the form of explicit step polynomials. These formulas are naturally valid for real (not just integer) dilations and thus provide a direct approach to real Ehrhart theory. The algorithms are polynomial time in fixed dimension. Following A. Barvinok (2006), the intermediate sums also provide an efficient algorithm to compute, for a fixed number k, the highest k Ehrhart coefficients in polynomial time if P is a simplex of varying dimension. We also present an application in optimization, a new fully polynomial-time approximation scheme for the problem of optimizing non-convex polynomial functions over the mixed-integer points of a polytope of fixed dimension, which improves upon earlier work that was based on discretization [J.A. De Loera, R. Hemmecke, M. Köppe, R. Weismantel, FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension, Math. Prog. Ser. A 118 (2008), 273--290]. The algorithm also extends to a class of problems in varying dimension. The talk is based on joint papers with Velleda Baldoni, Nicole Berline, Jesus De Loera, and Michele Vergne.