Тема №1. Основные понятия (2 Часа)

1.1 Основные понятия и определения дисциплины Алгоритмы эу

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

Алгоритм (определение №2) — Точное и понятное предписание исполнителю совершить последовательность действий, направленных на решение задачи.

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

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

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

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

• Понятность для исполнителя — исполнитель должен знать, как выполнять алгоритм;

• Дискретность — алгоритм должен представлять решение задачи как последовательное выполнение простых или ранее определенных действий;

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

• Результативность (конечность) — алгоритм должен приводить к решению задачи за определенное число шагов;

• Скорость — количество шагов для выполнения алгоритмом поставленной передним задачи должно быть минимально.

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

1.2 Понятие об исполнителе алгоритма

Исполнитель алгоритма — это некоторая абстрактная или реальная система, которая способна выполнять действия предписываемые алгоритмом.

Исполнитель характеризуют:

• Среда — место функционирования исполнителя.

• Система команд. Каждый исполнитель может выполнять команды из строго определенного списка команд — системы команд исполнителя. Для каждой команды должны быть заданы условия применимости (при каких состояниях среды возможен вызов команды) и описаны результаты выполнения команды.

• Элементарное действие — действие, выполняемое исполнителем, после вызова команды. Сложные команды (функции) могут состоять из нескольких элементарных действий.

• Отказ — неспособность исполнителя правильно выполнять указанные ему действия.

1.3 Способы записи (отображения) алгоритмов

Словесная — описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.

Пример. Алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел.

Алгоритм:

• задать два числа;

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

• определить большее из чисел;

• заменить большее из чисел разностью большего и меньшего из чисел;

• повторить алгоритм с шага 2.

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

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

• такие описания строго не формализуемы;

• страдают многословностью записей;

• допускают неоднозначность толкования отдельных предписаний.

Графическая — изображение алгоритма графическими символами по ГОСТ 19.701 – 90.

• Графический способ представления алгоритмов является более компактным и наглядным по сравнению со словесным.

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

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

Псевдокод — полуформализованное описание алгоритма на условном алгоритмическом языке, включающем в себя как элементы языка программирования так и фразы естественного языка, общепринятые математические обозначения.

Примером псевдокода может являться школьный алгоритмический язык в русской нотации, описанный в 1991 г. А. Г. Кушниренко учебнике «Основы информатики и вычислительной техники».

Пример записи алгоритма на школьном АЯ

алг Сумма квадратов (арг цел n, рез цел S)

дано | n > 0

надо | S = 1*1 + 2*2 + 3*3 + ... + n*n

нач цел i

  ввод n; S:=0

  нц для i от 1 до n

    S:=S+i*i

  кц

  вывод «S = », S

кон

Программная — запись алгоритма в виде текста на выбранном языке программирования.