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

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

 

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

Задание:

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

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

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

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

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

 

Теоретические сведения

Понятие алгоритма не есть в нашей жизни что-то но­вое и необычное. Каждый из нас, не задумываясь, ежедневно использует сотни различных алгоритмов. Например, правила сложения, вычитания, деления, умножения чисел; правила пре­образования алгебраических выражений; грамматические пра­вила правописания слов и предложений, а также различные ин­струкции и правила, рецепты и указания - все это алгоритмы. Для решения любой задачи надо знать, что дано и что следует получить, т.е. у задачи есть исходные данные и искомые резуль­таты. Для получения результатов необходимо знать способ ре­шения задачи, то есть располагать алгоритмом (инструкцией, правилом), в котором указано, какие действия и в каком порядке следует выполнить, чтобы решить задачу. Например, открывая дверь ключом, никто не размышляет над тем, в какой последо­вательности выполнять действия. Однако, чтобы кого-нибудь научить открывать дверь, придется четко указать и сами действия, и по­рядок их выполнения. Алгоритм открытия двери может подразделяться на следующие этапы (действия):

1)достать ключ;

2)вставить ключ в замочную скважину;

3)повернуть ключ 2 раза против часовой стрелки;

4)вынуть ключ.

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

1) достать ключ;

2)повернуть ключ 2 раза против часовой стрелки;

3)вставить ключ в замочную скважину;

4)вынуть ключ.

Этот алгоритм, конечно, тоже можно выполнить. Но дверь вряд ли откроется. А если поменять местами 1 и 3 пункты во вто­ром алгоритме, то он станет вообще невыполнимым.

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

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

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

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

Понятность. Первое свойство напрямую связано с понятием исполнителя. При составлении алгоритма нужно обязательно учи­тывать «правила игры», т.е. систему предписаний (или систему команд), которые понимает исполнитель. Поэтому, прежде чем составлять алгоритм решения задачи, надо узнать, какие действия способен выполнять выбранный нами исполнитель алгоритма. Например, нельзя задавать человеку действия: перемножить 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). Операторы выполняются последовательно. Только логический оператор может прервать эту последовательность.

 

Пример:

y =

№ п\п	Символ оператора	Содержание
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₃;А₄ П₅Я₆ _- операторная схема

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

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

	Начало, конец
	Ввод, вывод
	Выполнение различных операций
	Логический блок (выбор направления в зависимости от условий)
	Ввод-вывод данных, носителем которых служит бумага

 

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

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

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

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

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

 

Задания для самостоятельного выполнения

Вариант 1. Записать алгоритм вычисления значения y, используя словесную форму описания алгоритма.

Y = (2x + 5)(3 )

 

Вариант 2. Записать алгоритм вычисления значения С, используя формульно-словесную форму описания алгоритма.

С = Sinx+ x- 5

 

Вариант 3. Используя формульно-словесную форму описания алгоритма, вычислить:

Y =

 

Вариант 4. Используя словесную форму описания алгоритма, вычислить сумму 10-ти чисел.

 

Вариант 5. Используя словесную форму описания алгоритма, вычислить произведение 5-ти чисел.

 

Вариант 6. Используя формульно-словесную форму описания алгоритма, вычислить:

A = 3x - tg x

 

Задание 7. Используя операторную схему описания алгоритма, вычислить:

D =

 

Вариант 8. Используя словесную форму описания алгоритма, вычислить:

 

Вариант 9. Используя формульно-словесную форму описания алгоритма, вычислить:

Y =

 

Вариант 10. Используя операторную схему описания алгоритма, вычислить:

Y=

 

Вариант 11. Используя операторную форму описания алгоритма, вычислить:

 

Вариант 12. Используя операторную схему описания алгоритма, вычислить:

К = ½x - ln x½

 

Вариант 13. Используя словесную форму описания алгоритма, вычислить:

A = lnx +

 

Вариант 14. Используя операторную схему описания алгоритма, вычислить:

Y =

 

Вариант 15. Используя операторную форму описания алгоритма, вычислить:

C = 3y + lny

 

Вариант 16. Используя словесную форму описания алгоритма, вычислить:

Y = Cosx +

 

Вариант 17. Используя операторную форму описания алгоритма, вычислить:

 

Вариант 18. Используя формульно-словесную форму описания алгоритма, вычислить:

y =½cosx + sinx - tgx½

 

Вариант 19. Используя словесную форму описания алгоритма, вычислить:

K =

 

Вариант 20. Используя операторную форму описания алгоритма, вычислить:

B=