Что вы всегда хотели узнать, но боялись спросить

[NT]

Source of the post Вообще, по математической модели алгоритма все языки программирования можно разделить на три группы...

По математической модели - может так и деляться.
Вот C/ANSI куда отнести: алгоритмические, функциональные (вычислимая функция), логические (исчисление предикатов)?

A еще обычно языки программирования делять:
-- по способу компиляции,
-- уровню, как бы сказать, приближенным к нормальному языку или к языку машины,
-- структуруальные, обьекто-ориентированные ...

[Swetlana]

Детерминированная машина Тьюринга (ДМТ)

Рассмотрим "школьное" определение алгоритма.
1. Алгоритм – любой алгоритм задается последовательностью инструкций.
2. Алгоритм выполняется детерминировано, то есть для одинаковых данных выполняются одинаковые действия.
3. Должен существовать вычислитель, способный выполнить указания в алгоритм инструкции.
4. Вычислитель должен иметь средства для хранения и отображения информации

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

Опр. 5. ДМТ имеет бесконечную ленту, управляющее устройство и считывающее/пишущую головку. Лента разделена на ячейки, в каждой ячейке записан или пустой символ , или символ некоторого конечного алфавита. В каждый момент на ленте может быть только конечное число непустых символов.
Управляющее устройство находится в одном из конечного множества состояний, среди которых выделяются начальное и заключительное . Перед началом работы ДМТ находится в начальном состоянии , попав в заключительное , останавливается.

На одном такте работы ДМТ производит следующие действия:
1. Считывает символ из текущей ячейки.
2. Записывает вместо него новый.
3. Остаётся на месте или сдвигается в соседнюю ячейку.
4. В зависимости от текущего состояния и прочитанного символа переходит в новое состояние.
$$Îáîçíà÷èì \ A =\{a_1, \ldots, a_n\} \ - \ ìíîæåñòâî \ ñèìâîëîâ; \\
Q =\{q_1, \ldots, q_n\}\ - \ ìíîæåñòâî \ ñîñòîÿíèé;\ d_k \ – \ êîìàíäà \ ñäâèãà \ \{L, R, E\}$$.

Тогда один такт работы ДМТ записывается одной командой

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

Тезис Тьюринга
Всякий алгоритм может быть реализован машиной Тьюринга.
Тезис - не аксиома и не теорема, просто другое определение алгоритма.

Пример 1. На ленте записано слово из 0 и 1. Составить систему команд для машины Тьюринга, которая заменяет 0 на 1, а 1 на 0.
Решение. Изобразим систему команд с помощью графа (диаграммы) переходов.
ДМТ идёт по слову слева направо, переписывая нули и единицы, доходит до пустого символа и двигается налево, как кот учоный, пока не вернётся на первый непустой символ.
(Заметим, что стандартное заключительное состояние любой ДМТ - останов на первом непустом символе. Это нужно для композиций машин Тьюринга.)

[Swetlana]

Функции, правильно вычислимые по Тьюрингу

Заметим, что результативность алгоритма желаемое, но не обязательное свойство. Алгоритм может зациклиться, а машина Тьюринга работать бесконечно.

Пусть слова, записанные на ленте, будут иметь вид словарных векторов , где - слово в исходном алфавите , * - символ-разделитель. Такую запись назовем правильной.
Пусть и - множества словарных векторов над алфавитом .
Опр.6. Говорят, что ДМТ перерабатывает слово в слово , если начиная из начальной конфигурации приходит в заключительную :
Опр.7. ДМТ правильно вычисляет функцию , если:
$$1. \ q_{1}v \mapsto q_{z}w \ è \ f(v)=w;$$" title="$$ $$" align="middle" style="border: 0; vertical-align: middle">2. \ Åñëè \ f(v) \ íå \ îïðåäåëåíà \ â \ v, \ òî \ ÄÌÒ, \ çàïóùåííàÿ \ èç \ q_{1}v, \ áóäåò \ ðàáîòàòü \ áåñêîíå÷íî.$$

Опр.8. Если для функции существует ДМТ, которая ее правильно вычисляет, функция называется правильно вычислимой по Тьюрингу.

Заметим, что аналогично тезису Тьюринга существует тезис Чёрча о том, что любой алгоритм можно представить в виде вычислимой функции. Нетрудно доказать теорему о том, что функция, вычислимая по Тьюрингу, вычислима по Чёрчу и наоборот.

Литература

Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. Учебник. М.: Энергоатомиздат, 1980.

[Swetlana]

$$Êëàññ \ P$$

Опр.9. Время, требуемое ДМТ для вычисления на входе , есть число шагов, выполняемых ДМТ от до . Если ДМТ-программа останавливается на всех входах, то её временная сложность определяется так:
$$T_{ÄÌÒ}(n) = max \{t: \ ñóùåñòâóåò \ òàêîå \ âõîäíîå \ ñëîâî\ \alpha, \ |\alpha|=n,\ ÷òî \\ âû÷èñëåíèå \ ÄÌÒ \ íà \ âõîäå \ \alpha\ òðåáóåò \ t\ øàãîâ \}$$
(Взятие максимума соответствует самому плохому случаю.)

Опр.10. ДМТ называется полиномиальной ДМТ-программой, если существует такой полином , что для всех целых положительных $$T_{ÄÌÒ}(n) \leq p(n)$$.

Опр.11. Любая задача из класса решается полиномиальной ДМТ-программой.
Задачи из класса называются легкорешаемыми...
...не потому, что их легко решить, а потому что их можно решить эффективными алгоритмами. Хотя, как верно заметил folk, полиномиальные алгоритмы не всегда бывают эффективными.

Литература
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982, 416 стр.

[Swetlana]

Source of the post
Вот C/ANSI куда отнести: алгоритмические, функциональные (вычислимая функция), логические ..

к алгоритмическим
там, где программа - последовательность команд, матмоделью компилятора является U-машина (универсальная машина Тьюринга).

[Andrew58]

Немного несвоевременный и совсем детский вопрос. Почему нельзя прологарифмировать сложность задачи и переопределить классы после логарифмирования? Разве не удобнее будет? Полиномы превратятся в... экспоненты превратятся в ...

[zykov]

Source of the post
Cлучай 2: Сложность N^3 - метод гаусса. На практике практически не используется - во первых накапливает ошибки численные, во вторых куб это слишком много. Чаще используются итерационные методы в которых основная операция это умножение матриц а не обращение - то есть N^2 (и меньше нельзя так как элементов в матрице N^2 - если не брать разреженные матрицы и специализированные алгоритмы).

Это совсем не так!

Для плотных матриц метод Гаусса как раз является основным. Накопления ошибок нет при правильном выборе последовательности столбцов (или строк). Здесь итерационные методы почти не используются за редкими случаями (например когда матрица близка к ортонормированной).
Для разреженных матриц наоборот метод Гаусса - редкость. В основном итерационные (например сопряженные градиенты).

[Swetlana]

Source of the post
Немного несвоевременный и совсем детский вопрос. Почему нельзя прологарифмировать сложность задачи и переопределить классы после логарифмирования? Разве не удобнее будет? Полиномы превратятся в... экспоненты превратятся в ...

неудобно будет

идёт борьба за выч.сложность, полно алгоритмов, у которых уже не , а
например, сортировка на бинарном дереве

[Sonic86]

Svetlana Fainshtein, пишите формулы ТеХом!

Внесу свою маленькую лепту: NP-задачи - это те, у которых решение проверяется за полиномиальное время.
И еще: автоматическое доказательство теорем - NP-полная задача.

[Swetlana]

Sonic86, а я, по-вашему, чем пишу? :shock
У coNP (дополнительных к NP) неизвестно, можно ли решение проверить за полиномиальное время, я это покажу как в Гэри-Джонсоне, перестановкой состояний "да" и "нет" в НДМТ, чуть позже