Тип 1

1.Что изучает Теория алгоритмов?

Теория алгоритмов – наука, изучающая общие свойства и теории алгоритмов, а так же различные формальные модели и их представления . До 20 годов 20 века не возникало вопросов что такое алгоритм. 1931 год стал точкой отсчёта для современной теории алгоритмов.

2.Происхождение термина «алгоритм»

Одним из фундаментальных понятий в информатике является понятие алгоритма. Происхождение самого термина «алгоритм» связано с математикой. Это слово происходит от Algorithmi – латинского написания имени Мухаммеда аль-Хорезми (787 – 850) выдающегося математика средневекового Востока. В своей книге "Об индийском счете" он сформулировал правила записи натуральных чисел с помощью арабских цифр и правила действий над ними столбиком. В дальнейшем алгоритмом стали называть точное предписание, определяющее последовательность действий, обеспечивающую получение требуемого результата из исходных данных. Алгоритм может быть предназначен для выполнения его человеком или автоматическим устройством

3.Когда возникла наука Теория алгоритмов?

1931 год стал точкой отсчёта для современной теории алгоритмов. Курт Гёдель 1931.

1936 год – Алан Тьюринг, Алан Тьюринг Алоиз Черч предложили свои теории. Это можно считать отправной точкой для науки.

4.Какие ученые считаются основателями Тории алгоритмов?

Алан Тьюринг предложил в 1936 году свою машину, которая стала классической.

Алоиз Черч предложил теорию рекурсивных алгоритмов

Эмиль Пост предложил … свою машину.

5.Россияне, внесшие вклад в Теорию алгоритмов

Одним из наиболее удачных стандартизованных вариантов алгоритма является введённое А. А. Марковым понятие нормального алгоритма. Оно было разработано десятью годами позже работ Тьюринга, Поста, Чёрча и Клини в связи с доказательством алгоритмической неразрешимости ряда алгебраических проблем.

6.Объекты алгоритма

«Алгоритм — это система операторов, взятых из множества операторов некоторого исполнителя, которая полностью определяет некоторый класс алгоритмических процессов, то есть процессов, которые:

1.дискретны;

2.детерминированы;

3.потенциально конечны;

4.преобразовывают некоторые конструктивные объекты.

7.Финитный подход к объектам алгоритмов

Существо финитного подхода заключается в том, что он допускает только конечные комплексы действий над конечным числом объектов.

8.Детерминированность алгоритма

Детерминированный алгоритм — алгоритмический процесс, который выдаёт уникальный и предполагаемый результат для заданных входных данных

9.Требования к последовательности шагов алгоритма

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

10.Массовость алгоритмов

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

11.Перечислите алгоритмические модели

12.Прямое произведение множеств

Прямое или декартово произведение — множество, элементами которого являются всевозможные упорядоченные пары элементов исходных двух множеств

Множество, состоящее из всех кортежей длины n таких, что первый элемент кортежа принадлежит первому множеству-операнду, второй элемент — второму множеству-операнду и т.д., где n — число множеств-операндов. Декартово произведение двух множеств — множество, элементами которого являются всевозможные упорядоченные пары элементов исходных двух множеств

13.Степень множества

Декартовый квадрат это множество всех пар элементов множества, а n-ой степенью называется множество всех n-членных последовательностей элементов множества. Или, на другом языке, множество всех отображений множества чисел {1,2,...n} в множество.

14. Полная итерация множества

18.Область определения соответствия

20.Образ элемента в соответствии

21.Прообраз элемента в соответствии

22.Сюръективное соответствие

23.Всюдуопределенное соответствие

24.Инъективное соответствие

25.Функциональное соответствие

26.Состав машины Тьюринга

Лента, головка считывания\записи, УУ(устройство управления)

27.Шаг работы машины Тьюринга

Перемещение головки по ленте на 1 ячейку(либо стоять на месте), согласно команде УУ

28.Алфавиты машины Тьюринга

Все символы, имеющиеся на ленте – слово МТ

Алфавит состояний – конечное множество состояний МТ

29.Команда машины Тьюринга

Команда МТ – это система шагов, приводящая к результату(???)

30.Представление системы команд в виде таблицы

Это таблица, столбцы которой – символы алфавита ленты, а строки – символы алфавита состояний.

31.Диаграмма состояний машины Тьюринга

Граф, вершинам которого сопоставлены состояния м.Т

32.Конфигурация машины Тьюринга

Полное состояние м.Т. определяется состоянием УУ, состоянием ленты и положением головки на ленте. Полное состояние называется конфигурацией.

33.Функция, вычислимая по Тьюрингу (в общем виде)

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

34.Функция, вычислимая по Тьюрингу (в унарном коде)

Пусть дана f(x1,x2,…,xn). Она правильно вычислима по Т., если:

1)q11x1 * 1x2 * 1x3 … * 1xn => qz1y, где y=f(x1,x2,…,xn)

2)q11x1 * 1x2 * 1x3 … * 1xn => qz1y – не останавливается, если f(x1,x2,…,xn) – не существует.

35.Машина Тьюринга с полулентой и ее полнота

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

36.Композиция функций

Пусть заданы две функции f: A->B и g: B->C, тогда функция h: A->C называется композицией функций f и g.

37.Понятие машины Тьюринга для вычисления предиката

М.Т. правильно вычисляет предикат P(a), если T(a)=w и

w=И, когда P(a) истинен

w=Л, когда P(a) ложен

машина Т не останавливается, если P(a) не определен

38.Конструирование машины вычисления предиката с восстановлением

39.Функция разветвления

41.Кодирование алфавита ленты в универсальной машине Тьюринга

42.Кодирование алфавита состояний в универсальной машине Тьюринга

Пусть |А_т| = m_т – количество символов (&)-лямбда

Пусть |Q_т| = n_т – количество состояний

Символы алфавита нумеруются

S(&) = &^m_t Остальной алфавит нумеруется и его код

S(a_j) = a&^m_t ^{– 1 – j} 1^j

Состояния S(q_i) = q &^{nt - 1 – i} 1ⁱ

S(q_z) = q &^nt-1

Тип 2

1.Цели и задачи Теории алгоритмов

•Формализация понятия алгоритма и исследование формальных алгоритмических систем

•Формальное доказательство алгоритмической неразрешимости некоторых задач

•Классификация задач по сложности

•Анализ сложностей алгоритма

•Исследование и анализ рекурсивных алгоритмов

•Получение функции трудоемкости сравнительного анализа алгоритмов

•Разработка критериев сравнения алгоритмов

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

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