б) Модифицированная реализация алгоритма. boolfind (intX, intA[], intN) //пусть элементы массива, А пронумерованы с 1 //до N.{for (inti=1;i<=N;++i)if (A[i]==X)return true; else if (A[i]>X)return false;return false;}Данная реализация имеет ту же сложность: О (N). Но на практике будет показывать лучшее время.
4. Алгоритм бинарного поиска. Пользуясь тем, что данный массив элементов монотонно неубывает, можно применить алгоритм бинарного поиска. Имеем начальные границы поиска элемента l=1, r=N, где может быть элемент X. На каждой итерации будем сравнивать средний элемент текущего отрезка с элементом X. Если рассматриваемый элемент больше элемента X, то ответ не может находиться правее рассматриваемого элемента, то есть лежать в левой его части, иначе наоборот. Теперь рассмотрим новый получившийся отрезок.
В конечном счете длина нашего отрезка станет равна 1, т. е. одному элементу, который либо будет равен элементу X, либо нет. Не трудно показать, так как длина нашего отрезка на каждой итерации уменьшается вдвое, то сложность данного алгоритма ϴ(logn). 5. Реализация алгоритма бинарного поиска на языке С++ для чисел. bool find (int A[], int X, int N){intl=1,r=N+1; // r = N+1 нужно для удобства, мы будем содержать ответ //в левой части, то есть в l. while (l+1<r){int mid = (l+r)/2;if (A[mid]<=X)l=mid;else r=mid;}return A[l]==X;}Данную реализацию так можно ускорить благодаря замене «сложной» операции деления на два, более простой, а именно побитовому сдвигу вправо на 1 бит.
Данная реализация представлена ниже. bool find (int A[], int X, int N){int l=1,r=N+1; while (l+1<r){int mid = (l+r)>>1;if (A[mid]<=X)l=mid;else r=mid;}return A[l]==X;}Вывод: получили алгоритм, решающий задачу, сложностью ϴ(logn) с некоторой практической оптимизацией. 4.3 Задача одномерного динамического программирования1. Постановка задачи. Посчитать количество чисел длины N, состоящих из 0 и 1, где нет 2-ух и более подряд стоящих единиц. 2.
Переборный алгоритм. Не трудно заметить, так как числа состоят только из 0 и 1, то всего возможно чисел. Соответственно, чтобы сгенерировать все данные числа, потребуется алгоритм сложностью ϴ(). Для того, чтобы проверить получившееся число, нужно будет пройтись по всем его цифрам, т. е. по всей длине числа, что дает алгоритм сложностью O (N). Таким, образом получившейся алгоритм будет иметь сложность О (). Данный алгоритм является NP-полным.
3. Реализация алгоритма на С++. //данная реализация предполагает, что числа получившейся длины будут вмешаться в тип int. intans = 0; //количество чисел, которые ищем. boolcheck (intX)//проверка числа X, содержит ли оно две идущие подряд //цифры 1{int last=0;while (X≠0){if (last==1 && X%2==1)return false;last = X%2;X = X/2;}}Данную проверку также можно оптимизировать с помощью битовых операций, как на примере снизу. bool check (int X){int last=0;while (X≠0){if (last&(X&1))return false;last=X&1; X = X >> 1;}}voidgetall (intN, int I, int cur) //генерациявсехчиселдлины N{if (I>N)//если пришло число длины N{if (check (cur))++ans;return;}getall (N, I+1,cur<<1);getall (N, I+1,(cur<<1)+1);}Вызов в функции main надо осуществлять функции getall (N, 1,0)// где N-длина чисел, I-//текущая позиция, которую генерируем, cur — текущее число, которое уже //сгенерировали длины I-1. Теперь рассмотрим решение данной задачи за полиномиальное время с помощью метода динамического программирования. 4. Решение с помощью метода динамического программирования. Определим подзадачи K[n-1] - количество «правильных» чисел длины n-1, K[n-2] - количество «правильных» чисел длины n-2. «Правильным» в данном контексте будем называть числа, которые не содержат двух (и более) подряд идущих цифр 1. Определим тривиальные подзадачи:
при n=1, ответ 2 {0,1}при n=2, ответ 3 {00,10,01,}Посмотрим: как зависит K[n] от K[n-2], K[n-1]. Возможны следующие случаи: a) Если на позиции n стоит цифра 0, то первые n-1 цифр — любая «правильная» последовательность. Причем не важно, заканчивается ли она 0, или 1. б) Если на позиции n стоит цифра 1, то цифра n-1 должна быть 0, тогда как первые n-2 цифры могут быть любой «правильной» последовательностью. Таким образом, получаем рекуррентное соотношение: K[n] = K[n-1] + K[n-2], для любого n>2. Сложность данного алгоритма: ϴ(N). Вывод: смогли уменьшить вычислительную сложность решения задачи с NP — полной до полиномиальной.
Реализация решения задачи методом динамического программирования. int solve (int K[], int N){K[1]=2;K[2]=3;for (inti=3;i<=N;++i)K[i]=K[i-1]+K[i-2]; return K[N]; }5 Выводы.
Несмотря на то, что современные вычислительные системы имеют большие технические возможности для проведения сложных расчетов, и эти возможности постоянно возрастают благодаря современным технологиям, проблема уменьшения вычислительной сложности алгоритмов не уменьшилась. Это связано с тем, что объемы информации, которые необходимо обрабатывать, также растут значительно быстро. Очень сложно определить, какой из этих двух процессов (совершенствование средств вычислительной техники и рост объемов обрабатываемой информации) более стремителен. Возникает ситуация, когда одну и ту же вычислительную задачу можно решить различными методами, причем каждый метод обладает своей вычислительной сложностью. Естественно, что наиболее оптимальным будет такой метод и такой вычислительный алгоритм, который позволит достичь желаемого результата за меньшее количество шагов и меньшее количество затраченного времени. В работе рассмотрены примеры совершенствования вычислительных алгоритмов за счет использования определенных методов, таких как замена одних математических операций другими, а также с использованием метода бинарного поиска и динамического программирования.
Список использованных источников
1. А. Ахо, Дж.
Ульман, Дж. Хопкрофт — Построение и анализ вычислительных алгоритмов. Издательство «Мир», 1979. -536 с.
2. Вычислительная сложность некоторых задач математической логики тема диссертации и автореферата по ВАК 01.
01.06, кандидат физико-математических наук Дудаков С. М. 3. Крейнделин В. Б., Шлома А. М. Быстрые алгоритмы обработки радиосигналов и ихвычислительная сложность. Учебное пособие. М.: — 2001. — 62 с.
4. Перепелица В. А., Тебуева Ф. Б. Дискретная оптимизация и моделирование в условиях неопределенности данных, Издательство «Академия.
Естествознания", 2007 год. — 151 С.
5. Лавров С. С. Программирование. Математические основы, средства, теория. Издательство БХВ-Петербург. 2001 — 314 С.
6. Б. Шнайер Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. Издательство: Триумф. 2002 — 152 с.
