Информационные модели

 

Система основных понятий

 

1.3. Пример структуры данных — модели предметной области

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

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

Поставленная нами задача является не простой. Процесс приёма в университет  проходит через несколько стадий. Опишем их.

1. Подготовительный этап: предоставление информации о вузе, его факультета для принятия решения молодыми людьми о поступлении на конкретный факультет, на конкретную специальность.
2. Приём документов от абитуриентов, оформление документации.
3. Сдача абитуриентов приёмных экзаменов, обработка результатов экзаменов.
4. Процедура зачисления в университет по результатам экзаменов.

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

На подготовительном этапе от нашей  информационной модели в первую очередь потребуется сведения о плане приёма в университет: на каких факультетах, какие специальности открыты для поступления; сколько человек принимается на каждую специальность. Кроме того, абитуриентов (и их родителей) интересует: какие вступительные экзамены сдаются на каждом факультете, какие — засчитываются по результатам ЕГЭ.

 

 

 

 

 

 

 

 

 

Рис. 7. Иерархия данных об университетах и абитуриентах

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

На третьем этапе приёмная комиссия будет заносить в информационную базу результаты вступительных экзаменов (или ЕГЭ) для каждого поступающего.

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

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

Для каждого уровня дерева создаётся  таблица своего типа. Вот как выглядят таблицы для уровней факультетов  и специальностей (табл. 7 и 8).

 

 

 

Таблица 7. Факультеты

Название факультета	Экзамен 1	Экзамен 2	Экзамен 3
экономический	Математика	география	русский язык
исторический	история Отечества	иностранный язык	сочинение
юридический	русский язык	иностранный язык	обществознание
…	…	…	…

 

Таблица 8.Специальности

Название специальности	Название факультета	План приёма
финансы и кредит	экономический	25
бухгалтерский учёт	экономический	40
история	Исторический	50
политология	Исторический	25
юриспруденция	Юридический	60
социальная работа	Юридический	25
…	…	…

 

Таблицы 7 и 8 представляют собой экземпляры таблиц ФАКУЛЬТЕТЫ и СПЕЦИАЛЬНОСТИ. При описании структуры таблицы  достаточно указать её имя и перечислить  заголовки всех столбцов.

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

 

ФАКУЛЬТЕТЫ

Название факультета

Экзамен 1

Экзамен 2

Экзамен 3

СПЕЦИАЛЬНОСТИ

Название специальности

Название факультета

План приёма

 

идентификатор — номер регистрации. Далее под этим номером он будет  фигурировать во всех документах.

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

Всю таблицу с перечисленными данными  назовём АБИТУРИЕНТЫ.

АБИТУРИЕНТЫ

Регистрационный номер

Фамилия

Имя

Отчество

Дата рождения

Город

Законченное учебное заведение

Название специальности

Производственный стаж

Медаль

Оценка за экзамен 1

Оценка за экзамен 2

Оценка за экзамен 3

Зачисление

У вас может возникнуть вопрос: как в трёх полученных таблицах отражена связь между ними, которая явно отражена на графе рис. 7? Такая связь  между таблицами существует за счет имеющихся в них общих (совпадающих) полей. В таблицах ФАКУЛЬТЕТЫ и СПЕЦИАЛЬНОСТИ есть общее поле «Название факультета». В таблицах СПЕЦИАЛЬНОСТИ и АБИТУРИЕНТЫ общим полем является «Название специальности». Благодаря этому всегда можно понять, на какую специальность поступает данный абитуриент, а через информацию о специальности можно узнать, на какой факультет он поступает. Здесь предполагается, что названия специальностей на разных факультетах не повторяются, как это и принято в вузах.

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

1.4. Алгоритм как  модель деятельности

Что такое алгоритмическая  модель

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

Как вам известно, алгоритм — это понятие и точное предписание конкретному исполнителю совершить конечную последовательность действий, приводящую к поставленной цели. Из определения следует, что поставленная цель достигается через деятельность (последовательность действий) некоторого исполнителя.

Этапы деятельности от определения  цели (постановки задачи) до получения  результата такие:

1. Определение цели;
2. Планирования работы исполнителя;
3. Работа исполнителя;
4. Получение результата.

Где же здесь место алгоритму? Алгоритм — это детальный план работы исполнителя, это описание последовательности элементарных действий, который должен совершить  исполнитель. Но всякий план или описание есть информационная модель.  Следовательно:

 

Такую модель будем называть алгоритмической.

В схематическом виде четыре описанных  этапа представлены на рис. 8.

 

 

 

 

 

Рис. 8. Этапы движения от цели к результату

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

Оказывается гораздо проще построить  алгоритм для программно управляемого автомата (в том числе компьютера), чем для человека. Для автомата СКИ — это строго определённый конечный набор команд, заложенный в него конструкторами. Поэтому алгоритм представляет собой точное описание его работы, и автомат выполняет работу, формально следуя указаниям алгоритма. Для управления автоматом или компьютером нетрудно придумать формализованный язык описания  алгоритмов. Такие языки называются языками программирования, а алгоритм, представленный на языке программирования, называется программой.

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

Пример алгоритмической  модели

Обсудим описанные выше проблемы на конкретном примере.

Первый игрок загадывает целое  число из заданного диапазона  чисел, например от 1 до 100. Второй должен угадать это число за наименьшее количество вопросов.

Запишем алгоритм угадывания числа  методом половинного деления, ориентированный  на исполнителя-человека.

АлгоритмУгадывание числа

Дано :   диапазон чисел от А до В

Надо :   угадать число X, задуманное игроком, используя алгоритм половинного деления

Начало

1. Задать вопрос :X меньше среднего значения между А и В?
2. Если ответ «да», то принять за значение В целую часть среднего значения
3. Если ответ «нет», то принять за значение А ближайшее целое число, большее, чем среднее
4. Если значения А и В равны, то их общее значение и есть искомое число X
5. Если значения А и В не равны, то вернуться к выполнению пункта 1

Конец

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

Алгоритм, составленный для компьютера и переведённый на язык программирования, будет точно исполнен любым компьютером, «понимающим» этот язык. На рис. 9 приведён алгоритм поиска числа методом половинного  деления для исполнителя-компьютера в форме блок-схемы и на учебном алгоритмическом языке, знакомом вам из базового курса информатики. (Примечание.ЦЕЛ обозначает функцию выделения целой части аргумента.)

Напомним основные правила изображения  блок-схем.

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

нет да      да нет

Алг  Половинное деление Цел A, B, X Начало Ввод A, B, X       ПокаA≠B, повторять Нц ЕслиX≤ (A+B) / 2 ТоB: =ЦЕЛ ((A+B) / 2) ИначеA: =ЦЕЛ ((A+B) / 2) +1 Кв       Кц  Вывод   A Конец

 

Рис.9. Алгоритм «Половинное деление»

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

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

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

Не составит большого труда запрограммировать  описанный выше алгоритм на каком-нибудь языке программирования, например на Паскале или Бейсике.

Трассировка алгоритма  — модель работы процессора

Для того чтобы проверить правильность алгоритма, изображённого на рис. 9, совсем не обязательно переводить его  на язык программирования и выполнять  тесты на компьютере. Протестировать алгоритм может и человек — путём трассировки. Выполняя ручную трассировку, человек моделирует работу процессора, исполняя каждую команду алгоритма занося результаты выполнения команд в трассировочную таблицу. Построим трассировочную таблицу для алгоритма «Половинное деление». Выберем интервал угадываемых чисел от 1 до 8.