ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.03.2021
Просмотров: 6598
Скачиваний: 50
71
скобок.
Например, вычисление известного из школьного курса математики выражения
b
2
-
4*а*с
включает предварительное установление порядка выполнения операций:
14 2 3
b
2
–
4
*a*c
Для этого выражение просматривают несколько раз. Выполнение каждой операции дает
некоторое число, которое приходится записывать отдельно от выражения, запоминая тот фрагмент
выражения, для которого число является значением.
Сейчас рассмотрим экономный алгоритм вычисления значения выражения, использующий
два магазина для перестановки элементов выражения (с учетом старшинства операций) и для хра-
нения промежуточных результатов. Магазины обозначим
M
1
и
М
2
,
в
M
1
будут попадать знаки опе-
раций, в
М
2
-
числа, участвующие в записи выражения, значения переменных и все промежуточ-
ные числовые значения.
Ограничимся выражениями, состоящими только из чисел и переменных без индекса, свя-
занных знаками операций, *, /, +, -. Знак «минус» будет знаком лишь двухместной операции вычи-
тания, выражения типа « -
а +
I» исключаются из рассмотрения. От этих ограничений можно было
бы и отказаться, но это удлинило бы изложение. Пока предположим также, что в выражении нет
скобок.
Опишем алгоритм вычисления. Исходное выражение читается слева направо; если прочи-
тано число, то оно заносится в
M
2
,
если переменная - в
М
2
заносится ее значение; если же прочи-
тан знак операции, то необходимо различать несколько случаев.
1)
М
1
пуст; прочитанный знак помещается на вершину
М
1
.
2) прочитанный знак помещается на вершину
M
1
,
если он обозначает операцию, которая
старше и поэтому должна выполняться до операции, знак которой был расположен на вершине
М
1
.
3) если операции равноправны или если та, знак которой только что прочитан в выражении,
должна выполняться позднее, необходимо применить операцию, знак которой расположен на
вершине
M
1
,
к двум верхним числам из
М
2
(число на вершине - второй операнд, число под ним -
первый); знак операции на вершине
M
1
удаляется из
M
1
,
вместо двух верхних чисел в
M
2
помеща-
ется результат выполнения над ними операции.
В некоторый момент в исходном выражении не остается символов. Если пуст и
M
1
,
то вы-
числение окончено, результат находится в
M
2
;
в противном случае знаки операции извлекаются по
очереди из
M
1
и соответствующие операции применяются к числам из
M
2
.
Рассмотрим вычисление выражения
b
2
- 4
*а*с
; значения переменных
а, b, с
обозначим А,
В,
С.
Знак возведения в степень обозначим, как часто делается, стрелкой вверх.
72
Про знак операции говорят, что он имеет более высокий приоритет в сравнении с другим
знаком, если обозначаемая им операция старше. В других случаях говорят о равных приоритетах
или более низком приоритете. Рассмотренные знаки операций распадаются на группы равных по
приоритету:
Группы упорядочены по убыванию приоритета.
Теперь дадим правило работы со скобками. Левая скобка заносится в
M
1
сразу после про-
чтения. Прочтение правой скобки влечет выполнение всех операций, знаки которых находятся в
Mi
выше левой скобки; после выполнения этих операций обе скобки уничтожаются. Вот что будет
происходить при выполнении
(а + b) * с
:
Иерархическая организация данных
Во всех рассмотренных выше структурах отдельные элементы (компоненты, поля, состав-
ляющие) структуры были формально равноправны. Существует, однако, широкий круг задач, в
которых одни данные естественным образом «подвязаны» к другим. В этом случае возникает со-
подчиненная (иерархическая) структура данных. Ограничимся конкретным примером. Представим
себе генеалогическое дерево, корень которого - имя человека, на следующем уровне - имена его
родителей, еще на следующем - имена родителей родителей и т.д. Такая структура называется
двоичным деревом,
рис. 1.36.
73
Рис. 1.36. Структура типа «двоичное дерево»;
пара ближайших по горизонтали кружков -мужское и женское имя
Как структурировать эти данные (имена)? Для помещения их в текстовый массив и запись
трудно придумать логически оправданный порядок следования. Самое разумное - создать динами-
ческую структуру типа той, что изображена на рис. 1.36. современные языки программирования
позволяют это делать и обрабатывать такие структуры с высокой эффективностью.
Контрольные вопросы и задания
1. Какое значение имеет выбор представления и организации данных при разработке про-
граммы?
2. Какие данные можно отнести к простейшим неструктурированным?
3. Какие данные называют структурированными?
4. Охарактеризуйте свойства данных целого, действительного типа.
5. Какими свойствами обладают литерные и строковые величины?
6. Что называют логическими данными?
7. Что такое массив?
8. Решение каких задач требует использования массивов?
9. Разберите алгоритм сортировки массива, приведенный в тексте. Предложите свой алго-
ритм, отличный от данного.
10. Как определяется тип «множество»?
11. Чем отличается комбинированный тип данных (запись) от массива?
12. Что такое очередь (файл)? Какое применение имеют файлы?
13. Что такое стек?
14. Разберите по аналогии с примером, имеющимся в тексте о стеке, вычисление других
арифметических выражений с использованием стеков.
15. Придумайте примеры естественной иерархической организации данных.
§ 10. ПОНЯТИЕ ОБ ИНФОРМАЦИОННОМ МОДЕЛИРОВАНИИ
10.1. МОДЕЛИРОВАНИЕ КАК МЕТОД РЕШЕНИЯ ПРИКЛАДНЫХ ЗАДАЧ
С точки зрения информатики, решение любой производственной или научной задачи опи-
сывается следующей технологической цепочкой: «реальный объект -модель - алгоритм - програм-
ма - результаты - реальный объект». В этой цепочке очень важную роль играет звено «модель»,
как необходимый, обязательный этап решения этой задачи. Под моделью при этом понимается не-
который мысленный образ реального объекта (системы), отражающий существенные свойства
объекта и заменяющий его в процессе решения задачи.
Модель
- очень широкое понятие, включающее в себя множество способов представления
изучаемой реальности. Различают модели материальные (натурные) и идеальные (абстрактные).
Материальные модели основываются на чем-то объективном, существующем независимо от чело-
веческого сознания (каких-либо телах или процессах). Материальные модели делят на физические
(например авто- и авиамодели) и аналоговые, основанные на процессах, аналогичных в каком-то
отношении изучаемому (например, процессы в электрических цепях оказываются аналогичными
многим механическим, химическим, биологическим и даже социальным процессам и могут быть
использованы для их моделирования). Границу между физическими и аналоговыми моделями
74
провести можно весьма приблизительно и такая классификация моделей носит условный характер.
Еще более сложную картину представляют идеальные модели, неразрывным образом свя-
занные с человеческим мышлением, воображением, восприятием. Среди идеальных моделей мож-
но выделить интуитивные модели, к которым относятся, например, произведения искусства - жи-
вопись, скульптура, литература, театр и т.д., но единого подхода к классификации остальных ви-
дов идеальных моделей нет. Иногда эти модели все разом относят к информационным. В основе
такого подхода лежит расширительное толкование понятия «информация»: «информацией являет-
ся почти все на свете, а может быть, даже вообще все». Такой подход является не вполне оправ-
данным, так как он переносит информационную природу познания на суть используемых в про-
цессе моделей - при этом любая модель является информационной. Более продуктивным пред-
ставляется такой подход к классификации идеальных моделей, при котором различают следую-
щие.
1. Вербальные
(текстовые) модели. Эти модели используют последовательности предло-
жений на формализованных диалектах естественного языка для описания той или иной области
действительности (примерами такого рода моделей являются милицейский протокол, правила до-
рожного движения, настоящий учебник).
2. Математические
модели - очень широкий класс знаковых моделей (основанных на фор-
мальных языках над конечными алфавитами), широко использующих те или иные математические
методы. Например, можно рассмотреть математическую модель звезды. Эта модель будет пред-
ставлять собой сложную систему уравнений, описывающих физические процессы, происходящие
в недрах звезды. Математической моделью другого рода являются, например, математические со-
отношения, позволяющие рассчитать оптимальный (наилучший с экономической точки зрения)
план работы какого-либо предприятия.
3. Информационные
модели - класс знаковых моделей, описывающих информационные
процессы (возникновение, передачу, преобразование и использование информации) в системах
самой разнообразной природы.
Граница между вербальными, математическими и информационными моделями может
быть проведена весьма условно; возможно, информационные модели следовало бы считать под-
классом математических моделей. Однако, в рамках информатики как самостоятельной науки, от-
дельной от математики, физики, лингвистики и других наук, выделение класса информационных
моделей является целесообразным. Информатика имеет самое непосредственное отношение и к
математическим моделям, поскольку они являются основой применения компьютера при решении
задач различной природы: математическая модель исследуемого процесса или явления на опреде-
ленной стадии исследования преобразуется в компьютерную (вычислительную) модель, которая
затем превращается в алгоритм и компьютерную программу, рис. 1.37.
Рис. 1.37.
Обобщенная схема компьютерного математического моделирования
10.2. ОСНОВНЫЕ ПОНЯТИЯ ИНФОРМАЦИОННОГО МОДЕЛИРОВАНИЯ
Остановимся на информационных моделях, отражающих процессы возникновения, переда-
чи, преобразования и использования информации в системах различной природы. Начнем с опре-
деления простейших понятий информационного моделирования.
Экземпляром
будем называть представление предмета реального мира с помощью некото-
рого набора его характеристик, существенных для решения данной информационной задачи (слу-
жащей контекстом построения информационной модели). Множество экземпляров, имеющих од-
ни и те же характеристики и подчиняющиеся одним и тем же правилам, называется объектом.
75
Рис. 1.38.
Пример абстрагирования при построении информационной модели
Таким образом, объект есть абстракция предметов реального мира, объединяемых общими
характеристиками и поведением, рис. 1.38.
Информационная модель какой-либо реальной системы состоит из объектов. Каждый объ-
ект в модели должен быть обеспечен уникальным и значимым
именем
(а также идентификатором,
служащим ключом для указания этого объекта, связи его с другими объектами модели). Таким об-
разом обозначение, наименование объекта -это элементарная процедура, лежащая в основе ин-
формационного моделирования.
Объект представляет собой один типичный (но неопределенный) экземпляр чего-то в ре-
альном мире и является простейшей информационной моделью. Объекты представляют некие
«сущности» предметов реального мира, связанные с решаемой задачей.
Большинство объектов, с которыми приходится встречаться, относятся к одной из следую-
щих категорий:
реальные объекты;
роли;
события;
взаимодействия;
спецификации.
Реальный объект -
это абстракция физически существующих предметов. Например, на ав-
томобильном заводе это кузов автомобиля, двигатель, коробка передач; при перевозке грузов это
контейнер, средство перевозки.
Роль
- абстракция цели или назначения человека, части оборудования или учреждения (ор-
ганизации). Например, в университете как в учебном заведении это студент, преподаватель, декан;
в университете как в учреждении это приемная комиссия, отдел кадров, бухгалтерия, деканат.
Событие
- абстракция чего-то случившегося. Например, поступление заявления от абиту-
риента в приемную комиссию Университета, сдача (или несдача) экзамена.
Взаимодействия
- объекты, получаемые из отношений между другими объектами. Напри-
мер, сделка, контракт (договор) между двумя сторонами, свидетельство об образовании, выдавае-
мое учебным заведением его выпускнику.
Объекты-спецификации
используются для представления правил, стандартов или крите-
риев качества. Например, перечень знаний, умений и навыков выпускника математического фа-
культета, рецепт проявления фотопленки.
Для каждого объекта должно существовать его
описание
- короткое информационное ут-
верждение, позволяющее установить, является некоторый предмет экземпляром объекта или нет.
Например, описание объекта «Абитуриент университета» может быть следующим: человек в воз-
расте до 35 лет, имеющий среднее образование, подавший в приемную комиссию документы и за-
явление о приеме.
Предметы реального мира имеют
характеристики
(такие, например, как имя, название, ре-
гистрационный номер, дата изготовления, вес и т.д.). Каждая отдельная характеристика, общая для
всех возможных экземпляров объекта, называется атрибутом. Для каждого экземпляра атрибут
принимает определенное значение. Так, объект
Книга
имеет атрибуты
Автор
,
Название,
Год из-
дания. Число страниц.
У каждого объекта должен быть
идентификатор
- множество из одного или более атрибу-
тов, значения которых определяют каждый экземпляр объекта. Для книги атрибуты Автор и На-
звание совместно образуют идентификатор. В тоже время Год издания и Число страниц иденти-
фикаторами быть не могут - ни врозь, ни совместно, так как не определяют объект. Объект может