Вопросы к экзамену по дисциплине

«Теория алгоритмов»

Специальность «Информатика»

4 курс, 7 семестр

1. Интуитивное понятие алгоритма и эффективно вычислимой функции. Постановка задачи уточнения интуитивного понятия алгоритма. Основные направления исследований в теории алгоритмов.

2. Разрешимые (рекурсивные) и рекурсивно перечислимые множества. Признак Поста о разрешимости данного множества. Теорема о существовании перечислимого, но неразрешимого множество натуральных чисел.

3. Простейшие эффективно вычислимые функции (операторы сдвига, аннулирования и проектирования). Оператор суперпозиции (подстановки) функций.

4. Оператор примитивной рекурсии и схема примитивной рекурсии. Примитивно рекурсивные функции, примеры. Класс примитивно рекурсивных функций и его замкнутость.

5. Оператор минимизации. Частично рекурсивные, общерекурсивные функции и уточнение интуитивного понятия алгоритма на основе частично рекурсивных функций. Соотношение между классами примитивно рекурсивных, частично рекурсивных и общерекурсивных функций. Тезис Черча.

6. Несовпадение классов примитивно рекурсивных и вычислимых функций. Построение примера вычислимой, но не примитивно рекурсивной функции (функция Аккермана).

7. Уточнение (формализация) интуитивного понятия алгоритма с помощью машины Тьюринга. Тезис Тьюринга. Разновидности машин Тьюринга. Эквивалентность тезисов Черча и Тьюринга.

8. Композиция, итерация и разветвление машин Тьюринга. Имитация машины Тьюринга на компьютере фон Неймана и имитация компьютера фон Неймана на машине Тьюринга. Проблема очень больших ленточных алфавитов. Сравнение времени работы компьютеров и машин Тьюринга.

9. Нормальные алгоритмы Маркова, их свойства и области применимости. Схема алгоритма Маркова.

10. Общее понятие исчисления. Формальные языки и грамматики. Универсальный язык.

1. Интуитивное понятие алгоритма и эффективно вычислимой функции. Постановка задачи уточнения интуитивного понятия алгоритма. Основные направления исследований в теории алгоритмов.

Понятие алгоритма принадлежит к числу основных понятий математики. Примерами алгоритмов являются:

1. Правила выполнения арифметических действий над числами.

2. Правило отыскания наибольшего общего делителя (алгоритм Евклида).

3. Правило извлечения квадратного корня.

4. Правило отыскания решений квадратного уравнения.

5. Правило отыскания производной многочлена n-ой степени.

6. Правило интегрирования рациональной функции.

В каждом из приведённых примеров приходится иметь дело с классом однотипных задач, или, как говорят, с массовой проблемой. Задачи такого класса отличаются друг от друга значениями входящих в них параметров. Так, в задаче отыскания решения квадратного уравнения ax2+bx+c=0 участвует три параметра a, b и c; меняя их, получаем различные задачи одного класса.

В связи со сказанным можно дать следующее интуитивное определения понятия алгоритма.

Алгоритмом называется общий единообразный, точно определённый способ решения любой задачи из данной массовой проблемы.

Отметим характерные черты понятия алгоритма.

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

2. Детерминированность алгоритма. Система величин, получаемых в какой-то не начальный момент, однозначно определяется системой величин, полученных в предшествующие моменты времени.

3. Элементарность шагов алгоритма. Закон получения последующей системы величин из предшествующей должен быть простым.

4. Массовость алгоритма. Начальная система величин может выбираться из некоторого потенциально бесконечного множества.

5. Результативность алгоритма. Последовательный процесс построения величин должен быть конечным и давать результат, то есть решение задачи.

2. Разрешимые (рекурсивные) и рекурсивно перечислимые множества. Признак Поста о разрешимости данного множества. Теорема о существовании перечислимого, но неразрешимого множество натуральных чисел.

Разрешимые и перечислимые множества

Пусть имеется некоторый алфавит. Обозначим через S множество всех слов в данном алфавите, а через M подмножество множества S.

Определение 1. Множество М называется разрешимым, если для него существует алгоритм, решающий проблему вхождения слова x в М.

Определение 2. Множество М называется эффективно перечислимым, если существует алгоритм, позволяющий перечислить все элементы этого множества (возможно с повторениями).

Теорема 1. Если множества М и L эффективно перечислимы, то эффективно перечислимы множества M  L и M  L.

Доказательство. Пусть множества М и L эффективно перечислимы. Тогда для каждого из них существует свой алгоритм, позволяющий перечислить все элементы данного множества. Алгоритм для эффективного перечисления множеств М  L и M  L получается путём одновременного применения алгоритмов для эффективного перечисления множеств М и L.

Теорема 2 (Поста). Множество М разрешимо тогда и только тогда, когда оно само и его дополнение эффективно перечислимы.

Доказательство. Путь множество М и его дополнение СМ эффективно перечислимы, то есть существуют алгоритмы А и В, с помощью которых можно перечислить элементы этих множеств. Но тогда при перечислении элементов множеств М и СМ в их списке встретится элемент х. Следовательно, существует алгоритм С, позволяющий узнать, принадлежит элемент x множеству М или не принадлежит.

Пусть множество М разрешимо. Тогда существует алгоритм, решающий проблему вхождения x в М. Пользуясь этим алгоритмом, составим список элементов, входящих в М, и список элементов, входящих в СМ. Следовательно, мы получим два алгоритма А и В, позволяющих перечислить множества М и СМ. Примерам эффективно перечислимого множества являются множество М = {1, 4, 9 ,…,n2,…} квадратов натуральных чисел.

Действительно, множество М = {n2} перечислимо, т.к. для получения его элемен-тов нужно последовательно брать натуральные числа и возводить их в квадрат. Более то-го, это множество является также и разрешимым: для проверки того, принадлежит ли некоторое натуральное число х множеству М, нужно разложить число на простые множители, и это даст возможность установить, является ли оно точным квадратом.