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

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

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

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

В основе информационного моделирования лежат три постулата:

все состоит из элементов;

элементы имеют свойства;

элементы связаны между собой отношениями.

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

Стадии построения информационной модели.

Ф Объект познания И

О Познающие субъекты Н

Р Личностное представление Т

М Сформировавшаяся мысль Е

А «Живое» слово Р

Л Записанное слово П

И Научный текст Р

З Формальные конструкции Е

Классификации информационных моделей:

-по способу описания:

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

Графические (блок-схемы, диаграммы, графики и т.д.).

-по цели создания:

Классификационное (древовидные, генеалогическое дерево, дерево каталогов в компьютере);

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

- по природе моделируемого объекта:

Детерминированные (определенные), для которых известны законы, по которым изменяется или развивается объект;

Вероятностные (обработка статистической неопределенности и некоторых видов нечеткой информации).

Историческое происхождение и методологическое значение понятий модели и аналогии.

Слово «модель» произошло от латинского слова «modulus», означает «мера», «образец». Его первоначальное значение было связано со строительным искусством, и почти во всех европейских языках оно употреблялось для обозначения образа или прообраза, или вещи, сходной в каком-то отношении с другой вещью.

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

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

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

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

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

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

Методологическая основа моделирования .

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

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

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

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

Компьютерная модель.

Компьютерная модель – модель, реализованная средствами программной среды.

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

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

компьютерное моделирование (КМ) является перспективным методом активизации учебного процесса. Оно приобретает все большее и большее значение в современном научном познании, и, кроме того, в настоящее время становится популярным дидактическим средством. Рассмотрим это направление подробнее.

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

Математические модели.

Математическое моделирование позволяет при помощи математических символов и зависимостей составить описание происходящего процесса.

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

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

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

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

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

В качестве математических объектов выступают числа, переменные, множества, векторы, матрицы и т.п.

Классификация математических моделей на основе особенностей применяемого математического аппарата .

>>Информатика: Графические информационные модели

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

Основные темы параграфа:

♦ карта как информационная модель;
♦ чертежи и схемы;
♦ график - модель процесса.

Карта как информационная модель

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

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

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

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

На рисунке 2.5 приведена схема.

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

Структура – это определенный порядок объединения элементов системы в единое целое.

Структуру московского метрополитена называют радикально-кольцевой.

График - модель процесса

Для отображения различных процессов часто прибегают к построению графиков. На рис. 2.6 изображен график изменения температуры в течение некоторого периода.

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

Коротко о главном

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

Вопросы и задания

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

И. Семакин, Л. Залогова, С. Русаков, Л. Шестакова, Информатика, 9 класс
Отослано читателями из интернет-сайтов

Основы информатики, подборка рефератов к урокам информатики , скачать рефераты, уроки информатики 9 класс онлайн, домашняя работа

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

Если у вас есть исправления или предложения к данному уроку,

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

Основная цель моделирования

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

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

Системный анализ

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

Вариант представления

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

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

Применение моделирования

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

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

О классификации моделей

Для того чтобы работать с создаваемыми моделями было удобно, существует условное подразделение их на блоки:

• по сферам применения;
• отрасли знаний;
• временному фактору;
• виду представления.

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

Примеры образной информационной модели

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

Не только на уроках географии педагог предлагает своим воспитанникам многочисленные схемы и карты. Такой предмет, как история, также тесно связан с рисунками, графиками, разнообразными таблицами. Если учитель истории скажет своему воспитаннику: «Приведите примеры графических информационных моделей, касающихся Сталинградской битвы», ребенку достаточно открыть атлас на нужной странице. С помощью стрелок и цветового акцента на карте отражены все основные моменты, касающиеся этого легендарного события. Помимо учебных заведений, варианты образной информационной модели встречаются и научных учреждениях, специализирующихся на разделении объектов по их внешним признакам.

Подразделение моделей по времени

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

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

Вербальные информационные модели

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

Знаковые модели

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

Математические формы

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

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

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

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

Заключение

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

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

Урок 4
§1.3 Графические информационные модели

Ключевые слова:

Схема
карта
чертёж
график
диаграмма
граф
сеть
дерево

1.3.1. Многообразие графических информационных моделей

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

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

Рис. 1.5. Примеры схем, используемых на уроках физики, биологии, истории

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

Чертёж - условное графическое изображение предмета с точным соотношением его размеров, получаемое методом проецирования . Чертёж содержит изображения, размерные числа, текст. Изображения дают представления о геометрической форме объекта, числа - о величине объекта и его частей, надписи - о названии, масштабе, в котором выполнены изображения.

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

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

1.3.2. Графы

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

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

Граф называется взвешенным , если его вершины или рёбра характеризуются некоторой дополнительной информацией - весами вершин или рёбер. На рис. 1.6, в с помощью взвешенного неориентированного графа изображены дороги между пятью населёнными пунктами А, В, С, D, Е; веса рёбер - протяжённость дорог в километрах.

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

Рис. 1.6. Графы

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

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

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

Всякая иерархическая система может быть представлена с помощью дерева . У дерева выделяется одна главная вершина, называемая его корнем. Каждая вершина дерева (кроме корня) имеет только одного предка, обозначенный предком объект входит в один класс1* высшего уровня. Любая вершина дерева может порождать несколько потомков - вершин, соответствующих классам нижнего уровня. Такой принцип связи называется «один-ко-многим». Вершины, не имеющие порождённых вершин, называются листьями.

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

Ресурс «Живая Родословная» (145555) - инструмент для формирования и анализа генеалогических деревьев, содержащий примеры родословных. С его помощью вы можете изучить генеалогические деревья многих известных семей и построить генеалогическое дерево своей семьи (http://sc.edu.ru/) .

Класс - множество объектов, обладающих общими признаками .

1.3.3. Использование графов при решении задач

Графы удобно использовать при решении некоторых классов задач .

Пример 1 . На рисунке 1.7 изображена схема дорог, связывающих торговые точки А, В, С, D, Е. По каждой дороге можно двигаться только в направлении, указанном стрелкой. Сколько существует различных путей от точки А до точки Е?

Рис. 1.7. Схема дорог, представленная ориентированным графом

В вершину Е можно попасть только из вершин С и D. Если мы будем знать число путей из вершины А в вершину С и из вершины А в вершину D, то, сложив их, получим искомое число путей из А в Е. Действительно, для того чтобы попасть из вершины А в вершину Е, мы просто все пути из вершины А в вершину С дополним дугой СЕ, а пути из вершины А в вершину D дополним дугой DE. Число путей при этом не изменится. Итак, число путей из вершины А в вершину Е равно сумме путей из А в С и из А в П.

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

В вершину С можно попасть непосредственно из вершины А и из вершины В. В свою очередь, существует единственный путь из вершины А в вершину В. Таким образом, из вершины А в вершину С можно попасть двумя путями: 1 (напрямую из А) + 1 (через В) = 2.

Попробуйте доказать, что путь из вершины А в вершину В - единственный.

Что касается вершины D, она является конечной вершиной для трёх дуг: BD, AD и CD. Следовательно, в неё можно попасть из вершин А, В и С:

Итак, существуют четыре пути из вершины А в вершину D.

Теперь выполним подсчёт путей из А в Е:

2 (через С) + 4 (через D) = 6.

Решение задачи будет гораздо проще, если двигаться от вершины А (начало маршрута) к вершине Е и проставлять веса вершин - число путей из А в текущую вершину (рис. 1.8). При этом вес вершины А можно принять за 1. Действительно, существует единственный способ попасть из А в А - оставаться на месте.

Рис. 1.8. Схема дорог, представленная взвешенным ориентированным графом

Пример 2. Для того чтобы записать все трёхзначные числа, состоящие из цифр 1 и 2, можно воспользоваться графом (деревом) на рис. 1.9.

Дерево можно не строить, если не требуется выписывать все возможные варианты, а нужно просто указать их количество. В этом случае рассуждать нужно так: в разряде сотен может быть любая из цифр 1 и 2, в разряде десятков - те же два варианта, в разряде единиц - те же два варианта. Следовательно, число различных вариантов: 2 2 2 = 8.

Рис. 1.9. Дерево для решения задачи о записи трёхзначных чисел

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

Пример 3 . Рассмотрим несколько видоизменённую классическую задачу о переправе.

На берегу реки стоит крестьянин (К) с лодкой, а рядом с ним - собака (С), лиса (Л) и гусь (Г). Крестьянин должен переправиться сам и перевезти собаку, лису и гуся на другой берег. Однако в лодку кроме крестьянина помещается либо только собака, либо только лиса, либо только гусь. Оставлять же собаку с лисой или лису с гусём без присмотра крестьянина нельзя - собака представляет опасность для лисы, а лиса - для гуся. Как крестьянин должен организовать переправу?

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

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

На графе видно, что существуют два решения этой задачи. Приведём соответствующий одному из них план переправы:

1) крестьянин перевозит лису;
2) крестьянин возвращается;
3) крестьянин перевозит собаку;
4) крестьянин возвращается с лисой;
5) крестьянин перевозит гуся;
6) крестьянин возвращается;
7) крестьянин перевозит лису.

Пример 4. Рассмотрим следующую игру: сначала в кучке лежат 5 спичек; два игрока убирают спички по очереди, причём за 1 ход можно убрать 1 или 2 спички; выигрывает тот, кто оставит в кучке 1 спичку. Выясним, кто выигрывает при правильной игре - первый (I) или второй (II) игрок.

Игрок I может убрать одну спичку (в этом случае их останется 4) или сразу 2 (в этом случае их останется 3).

Если игрок I оставил 4 спички, игрок II может своим ходом оставить 3 или 2 спички. Если же после хода первого игро- . ка останутся 3 спички, второй игрок может выиграть, взяв две спички и оставив одну.

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

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

На рис. 1.11 представлен граф, называемый деревом игры; на нём отражены все возможные варианты, в том числе ошибочные (проигрышные) ходы игроков.

Рис. 1.11. Дерево игры

САМОЕ ГЛАВНОЕ

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

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

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

Вопросы и задания

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

2. Какие информационные модели относят к графическим?

3. Приведите примеры графических информационных моделей, с которыми вы имеете дело:

а) при изучении других предметов;
б) в повседневной жизни.

4. Что такое граф? Что является вершинами и рёбрами графа на рис. 1.6, в? Приведите примеры цепей и циклов, имеющихся в этом графе. Определите, какие два пункта наиболее удалены друг от друга (два пункта считаются самыми удалёнными, если длина кратчайшего пути между ними больше, чем длина кратчайшего пути между любыми другими двумя пунктами). Укажите длину кратчайшего пути между этими пунктами.

5. Приведите пример системы, модель которой можно представить в форме графа. Изобразите соответствующий граф.

6. Грунтовая дорога проходит последовательно через населённые пункты А, В, С и D. При этом длина грунтовой дороги между А и В равна 40 км, между В и С - 25 км, и между С и D - 10 км. Между А и D дороги нет. Между А и С построили новое асфальтовое шоссе длиной 30 км. Оцените минимально возможное время движения велосипедиста из пункта А в пункт В, если его скорость по грунтовой дороге - 20 км/ч, по шоссе - 30 км/ч.

7. На рисунке изображена схема дорог, связывающих торговые точки А, Б, В, Г, Д, Б, К. По каждой дороге можно двигаться только в направлении, указанном стрелкой. Сколько существует различных путей от точки А до точки К?

8. Работая в группе, составьте семантическую сеть по одной из русских народных сказок: «Колобок», «Курочка Ряба», «Репка».

9. Что такое дерево? Моделями каких систем могут служить деревья? Приведите пример такой системы.

10. Сколько трёхзначных чисел можно записать с помощью цифр 2, 4, 6 и 8 при условии, что в записи числа не должно быть одинаковых цифр?

11. Сколько существует трёхзначных чисел, все цифры которых различны?

12. Для составления цепочек используются бусины, помеченные буквами А, В, С, D, Е. На первом месте в цепочке стоит одна из бусин А, С, Е. На втором - любая гласная, если первая буква гласная, и любая согласная, если первая согласная. На третьем месте - одна из бусин С, D, Е, не стоящая в цепочке на первом месте. Сколько цепочек можно создать по этому правилу?

13. Два игрока играют в следующую игру. Перед ними лежит куча из 6 камней. Игроки берут камни по очереди. За один ход можно взять 1, 2 или 3 камня. Проигрывает тот, кто забирает последний камень. Кто выигрывает при безошибочной игре обоих игроков - игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

Презентация:

2. Какие информационные модели относят к графическим?

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

3. Приведите примеры графических информационных моделей, с которыми вы имеете дело:
а) при изучении других предметов;
б) в повседневной жизни.

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

4. Что такое граф? Что является вершинами и рёбрами графа на рис. 1.6? Приведите примеры цепей и циклов, имеющихся в этом графе. Определите, какие два пункта наиболее удалены друг от друга (два пункта считаются самыми удалёнными, если длина кратчайшего пути между ними больше, чем длина кратчайшего пути между любыми другими двумя пунктами). Укажите длину кратчайшего пути между этими пунктами.

Граф - это объект изображенный с помощью вершин, а связи между ними - линиями (ребрами).
На данном рисунке вершины - города A, B, C, D, E; рёбра - дороги(линии) между ними.
Города B и D - наиболее удалены друг от друга. Длина кратчайшего пути между ними составляет 170.

5. Приведите пример системы, модель которой можно представить в форме графа. Изобразите соответствующий граф.

Пример графа: Персональный компьютер

6. Грунтовая дорога проходит последовательно через населённые пункты А, В, С и D. При этом длина грунтовой дороги между А и В равна 40 км, между В и С - 25 км, и между С и D - 10 км. Между А и D дороги нет. Между A и С построили новое асфальтовое шоссе длиной 30 км. Оцените минимально возможное время движения велосипедиста из пункта А в пункт В, если его скорость по грунтовой дороге - 20 км/ч, по шоссе - 30 км/ч.

На графе черная линия - асфальтированное шоссе, а серая линия - грунтовая дорога.
По условию скорость велосипедиста по грунтовой - 20 км/ч, по шоссе - 30 км/ч.
От A до B можно добраться двумя способами: 1) 40 км по грунтовой дороге; 2) 30 по шоссе и 25 км по грунту.
Найдем время, которое может затратить велосипедист этими двумя способами(Расстояние делим на скорость).
1) 40:20 = 2 часа.
2) 25:20 = 1,25 часа по грунту, 30:30 = 1 час по шоссе, 2,25 часа займёт весь путь.
Ответ: 2 часа по грунтовой дороге в 40 км.

7. Составьте семантическую сеть по русской народной сказке «Колобок».

8. Что такое дерево? Моделями каких систем могут служить деревья? Приведите пример такой системы.

Дерево - это граф, в котором нет циклов. Все иерархические системы можно представить в виде дерева.
Пример: генеалогическое дерево.

9. Сколько трёхзначных чисел можно записать с помощью цифр 2, 4, 6 и 8 при условии, что в записи числа не должно быть одинаковых цифр?

246; 248; 264; 284; 268; 286
426; 428; 462; 468; 482; 486
624; 628; 642; 648; 682; 684
824; 826; 842; 846; 862; 864
Всего 24 числа.

10. Сколько существует трёхзначных чисел, все цифры которых различны?

Всего цифр 10: 0,1,2,3,4,5,6,7,8,9
В трёхзначном числе три места
На первое можно поставить любую из девяти цифр(0 нельзя)- 9 способов
На второе место останется 8 цифр + 0 = 9 цифр - 9 способов
На третье место 8 цифр, - 8 способов
Всего 9·9·8=648 чисел

11. Для составления цепочек используются бусины, помеченные буквами А, В, С, D, Е. На первом месте в цепочке стоит одна из бусин А, С, Е. На втором - любая гласная, если первая буква гласная, и любая согласная, если первая согласная. На третьем месте - одна из бусин С, D, Е, не стоящая в цепочке на первом месте. Сколько цепочек можно создать по этому правилу?

13 вариантов

12. Два игрока играют в следующую игру. Перед ними лежит куча из 6 камней. Игроки берут камни по очереди. За один ход можно взять 1, 2 или 3 камня. Проигрывает тот, кто забирает последний камень. Кто выигрывает при безошибочной игре обоих игроков - игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

При безошибочной игре выигрывает первый игрок. Своим первых ходом он должен взять один камень. В куче остается пять камней. Какой бы ход ни сделал второй игрок, в куче останется 4, 3 или 2 камня. Это позволяет первому игроку своим вторым ходом оставить в куче ровно один камень, его и должен будет забрать своим вторым ходом второй игрок.