Контрольные вопросы

1. Каково понятие модели?

2. Перечислите основные различия между моделями?

3. Назовите необходимое условие моделирования.

4. Дайте классификацию моделей по способу построения.

5. Что такое информационная модель?

6. Объясните, что понимают под адекватностью?

7. Что такое физическое моделирование?

8. В чем особенность математического моделирования?

9. Что представляет собой модель при имитационном моделировании?

10. Перечислите основные математические модели.

11. Какие требования предъявляются к ММ?

12. Что понимают под компьютерным моделированием?

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

Понятие алгоритма

Для описания метода решения любой задачи необходимо:

- указать величины, являющиеся исходными;

- разбить процесс решения задачи на этапы, которые известны исполнителю и которые он может выполнить однозначно без пояснений;

-указать порядок выполнения этапов;

- указать признак окончания процесса решения задачи;

- указать, что является результатом решения задачи.

Такое описание метода решения задачи называется алгоритмом. Алгоритм – это центральное понятие информатики. Итак, алгоритм – это метод (способ) решения задачи, записанный по определенным правилам, обеспечивающим однозначность его понимания и механического исполнения при любых значениях исходных данных из некоторого допустимого множества значений.

Свойства алгоритма

Из определения алгоритма вытекают его основные свойства.

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

2. Определенность (детерминированность) алгоритма. Каждая команда алгоритма должна быть понятна и однозначна для исполнителя.

3. Результативность (выполнимость) алгоритма. Он должен всегда приводить к получению результата через конечное число шагов или сигнализировать о невозможности получения решения при имеющихся исходных данных.

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

Способы описания алгоритмов

1. Словесно-формульное описание (с помощью слов и формул).

2. Графическое (с помощью специальных геометрических схем – блок-схем).

3. Способ, использующий псевдокоды.

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

4. Запись алгоритма на одном из языков программирования.

Наибольшей наглядностью обладает описание алгоритма в виде блок-схем.

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

- блок пуск-останов. Определяет начало-конец

процесса вычисления;

- блок ввода-вывода информации;

- блок вычислений;

- блок проверки выполнения условия (логический блок);

- начало-конец цикла (модификация);

- вычисление по подпрограмме, стандартной программе;

- печать результатов на бумаге;

- линии потока, изображают последовательность связей

между блоками;

- соединители, указывают связи между прерванными линиями потока, связывающими блоки;

--- - пояснения, содержание подпрограмм, формулы.

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

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

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

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

Пример

Составить блок-схему вычисления выражения

.

Необходимо наряду со значением y вывести значения числителя и знаменателя. На рис. 6 приведена блок-схема вычисления требуемых значений данного выражения.

Рис. 6. Схема линейного алгоритма

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

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

да нет или x > y x < y

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

Пример

Составить блок-схему вычисления переменной

На рис. 7 приведена блок-схема вычисления значений y. Ветвление происходит по двум взаимоисключающим ветвям.

Рис. 7. Схема разветвляющегося алгоритма

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

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

Рассмотрим алгоритм вычисления суммы n слагаемых a₁, a_2,…a_n по формуле

Для получения значения S необходимо многократно (n раз) выполнить операцию сложения. При каждом выполнении операции сложения к предыдущему результату добавляется значение последующего слагаемого, т.е. многократно выполняется участок алгоритма (рис. 8) вида

Инструкцией S= S + a_i можно осуществить постепенное последовательное накопление суммы, если предварительно выполнено действие S=0.

Рис.4.1

Рис. 8. Схема циклического алгоритма

Для того чтобы при каждом очередном выполнении инструкции S=S+a_i слагаемое a_i было новым, в цикле наряду с этой инструкцией должна выполняться инструкция перехода к следующему слагаемому i=i+1; до цикла должно быть выполнено действие i=1.

Инструкции цикла не должны выполняться бесконечно: последним слагаемым должно быть слагаемое a_n. Поэтому в контур цикла включается блок проверки текущего значения i. Если это значение еще не превышает п, то вновь выполняются инструкции и i = i+1 . Когда значение i превысит n, их выполнение должно прекратиться. Поэтому указанный блок в общем случае называется блоком проверки условия и изображается с двумя выходами (рис. 8, блок 6): линия потока, изображающая один из выходов, входит в контур цикла, другая, соответствующая случаю i  n, означает завершение цикла и передачу управления на блок вывода результатов.

Аналогично накапливается и произведение с той лишь разницей, что для его накопления используется инструкция S=S  a_i, а начальное значение произведения должно быть равно единице. Переменная, значение которой изменяется в цикле в заданных пределах и определяет момент окончания цикла, называется параметром цикла (в рассматриваемом примере i – параметр цикла).

Таким образом, для циклов с известным числом повторений задаются:

• начальное и конечное значения параметра цикла;

• закон изменения параметра цикла при каждом его повторении;

• количество необходимых повторений цикла или условие окончания

цикла.

Для циклов с известным числом повторений в блок-схемах можно использовать блок вида

В

Рис. 9. Схема алгоритма

с использованием блока цикла

нутри этого блока записываются границы изменения m₁ и m₂ параметра цикла i и шаг. Это позволяет сделать блок-схему более компактной. Одна из линий потока входит в контур цикла, другая линия потока, соответствующая окончанию цикла, связывает данный блок с тем блоком, который должен выполняться по окончании цикла. Например, блок-схема на рис. 8 с использованием данного блока будет иметь вид, приведенный на рис. 9. Если параметр цикла с каждым шагом увеличивается на единицу, то шаг в блоке цикла, как правило, не указывается.

Выводы

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

1. Дискретность – решение разбивается на ряд этапов в порядке их выполнения.

2. Определенность – каждый этап не должен оставлять возможности его неоднозначного толкования и неопределенного исполнения.

3. Результативность – работа ЭВМ должна завершиться либо получением решения задачи, либо сообщением, что такого решения нет.

4. Массовость – каждый алгоритм должен быть применим для решения ряда задач этого типа при всех допустимых значениях исходных данных.

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

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