Реферат. Вопрос №5 Понятие и свойства алгоритмов
Работа Лапшина А.С.

Определение алгоритма
Свойства алгоритма
Структура алгоритма
Вопросы

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

   Алгоритмы могут описывать процессы преобразования самых разных объектов. Широкое распространение получили вычислительные алгоритмы, которые описывают преобразование числовых данных.

Алгоритм может быть записан словами и изображён схематически. Обычно сначала (на уровне идеи) алгоритм описывается словами, но по мере приближения к реализации он обретает всё более формальные очертания и формулировку на языке, понятном исполнителю (например, машинный код). Для схематического описания алгоритма применяются блок-схемы.

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

   Программа- это алгоритм, записанный на языке программирования.

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

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

Основные свойства алгоритмов следующие:

1. Понятность для исполнителя — исполнитель алгоритма должен понимать, как его выполнять. Имея алгоритм и произвольный вариант исходных данных, исполнитель должен знать, как надо действовать для выполнения этого алгоритма.
2. Дискретность(прерывность, раздельность) — алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов (этапов).
3. Определенность — каждое правило алгоритма должно быть четким, однозначным. Благодаря этому свойству выполнение алгоритма носит механический хаpактеp и не требует никаких дополнительных указаний или сведений о решаемой задаче.
4. Результативность (или конечность) состоит в том, что за конечное число шагов алгоритм либо должен приводить к решению задачи, либо после конечного числа шагов останавливаться из-за невозможности получить решение с выдачей соответствующего сообщения, либо неограниченно продолжаться в течение времени, отведенного для исполнения алгоритма, с выдачей промежуточных результатов.
5. Массовость означает, что алгоритм решения задачи pазpабатывается в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.

   По структуре алгоритмы бывают: линейные, с ветвлением, циклические Алгоритм линейной структуры (линейный алгоритм) – алгоритм, в котором блоки выполняются последовательно друг за другом. Такой порядок выполнения блоков называется естественным.

   Псевдокоды- это интерпретация шагов алгоритма на обычном языке, которая описывает действие команды. Пример линейного алгоритма Рис.1

    Входные данные: R - радиус основания цилиндра, h - высота цилиндра, р- плотность материала слитка. Выходные данные: m - масса слитка, V - объем, S - площадь основания

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

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

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

  Пусть, например, В - проверяемое условие, а s1, s2 - некоторые выполняемые инструкции (действия). Тогда:
Если условие В выполняется (истинно), то
выбрать для исполнения s1,
иначе
выбрать для исполнения s2
Рис.2

Пример алгоритма в псевдокодах: . Вычислить значение Y по одной из формул:

Алгоритм Ветв1;
    Переменные х,у:вещественные;
Начало
    Ввод(х);
    Если х<0 тогда y:=x+2
    иначе y:=x-2;
    Вывод(у);
Конец.

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

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

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

1. Инструкция "цикл с параметром" (цикл с заданным количеством повторений).
   Обозначим:
   x - параметр цикла (является счетчиком количества повторений);
   a, b - соответственно начальные и конечные значения параметра цикла;
   h - шаг, с которым изменяется параметр цикла;
   S - Оператор (инструкция), повторяемый в цикле;
   Общий вид структуры цикла с параметром будет:
   
   
   
2. Инструкция "цикл с предусловием" (цикл-"пока"):
   Обозначим:
   В - некоторое проверяемое логическое условие;
   S - Оператор (инструкция), повторяемый в цикле;
   


3. Инструкция "цикл с постусловием" (цикл-"до"):
   

Вопросы:

1. Составьте и опишите словесно алгоритм "Окраска забора",определите его тип:
2. Опишите алгоритм вычисления квадратного корня с помощью блок-схемы, определите тип
3. Что такое форма представления алгоритма и какие формы вы знаете?

Ответы
Тестовые вопросы с ответами