8/ В чем заключается проблема остановки машины Тьюринга. Является ли она алгоритмически разрешимой?

В теории вычислимости проблема остановки — это проблема разрешимости, которая может неформально быть поставлена в виде:

Даны описание алгоритма и его начальные входные данные, требуется определить, сможет ли выполнение алгоритма с этими данными завершиться когда-либо. Альтернативой этому является то, что он работает всё время без остановки.

Алан Тьюринг доказал в 1936 году, что не существует общего алгоритма для решения проблемы остановки. Другими словами, проблема остановки неразрешима на машине Тьюринга.

Набросок доказательства

Рассмотрим множество алгоритмов, которые принимают на вход натуральное число и на выходе тоже выдают натуральное число. Выберем какой-нибудь полный по Тьюрингу язык программирования. Каждый алгоритм можно записать в виде конечной последовательности символов на этом языке. Упорядочим множество лексикографически (в словарном порядке), при этом каждый алгоритм получит свой порядковый номер. Назовем Анализатором гипотетический алгоритм, который получает на вход пару натуральных чисел , и:

останавливается и возвращает 1, если алгоритм с номером не останавливается, получив на вход

не останавливается в противном случае (если алгоритм с номером останавливается, получив на вход ).

Проблему остановки можно переформулировать следующим образом: существует ли Анализатор?

Теорема. Анализатор не существует.

9/ Как определяется временная сложность алгоритма?

Временная сложность - это один из критериев оценки алгоритма. Под ней понимается зависимость итераций алгоритма от размера входных данных, т.е. это функция от N, где N это количество входных данных.

Временная сложность алгоритма отражает требующиеся для его работы затраты времени. Эта функция, которая каждой входной длине ставит в соответствие максимальное ( по всем индивидуальным задачам длины п) время, затрачиваемое алгоритмом на решение индивидуальных задач этой длины.

Временная сложность алгоритма - это функция от длины записи набора входных данных задачи, определяемая по аналогии с временной сложностью машины Тьюринга. Отличия заключаются в следующем. Вместо шага работы машины должна фигурировать элементарная операция. Под заключительным состоянием алгоритма следует понимать ситуацию, в которой получен ответ да, если речь идет о задаче распознавания, либо выбран элемент х е X, доставляющий экстремум целевому функционалу, если рассматривается экстремальная задача.

Временная сложность алгоритма (в худшем случае) — это функция размера входных и выходных данных, равная максимальному количеству элементарных операций, проделываемых алгоритмом для решения экземпляра задачи указанного размера. В задачах, где размер выхода не превосходит или пропорционален размеру входа, можно рассматривать временную сложность как функцию размера только входных данных.

10/ Что означает выражение «Задача решается за реальное время»?

Реальное время — режим работы автоматизированной системы обработки информации и управления, при котором учитываются ограничения на временны́е характеристики функционирования.

Примеры временных характеристик и связанных с ними ограничений:

deadline — дедлайн — предельный срок завершения какой-либо работы;

latency — латентность — время отклика (задержка реакции) системы на внешние события;

jitter — джиттер — разброс значений времени отклика.

Также (преимущественно, в материалах рекламного и коммерческого характера) встречаются термины:

жёсткое реальное время — режим работы системы, при котором нарушение временных ограничений равнозначно отказу системы;

мягкое реальное время — режим работы системы, при котором нарушения временных ограничений приводят к снижению качества работы системы.

Система реального времени (СРВ) — это любая система, работающая в режиме реального времени.

Назначение систем, работающих в режиме реального времени, — взаимодействие с объектами внешнего (по отношению к системе) мира в темпе процессов, протекающих в этих объектах. Как правило, система реального времени должна:

либо по собственной инициативе воздействовать на внешние процессы в заданные моменты времени;

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

За своевременность воздействий на объект отвечает характеристика deadline. Задержка реакции на внешнее событие характеризуется значениями latency и jitter.