Тема: «Алгоритмы. Основы разработки алгоритмов»
Цель занятия: изучить стратегию решения задач, алгоритмы, их свойства, стратегию реализации алгоритмов
Форма проведения: индивидуальное задание
Задание:
1. Рассмотреть стратегию решения задач, алгоритмы и поиск решения
2. Дать характеристику свойствам алгоритмов
3. Изучить стратегию реализации алгоритмов
4. Решение задач на составление алгоритмов
5. Выполнить индивидуальное задание
6. Составить отчет
МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ
Алгоритм – это конечная последовательность указаний …
- … на языке понятном исполнителю, …
- … задающая процесс решения задач определенного типа …
- … и ведущая к получению результата, однозначно определяемого допустимыми исходными данными.
Любой алгоритм существует не сам по себе, а предназначен для определенного исполнителя. Исполнитель - это объект, который способен обрабатывать данные и исполнять набор определенных действий. Для каждого исполнителя определена система команд. Система команд исполнителя есть множество команд, которые он может выполнять исполнитель. Алгоритм описывается в командах того исполнителя, который этот алгоритм будет выполнять. Объекты, над которыми исполнитель может совершать действия, образуют так называемую среду исполнителя. Исходные данные и результаты любого алгоритма всегда принадлежат среде того исполнителя, для которого предназначен алгоритм. Необходимо осознать, что исполнитель всегда четко следует командам алгоритма, не «размышляя» над их содержанием. Например, при переходе улицы мы часто пользуемся простым алгоритмом «посмотри налево, если машины нет, то дойди до середины, посмотри направо и т.д.». Как должен поступить исполнитель в ситуации, если машина слева есть, но она стоит сломанная, ей меняют колесо? Исполнитель обязан стоять и ждать! Теперь сформулируем одно из возможных неформальных определений алгоритма.
Алгоритм - это точная конечная система правил, определяющая содержание и порядок действий исполнителя над некоторыми объектами (исходными и промежуточными данными) для получения искомого результата.
Из сказанного выше видно, что алгоритм не существует сам по себе, а предназначен для исполнения кем-либо с использованием чего-либо. Поэтому при решении задач соединяют эти понятия в алгоритмической модели. Алгоритмическая модель - это совокупность данных, алгоритма и исполнителя. Целью создания алгоритмической модели является получение некоторого результата путем управления исполнителем. Данные подразделяются на входные, промежуточные и выходные. Входные данные алгоритма - это информация, необходимая для получения результата. Выходные данные - это информация, представляющая результат выполнения алгоритма. Промежуточные данные - это информация, которая получается на основании исходной и требуется для получения результата. Например, для алгоритма решения квадратного уравнения входными данными являются коэффициенты уравнения, к промежуточным относится дискриминант, а выходными являются корни уравнения или сообщение об отсутствии решения.
Основные свойства алгоритмов:
Понятность. Первое свойство напрямую связано с понятием исполнителя. При составлении алгоритма нужно обязательно учитывать «правила игры», т.е. систему предписаний (или систему команд), которые понимает исполнитель. Поэтому, прежде чем составлять алгоритм решения задачи, надо узнать, какие действия способен выполнять выбранный нами исполнитель алгоритма. Например, нельзя задавать человеку действия: перемножить 3 шестизначных числа в уме, а компьютеру: пройти 2 квартала прямо. Эти действия окажутся невыполнимы. При составлении алгоритма можно использовать только допустимые действия. Например, чтобы решить уравнение х2 -9 х + 8 = 0, ученику 10 класса достаточно дать следующий алгоритм:
1) решить уравнение;
2) сообщить результат.
А другому исполнителю - ученику пятого класса, который не знает формулу корней квадратного уравнения, - придется написать более развернутый алгоритм:
1) вычислить значение выражения 92 - 4 × 8 (дискриминант);
2) извлечь из полученного числа квадратный корень и обозначить результат буквой d;
3) вычислить значения (9 + d)/2 и (9 -d) /2;
4) сообщить результат.
Ученик третьего класса тоже сможет решить это уравнение, если для него составить еще более развернутый алгоритм, содержащий только знакомые ему арифметические действия. Теперь ясно, что алгоритм пишется для конкретного исполнителя. В данном случае говорят о понятности алгоритма.
Свойство понятности алгоритма заключается в том, что алгоритм не должен содержать команд, смысл которых не понятен исполнителю.
Другими словами, алгоритм должен состоять только из тех команд, которые входят в систему команд исполнителя.
Однозначность. Будучи понятным, алгоритм не должен содержать предписаний, смысл которых может восприниматься неоднозначно. Этими свойствами часто не обладают предписания и инструкции, которые составляются для людей. Например, в рецепте приготовления омлета сказано: «Разбить в эту смесь 3 яйца и все хорошо взбить». На бытовом уровне нам понятно, что речь идет о трех куриных яйцах (а каких еще! - скажете вы). Но яйца могут быть и голубиные, и утиные, и даже страусиные (все резко отличаются по величине друг от друга). Здесь явно «закралась» неоднозначность. Указания типа: «посолить по вкусу», «насыпать две-три ложки сахарного песку», «получил оценку 4 или 5», «жарить до готовности», «копать от забора до обеда» не могут встречаться в алгоритмах. Очевидно, что понятные в определенных ситуациях для человека предписания могут поставить в тупик компьютер. Кроме того, в алгоритмах недопустимы такие ситуации, когда после выполнения очередного предписания исполнителю неясно, какое из них должно выполняться на следующем шаге.
Свойство однозначности алгоритма заключается в том, что алгоритм не должен содержать предписаний, смысл которых может восприниматься неоднозначно, и на каждом шаге выполнения алгоритма должно быть известно, какую команду надо выполнить следующей.
Дискретность. Как мы уже знаем, алгоритм задает полную последовательность действий, которые необходимо выполнить для решения задачи. Выполнить действия следующего предписания, можно лишь выполнив действия предыдущего. В сущности, программирование - это процесс разложения сложной задачи на ряд простых действий.
Свойство дискретности алгоритма заключается в том, что процесс выполнения алгоритма можно разбить на последовательность отдельных элементарных действий, каждое из которых должно быть закончено исполнителем прежде, чем он приступит к исполнению следующего.
Массовость. Очень важно, чтобы составленный алгоритм обеспечивал решение не одной частной задачи, а мог выполнять решение широкого класса задач данного типа. Например, необходимо решить конкретное квадратное уравнение х2 - Ах + 3 = 0. Но ведь можно составить алгоритм решения любого квадратного уравнения вида ах + bх + с = 0. Действительно, для случая, когда дискриминант D = b2 - Аас > 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 | Остановка |
В1Р2(x > 0) A3;А4 П5Я6 _- операторная схема
Графическая форма записи, называемая также схемой алгоритма (или блок-схемой) представляет собой изображение алгоритма в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий.
Основные блоки:
| Вид блока | Назначение блока |
| Блок начала алгоритма |
| Блок завершения алгоритма |
| Блок ввода данных с клавиатуры. Внутри блока указано, в качестве примера, имя вводимой переменной, |
| Блок вычислений. Внутри блока указано, в качестве примера, имя вычисляемой переменной. |
| Блок вывода данных на экран монитора. Внутри блока указано, в качестве примера, имя выводимой переменной. |
| Блок условия (ветвления). Внутри блока указано, в качестве примера, проверяемое условие. |
| Блок цикла. Внутри блока указывается количество повторений тела цикла с помощью счётчика циклов. В качестве примера счётчика циклов использована переменная i, которая изменяется от 1 до 10 с шагом 1 (по умолчанию). Таким образом, для данного примера тело цикла повторится 10 раз. (Тело цикла может содержать любые блоки; на рисунке оно не изображено, а обозначено многоточием). |
| Обозначения разрыва ветвей для переноса на другой лист. В кружке указывается номер ветви. (В качестве примера указан номер 1). |
| Обозначение объединения ветвей |
Графическая запись является более компактной и наглядной по сравнению со словесной. В схеме алгоритма каждому типу действий соответствует геометрическая фигура. Фигуры соединяются линиями переходов, определяющими очередность выполнения действий.
Псевдокод представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов.
Алгоритм, записанный с помощью псевдокода, представляет собой полуформализованное описание на условном алгоритмическом языке, включающее как основные элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и другие.
Алгоритмический язык - язык, используемый для формальной записи алгоритмов.
Большинство языков программирования относятся к алгоритмическим языкам. Запись алгоритма на алгоритмическом языке называют программой.
