- •1.1. Вычислимые функции, разрешимые и перечислимые множества.
- •1.2. Основные свойства разрешимых и перечислимых множеств (с доказательством).
- •1.3. Теоремы, связывающие понятия вычислимость, разрешимость и перечислимость.
- •Разрешимые множества.
- •Перечислимые множества.
- •1.4. Теорему Поста и теорему о графике вычислимой функции (с доказательством).
- •1.5. Интуитивное понятие алгоритма, исполнитель алгоритма. Основные свойства алгоритма.
- •Свойства алгоритмов:
- •Машина Тьюринга как алгоритмическая модель. Модель Тьюринга (Тьюринга-Поста).
- •Та.2.Алгоритмически неразрешимые проблемы.
- •2.3. Нумерация, натуральная нумерация, однозначная нумерация.
- •2.4. Девятая проблему Гильберта о диофантовых уравнениях.
- •Та.3.Основные меры сложности вычисления
- •3.1.Временная и емкостная сложность.
- •3.2. Нижние и верхние оценки временной сложности.
- •3.3. Эффективность вычислений
- •3.4. Классы сложности (p, exp, np, npc).
1.5. Интуитивное понятие алгоритма, исполнитель алгоритма. Основные свойства алгоритма.
Алгоритм – это точное и полное предписание о последовательности выполнения конечного числа некоторых действий, необходимых для решения любой задачи данного типа. Алгоритм – это процесс последовательного построения величин, идущий в дискретном времени таким образом, что в начальный момент задаётся исходная конечная система величин, а в каждый следующий момент система величин получается по определённому за-кону из системы величин, имевшихся в предыдущий момент времени.
Исполнитель алгоритма - это человек или автомат (в частности, им может быть процессор ЭВМ), умеющий выполнять некоторый, вполне определенный набор действий.
Свойства алгоритмов:
-
дискретность-поочередное выполнение команд алгоритма за конечное число шагов приводит к решению задачи, к достижению цели.
-
определенность (или точность) -каждый алгоритм строится в расчете на некоторого исполнителя.
-
результативность (или конечность)-исполнение алгоритма должно закончиться за конечное число шагов.
-
Универсальность-Алгоритм дол-жен быть составлен так, чтобы им мог воспользоваться любой исполнитель для решения аналогичной задачи.
1.6. Частично-рекурсивные функции. Тезис Черча. Машина Тьюринга как алгоритмическая модель. Тезис Тьюринга. Нормальные алгоритмы Маркова как алгоритмическая модель. Тезис Маркова. Композиция алгоритмов (на любой модели).
Частично-рекурсивные функции в модели Чёрча. Этот класс функций строится на множестве N0 и задаётся так: 1) O(x)=0 (тождественное равенство нулю); 2) S(x)=x+1 (непосредственное следование); 3) Inm(x1, x2, …, xn)=xm (функция выбора одного из своих аргументов).
Тезис Черча. Все частично-рекур-сивные функции являются алгоритмически вычислимыми.
Машина Тьюринга как алгоритмическая модель. Модель Тьюринга (Тьюринга-Поста).
Он описывает некоторую формально работающую машину, которая состоит из ленты, управляющего (логического) устройства (оно мо-жет находиться в одном из конечного числа внутренних состояний Q), считывающе-записывающего устройства (R, L, S - команды движения СЗУ). 3 алфавита: внешний A={a0,…,am}, внутренний (алфавит состояний) Q={q0,q1,…,qn} (q0 – стоп, q1 - начало), алфавит сдвигов D={R,L,S}. Команда машины Тьюринга: qiaj alDqk.
В рамках этой системы алгоритмом мы называем машину Тьюринга, заданную алфавитами A, Q, D и совокупностью конечных команд: qiaj alDqk.
Тезис Тьюринга: Для всякого алго-ритма может быть построен Тьюрингов алгоритм (программа машины Тьюринга), дающий при одинаковых исходных данных тот же результат.
Нормальные алгоритмы Маркова как алгоритмическая модель. Суть: последовательное порождение слов в алфавите согласно предписанию, которое задаётся системой подстановок (схемой) в словах, которые указывают, какие замены символов необходимо производить и в каком порядке эти подстановки должны следовать.В этой модели есть алфавит и система формул, но нет понятия машины.
Тезис Маркова: Любой алгоритм нормализуем. Тот или иной алгоритм нормализуем, если можно построить эквивалентный ему нормальный алгоритм.