  This paper studies function approximation in Gaussian Sobolev spaces over the
real line and measures the error in a Gaussian-weighted $L^p$-norm. We
construct two linear approximation algorithms using $n$ function evaluations
that achieve the optimal or almost optimal rate of worst-case convergence in a
Gaussian Sobolev space of order $\alpha$. The first algorithm is based on
scaled trigonometric interpolation and achieves the optimal rate $n^{-\alpha}$
up to a logarithmic factor. This algorithm can be constructed in almost-linear
time with the fast Fourier transform. The second algorithm is more complicated,
being based on spline smoothing, but attains the optimal rate $n^{-\alpha}$.
