Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

Поняття алгоритму. Види алгоритмів, способи їх подання



 

Первое определение

Алгоритм - описание набора операций и правил их выполнения, с помощью которого исходные данные могут быть преобразованы в искомый результат (В.П.).

 

Второе определение

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

 

Правильные и неправильные алгоритмы

Алгоритм называют правильным, если для любого допустимого входа он:

а) не зацикливается;

б) дает правильный результат при любых допустимых входах.

Неправильные алгоритмы не рассматриваются.

 

Надежные и ненадежные алгоритмы

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

Доводом в пользу использования алгоритмов с отказами является их более высокая эффективность.

 

Точные и приближенные алгоритмы

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

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

 

Вход и выход алгоритма. Размер входа

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

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

Примеры выбора размера входа для разных задач:

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

2) для задач кодирования информации в качестве размера входа используют число битов или байтов, необходимое для представления входных данных;

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

4) для задач на графах в качестве размера входа используют число вершин или число ребер графа;

 

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

Состояние алгоритма.

Алгоритм называется детерминированным, если для любого данного состояния существует не больше одного следующего состояния.

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

 

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

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

Ниже приведен пример описания алгоритма сортировки массива методом вставки на метаязыке.

 

Insertion-Sort(A)

1 for j 2 to length[A]

2 do key A[j]

3 i j-1

4 while i>0 and A[j]>key

5 do A[i+1] A[i]

6 i i-1

7 A[i+1] key

 

Отметим некоторые правила записи алгоритмов на псевдокоде.

1. Отступ от левого поля указывает на уровень вложенности.

2. Циклы while, for, repeat и условные конструкции if, then, else имеют тот же смысл, что и в Паскале.

3. Операция присваивания обозначается символом "". Например, операция "переменной a присвоить значение переменной b" запишется так: a b . Можно записывать цепочку операций присваивания вида: a b c .

4. Переменные, объявленные внутри процедуры локальны внутри нее (если не оговорено противное).

5. Индекс массива пишется в квадратных скобках: A[i] . Запись A[1 .. j] обозначает участок массива.

Полный набор правил записи алгоритмов на псевдокоде см. в [ ].

 

Описание этого же алгоритма в виде функции С++ имеет такой вид:

 

void Insertion_Sort(int* A, int n)

{ int i, j, key;

for (j=1; j<n; j++)

{ key=A[j];

i=j-1;

while (i>=0 && A[i]>key) { A[i+1]=A[i]; i--; }

A[i+1]=key;

}

}

Обратим внимание на то, что в программах на С/С++ нумерация элементов массивов принята с нуля, в то время как в общематематической нотации элементы массивов нумеруются с 1.

 

 




Поиск по сайту:

©2015-2020 studopedya.ru Все права принадлежат авторам размещенных материалов.