Here is a time sample: $Q = \{(t_i, x_i) | 0 \leq x_i \leq x_{i+1}, 1 \leq i \leq n\}$
and rules:
(1) $T_1 \leq t_{i+1} - t_i < T_2$ where $T_1, T_2 > 0$
(2) $x_i$ comes with error:
$x_i = \lfloor x(t_i) \rfloor$ where $\lfloor x \rfloor$ - whole part of $x$, $x(t_i)$ - voluntary unknown law of object motion.
How we can find (approximately but sufficiently accurate) speed of the object at the given time?
On
Since you mention that your $x_i$ is error-contaminated; the sanest solution (in the absence of other pertinent information that could be used to simplify your problem, e.g. a conjectured functional form for $x(t)$) would be probably a smoothing spline; this is a similar but probably more amenable proposal to Laurent's, with the advantage that any bad nonpolynomial behavior your data might exhibit can be confined to only a few intervals.
I don't know what computing environment you're using, but MATLAB at least has smoothing splines in its Spline Toolbox (check the documentation for syntax and proper use); and there are FORTRAN programs developed by Carl de Boor (in fact, the MATLAB toolbox was based on these old FORTRAN programs) @ NetLib ; pppack is the particular library you want.
If I understand the question correctly, we are given real numbers $0 \leq x_1 \leq \dots \leq x_n$, and real numbers $0 < t_1 < \dots < t_n$. We also have some unknown differentiable function $x(t)$ that satisfies: $$ x_i \leq x(t_i) < x_i+1 \quad for\quad i=1,2,\dots ,n $$ Our goal is to estimate $\frac{d}{dt}x(t)$.
Suppose we are interested in the derivative at some point $t_0$. It is clear that the constraints above do not constrain the possible values of the derivative at $t_0$. Indeed, given any set of $x_i$ and $t_i$, one could find an admissible function $x(t)$ for which the derivative at $t_0$ is anything we want it to be. So unless we know something more about the "law of motion" governing x, there isn't a reasonable way to estimate the velocity.
In the absence of more information, I'll just assume that x is a polynomial. This will enforce some sort of smoothness. Finding the lowest-degree polynomial that satisfies all the constraints can be cast as a linear program. To see how, suppose that our polynomial is of degree k. Namely, $x(t) = a_0 + a_1 t + \dots + a_{k}t^k$. Then, consider the LP: \begin{align*} minimize &\quad z \\ \text{subject to:}&\quad 0 \leq x(t_i) \leq z\quad i=1,\dots,n \end{align*} Start with $n=0$, and keep increasing until you find an optimal $z$ that is less than 1. Now that you have your polynomial approximation for $x$, you can easily evaluate its derivative anywhere.