Вычисления в реальном времени

Вычисления в реальном времени — класс задач, решаемых в рамках теории алгоритмов и впервые рассмотренных Hisao Yamada — версия статьи «Ямада, Хисао» на английском языке Хисао Ямадой (англ.) (рус. в 1962 году. Обычно задачи формулируются в терминах абстрактных вычислителей, таких как машина Тьюринга или машина Поста, и связаны с исследованиями свойств монотонно возрастающих функций $\text{[math]}$ $\text{[math]}$ $U(n)$ $U(n)$ , для которых существует генератор последовательностей выходных символов, печатающих на $\text{[math]}$ $\text{[math]}$ $j$ $j$ -м такте работы на ленте $\text{[math]}$ $\text{[math]}$ $1$ $1$ , если $\text{[math]}$ $\text{[math]}$ $U(i)=j$ $U(i)=j$ для некоторого $\text{[math]}$ $\text{[math]}$ $i$ $i$ , и $\text{[math]}$ $\text{[math]}$ $0$ $0$ в противном случае. Такие функции называются «вычислимыми в реальное время»^[1].

Решения подобных задач могут использоваться в качестве теоретического базиса для доказательства корректности и эффективности алгоритмов, используемых в системах реального времени.

ПримечанияПравить

↑ Марченков, С. С., Матросов, В. Л. Сложность алгоритмов и вычислений // Итоги науки и техники. Серия «Теория вероятностей. Математическая статистика. Теоретическая кибернетика». — М.: ВИНИТИ, 1979. — Т. 16. — С. 103—149.

[1] Марченков, С. С., Матросов, В. Л. Сложность алгоритмов и вычислений // Итоги науки и техники. Серия «Теория вероятностей. Математическая статистика. Теоретическая кибернетика». — М.: ВИНИТИ, 1979. — Т. 16. — С. 103—149.

[1]