Лекции - Теория алгоритмов
Подождите немного. Документ загружается.
Основные черты алгоритмов
► Дискретность алгоритма. Процесс последовательного
преобразования исходного набора данных в
алгоритмическом процессе происходит по тактам
(шагам): такт 1, такт 2,…. Каждый такт является
сменой одного набора данных другим набором.
► Детерминированность алгоритма. В алгоритмическом
процессе происходит преобразование объекта
P
на
входе в объект
Q
на выходе алгоритма. При этом все
шаги алгоритма
A,
величины промежуточных
вычислений и выходной объект
Q
однозначно
обусловлены заданием пары
(A,P).
Детерминированность алгоритма означает, что при
повторном выполнении
A
с объектом
P
на входе снова
получится объект
Q.
Основные черты алгоритмов
(продолжение)
► Массовость алгоритма - требование найти единый
алгоритм для решения не отдельной задачи, а серии
задач из некоторого класса. Отдельные задачи класса
получаются при варьировании входных данных.
Поэтому для каждого алгоритма существует некоторая
фиксированная, потенциально бесконечная
совокупность
X
возможных начальных данных. Из этой
совокупности выбирается объект
P,
поступающий на
вход алгоритма. Например, в алгоритме сложения
натуральных чисел в качестве
X
выступает множество
всех пар
(a,b),
где
a,b
– произвольные натуральные
числа.
Абстракция потенциальной
осуществимости
► Изучая алгоритмы, мы придерживаемся некоторых соглашений -
абстракций теории алгоритмов.
Абстракция потенциальной осуществимости.
1. Алгоритмический процесс при выработке результата
Q
из
исходных данных
P
совершает несколько отдельных шагов.
Число таких шагов может быть настолько велико, что
достижение результата
Q
является практически неосуществимым.
Однако в общей теории алгоритмов мы не учитываем
практическую осуществимость и считаем возможным выполнить
любое конечное число шагов.
2. Абстракция потенциальной осуществимости предполагает также
то, что мы можем оперировать со сколько угодно большими
объектами, например, со сколь угодно длинными словами.
Необходимость уточнения понятия
алгоритма
► Пусть имеется некоторая алгоритмическая проблема, т.е. необходимо
найти алгоритм для решения определенного класса задач. Если такой
алгоритм найден, то предложенный способ для решения задачи
признается всеми как алгоритм, исходя из их собственного интуитивного
представления об алгоритме. Поэтому не требуется точного определения
понятия алгоритма.
► Однако ситуация становится противоположной, если у нас после
длительных, безуспешных попыток нахождения алгоритма возникает
гипотеза, что такого алгоритма не существует. Чтобы иметь возможность
доказывать несуществование алгоритма, мы должны математически точно
определить объект, существование которого будет опровергаться.
► Для доказательства несуществования алгоритма необходимо располагать
точным определением понятия алгоритма.
► В двадцатых годах XX века задача точного определения понятия
алгоритма стала одной из центральных математических проблем. Она
заключалась в попытке дать строгое математическое определение
алгоритма, которое соответствовало бы имевшимся в то время
интуитивным представлениям об алгоритме.
Формализация А. Черча и С. Клини
► Строгое определение
алгоритма,
предложенное Черчем и
Клини, основано на
понятии частично
рекурсивной функции.
Они предложили
отождествить
интуитивное понятие
«алгоритм» со строгим
математическим
понятием «частично
рекурсивная функция».
Формализация А. Тьюринга
► С точки зрения английского
математика А.Тьюринга
алгоритмический процесс – это
работа некоторой
воображаемой вычислительной
машины – машины Тьюринга.
Он предложил отождествить
интуитивное понятие
«алгоритм» с точным понятием
«машина Тьюринга».
Формализация А.А. Маркова
► Третий вариант определения
алгоритма предложил в 1947
г. российский математик
А.А.Марков. С его точки
зрения, алгоритмический
процесс - это переработка
слов некоторого алфавита с
помощью точно описанных
правил переработки. Вместо
интуитивного понятия
«алгоритм» А.А.Марков вводит
строгое понятие «нормальный
алгорифм».
Лекция 2. Конструктивные объекты.
Числовые функции и алгоритмы их
вычисления
►Для того чтобы правильного понимать
понятие алгоритма, нужно ответить на
следующий вопрос. Какие объекты
поступают на вход алгоритма, какие
объекты возникают в процессе вычислений
и на выходе алгоритма?
Ответ следующий: Исходными и
промежуточными данными, а также и
результатом алгоритмического процесса
являются конструктивные объекты.
Конструктивные объекты
► Понятие конструктивного объекта является первичным,
неопределяемым понятием теории алгоритмов, которое
разъясняется далее на ряде примеров.
► Алфавит. Простейшим примером конструктивных
объектов являются слова в некотором алфавите
A={a,b,c,...}.
Элементы алфавита называются буквами,
а последовательности букв – словами. Количество букв
в слове называется длиной слова. Длина слова – это
натуральное число. Рассматривается так же и пустое
слово - слово нулевой длины.
► Пример. Алгоритм сложения натуральных чисел
перерабатывает конструктивные объекты – слова в
алфавите A={0,1,2,...,9,+}.
Конструктивные объекты
(продолжение)
► Можно указать другие конструктивные объекты: натуральные
числа, записанные в какой-либо системе счисления; слова в
естественном языке; формулы в алгебре высказываний. В
школьном курсе алгебры рассматриваются буквенные выражения,
в высшей алгебре – матрицы, а в дискретной математике – графы,
в информатике – программы на каком-либо языке
программирования.
► Пример. Прямоугольная матрица может быть представлена в виде
одной строки: A=[[10,12,5],[3,24,7],[6,5,-3]]. Этот пример является
проявлением общего правила:
► Конструктивные объекты при подходящей записи могут быть
представлены словами в некотором конечном алфавите.