Тема. алгоритмизация вычислительного процесса

Урок №13: Алгоритмизация вычислительного процесса. Этапы решения задач на ЭВМ. Алгоритмы, их свойства

 

Вам известно, что ЭВМ были созданы для вычислений. А с другой стороны ЭВМ используются для изучения явлений природы, для управления технологическими процессами, для рисования рисунков, мультфильмов, т.е. для решения задач с математикой не всегда связанных. Как же это удается? О том, что нужно сделать, чтобы применять ЭВМ, для решения не математических задач и пойдет речь.

С чего начать?

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

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

Таким образом вы давно знакомы с математической моделью, хотя ранее и не встречались с этим термином.

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

Как вы видите из всех свойств объекта (стола) мы выделили три:

1. форму поверхности (прямоугольную)

2. длины сторон.

Другие свойства этой задачи нам не важны (цвет, материал, цена) если бы мы решали другую задачу возможно бы мы решали другую задачу возможно бы для нас была важна и эта информация.

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

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

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

В данной задачи исходные данные это длины сторон (а и в) результат площадь (S)

S= а*в

Если поверхность стола не прямоугольная то нам понадобятся другие данные и соотношения.

Итак для создания математической модели нужно:

3. Определить, что считать исходными данными и что считать результатами.

4. Записать математические соотношения (формулы, уравнения, неравенства и т. д.), связывающие результаты с исходными данными.

Созданием математической модели завершается первый этап решения задач с помощью ЭВМ.

Для того чтобы ЭВМ произвела необходимые вычисления и получила ответ нужно составить для нее четкую инструкцию строго указать необходимую последовательность действий.

Такая инструкция называется алгоритмом решения задачи.

Каждый из нас ежедневно использует различные алгоритмы, инструкции, правила, рецепты и т. п. Мы это делаем не задумываясь:

Например: открыть дверь ключом никто не думает как это сделать, но научить это делать сестру придется четко указать и сами действия и порядок их выполнения.

Например:

1. Достать ключ

2. Вставить в замочную скважину

3. Повернуть 2 раз против часовой стрелки

4. Вынуть ключ

А теперь представьте себе, что вы идете в гости наверняка вы попросите подробно объяснить как добраться

5. Выйти из дома

6. Дойти до остановки

7. Сесть в автобус № 25 идущий к центру города

8. Проехать 3 остановки

9. Выйти из автобуса

Посмотрим на эти алгоритмы на первый взгляд между ними нет ничего общего. Но одно дело открыть дверь, другое ехать в гости. Однако, если приглядеться внимательно, можно заметить существенное сходство между ними, прежде всего это строгий порядок выполнения действий. Давайте переставим порядок действий в первом алгоритме 2 и 3. Вы конечно сможете выполнить данный алгоритм, но дверь вряд ли откроется.

Во втором алгоритме если поменять местами 3 и 4 действие он станет невыполнимым.

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

В этом заключается одно из общих свойств всех алгоритмов.

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

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

Теперь мы можем сказать, что:

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

Скажем сразу абсолютно строго определенного понятия алгоритма мы не дадим. Понятие алгоритма в информатике является фундаментальным. Таким же как понятие точки, прямой и плоскости в геометрии. Для ЭВМ так же как и для математики алгоритм является фундаментальным.

Остановимся подробнее на принципиальных аспектах алгоритмизации в связи с ЭВМ.

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

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

Наиболее важные принципы алгоритмизации:

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

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

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

2. Определенность. В соответствии с этим принципом требуется строгое определение каждого промежуточного шага к достижению решения. Если речь идет о решении задачи на ЭВМ то:

- Составлению алгоритма второй этап решения задачи с помощью ЭВМ.

- ЭВМ может выполнять алгоритмы без участия человека, автоматически.

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

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

Проводя вычисления на ЭВМ необходимо проанализировать результаты, после их анализа может потребоваться уточнение модели. Так будет продолжаться до тех пор пока анализ результатов не покажет полное соответствие изображенному объекту.

Итак третий этап решения задачи: написание программы, получение и анализ результатов работы ЭВМ.

Схема решения задачи с помощью ЭВМ:

Математическая модель. Алгоритм. Программа анализ результатов.