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

Лекция №10.

 

Алгоритм – описание последовательности действий (план), строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов.

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

· дискретность (алгоритм должен состоять из конкретных действий, следующих в определенном порядке);

· детерминированность (понятность и точность) (любое действие должно быть строго и недвусмысленно определено в каждом случае и исполнитель должен понимать, как выполнять каждое действие);

· конечность (каждое действие и алгоритм в целом должны иметь возможность завершения);

· массовость (один и тот же алгоритм можно использовать с разными исходными данными);

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

Виды алгоритмов:

· линейный алгоритм (описание действий, которые выполняются однократно в заданном порядке);

· циклический алгоритм (описание действий, которые должны повторятся указанное число раз или пока не выполнено заданное условие);

· разветвляющийся алгоритм (алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий);

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

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

· в устной форме;

· в письменной форме (на естественном или формальном языке);

· в графической форме в виде блок-схемы, которая составляется из стандартных графических объектов.

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

Объект, который будет выполнять алгоритм, обычно называют исполнителем. Компьютер - автоматический исполнитель алгоритмов. Алгоритм, записанный на «понятном» компьютеру языке программирования, называется программой. Каждый исполнитель характеризуется средой («местом обитания») и системой команд. Среда (или обстановка) — это "место обитания", множество объектов, которые окружают исполнителя. Совокупность всех команд, которые исполнитель может выполнить, называется системой команд исполнителя. За каждой командой из системы команд исполнителя закреплено конкретное элементарное действие. Отказы исполнителя возникают при вызове команды в недопустимом для данной команды состоянии среды. Другими словами – это случай, когда попытка выполнить команду приводит к аварии.

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

Описание последовательности действий только тогда является алгоритмом, когда у разных исполнителей, точно выполняющих все предписания, всегда получается один и тот же результат. Это возможно только тогда, когда исполнитель не изменяет порядок действий, не дополняет систему команд исполнителя (СКИ) и не «улучшает» отдельные действия, не интересуется целью, не отступает от описания, не может дать отказ «не хочу». Такой исполнитель называется формальным. Заметим, что все алгоритмы создаются именно для формальных исполнителей. В отличие от формального, неформальный исполнитель всегда интересуется, зачем он выполняет то или иное действие, стремится выполнить его лучше, эффективнее (с его точки зрения).

Технические устройства (в том числе и компьютер как совокупность аппаратного и программного обеспечения) могут быть только формальными исполнителями, в этом случае результат их действий предсказуем. Человек-пользователь не объясняет исполнителю-компьютеру свои цели и смысл команд программы. Очевидно, что компьютер и не сможет понять смысла совершаемых им действий. Более того, компьютер не обладает способностью к анализу результатов, например, относительно их соответствия постановке задачи.

Работа ни одного устройства компьютера не обходится без программы и исходных данных к ней. Не только устройства компьютера, но и каждое программное средство можно рассматривать в качестве формального исполнителя, который характеризуется своей системой команд, средой, системой отказов. В любой программе пользовательский интерфейс можно рассматривать как среду исполнителя; сообщения об ошибочных действиях пользователя или о сбоях в работе программы или устройств компьютера как систему отказов; команды управления программой (параметры команд, система меню, «горячие клавиши» и т.д.) как систему команд исполнителя.

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

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

 

Компьютерные модели

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

Примеры моделей:

· Теоретические модели (теории, законы; гипотезы и пр.) – отражают строение, свойства и поведение реальных объектов.

· Художественное творчество, фактически процесс создания моделей (басня – модель человеческих отношений, скульптуры, картины и пр.)

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

Моделирование – это метод познания, состоящий в создании и исследовании моделей.

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

Формы представления моделей:

· предметные (материальные);

· информационные.

Информационные модели делятся на:

· словесные (загадки, описание свойств объекта);

· образы (рисунки, плакаты, фото, видео);

· графические (карта, чертеж, схема, график, граф);

· знаковые (программы на языке программирования, математические, физические, химические формулы);

· табличные («объект-свойство», «объект-объект», матрицы).

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

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

Компьютерные модели используются людьми различных отраслей народного хозяйства:

· метеорологи;

· дизайнеры (модельеры, архитекторы, web-дизайнеры и т.д.);

· инженеры-конструкторы;

· нейрохирурги;

· геологи и т.д.

 

Графические информационные модели.

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

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

Схема – это графическое отображение состава и структуры сложной системы.

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

График – модель процесса (например, график изменения температуры в течение некоторого периода времени).

 

Табличные модели

Таблицы типа «объект – свойство» – самая распространенная форма информационной модели – прямоугольная таблица. При составлении таблицы используется только необходимая информация для пользователя. Таблица может отражать процесс, происходящий во времени. В одной строке такой таблицы содержится информация об одном объекте (книга или состояние погоды на 12.00 в данный день). Столбцы – отдельные характеристики (свойства) объектов.

 

Автор	Название	Год издания	Жанр
А. Беляев	Человек-амфибия	1990 г.	Фантастика
А. Пушкин	Сказка о царе Салтане	1985 г.	Поэтическая сказка
Л. Толстой	Война и мир	1972 г.	Трагедия

 

День	Осадки	Температура (С)	Давление (мм рт.ст.)	Влажность (%)
15.03	Снег	-5	746	67
16.03	Дождь	0	743	100
17.03	Без осадков	+2	745	62
18.03	Туман	0	746	87
19.03	Без осадков	-2	760	67

 

Таблицы типа «объект – объект». Например, таблица успеваемости. В ней строки относятся к ученикам – это первый вид объектов; столбцы – к школьным предметам – это второй тип объектов. В каждой клетке оценка ученика по данному предмету.

 

Ученик	Алгебра	Геометрия	Физика	История	Информатика	Музыка
Алексеев А.	4	4	3	4	5	5
Петров М.	5	5	4	4	4	4
Зимина С.	4	5	3	3	3	3
Луговая Р.	3	3	4	5	4	4
Кучин Д.	3	4	4	5	5	5

 

Следующая таблица так же относится к типу «объект – объект», но в ней строки и столбцы относятся к одному виду объектов. В этой таблице информация о наличии дорог между населенными пунктами с карты.

 

	Дачи	Озерная	Еловая	Подгорная	Бобры
Дачи	1	1	1	1	0
Озерная	1	1	0	1	0
Еловая	1	0	1	0	1
Подгорная	1	1	0	1	1
Бобры	0	0	1	1	1

 

Матрицы

В математике прямоугольная таблица, составленная из чисел, называется матрицей. Если матрица содержит только нули и единицы, то она называется двоичной матрицей. Числовая часть таблицы «Дороги» двоичная матрица.

 

Интерактивные моделипо экономике позволяют проводить полноценные экономические эксперименты:

· исследовать рынок;

· вести биржевую игру;

· демонстрировать продвижения товара на рынке;

· изучать факторы, влияющие на цену товаров и др.

 

 

Модели в Астрономии

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

 

 

Модели по химии

Интерактивные компьютерные модели демонстрируют основные химические законы и интересные химические явления. Интерактивная таблица Менделеева позволяет подробно ознакомиться со свойствами химических элементов.

 

Основные этапы разработки и исследования моделей на компьютере

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

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

3. Компьютерная модель. Создание проекта модели на одном из языков программирования Построение компьютерной модели.

4. Компьютерный эксперимент. Ввести исходные данные и получить результат.

5. Анализ полученных результатов и корректировка исследуемой модели. В случае несоответствия полученных результатов измеряемым параметрам реальных объектов, можно сделать вывод, что на предыдущих этапах были допущены ошибки или неточности.

 

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

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

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

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

- создание компьютерной модели в форме проекта на одном из языков программирования;

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

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

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

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

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

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

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

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

 

 

Вопросы.

1. Что такое алгоритм? Назовите свойства алгоритма.

2. Перечислите виды алгоритмов и поясните их.

3. Какие вы знаете способы описания (формы представления) алгоритма?

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

5. В чем состоит программный принцип работы компьютера?

6. Какие существуют формы представления и виды моделей?

7. Приведите примеры информационных моделей.

8. Какие преимущества табличных и графических моделей перед словесными можно привести.

9. Назначение компьютерных моделей.

10. Перечислите основные этапы разработки и исследования моделей на компьютере.