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

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

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

1. математическая или информационная формулировки задачи

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

3. построения алгоритма решения поставленной задачи

4. выбор языка программирования и написание текста программы

5. отладка программ

6. выполнение программы с получением требуемого результата

Понятие алгоритма

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

Рассмотрим наиболее важные понятия программирования.

1. Действие - некоторая операция, имеющая конкретную продолжительность и приводящая к конкретному результату.

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

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

4. Если действие можно разложить на составные части, то его называют процессорным (вычислением).

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

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

Алгоритм- строгий и четкий набор правил, определяющий порядок действий приводящих к достижению поставленных целей.

Свойство алгоритма

1. Дискретность - значение новых величин, вычисляются по определённым правилам, из других величин, с уже известными значениями

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

3. Результативность (конечность) - алгоритм решает поставленную задачу за конечное число шагов.

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

 

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

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

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

Например, сложность задачи линейного программирования решаемой симплекс методом определяется функцией сложности f(n)=2ⁿ и является трудно решаемой (экспоненциальная).

Сложность задачи вычисления определителя системы n линейных уравнений, с n неизвестными, характеризуется полиномом третьей (3) степени (f(n)=n³).

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

Существуют несколько способов описания алгоритмов. Рассмотрим два из них: словестное описание алгоритмов и графическое описание алгоритмов.

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

1. Шаг (этап) обработки(вычисление) значений данных- присвоить «=».

2. Проверка логического условия: если условие «истинна» то выполнить действие один, иначе - действие два.

3. Переход (передача управления) к определенному шагу (этапу).

Для примера рассмотрим алгоритм решения квадратного уравнения ax²+bx+c=0 и его словестное описание алгоритма.

Шаг 1. Ввод исходных данных a,b,c (a!=0 b!=0 c!=)
Шаг 2. Вычислить дискриминант.
Шаг 3. Если дискриминант меньше нуля, то сообщить что корней нет и перейти к Шагу 5; Иначе вычислить x1 и х2.
Шаг 4. Вывести результаты х1 и х2.
Шаг 5. Конец алгоритма.

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

Правила изображения схем алгоритмов сведены в единую систему программной документации (ЕСПД). Дата введения последнего стандарта ГОСТ 19.701.90- 1 января 1992 года. Схема данных состоит из следующих элементов (по упомянутому стандарту графическое изображения алгоритма это схема данных, которая отображает путь данных при решении задач и определяет этапы их обработки):

- символы данных (символы могут отображать вид носителя данных)

- символы процесса, которые нужно выполнить над данными

- символов линий, указывающих потоки данных между процессами и носителями данных

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

Рассмотрим эти символы подробнее.

Символы ввода вывод данных:

1 Паралепипед - данные если носитель не определен

2 Ручной ввод с устройства любого типа- прямоугольная трапеция

3 Отображение данных в удобно читаемой форме на некотором устройстве например дисплее

Символы процесса:

1 Отображает функцию обработки данных(прямоугольник

2 Отображает группу операций которые определены в другом месте, например в подпрограмме

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

Символы линий:

1 Отображают поток данных или передачу управления. Линии изображаются горизонтально или вертикально и могут иметь только прямой угол перегиба. Стрелки – указатели направления линий можно не указывать если они направленны сверху вниз или слева направо.

Специальные символы:

1 Используется при определении и продолжении в другом месте(внутри указывается название или номер обрыва)

2 Обозначает вход из внешней среды или выход во внешнюю среду, например начало и конец схемы алгоритма

3 Комментарий: прерывистая линия [

Поделиться:

Воспользуйтесь поиском по сайту: