ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ

11 минут

2 прочтения

7 июля 2020

Элементы теории алгоритмов... Звучит, конечно, страшно, но попробуем разобраться. Что такое алгоритм? Какие свойства имеет? Какие виды бывают? Что такое вспомогательный алгоритм и кому он помогает? Это и многое другое предлагаю рассмотреть прямо здесь и сейчас, доступным языком и на конкретных примерах. Согласен? Тогда листай и познавай ;)

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

А.Н. Колмогоров

Алгоритм – точное предписание, определенный вычислительный процесс, варьирует исходные данные к результату.

А.А. Марков

Термин «алгоритм» («алгорифм») происходит от имени среднеазиатского ученого Мухаммеда Аль Хорезми (787 – ок. 850) – им были сформулированы правила выполнения четырех арифметических действий над числами в десятичной записи.

Основные свойства алгоритмов

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

2. Детерминированность (определенность): каждый последующий шаг однозначно определяется предыдущими шагами.

3. Дискретность (прерывность или скачкообразность) т.е. работа алгоритма происходит тактами (скачками, шагами).

4. Результативность. После конечного числа шагов алгоритм должен выдать результат.

5. Элементарность. Каждый шаг должен быть достаточно простым.

6. Абстракция потенциальной осуществимости. Конечный алгоритм считается осуществимым даже если на его выполнение не хватает одной человеческой жизни или поколения, бумаги на всем земном шаре.

Исполнитель алгоритма — это субъект или устройство, которые способны правильно интерпретировать описание алгоритма и выполнить содержащийся в нем перечень действий.

Понятие вычислимой функции (ВФ). График вычислимой функции

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

Графиком ВФ называется множество пар вида (х, f(х)).

Примеры:

х – любое натуральное число, f(х)=х2;

х – пара рациональных чисел х1, х2, f(х)=х1:х2 (эта функция определена лишь для тех х, у которых х2≠0);

х – пара матриц X1, X2 с целочисленными элементами, f(X)=X1*X2 (эта функция определена лишь для тех X, у которых число столбцов в X1 равно числу строк в X2).

Аргументами и значениями вычислимых функций могут быть лишь конструктивные объекты, так как только такими объектами могут манипулировать алгоритмы.

Понятие конструктивного объекта является первичным, неопределяемым понятием теории алгоритмов.

Простейшим примером конструктивных объектов являются слова в некотором алфавите А = {a, b, c, ….}. Элементы алфавита называются буквами, а последовательности букв - словами. Длина слова – это количество букв в слове и натуральное число. Слово нулевой длины - пустое слово.

Пример: Алгоритм сложения натуральных чисел перерабатывает конструктивные объекты – слова в алфавите А = {0, 1, 2, … , 9, +}.

Теоретико-числовая функция – это вычислимая функция, областью определения и множеством значений которой являются натуральные числа.

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

Областью применимости алгоритма называется совокупность тех объектов, к которым он применим, то есть дает результат.

Про алгоритм А говорят, что он:

-«вычисляет функцию f», если его область применимости совпадает с областью определения f, и А перерабатывает любой х из своей области применимости в f(х);

-«разрешает множество М относительно множества Х», если он применим к любому х из Х и перерабатывает любой х из Х∩М в слово «да», а любой х из Х\М – в слово «нет»;

-«перечисляет множество М», если его область применимости есть натуральный ряд, а совокупность результатов есть М. Множество называется разрешимым относительно Х, если существует разрешающий его относительно Х алгоритм. Множество называется перечислимым, если либо оно пусто, либо существует перечисляющий его алгоритм.

Теорема 1

Функция f вычислима тогда и только тогда, когда перечислим ее график.

Теорема 2

Подмножество М перечислимого множества Х тогда и только тогда разрешимо относительно Х, когда М и Х\М перечислимы.

Теорема 3

Если Р, Q перечислимы, то Р Q, Р∩ Q также перечислимы.

Теорема 4

В каждом бесконечном перечислимом множестве Х существует перечислимое подмножество с неперечислимым дополнением. (в силу теоремы 2 это перечислимое подмножество будет неразрешимым относительно Х).

Теорема 5

Для каждого бесконечного перечислимого множества Х существует вычислимая функция, определенная на подмножестве этого множества и не продолжаемая до вычислимой функции, определенной на всем Х.

Теоремы 4, 5 в совокупности дают пример алгоритма с неразрешимой областью применимости.

Способы представления алгоритмов:

Графический (в виде блок-схемы).
Словесный, текстовый (в виде последовательности шагов, описывающих действия естественным языком).
Программный (в виде программы, полностью или сжато представленной на каком-либо алгоритмическом языке).

Наиболее наглядным считается графический способ. В блок-схеме каждому типу действий соответствует геометрическая фигура, представленная в виде блочного символа. Блочные символы соединяются линиями переходов, определяющими очередность выполнения действий.

Этапы решения задач на ЭВМ:

Постановка задачи
Анализ и исследование задачи, модели
Разработка алгоритма
Программирование
Тестирование и отладка
Анализ результатов решения задачи и уточнение в случае необходимости математической модели с повторным выполнением этапов 2-5
Сопровождение программы

Линейные вычислительные алгоритмы

Линейный алгоритм – это алгоритм, содержащий алгоритмическую структуру «следование».

Конструкция ветвления - это часть алгоритма, в которой в зависимости от выполнения или невыполнения некоторого условия выполняется либо одна, либо другая последовательность действий. Алгоритм, в котором используется конструкция ветвления, называется алгоритмом с ветвлением.

Для реализации алгоритмов с разветвленной структурой в языках программирования используются условные операторы.

Циклические алгоритмы – алгоритмы, содержащие фрагменты повторения вычислений.

В зависимости от того, известно ли наперед число повторений некоторого участка алгоритма или нет, выделяют циклы арифметические и итерационные.

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

В итерационных циклах число повторений неизвестно, выход из цикла осуществляется при выполнении некоторого условия. Все арифметические циклы – это циклы с предусловием, когда условие проверяется до начала повторений. Проверка происходит после очередной итерации в циклах с постусловием.

Машина Поста

В 1936 году Эмиль Леон Пост (1897–1954) предложил машину, позволяющую формально определить алгоритм.

Тезис Поста: Всякий алгоритм представим в форме машины Поста.

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

Тезис Поста является гипотезой, его невозможно строго доказать.

Состав машины Поста: машина состоит из ленты и каретки. Лента бесконечна и разделена на секции одинакового размера — ячейки.

В каждой ячейке ленты может стоять метка V либо ничего не записано.. Состояние ленты — это распределение меток по ячейкам. Состояние ленты меняется в процессе работы машины.

Команды машины Поста:

1. записать 1 (метку), перейти к i-й строке программы;

2. записать 0 (стереть метку), перейти к i-й строке программы;

3. сдвиг влево, перейти к i-й строке программы;

4. сдвиг вправо, перейти к i-й строке программы;

5. останов;

6. если 0, то перейти к i, иначе перейти к j.

Недопустимые действия:

попытка записать 1 (метку) в заполненную ячейку;
попытка стереть метку в пустой ячейке;
бесконечное выполнение (зацикливание).

Команды машины обозначают следующим образом:

Пример: На ленте задан массив меток. Увеличить длину массива на 2 метки. Каретка находится либо слева от массива, либо над одной из ячеек самого массива. (увеличение числа на 2).

Решение:

1. ? 2; 3 (команды 1 и 2 — передвигаем каретку к массиву)

2. → 1

3. → 4 (команды 3 и 4 — передвигаем каретку к концу массива)

4. ? 5; 3

5. V 6 (команды 5–7 — ставим 2 метки в конце массива)

6. → 7

7. V 8

8. !

Машина Тьюринга

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

Состав Машины Тьюринга: это автомат, управляемый таблицей. Строки в таблице соответствуют символам выбранного алфавита A={a0,a1,…,aN}., а столбцы — состояниям автомата Q={q0,q1,…,qM}. При вводе команд пробел заменяется знаком подчеркивания «_».

В начале работы машина Тьюринга находится в состоянии q1. Состояние q0 — это конечное состояние: попав в него, автомат заканчивает работу.

Пример:

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

Решение:

a0

0

1

2

3

…

7

8

9

q1

1 H q0

2 H q0

3 H q0

4 H q0

8 H q0

9 H q0

0 λ q0

Здесь q1 — состояние изменения цифры, q0 — остановка. Если в q1 автомат фиксирует элемент из ряда 0..8, то он замещает ее на один из 1..9 соответственно и затем переключается в состояние q0, то есть устройство останавливается. В случае если же каретка фиксирует число 9, то замещает ее на 0, затем перемещается влево, останавливаясь в состоянии q1. Такое движение продолжается до того момента, пока устройство не зафиксирует цифру, меньшую 9. Если все символы оказались равными 9, они замещаются нулями, на месте старшего элемента запишется 0, каретка переместится влево и запишет 1 в пустую клетку. Следующим шагом будет переход в состояние q0– остановка.

Вспомогательные алгоритмы

В современном программировании применяется технология нисходящего программирования «сверху вниз». Суть технологии в дроблении сложной задачи на более простые подзадачи (декомпозиция) до тех пор, пока не прояснятся все детали решения. Такие подзадачи оформляются в виде вспомогательных алгоритмов.

Реализация вспомогательных алгоритмов осуществляется посредством подпрограмм.

Подпрограмма – обособленная, оформленная в виде отдельной синтаксической конструкции и снабженная именем часть программы. Использование подпрограмм позволяет, сосредоточив в них подробное описание некоторых операций, в остальной программе указывать только имена подпрограмм, чтобы выполнить эти операции.

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

Функция – подпрограмма, которая передает в точку вызова скалярное значение.

Технология создания и использования процедур и функций

Процедура: структура процедуры схожа со структурой программы.

Вызов процедуры:

Пояснение: в данном фрагменте программы вызывается процедура вычисления суммы двух целых чисел. Процедура вызывается по имени.

При вызове процедуры Sum(a,b,c) из основной программы значение переменной присваивается переменной процедуры Sum, а значение переменной – переменной.

Глобальные и локальные переменные

В данном фрагменте программы переменные k, p – глобальные, a d,f - локальные.

Глобальные переменные описываются в разделе описаний основной части программы, а локальные – только в том, где описываются переменные. Локальные переменные существуют только во временя работы процедуры, определяются (создаются) при её вызове и «исчезают» после завершения работы процедуры.

При описании процедуры указывается список формальных параметров. Каждый параметр является локальным, к нему можно обращаться только в пределах данной процедуры (в примере x,y,z - формальные параметры).

Фактические параметры – это параметры, которые передаются процедуре при обращении к ней. (a,b,c – фактические параметр). Количество и типы формальных и фактических параметров должны совпадать.

Параметры-значения, т.е. передача параметров по значению. При таком способе передачи параметров значение фактического параметра становится значением соответствующего формального параметра. Внутри процедуры можно производить любые действия с данным формальным параметров (допустимые для его типа), но эти изменения никак не отражаются на значении фактического параметра, т. е. каким он был до вызова процедуры, таким же и останется после завершения её работы (x,y – формальные параметры-значения).

Параметры-переменные - формальные параметры, перед которыми стоит служебное слово Var. При таком способе передачи параметров в процедуру передаётся не значение, а адрес фактического параметра (обязательно переменной). Любые операции с формальным параметром выполняются непосредственно над фактическим параметром.

Функции

Структура функции: в теле функции обязательно должен быть хотя бы один оператор присвоения, где в левой части стоит имя функции, а в правой — ее значение. Иначе значение функции не будет определено.

Обращение к функции осуществляется по имени с необязательным указанием списка аргументов. Каждый аргумент должен соответствовать формальным параметрам, указанным в заголовке, и иметь тот же тип.