Практическое занятие №7 (1 час)

Тема: «Алгоритмы. Основы разработки алгоритмов»

 

Цель занятия: изучить стратегию решения задач, алгоритмы, их свойства, стратегию реализации алгоритмов

Форма проведения: индивидуальное задание

Задание:

1. Рассмотреть стратегию решения задач, алгоритмы и поиск решения

2. Дать характеристику свойствам алгоритмов

3. Изучить стратегию реализации алгоритмов

4. Решение задач на составление алгоритмов

5. Выполнить индивидуальное задание

6. Составить отчет

 

МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ

Алгоритм – это конечная последовательность указаний …

- … на языке понятном исполнителю, …

- … задающая процесс решения задач определенного типа …

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

Любой алгоритм существует не сам по себе, а предназначен для определенного исполнителя. Исполнитель - это объект, ко­торый способен обрабатывать данные и исполнять набор опреде­ленных действий. Для каждого исполнителя определена система команд. Система команд исполнителя есть множество ко­манд, которые он может выполнять исполнитель. Алгоритм описывается в командах того исполнителя, который этот алго­ритм будет выполнять. Объекты, над которыми исполнитель может совершать действия, образуют так называемую среду ис­полнителя. Исходные данные и результаты любого алгоритма всегда принадлежат среде того исполнителя, для которого пред­назначен алгоритм. Необходимо осознать, что исполнитель все­гда четко следует командам алгоритма, не «размышляя» над их содержанием. Например, при переходе улицы мы часто пользу­емся простым алгоритмом «посмотри налево, если машины нет, то дойди до середины, посмотри направо и т.д.». Как должен поступить исполнитель в ситуации, если машина слева есть, но она стоит сломанная, ей меняют колесо? Исполнитель обязан стоять и ждать! Теперь сформулируем одно из возможных не­формальных определений алгоритма.

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

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

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

Понятность. Первое свойство напрямую связано с понятием исполнителя. При составлении алгоритма нужно обязательно учи­тывать «правила игры», т.е. систему предписаний (или систему команд), которые понимает исполнитель. Поэтому, прежде чем составлять алгоритм решения задачи, надо узнать, какие действия способен выполнять выбранный нами исполнитель алгоритма. Например, нельзя задавать человеку действия: перемножить 3 шестизначных числа в уме, а компьютеру: пройти 2 квартала прямо. Эти действия окажутся невыполнимы. При составлении алгоритма можно использовать только допустимые действия. Например, чтобы решить уравнение х² -9 х + 8 = 0, ученику 10 класса достаточно дать следующий алгоритм:

1) решить уравнение;

2) сообщить результат.

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

1) вычислить значение выражения 9² - 4 × 8 (дискриминант);

2) извлечь из полученного числа квадратный корень и обозначить результат буквой d;

3) вычислить значения (9 + d)/2 и (9 -d) /2;

4) сообщить результат.

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

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

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

Однозначность. Будучи понятным, алгоритм не должен со­держать предписаний, смысл которых может восприниматься неоднозначно. Этими свойствами часто не обладают предписа­ния и инструкции, которые со­ставляются для людей. Напри­мер, в рецепте приготовления омлета сказано: «Разбить в эту смесь 3 яйца и все хорошо взбить». На бытовом уровне нам понятно, что речь идет о трех куриных яйцах (а каких еще! - скажете вы). Но яйца могут быть и голубиные, и ути­ные, и даже страусиные (все резко отличаются по величине друг от друга). Здесь явно «закралась» неоднозначность. Указания типа: «посолить по вкусу», «насыпать две-три ложки сахарного песку», «получил оценку 4 или 5», «жарить до готовности», «копать от забора до обеда» не могут встречаться в алгорит­мах. Очевидно, что понятные в определенных ситуациях для человека предписания могут поставить в тупик компьютер. Кроме того, в алгоритмах недопустимы такие ситуации, когда после выполнения очередного предписания исполнителю неяс­но, какое из них должно выполняться на следующем шаге.

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

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

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

Массовость. Очень важно, чтобы составленный алгоритм обеспечивал решение не одной частной задачи, а мог выполнять решение широкого класса задач данного типа. Например, необ­ходимо решить конкретное квадратное уравнение х² - Ах + 3 = 0. Но ведь можно составить алгоритм решения лю­бого квадратного уравнения вида ах + bх + с = 0. Действительно, для случая, когда дискриминант D = b² - Аас > 0, корни квад­ратного уравнения можно найти по известным формулам, если же D < 0, то действительных корней не существует. Таким об­разом, этот алгоритм можно использовать для любого квадрат­ного уравнения.

Свойство массовости (универсальности) алгоритма за­ключается в том, что он должен решать любую задачу из некоторого класса задач.

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

Результативность. По определению алгоритма его выполне­ние должно приводить к получению определенных результатов.

Нередко возникают ситуации, когда какие-либо действия невоз­можно выполнить. В математике такие ситуации называют не­определенностью. Например, деление числа на ноль, извлечение квадратного корня из отрицательного числа, да и само понятие бесконечности неопределенно. Если алгоритм задает бесконеч­ную последовательность действий, то в этом случае результат также считается неопределенным. В таких ситуациях необходи­мо указать причину неопределенного результата, и тогда пояс­нения типа «на ноль делить нельзя», «компьютер выполнить такое не в состоянии», «дискриминант меньше нуля, корней нет», «задача решения не имеет» можно считать результатами выполнения алгоритмов.

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

Нa практике наиболее распространены следующие формы записи алгоритмов:

1) словесная;

2) формульно-словесная;

3) операторные схемы;

4) графическая;

5) на псевдокоде;

6) на алгоритмическом языке.

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

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

Например:

Y = 5× x

шаг 1: прочитать x

шаг 2: умножить x на 5

шаг 3: вывести y

Формульно-словесная форма задается с помощью математических формул с пояснением.

Например:

шаг 1: прочитать x

шаг 2: вычислить 5× x - 1

шаг 3: вычислить

шаг 4: умножить 8×

шаг 5: шаг 2 разделить на шаг 4

шаг 6: вывести y

Операторные схемы - алгоритм представляется с помощью операторов:

В - ввод исходных данных

А- арифметические операции

П - вывод

Р - логический оператор

Я - оператор остановки

Операторы имеют номера и индексы в соответствии с порядком их следования. Логический оператор записывается как функция, аргументом которой служит проверяемое условие: Р (x > 0). Операторы выполняются последовательно. Только логический оператор может прервать эту последовательность.

Пример:

№ п\п	Символ оператора	Содержание
1.	В1	Ввод исходных данных
2.	Р2(x > 0)	Проверка логического условия (x > 0)
3.	A3	Вычисление y = x + 1
4.	A4	Вычисление y = x – 1
5.	П5	Печать вычисленного y
6.	Я6	Остановка

В₁Р₂(x > 0) A₃;А₄ П₅Я₆ _- операторная схема

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

Основные блоки:

Вид блока	Назначение блока
	Блок начала алгоритма
	Блок завершения алгоритма
	Блок ввода данных с клавиатуры. Внутри блока указано, в качестве примера, имя вводимой переменной,
	Блок вычислений. Внутри блока указано, в качестве примера, имя вычисляемой переменной.
	Блок вывода данных на экран монитора. Внутри блока указано, в качестве примера, имя выводимой переменной.
	Блок условия (ветвления). Внутри блока указано, в качестве примера, проверяемое условие.
	Блок цикла. Внутри блока указывается количество повторений тела цикла с помощью счётчика циклов. В качестве примера счётчика циклов использована переменная i, которая изменяется от 1 до 10 с шагом 1 (по умолчанию). Таким образом, для данного примера тело цикла повторится 10 раз. (Тело цикла может содержать любые блоки; на рисунке оно не изображено, а обозначено многоточием).
	Обозначения разрыва ветвей для переноса на другой лист. В кружке указывается номер ветви. (В качестве примера указан номер 1).
	Обозначение объединения ветвей

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

Псевдокод представляет собой систему обозначений и правил, предназначенную для единообразной записи алго­ритмов.

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

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

Большинство языков программирования относятся к алго­ритмическим языкам. Запись алгоритма на алгоритмическом языке называют программой.