3.Практический аспект применения Теории алгоритмов

Практический аспект: методы и методики теории алгоритмов (в основ-ном разделов асимптотического и практического анализа) позволяют осуществить:

• рациональный выбор из известного множества алгоритмов решения данной задачи с учетом особенностей их применения (например, при ограничениях на размерность исходных данных или объема дополнительной памяти);

• получение временных оценок решения сложных задач;

• получение достоверных оценок невозможности решения некоторой задачи за определенное время, что важно для криптографических методов;

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

4.Требования, которым должен удовлетворять алгоритм

•− алгоритм должен содержать конечное количество элементарно выполнимых предписаний, т.е. удовлетворять требованию конечности записи;

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

•− алгоритм должен быть единым для всех допустимых исходных данных, т.е. удовлетворять требованию универсальности;

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

5.Формализация алгоритмов

Известно несколько подходов к формализации понятия «алгоритм»:

• теория конечных и бесконечных автоматов;

• теория вычислимых (рекурсивных) функций;

• λ-исчисление Черча.

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

6.Понятие соответствия, области соответствия, образ и прообраз элемента и подмножества

Пусть заданы множества A и B. Соответствием между этими множествами называется подмножество вида G(знак включения) AxB. Множ A называется областью отправления а B – прибытия. Первая проекция множ G на A называется областью определения соответствия, а B – значения.

Множество всех элементов b, соответствующих элементу a, называется образом элемента a в B при соответствии G.

Множество всех элементов a, соответствующих элементу b, называется прообразом элемента b в A при соответствии G.

7.Свойства соответствий

Было уже, смотри выше

8.Понятие машины Тьюринга, состав, принцип работы

МТ – формальная модель алгоритмической системы, связывающая работу алгоритма с работой некоторого абстрактного устройства.

Состоит:

•Ленты

•Головки считывания/записи

•Устройства управления (УУ)

Лента разбита на ячейки с 1 символом. Множество символов, которые могут быть записаны на ленту, - алфавит. В него включается пустой символ. Цепочка символов на ленте – слово.

Головка в определённый момент времени обозревает 1 ячейку ленты, может либо считать ее, либо записать в нее. После этого головка может сдвинуться вправо/влево на 1 позицию или остаться на месте. Действиями головки руководит УУ. В множестве состояний выделяется 1 начальное состояние, с которого МТ начинает работать. Может быть несколько состояний, которые объявлены заключительными. При достижении их работа завершается.