Введение в информационные системы. Брюхомицкий Ю.А. - 100 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

100
который предложил трактовать конструктивные объекты как топологические
комплексы определенного вида.
Следует отметить, что модели второго и третьего типа довольно близки
и их взаимная сводимость легко доказывается. В целом же все предложенные
уточнения в некотором естественном смысле эквивалентны друг другу.
Сложность алгоритмов. Сложность алгоритма вычислений – функция,
дающая числовую оценку трудности (громоздкости)
процессов применения ал-
горитма к исходным данным. Уточнением понятия сложности алгоритма вы-
числений служит понятие сигнализирующей функции, которая задается разре-
шимым отношением между объектами применения алгоритма и натуральными
числами и имеет область определения, совпадающую с областью применимости
алгоритма. Чаще для измерения сложности служат временные и пространствен-
ные характеристики алгоритмических процессов. Так
, для машины Тьюринга
сигнализирующая функция времени работы Т
М
(Р) есть число так-
тов работы М преобразования исходных слов Р в заключительные; сигнали-
зирующая функция памяти (или емкости) S
M
(P) определяется как
количество ячеек ленты, в которых хотя бы раз побывала каретка при работе
над Р.
Для недетерминированных автоматов под сложностью вычислений по-
нимается сложность «самого простого» варианта процесса. Для вероятностных
автоматов конкретный ход процесса определяется, помимо программы и аргу-
мента, последовательностью показаний датчика случайных чисел, а результат
должен
с большой вероятностью совпадать со значением вычисляемой функ-
ции. Для таких автоматов иногда удается доказать уменьшение сложности вы-
числений по сравнению с детерминированными процессами.
Кроме сложности алгоритма вычислений оценивают также сложность
описания – величину, характеризующую длину описания алгоритма. Эта харак-
теристика зависит от точной концепции алгоритма. Единого уточнения к на-
стоящему моменту
не существует. Так, под сложностью нормального алгориф-
ма обычно понимают длину его изображения, т.е. длину записи всех его формул
подстановок в одну строку. Под сложностью описания машины Тьюринга
обычно понимают число ее внутренних состояний и внешних символов, иногда
– число команд машины. Для рекурсивных функций, задаваемых схемами ре-
курсий, в
качестве меры сложности обычно используют число букв в этих схе-
мах.
Машины Тьюринга. В качестве иллюстрации применения теории алго-
ритмов в приложениях кибернетики и вычислительной техники, рассмотрим
одно из уточнений алгоритма (алгоритмическую модель), известную под назва-
нием машины Тьюринга (Т).
Машина Т состоит из:
бесконечной ленты, разбитой на следующие друг
за другом в линейном
порядке ячейки, в каждой из которых может быть записан один из символов
конечного алфавита А={а
1
, ..., a
m
};

Страницы