Типы алгоритмов. Способы реализации методы построения

на:
естественном языке
на языке программирования
с помощью математической или другой символической нотации
Название алгоритма может, и должно указывать на его назначение или определять используемый в нем метод решения

НГТУ, кафедра АСУ, Лауферман О.В.

вносящие неопределенность, для них невозможна произвольность в выборе решений, определяющих последовательность действий

НГТУ, кафедра АСУ, Лауферман О.В.

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

НГТУ, кафедра АСУ, Лауферман О.В.

поставленную задачу, а для моделирования сложных систем с использованием ЭВМ

НГТУ, кафедра АСУ, Лауферман О.В.

в них используется метод проб и ошибок

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

НГТУ, кафедра АСУ, Лауферман О.В.

кафедра АСУ, Лауферман О.В.

недетерминированных алгоритмов

НГТУ, кафедра АСУ, Лауферман О.В.

наиболее правдоподобные варианты, называются эвристическими

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

НГТУ, кафедра АСУ, Лауферман О.В.

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

НГТУ, кафедра АСУ, Лауферман О.В.

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

НГТУ, кафедра АСУ, Лауферман О.В.

виде: n !=1, для n =0; n ! = n*(n-1)! , для n > 0

int fact_rec (int n)
{
if( n == 0) return 1;
else
return ( n* fact_rec ( n – 1));
}

int fact_iter (int n)
{
int f = 1, k = n;
while ( k > 0 )
{
f = f * k; k --;
}
return f;
}

НГТУ, кафедра АСУ, Лауферман О.В.

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

НГТУ, кафедра АСУ, Лауферман О.В.

Евклида:

void Delitel ( int a, int b)
{
if ( b == 0)
{ printf (“ НОД = %d”, a);
return;
}
else
Delitel ( b, a % b);
}

void Evklid ( int a, int b)
{
int c;
while ( b > 0)
{
c = a % b;
a = b;
b = c;
}
printf (“ НОД = %d”, a);
}

НГТУ, кафедра АСУ, Лауферман О.В.

1 = F n + F n – 1, для n > 0 и F 0 = 0, F 1 = 1

int Fib_rec ( int n )
{
if ( n == 0) return 0;
if ( n == 1) return 1;
return ( Fib_rec( n - 1) +
Fib_rec( n - 2) ;
}

int Fib ( int n )
{
int i = 1, x = 1, y = 0;
while ( i < n )
{
x = x + y;
y = x – y;
i ++;
}
return x;
}

НГТУ, кафедра АСУ, Лауферман О.В.

очевидное итерационное решение поставленной задачи

НГТУ, кафедра АСУ, Лауферман О.В.

объединяют их с  «рекурсивными структурами данных» и  «рекурсивными определениями»

НГТУ, кафедра АСУ, Лауферман О.В.

f ( x ) ) { f ( x ) – выражение, зависящее от x};
программа b ( аргумент y, …)
| a ( g ( y ) ) { g ( y ) – выражение, зависящее от y};

НГТУ, кафедра АСУ, Лауферман О.В.

конечными

Одна из функций должна иметь следующий общий вид:
Если С то
А прямое { действие или выражение, выполняемое непосредственно}
Иначе
В рекурсивное { часть, включающая при необходимости рекурсивные вызовы}
Или
Пока ~ С повторять
В рекурсивное
А прямое

НГТУ, кафедра АСУ, Лауферман О.В.

подпрограммы могло быть завершено

Это есть целое неотрицательное число, относительно которого можно сказать, что оно строго убывает при каждом рекурсивном вызове функции:
Программа Р ( аргументы: n целое; х, у, z, …)
Если n = 0 , то
А прямое ( n, x, y, z, …) {без рекурсивного вызова}
Иначе
В рекурсивное { где все рекурсивные вызовы имеют вид
Р ( n – 1, f(x), g(y), h(z), …) }

НГТУ, кафедра АСУ, Лауферман О.В.

этапа:

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

НГТУ, кафедра АСУ, Лауферман О.В.

== 0) return 1; // тривиальный случай

else
return ( n* fact_rec ( n – 1)); // общий случай
}

НГТУ, кафедра АСУ, Лауферман О.В.

a, int b) // параметризация задачи
{

if ( b == 0)
{ printf (“ НОД = %d”, a);
return; } // тривиальный случай

else
Delitel ( b, a % b); // общий случай
}

НГТУ, кафедра АСУ, Лауферман О.В.

задачи
{

if ( n == 0) return 0;
if ( n == 1) return 1; // тривиальный случай

return ( Fib_rec( n - 1) +
Fib_rec( n - 2) ; // общий случай
}

НГТУ, кафедра АСУ, Лауферман О.В.

кодирования
улучшает читаемость программы
сокращает объем программного кода

НГТУ, кафедра АСУ, Лауферман О.В.

доступа ко всем элементам
для обработки неупорядоченного набора данных
для выполнения операций на различных ветвях программы и проверки множества различных вариантов решений недетерминированной задачи
Все эти операции выполняются одновременно с  доступом ко всем элементам

 

 

 

 

НГТУ, кафедра АСУ, Лауферман О.В.

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

НГТУ, кафедра АСУ, Лауферман О.В.

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

НГТУ, кафедра АСУ, Лауферман О.В.

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

НГТУ, кафедра АСУ, Лауферман О.В.

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

НГТУ, кафедра АСУ, Лауферман О.В.

для его уточнения, можно использовать данный подход

НГТУ, кафедра АСУ, Лауферман О.В.

n = 0

Если требуется найти квадратный корень s из числа n, то процедура поиска задается следующим образом:
S k = n / 2, для k = 0, n ≠ 0
S k = ½ ( s k-1 + n/ s k-1) для k > 0
Вычисление заканчивается при том значении индекса k, когда значения s k-1 и s k приблизительно равны между собой

НГТУ, кафедра АСУ, Лауферман О.В.

делится на равные части, и на каждой из этих частей вычисляется приближение с помощью значения
f (x k)*Δx,
где xk – некоторое значение x в пределах k-ой части, а  Δx – размер каждой из частей отрезка.
Затем производится дальнейшее разбиение частей на более мелкие отрезки и вычисляется следующее приближение. Когда два приближения достаточно близки друг к другу, то решение найдено

НГТУ, кафедра АСУ, Лауферман О.В.

одной монеты с дефектом, которая весит меньше остальных

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

НГТУ, кафедра АСУ, Лауферман О.В.

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

НГТУ, кафедра АСУ, Лауферман О.В.

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

НГТУ, кафедра АСУ, Лауферман О.В.

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

НГТУ, кафедра АСУ, Лауферман О.В.

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

НГТУ, кафедра АСУ, Лауферман О.В.

к  последовательности более простых задач. С  помощью этих подзадач исходную задачу можно решить по частям или её упростить и решить

НГТУ, кафедра АСУ, Лауферман О.В.

служить примером применения метода выделения подцелей, если, например, процесс решения имеет следующий вид.
Подцели: разделить задачу на части; решить каждую часть.
Цель: объединить все частичные решения вместе, чтобы получить решение всей задачи

НГТУ, кафедра АСУ, Лауферман О.В.

две подцели.
Подцели: найти приближенное решение; уточнить его.
Вторая из этих подцелей повторяется до тех пор, пока не будет получено достаточно точное приближение

НГТУ, кафедра АСУ, Лауферман О.В.