5. Теория алгоритмов
Основные понятия
Численный алгоритм – алгоритм, сводящий решение данной задачи к операциям над числами.
Пример словесного алгоритма Евклида (нахождение наибольшего общего делителя):
обозревай a и b и переходи к следующему;
сравни обозреваемые числа (
,
или
,
или
)
и переходи к следующему;если обозреваемые числа равны, то каждое из них дает искомый результат, если нет – переходи к следующему;
если первое обозреваемое число меньше второго, переставь их местами и переходи к следующему;
вычитай второе число из первого и обозревай два числа – вычитаемое и остаток; переходи к указанию 2.
Логический алгоритм – содержит предписания, относящиеся не к цифрам, а к объектам любой природы. Пример – поиск пути в конечном лабиринте.
Программа – процесс последовательного построения заданных величин, идущий в дискретном времени в определенной последовательности.
Алфавит – конечная система символов (букв).
Слово
– конечная последовательность букв
некоторого алфавита. Например, в алфавите
словами будут последовательности b,
ac,
bac,
abbca
и т.д. Пустое слово обозначается «»
.
Подстановка
L–M
в слове R
означает замену словом M
всех вхождений слова L
в слове R,
и наоборот,
замену словом L
всех вхождений
слова M
в слове R.
Например, подстановка
,
примененная к слову
даст слово
,
либо слово
.
Эквивалентные слова могут быть получены друг из друга последовательным применением допустимых перестановок.
Стандартные алгоритмы
Нормальный алгоритм Маркова.
Задается
алфавит и фиксируется система
ориентированных (однонаправленных)
подстановок. В заданном слове R
просматриваются возможные подстановки
в том порядке, в котором они заданы.
Первая встретившаяся подстановка
используется для преобразования слова
в слово
(вместо первого вхождения левой части
подстановки подставляется ее правая
часть). Далее процесс повторяется для
слова
.
Машина Тьюринга.
Работа
машины происходит в дискретном времени.
На каждом такте считываемый символ
заменяется другим
,
который определяется состоянием машины
в данный момент времени. Кроме того,
определяется следующее состояние машины
и команда перемещения ленты, с которой
считываются символы («П» – смотреть
ячейку справа; «Л» – смотреть ячейку
слева; «Н» – смотреть ту же ячейку; «!»
– стоп).
Задачи
Составьте словесные алгоритмы для решения следующих задач:
а)
умножение n
чисел
;
б)
поиск максимального элемента из множества
;
в)
определение множества
равного пересечению двух множеств
и
(
);
г)
определение множества
равного объединению двух множеств
и
(
);
д) поиск минимального элемента из множества .
Нормальный алгоритм Маркова задан в алфавите системой подстановок:
;
;
;
.
Найдите слова в которые это алгоритм
перерабатывает слова:
а)
и
;
б)
и
;
в)
и
;
г)
cacab
и
;
д)
и
.
Перечень рекомендуемой литературы:
Акимов О.Е. Дискретная математика: логика, группы, графы. – М.: Лаборатория Базовых Знаний, 2001. – 352 с.
Яблонский С.В. Введение в дискретную математику: Учеб. пособие для вузов. / Под ред. В.А. Садовничего. – 3-е изд., стер. – М.: Высш.шк.; 2003. – 384 с.
Пухальский Г.И., Новосельцева Т.Я. Цифровые устройства. – М.: Радио и связь, 1996.
Сигорский В.П. Математический аппарат инженера. Изд. 2-е, стереотип. «Технiка», 1977. - 768 с.
Фудзисава Т., Касами Т. Математика для радиоинженеров: Теория дискретных структур: Пер. с япон. – М.: Радио и связь, 1984. – 240 с.
Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энегия, 1980. – 344 с.
Горбатов В.А. Основы дискретной математики: Учеб. пособие для студентов вузов. – М.: Высш. шк., 1986. – 311 с.
Таха Х. Введение в исследование операций: В 2-х книгах. Кн.1. Пер. с англ. – М.: Мир, 1985. – с.241-270.