Лекція 1. Теорія алгоритмів. Аналіз алгоритмів

1.1 Задачи теории алгоритмов.

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

Примеры задач теории алгоритмов:

– доказательство алгоритмической неразрешимости задач;

– асимптотический анализ сложности алгоритмов;

– классификация алгоритмов в соответствии с классами сложности.

В 1936 г. английский математик Алан Тьюринг описал схему абстрактной машины и предложил назвать алгоритмом то, что умеет делать эта машина. Машина Тьюринга – это не реальная вычислительная машина, а способ описания алгоритма, при помощи которого формализуется понятие алгоритма, что дает возможность его исследовать [1]. Машина Тьюринга есть средство формализации алгоритма.

В машине Тьюринга можно выделить следующие составные части:

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

2) считывающее устройство, которое на любом шаге работы машины Тьюринга обозревает некоторую ячейку памяти;

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

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

Алгоритм (определение 1) – точное предписание, определяющее вычислительный процесс, ведущий к искомому результату [2].

Алгоритм (определение 2) – любая корректно определенная вычислительная процедура, на вход которой подается некоторая величина или набор величин и результатом выполнения которой является выходная величина или набор значений [3].

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

Определение 1 можно рассматривать как более абстрактное, нежели определение 2, а последнее – как таковое в контексте информационных технологий.

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

Говорят, что алгоритм корректен, если для любых корректных входных данных результатом его работы являются корректные выходные данные. Под корректностью зачастую подразумеваются согласованность и непротиворечивость (данных), соответствие требованиям, правильность, точность. Корректный алгоритм – такой алгоритм, который корректно решает некоторую данную вычислительную задачу [3]. Если алгоритм некорректный, то для некоторых входных данных он не может завершить свою работу или выдает неправильный результат.

Алгоритм может быть задан следующим образом:

– на естественном языке – словесное описание (в виде тезисов);

– формализовано – в виде псевдокода или компьютерной программы; от программного кода псевдокод отличает то, что последний позволяет более выразительно и лаконично описывать алгоритм;

– реализован аппаратно.

Алгоритмы могут быть описаны словесно (поэтапно или пошагово), представлены графически в виде блок-схемы, представлены в виде псевдокода или в виде программы.

1.2 Определения и свойства алгоритмов[1]:

1) свойство массовости – каждый алгоритм является инструментом решения потенциально бесконечного множества задач;

2) свойство дискретности – алгоритм состоит из шагов (этапов); на каждом шаге обработке подлежат соответствующие входные данные, результатом которой будут некоторые выходные данные;

3) свойство детерминированности – для каждого множества входных данных для отдельно взятого шага алгоритма существует единственное множество корректных выходных данных;

4) свойство элементарности шагов алгоритма – каждый из шагов характеризуется входными, выходными данными, а также ссылкой на последующий шаг алгоритма. Если разделение некоторого шага на составляющие (более мелкие) шаги сопровождается утратой некоторой (некоторых) из названных трех характеристик, то такой шаг алгоритма является элементарным или неделимым;

5) свойство направленности алгоритма (формирует вышеназванное свойство элементарности шагов) – заключается в определении следующего шага, подлежащего выполнению;

6) конечность шагов алгоритма – среди шагов алгоритма обязательно должен быть шаг, прекращающий выполнение алгоритма.

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

1.3 Алгоритм как инструмент решения задач. Примеры задач.

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

Для того, чтобы удовлетворить названному временному ограничению (поиск должен выполняться, например, не дольше секунды), можно воспользоваться таким инструментом (средством), как "алгоритм". В рассматриваемом сценарии целесообразно выделить следующие ключевые этапы:

– сортировка записей таблиц по некоторому ключу (столбцу) – как вспомогательный шаг, направленный на повышение эффективности;

– непосредственно поиск нужной записи в отсортированной последовательности записей.

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

Для осуществления эффективного поиска важно, чтобы элементы пространства поиска были отсортированы. Для решения задачи сортировки выполним ее формализованную постановку [3]:

– вход – последовательность из записей таблицы ;

– выход – перестановка входной последовательности (отсортированная последовательность) : – для случая сортировки по возрастанию.

Входную последовательность называют экземпляром задачи сортировки. Под экземпляром подразумеваются входные данные, необходимые для решения задачи и удовлетворяющие заданным ограничениям. Например, входная последовательность является экземпляром задачи сортировки, а перестановка – результатом работы алгоритма сортировки.

Во многих алгоритмах (программах) сортировка рассматривается в качестве промежуточного (или начального) шага – например в случае осуществления бинарного поиска.

1.4 Анализ работы алгоритмов.

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

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

В качестве ресурса будем рассматривать "время".

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

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

Определение понятия "размера входных данных" (input size) зависит от решаемой задачи. Для задач сортировки это количество элементов массива, подлежащего сортировке. Для случая перемножения целых чисел – это количество битов, необходимых для представления операндов в бинарном виде и т.д. Зачастую под входными данными подразумевается граф, который характеризуется некоторым количеством вершин и ребер.

"Время работы" алгоритма измеряется в количестве элементарных операций или "шагов", которые необходимо выполнить. Зачастую подразумевают, что для выполнения некоторого элементарного шага требуется некоторое фиксированное (известное либо измеренное) время.

Для оценки времени работы алгоритма используются понятия "скорости роста" алгоритма (rate of growth) или "порядка роста" (order of growth).

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

Рассматривая входные данные достаточно больших размеров для оценки такой величины как "порядок роста" времени работы алгоритма изучают асимптотическую эффективность алгоритмов. Это означает, что нас интересует характер или скорость роста времени работы алгоритма в зависимости от размера входных данных в пределе, когда этот размер увеличивается до бесконечности. Как правило, алгоритм, более эффективный в асимптотическом смысле, будет более производительным для входных данных любого размера, кроме очень малого.

1.5 Асимптотические обозначения.

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

Асимптотические обозначения используются для описания времени работы алгоритмов и фактически применяются к функциям. Они приведены в табл. 1.1.

 

Таблица 1.1 – Асимптотические обозначения

Обозначения Характеристики Комментарии
Оценка верхней и нижней границ. Точная оценка.
Нестрогая оценка сверху.
Строгая оценка сверху. Оценка худшего случая:
Нестрогая оценка снизу.
Строгая оценка снизу. Оценка лучшего случая:

 

Кратко рассмотрим каждую из приведенных в табл. 1.1 асимптотических оценок:

1. -оценка. , где и .

2. -оценка.

 

Говорят, что функция является асимптотически точной оценкой функции .

 

 

 

 

 

 

 

Сравнение функций.

 

График роста O большое

 

Сложности алгоритмов.

Поиск

Сортировка

 

Числа Фибоначчи

Последовательность Фибоначчи определяется следующим образом:



Несколько первых её членов:

Свойства

Правило "сложения":

Теорема Цекендорфа утверждает, что любое натуральное число можно представить единственным образом в виде суммы чисел Фибоначчи:

где , , , (т.е. в записи нельзя использовать два соседних числа Фибоначчи).

По отношению к алгоритму Евклида числа Фибоначчи обладают тем замечательным свойством, что они являются наихудшими входными данными для этого алгоритма (см. "Теорема Ламе" в Алгоритме Евклида).

 

Алгоритм Евклида нахождения НОД (наибольшего общего делителя)

Даны два целых неотрицательных числа и . Требуется найти их наибольший общий делитель, т.е. наибольшее число, которое является делителем одновременно и , и . На английском языке "наибольший общий делитель" пишется "greatest common divisor", и распространённым его обозначением является :

(здесь символом " " обозначена делимость, т.е. " " обозначает " делит ")

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

 

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

Алгоритм

Сам алгоритм чрезвычайно прост и описывается следующей формулой:

 

Реализация

int gcd (int a, int b) {

if (b == 0)

return a;

else

return gcd (b, a % b);

}

Используя тернарный условный оператор C++, алгоритм можно записать ещё короче:

int gcd (int a, int b) { return b ? gcd (b, a % b) : a;}

 

Наконец, приведём и нерекурсивную форму алгоритма:

int gcd (int a, int b) { while (b) { a %= b; swap (a, b); } return a;}

Время работы

Время работы алгоритма оценивается теоремой Ламе, которая устанавливает удивительную связь алгоритма Евклида и последовательности Фибоначчи:

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

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

Учитывая, что числа Фибоначчи растут экспоненциально (как константа в степени ), получаем, что алгоритм Евклида выполняется за операций умножения.

 

Сортировка.

Пузырьковая.

 

 

1.6 Алгоритмы сортировки.

Пузырьковая сортировка. Наименее эффективна, но наиболее проста в реализации. Программный код соответствующего алгоритма приведен в листинге 1.1.

 

Листинг 1.1 – Реализация пузырьковой сортировки

template <class T>

void bubbleSort(vector<T> &v) {

int in, out, tmp;

for(out = v.size()-1; out>0; --out) {

for(in = 0; in<out; ++in) {

if(v[in] > v[out]) {

tmp = v[in];

v[in] = v[out];

v[out] = tmp;

} } } }

 

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

Размером входа рассматриваемого алгоритма есть размер (количество элементов) сортируемого массива .

Из листинга 1.1 видно, что на 1-м проходе внешнего цикла выполниться сравнений, на 2-м проходе – сравнения, и т.д. Таким образом, для сортировки (по возрастанию) элементов массива необходимо выполнить сравнений. Например, для массива из элементов таких сравнений потребуется выполнить 45. Количество перестановок, обусловленных выполнимостью -условий, в худшем случае не будет превышать значения – когда на вход алгоритма подана последовательность элементов, отсортированных в порядке убывания.

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

 

Сортировка методом выбора.

 

Сортировка методом вставки.

 

 

 

 

 

 

 

Решето Эратосфена — алгоритм нахождения всех простых чисел до некоторого целого числа n, который приписывают древнегреческому математику Эратосфену Киренскому[1]. Как и во многих случаях, здесь название алгоритма говорит о принципе его работы, то есть решето подразумевает фильтрацию, в данном случае фильтрацию всех чисел за исключением простых. По мере прохождения списка нужные числа остаются, а ненужные (они называются составными) исключаются.

Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:

  1. Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).
  2. Пусть переменная p изначально равна двум — первому простому числу.
  3. Зачеркнуть в списке числа от 2p до n считая шагами по p (это будут числа кратные p: 2p, 3p, 4p, …).
  4. Найти первое незачеркнутое число в списке, большее чем p, и присвоить значению переменной p это число.
  5. Повторять шаги 3 и 4, пока возможно.

На практике, алгоритм можно улучшить следующим образом. На шаге № 3 числа можно зачеркивать начиная сразу с числа p2, потому что все составные числа меньше него уже будут зачеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда p2 станет больше, чем n.[2] Также, все p большие чем 2 — нечётные числа, и поэтому для них можно считать шагами по 2p, начиная с p2.

 

Псевдокод

Вход: натуральное число n Пусть A — булевый массив, индексируемый числами от 2 до n, изначально заполненный значениями true. для i := 2, 3, 4, ..., пока i2 n: если A[i] = true: для j := i2, i2 + i, i2 + 2i, ..., пока j n: A[j] := false Выход: числа i, для которых A[i] = true - это все простые числа от 2 до n.

 

С/С++

int n;vector<bool> prime (n+1, true);prime[0] = prime[1] = false;for (int i=2; i*i<=n; ++i) // valid for n < 46340^2 = 2147395600 if (prime[i]) for (int j=i*i; j<=n; j+=i) prime[j] = false;

 

Література:

1. Рублев В.С. Основы теории алгоритмов: учеб. пособие / В.С. Рублев. – Ярославль: ЯрГУ, 2005. – 143 с.

2. Гуц А.К. Математическая логика и теория алгоритмов: учеб. пособие / А.К. Гуц. – Омск: Наследие, 2003. – 108 с.

3. Кормен Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн; пер. с англ., под ред. И.В. Красикова. – [3-е изд.]. – М.: Вильямс, 2013. – 1328 с.

4. Лафоре Р. Структуры данных и алгоритмы в Java / Р. Лафоре; пер. с англ. – [2-е изд.]. – СПб.: Питер, 2013. – 704 с.