«1 ЭНЦИКЛОПЕДИЯ УЧИТЕЛЯ ИНФОРМАТИКИ II. Теоретические основы информатики Список статей 1. Измерение информации — алфавитный подход 2. Измерение информации — содержательный подход 3. Информационные процессы 4. Информация ...»

Андреева Е.В., Босова Л.Л., Фалина И.Н. Математические основы информатики. М.:

БИНОМ, Лаборатория Знаний, 2005, 328 с.

Ямпольский В.С. Основы автоматики и электронно-вычислительной техники. М.:

Просвещение, 1991, 223 с.

Токхейм Р. Основы цифровой электроники. М.: Мир, 1988, 392.

И.Г. Семакина, Е.К. Хеннера: Т. 1. М.: Лаборатория Базовых Знаний, 1999.

См., например, эксперименты 3.6.2 в: Еремин Е.А. Популярные лекции об устройстве компьютера. СПб.: BHV-Петербург, 2003, 272 с.

Подробному описанию учебных моделей посвящен сайт http://educomp.org.ru.

Петцольд Ч. Код. М.: Русская Редакция, 2001, 512 с.

Автор цитаты использует термин постоянная память вместо внешняя.

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

Гук М.Ю. Процессоры Intel: от 8086 до Pentium II. СПб.: Питер, 1997, 224 с.

Шагурин И.И., Бердышев Е.М. Процессоры семейства Intel P6. Архитектура, программирование, интерфейс. М.: Горячая линия — Телеком, 2000, 248 с.

Лин В. PDP-11 и VAX-11. Архитектура ЭВМ и программирование на языке ассемблера.

М.: Радио и связь, 1989, 320 с.

Например, в учебнике: Максимов Н.В., Партыка Т.Л., Попов И.И. Архитектура ЭВМ и вычислительных систем. М.: ФОРУМ: ИНФРА-М, 2005, 512 с. — этому описанию отведено около 40 страниц.

Читатели газеты могут обратиться за подробностями к статье Е.А. Еремина От нажатия клавиши до сохранения данных в ОЗУ. Информатика, 2005, № 20–22.

Олифер В.Г., Олифер Н.А. Сетевые операционные системы. СПб.: Питер, 2002, 544 с.

Таненбаум Э. Современные операционные системы. СПб.: Питер, 2004, 1040 с.

Беркс А., Голдстейн Г., Нейман Дж. Предварительное рассмотрение логической конструкции электронного вычислительного устройства // Кибернетический сборник. М.:

Мир, 1964. Вып. 9.

Математический энциклопедический словарь / Гл. ред. Ю.В. Прохоров. М.: Советская Энциклопедия, 1988, 847 с.

Гук М. Аппаратные средства IBM PC. Энциклопедия. СПб.: Питер, 2003, 923.

ЭНЦИКЛОПЕДИЯ УЧИТЕЛЯ ИНФОРМАТИКИ

IV. Информационное моделирование Список статей 1. Графические модели 2. Имитационные модели 3. Математические модели 4. Моделирование процессов оптимального планирования 5. Моделирование глобальных процессов 6. Моделирование физических систем и процессов 7. Моделирование экологических систем и процессов 8. Объектно-информационные модели 9. Системный анализ 10. Статистические модели 11. Табличные модели 12. Формализация и моделирование В школьном курсе информатики традиционно присутствует содержательная линия формализации и моделирования. Понятие модели относится к фундаментальным общенаучным понятиям, а моделирование — это метод познания действительности, используемый различными науками.

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

Компьютерное моделирование включает в себя процесс реализации информационной модели на компьютере и исследование с помощью этой модели объекта моделирования — проведение вычислительного эксперимента. С помощью компьютерного моделирования решаются многие научные и производственные задачи.

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

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

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

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

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

1. Графические модели Разнообразие графических моделей достаточно велико. Рассмотрим некоторые из них.

Графы Наглядным средством отображения состава и структуры систем (см. Системология) являются графы.

Рассмотрим пример. Имеется словесное описание некоторой местности: Наш район состоит из пяти поселков: Дедкино, Бабкино, Репкино, Кошкино и Мышкино.

Автомобильные дороги проложены между: Дедкино и Бабкино, Дедкино и Кошкино, Бабкино и Мышкино, Бабкино и Кошкино, Кошкино и Репкино. По такому описанию довольно трудно представить себе эту местность. Гораздо легче та же информация воспринимается с помощью схемы (см. рисунок). Это не карта местности. Здесь не выдержаны направления по сторонам света, не соблюден масштаб. На этой схеме отражен лишь факт существования пяти поселков и дорожной связи между ними. Такая схема, отображающая элементный состав системы и структуру связей, называется графом.

Составными частями графа являются вершины и ребра. На рисунке вершины изображены кружками — это элементы системы, а ребра изображены линиями — это связи (отношения) между элементами. Глядя на этот граф, легко понять структуру дорожной системы в данной местности.

Построенный граф позволяет, например, ответить на вопрос: через какие поселки надо проехать, чтобы добраться из Репкино в Мышкино? Видно, что есть два возможных пути:

1) Р К Б М и) Р К Д Б М. Можно ли отсюда сделать вывод, что 1-й путь короче 2-го? Нет, нельзя. Данный граф не содержит количественных характеристик. Это не карта, где соблюдается масштаб и есть возможность измерить расстояние.

Граф, приведенный на следующем рисунке, содержит количественные характеристики.

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

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

На рассмотренных схемах каждое ребро обозначает наличие дорожной связи между двумя пунктами. Но дорожная связь действует одинаково в обе стороны: если по дороге можно проехать от Б к М, то по ней же можно проехать и от М к Б (предполагаем, что действует двустороннее движение). Такие графы являются неориентированными, а их связи называют симметричными.

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

Граф совместимости групп крови Этот пример относится к медицине. Известно, что у разных людей кровь отличается по группе. Существуют четыре группы крови. Оказывается, что при переливании крови от одного человека к другому не все группы совместимы. Граф показывает возможные варианты переливания крови. Группы крови — это вершины графа с соответствующими номерами, а стрелки указывают на возможность переливания одной группы крови человеку с другой группой крови. Например, из этого графа видно, что кровь I группы можно переливать любому человеку, а человек с I группой крови воспринимает только кровь своей группы. Видно также, что человеку с IV группой крови можно переливать любую, но его собственную кровь можно переливать только в ту же группу.

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

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

Дерево — граф иерархической структуры Весьма распространенным типом систем являются системы с иерархической структурой.

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

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

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

Деревья не содержат циклов и петель.

Посмотрите на граф, отражающий иерархическую административную структуру нашего государства: Российская Федерация делится на семь административных округов; округа делятся на регионы (области и национальные республики), в состав которых входят города и другие населенные пункты. Такой граф называется деревом.

Дерево административной структуры РФ У дерева существует одна главная вершина, которая называется корнем дерева. Эта вершина изображается вверху; от нее идут ветви дерева. От корня начинается отсчет уровней дерева. Вершины, непосредственно связанные с корнем, образуют первый уровень. От них идут связи к вершинам второго уровня и т.д. Каждая вершина дерева (кроме корня) имеет одну исходную вершину на предыдущем уровне и может иметь множество порожденных вершин на следующем уровне. Такой принцип связи называется один ко многим. Вершины, которые не имеют порожденных, называются листьями (на нашем графе это вершины, обозначающие города).

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

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

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

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

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

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

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

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

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

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

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

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

2. Имитация модели Имитационная модель воспроизводит поведение сложной системы взаимодействующих элементов. Для имитационного моделирования характерно наличие следующих обстоятельств (одновременно всех или некоторых из них):

· объект моделирования — сложная неоднородная система;

· в моделируемой системе присутствуют факторы случайного поведения;

· требуется получить описание процесса, развивающегося во времени;

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

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

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

Детерминированное моделирование Имитационная модель основана на подражании реальному процессу (имитации).

Например, моделируя изменение (динамику) численности микроорганизмов в колонии, можно рассматривать много отдельных объектов и следить за судьбой каждого из них, и т.д. Эти условия обычно задаются в вербальной форме. Например: по истечении некоторого промежутка времени микроорганизм делится на две части, а по прошествии другого (большего) временноRго отрезка — погибает. Выполнение описанных условий алгоритмически реализуется в модели.

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

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

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

Такой компьютерный эксперимент фактически претендует на воспроизведение натурного эксперимента. На вопрос: Зачем это нужно делать? можно дать следующий ответ:

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

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

Модели случайных процессов Кому не случалось стоять в очереди и с нетерпением прикидывать, успеет ли он сделать покупку (или заплатить за квартиру, покататься на карусели и т.д.) за некоторое имеющееся в его распоряжении время? Или, пытаясь позвонить по телефону в справочную и натыкаясь несколько раз на короткие гудки, нервничать и оценивать — дозвонюсь или нет? Из таких простых проблем в начале XX века родилась новая отрасль математики — теория массового обслуживания, использующая аппарат теории вероятностей и математической статистики, дифференциальных уравнений и численных методов. Впоследствии выяснилось, что эта теория имеет многочисленные выходы в экономику, военное дело, организацию производства, биологию и экологию и т.д.

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

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

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

· ремонтная зона в автохозяйстве и автобусы, сошедшие с линии из-за поломки;

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

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

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

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

Целью моделирования систем такого вида является получение ответа на ряд вопросов.

Относительно простой вопрос — какое в среднем время придется стоять в очереди при заданных законах распределения указанных выше случайных величин? Более сложный вопрос: каково распределение времен ожидания обслуживания в очереди? Не менее сложный вопрос: при каких соотношениях параметров входных распределений наступит кризис, при котором очередь до вновь вошедшего покупателя не дойдет никогда? Если задуматься над этой относительно простой задачей, возможные вопросы будут множиться.

Способ моделирования выглядит в общих чертах так. Используемые математические формулы — законы распределения исходных случайных величин; используемые числовые константы — эмпирические параметры, входящие в эти формулы. Не решается никаких уравнений, которые использовались бы при аналитическом исследовании данной задачи. Вместо этого происходит имитация очереди, разыгрываемая с помощью компьютерных программ, генерирующих случайные числа с заданными законами распределения. Затем производится статистическая обработка совокупности полученных значений величин, определяемых заданными целями моделирования. Например, находится оптимальное количество продавцов для разных периодов времени работы магазина, которое обеспечит отсутствие очередей. Математический аппарат, который здесь используется, называется методами математической статистики.

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

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

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

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

Для любой внутренней клетки поля с координатами (i, j) можно определить 8 соседей.

Если клетка живая, ее закрашиваем, если клетка мертвая, она пустая.

Зададим правила игры. Если клетка (i, j) живая и ее окружает более трех живых клеток, она погибает (от перенаселения). Живая клетка также погибает, если в ее окружении находится менее двух живых клеток (от одиночества). Мертвая клетка оживает, если вокруг нее появляются три живые клетки.

Для удобства введем двумерный массив A[0..n, 0..n], элементы которого принимают значение 0, если соответствующая клетка пустая, и 1, если клетка живая. Тогда алгоритм определения состояния клетки с координатой (i, j) можно определить следующим образом:

S := А[I - 1, J - 1] + А[I – 1, J] + + А[I + 1, J] + А[I + 1, J + 1] + + А[I, J + 1] + А[I, J - 1];

If (А[I, J] = 1) And ((S > 3) Or