Мне известно о моделировании то что
Что такое модели и моделирование — 5 этапов моделирования, когда и какие модели применяются
Здравствуйте, уважаемые читатели блога KtoNaNovenkogo.ru. Что общего между девушкой на подиуме, игрушечной машинкой и изображением атома на экране монитора? Во всех случаях мы говорим о моделях.
Это понятие плотно вошло в повседневную речь, но немногие понимают его подлинное значение и умеют применять осознанно.
Без всякого занудства я расскажу о моделях и моделировании все, что нужно знать.
Что такое модель
Термин образовался от латинского слова modulus — «мера, аналог, образец».
Под «моделью» понимается образ некого объекта или явления, который отражает лишь отдельные свойства.
Например, глобус – это модель земного шара. Он статичен, а не вращается вокруг солнца. Не может похвастаться собственной силой притяжения. Не имеет атмосферы. На поверхности глобуса не живут крошечные человечки. Он воспроизводит внешний вид нашей планеты, не затрагивая другие характеристики.
Военачальник разрабатывает план сражения. Чтобы обозначить ландшафт, он создает модель поля боя на своем столе. Вот этот камень будет горой, коробок спичек – вражеским танком, а зеленый платок – лесом.
При моделировании важна степень соответствия модели и реального объекта.
Поставив камешек не туда, можно проиграть настоящую битву.
Но избыточная схожесть также вредит делу — усложняет процесс и отвлекает от сути.
Стратег слишком увлекся, потратил время на воспроизведение полной копии танка в миниатюре. Враг начал наступление, застал военачальника врасплох, пока тот собирал макет.
Американский словарь английского языка дает такое определение:
«Модель — это упрощенное описание сложного объекта или явления».
Земля имеет шарообразную форму, но для простоты говорят, что она круглая.
Моделирование — это.
Моделирование — это метод познания. Он заключается в исследовании предметов, систем, процессов и явлений на основе их моделей.
Вот мы возвели небоскреб в зоне с высокой сейсмической активностью. Теперь хотим выяснить, выдержит ли постройка толчки земной коры. Как это сделать? Проведем эксперимент: произведем подрыв, чтобы вызвать землетрясение. Если здание устоит — все хорошо.
Но вот проблема — затея дорогостоящая, может привести к человеческим жертвам, уничтожить сам предмет исследования. Гораздо проще создать модель небоскреба в компьютерной программе, задать силу виртуального землетрясения и проверить устойчивость, не вставая с дивана.
Что можно моделировать:
5 этапов моделирования
Процесс состоит из 5 этапов:
Исследователь выбирает те части, которые его интересуют, а остальные отбрасывает, чтобы не мешались. Один объект может иметь несколько моделей, каждая из которых отображает некоторые из его особенностей.
Например, мы хотим изучить человека:
Получаются 3 разных описания человека, которые только частично замещают оригинал.
Моделирование — это циклический процесс. Исследователь возвращается к самому началу, снова строит модель, но уже более точную.
С каждым кругом он получает все больше информации о предмете изучения.
Моделирование – это воссоздание и изучение фрагмента реальности для исследовательских целей.
Метод применяется, когда необходимо:
Когда применяется моделирование
Зачем экспериментировать с моделями, когда есть оригинал?
Существуют ситуации, когда без построения модели не обойтись:
Какие бывают модели (их виды)
По своему характеру они делятся на 2 вида: материальные и информационные.
Материальные модели можно потрогать, увидеть, услышать, понюхать. Они воспроизводят физические особенности изучаемой системы, явления или процесса.
Деревянный макет здания – это изделие, которое отражает некоторые свойства реальной постройки. Плюшевый мишка – упрощенное представление большого медведя. Маленький ребенок приходит в зоопарк и легко узнает в грозном животном прообраз своей игрушки.
Информационные модели не существуют в реальном мире. Это набор информации, выраженный определенным образом – вербальным или знаковым.
Примерами знакового обозначения могут быть математические формулы, схемы, графики и рисунки. Вербальное представление – это слова или мысли. Например, модель поведения при переходе регулируемого перекрестка: посмотреть на светофор, если горит зеленый человечек, нужно убедиться, что нет машин. Только потом можно идти.
Более подробно на эту тему смотрите в видео:
Удачи вам! До скорых встреч на страницах блога KtoNaNovenkogo.ru
Эта статья относится к рубрикам:
Комментарии и отзывы (2)
Компьютерное моделирование вряд ли сможет заменить полноценный эксперимент с физической моделью, тем более, что программу пишут люди, а они могут ошибаться. На модели же можно проверить, к примеру, аэродинамические качества объекта, поместив уменьшенную копию в аэродинамическую трубу, чего нельзя сделать с реальным объектом, например, пассажирским самолётом. Потому модели будут существовать всегда.
Раньше и дети моделированием увлекались, самолеты небольшие конструировали, а сейчас только в компьютерные стрелялки играют.
Моделирование
Моделирование — это метод воспроизведения и исследования определённого фрагмента действительности (предмета, явления, процесса, ситуации) или управления им, основанный на представлении объекта с помощью его копии или подобия — модели (см. Модель). Модель обычно представляет собой либо материальную копию оригинала, либо некоторый условный образ, представленный в абстрактной (мысленной или знаковой) форме и содержащий существенные свойства моделируемого объекта. Процедуры создания моделей широко используются как в научно-теоретических, так и в прикладных сферах человеческой деятельности.
В научном познании (см. Наука) модель рассматривается как «объект-подобие» или «объект-заместитель» объекта-оригинала, воспроизводящий определённые его характеристики. В этом смысле модель всегда соответствует объекту-оригиналу — в тех свойствах, которые подлежат изучению, но в то же время отличается от него по ряду других признаков, что делает модель удобной для исследования изучаемого объекта. Результаты разработки и исследования моделей при определённых условиях, принимаемых в методологии науки и специфических для различных областей и типов моделей, распространяются на оригинал. Использование метода моделирования в научном познании диктуется необходимостью раскрыть такие стороны объектов, которые либо невозможно постигнуть путём непосредственного изучения, либо непродуктивно изучать их таким образом в силу каких-либо ограничений.
В научном познании возможны два способа моделирования:
Модели, применяемые в научном познании, разделяются на два больших класса:
Соответственно указанным различениям выделяют основные разновидности моделирования. Каждое из них применяется в зависимости от особенностей изучаемого объекта и характера познавательных задач.
Предметно-физическое моделирование широко используется как в научной практике, так и в сфере материального производства. Такое моделирование всегда предполагает, что модель должна быть сходна с оригиналом по физической природе и отличаться от него лишь численными значениями ряда параметров. Наряду с этим в практике научного исследования часто используется и такой вид моделирования, при котором модель строится из объектов иной физической природы, чем оригинал, но описывается одинаковой с ним системой математических зависимостей. В отличие от предметно-физического этот вид моделирования называют предметно-математическим. Предметная модель становится здесь объектом испытания и изучения, в результате которого создаётся её математическое описание. Последнее затем переносится на моделируемый объект, характеризуя его структуру и функционирование.
В развитой науке, особенно при переходе к теоретическим исследованиям, широко используется моделирование с применением идеальных моделей. Этот способ получения знаний об объектах может быть охарактеризован как моделирование посредством идеализированных представлений. Он является ведущим инструментом теоретического исследования. Активно используя модельные представления, научное исследование вместе с тем применяет и так называемое знаковое моделирование, которое основано на построении и испытании математических моделей некоторого класса явлений, без использования при этом вспомогательного физического объекта, который подвергается испытанию. Последнее отличает знаковую модель от предметно-математической. Такой вид моделирования иногда называют также абстрактно-математическим. Он требует построения знаковой модели, представляющей некоторый объект, где отношения и свойства объекта представлены в виде знаков и их связей. Эта модель затем исследуется чисто логическими средствами, и новое знание возникает в результате дедуктивного развёртывания модели без обращения к предметной области, на основании которой выросла данная знаковая модель. В абстрактно-математическом моделировании модель — это конструкция, изоморфная моделируемой системе. При таком моделировании каждому объекту системы ставится в соответствие определённый элемент моделирующей конструкции, а свойствам и отношениям объектов соответствуют свойства и отношения элементов.
Классическими примерами моделей, основанных на изоморфизме, являются модели аксиоматических систем в математике. Они задают семантику формальных построений и создают возможность для содержательной интерпретации аксиом. Сами аксиомы, как и следствия из них, считаются предложениями некоторого формального языка. Кроме того, задана область интерпретаций, представляющая собой множество индивидных объектов. Изоморфизм задаётся функцией, сопоставляющей каждому имени языка некоторый объект из заданного множества, а каждому выражению языка некоторое отношение объектов этого же множества. Если любое высказывание, которое выведено из аксиом, истинно в области интерпретаций (то есть соответствует реальным отношениям объектов), то эта область называется моделью системы аксиом. Моделирование в математике используется, например, для доказательства непротиворечивости формальных систем.
Этот вид моделирования используется не только в чистой математике, но также при математическом описании природных, общественных, технологических и других сложных систем. Смысл такого описания состоит в том, что отношения между элементами системы выражаются с помощью уравнений, причём так, чтобы каждому термину содержательного описания системы соответствовала какая-либо величина (константа или переменная) или функция, фигурирующая в уравнении. Сами уравнения называются при этом моделью. Как правило, абстрактно-математическое моделирование требует абстракции (см. Абстракция), то есть отвлечения от некоторых свойств и отношений в моделируемой системе. Это позволяет достичь общности модели и утверждать, что она, игнорируя частности, описывает достаточно широкий круг процессов или систем. К тому же без таких упрощений моделирование оказывается бессмысленным ( чрезмерной сложности модели) или вообще невозможным. Другим важным гносеологическим условием моделирования является измеримость всех описываемых объектов и отношений. Чтобы построить модель, необходимо найти их числовое представление. Всякий моделируемый процесс должен быть полностью охарактеризован с помощью параметров, поддающихся измерению.
Другая разновидность моделирования с применением идеальных моделей основана на понятии «чёрный ящик». Этим термином принято называть объект, внутренняя структура которого недоступна для наблюдения и о котором можно судить только по его внешнему поведению, в частности по тому, как он преобразует приходящие на вход сигналы. Если некоторая система слишком сложна, то нет смысла искать её математическое описание. Проще попытаться построить вместо неё другую систему, которая при заданных условиях будет вести себя точно так же. Такое моделирование часто используется при исследовании отдельных систем живых организмов с помощью компьютерной симуляции. Описать работу живого организма уравнениями крайне тяжело или вообще невозможно. Но возможно построить компьютерную схему, которая при подаче на вход определённого стимула давала бы на выходе реакцию, тождественную или близкую к реакции моделируемой системы. Если спектр совпадающих входных и выходных процессов достаточно широк, то можно ожидать, что построенная схема точно воспроизводит исследуемый объект.
Трехмерное моделирование в современном мире
Сегодня я расскажу вам о том, что такое 3D-моделирование, каким оно бывает, где его применяют и с чем его едят. Эта статья в первую очередь ориентирована на тех, кто только краем уха слышал, что такое 3D-моделирование, или только пробует свои силы в этом. Поэтому буду объяснять максимум «на пальцах».
Сам я технический специалист и уже более 10 лет работаю с 3D-моделями, поработал более чем в 10ке различных программ разных классов и назначений, а также в различных отраслях. В связи с этим накопился определенный helicopter view на эту отрасль, с чем и хотел с вами поделиться.
3D-моделирование прочно вошло в нашу жизнь, частично или полностью перестроив некоторые виды бизнеса. В каждой отрасли, в которую 3D-моделирование принесло свои изменения, имеются как свои определенные стандарты, так и негласные правила. Но даже внутри одной отрасли, количество программных пакетов бывает такое множество, что новичку бывает очень трудно разобраться и сориентироваться с чего начинать. Поэтому, для начала давайте разберем какие же бывают виды 3D-моделирования и где они применяются.
Можно выделить 3 крупные отрасли, которые сегодня невозможно представить без применения трехмерных моделей. Это:
Полигонами называются вот эти треугольники и четырехугольники.
Чем больше полигонов на площадь модели, тем точнее модель. Однако, это не значит, что если модель содержит мало полигонов (low poly), то это плохая модель, и у человека руки не оттуда. Тоже самое, нельзя сказать про то, что если в модели Over999999 полигонов (High poly), то это круто. Все зависит от предназначения. Если, к примеру, речь идет о массовых мультиплеерах, то представьте каково будет вашему компьютеру, когда нужно будет обработать 200 персонажей вокруг, если все они high poly?
Полигональное моделирование происходит путем манипуляций с полигонами в пространстве. Вытягивание, вращение, перемещение и.т.д.
Пионером в этой отрасли является компания Autodesk (известная многим по своему продукту AutoCAD, но о нем позже).
Продукты Autodesk 3Ds Max, и Autodesk Maya, де-факто стали стандартом отрасли. И свое знакомство с 3D моделями, будучи 15-летним подростком, я начал именно с 3Ds Max.
Что же мы получаем на выходе сделав такую модель? Мы получаем визуальный ОБРАЗ. Геймеры иногда говорят: «я проваливался под текстуры» в игре. На самом деле вы проваливаетесь сквозь полигоны, на которые наложены эти текстуры. И падение в бесконечность происходит как раз потому, что за образом ничего нет. В основном, полученные образы используются для РЕНДЕРА (финальная визуализация изображения), в игре / в фильме / для картинки на рабочем столе.
Собственно, я в свое время и пытался что-то «слепить», чтобы сделать крутой рендер (тогда это было значительно сложнее).
Кстати о лепке. Есть такое направление как 3D-sсulpting. По сути, тоже самое полигональное моделирование, но направленное на создание в основном сложных биологических организмов. В ней используются другие инструменты манипуляций с полигонами. Сам процесс больше напоминает чеканку, чем 3D моделинг.
Если полигональная модель выполнена в виде замкнутого объема, как например, те же скульптуры, то благодаря современной технологии 3D-печати (которая прожует почти любую форму) они могут быть воплощены в жизнь.
По сути, это единственный путь для полигональных 3D моделей оказаться в реальном мире. Из вышеописанного можно сделать вывод, что полигональное моделирование нужно исключительно для творческих людей (художников, дизайнеров, скульпторов). Но это не однозначно. Так, например, еще одной крупной сферой применения 3D моделей является медицина, а именно- хирургия. Можно вырастить протез кости взамен раздробленной. Например, нижняя челюсть для черепашки.
У меня нет медицинского образования и я никогда ничего не моделил для медицины, но учитывая характер форм модели, уверен, что там применяется именно полигональное моделирование. Медицина сейчас шагнула очень далеко, и как показывает следующее видео, починить себе можно практически все (были бы деньги).
Конечно, используя полигональное моделирование, можно построить все эти восстанавливающие и усиливающие элементы, но невозможно контролировать необходимые зазоры, сечения, учесть физические свойства материала и технологию изготовления (особенно плечевого сустава). Для таких изделий применяются методы промышленного проектирования.
По правильному они называются: САПР (Система Автоматизированного ПРоектирования) или по-английский CAD (Computer-Aided Design). Это принципиально другой тип моделирования. Именно на нем я специализируюсь уже 8 лет. И именно про него я буду вам в дальнейшем рассказывать. Чем этот метод отличается от полигонального? Тем, что тут нет никаких полигонов. Все формы являются цельными и строятся по принципу профиль + направление.
Базовым типом является твердотельное моделирование. Из названия можно понять, что, если мы разрежем тело, внутри оно не будет пустым. Твердотельное моделирование есть в любой CAD-системе. Оно отлично подходит для проектирования рам, шестеренок, двигателей, зданий, самолётов, автомобилей, да и всего, что получается путем промышленного производства. Но в нем (в отличии от полигонального моделирования) нельзя сделать модель пакета с продуктами из супермаркета, копию соседской собаки или скомканные вещи на стуле.
Цель этого метода — получить не только визуальный образ, но также измеримую и рабочую информацию о будущем изделии.
CAD – это точный инструмент и при работе с CAD, нужно предварительно в голове представлять топологию модели. Это алгоритм действий, который образует форму модели. Вот, как раз по топологии, можно отличить опытного специалиста от криворукого. Не всегда задуманную топологию и сложность формы можно реализовать в твердотелке, и тогда нам на помощь приходит неотъемлемая часть промышленного проектирования — поверхностное моделирование.
Топология в поверхностях в 10 раз важнее, чем при твердотельном моделирование. Неверная топология – крах модели. (напоминаю, что это статья обзорная и для новичков, я не расписываю тут нюансы). Освоение топологии поверхностей на высоком уровне, закрывает 70% вопросов в промышленном моделировании. Но для этого нужно много и постоянно практиковаться. В конечном итоге, поверхности все равно замыкаются в твердотельную модель.
Со временем приходит понимание наиболее удобного метода при моделировании того или иного изделия. Тут полно лайф-хаков, причем у каждого специалиста есть свои.
ВАЖНО: использование CAD без профильного образования не продуктивно! Я сам много раз наблюдал, как творческие люди, или мастера на все руки пытались проектировать. Да, конечно они что-то моделировали, но все это было «сферическим конем в вакууме».
При моделировании в CAD, помимо топологии, необходимо иметь конструкторские навыки. Знать свойства материалов, и технологию производства. Без этого, все равно, что подушкой гвозди забивать, или гладить пылесосом.
В CAD мы получаем электронно-геометрическую модель изделия.
(Напоминаю, что при полигональном моделировании мы получаем визуальный образ)
Учитель информатики
Сайт учителя информатики. Технологические карты уроков, Подготовка к ОГЭ и ЕГЭ, полезный материал и многое другое.
Модели и моделирование
§ 10. Модели и моделирование
Информатика. 11 класса. Босова Л.Л. Оглавление
10.1. Общие сведения о моделировании
Человек стремится познать объекты (предметы, процессы или явления) окружающего мира, т. е. понять, как устроен конкретный объект, каковы его структура, основные свойства, законы развития и взаимодействия с другими объектами. При этом зачастую исследуются не сами объекты, а их модели.
Из курса информатики основной школы вам известно, что:
• модель — это новый объект, который имеет свойства данного объекта, существенные для определённого исследования;
• моделирование — метод познания, заключающийся в создании и исследовании моделей;
• натурная (материальная) модель — реальный предмет, в уменьшенном или увеличенном виде воспроизводящий внешний вид, структуру или поведение моделируемого объекта;
• информационная модель — описание объекта-оригинала на одном из языков кодирования информации;
• по форме представления можно выделить знаковые, образные и смешанные информационные модели;
• для создания информационной модели объекта необходимо:
1) выяснить цель моделирования;
2) выделить свойства объекта-оригинала, существенные с точки зрения цели моделирования;
3) установить взаимосвязи между значениями выбранных свойств и выразить их в некоторой форме (словесно, таблицей, графиком, функцией, уравнением, неравенством, системой и т. п.).
Модель — общенаучное понятие; моделирование имеет место в любых областях знания и сферах человеческой деятельности.
Приведите примеры моделей, с которыми вы встречались на уроках физики, химии, биологии, истории, математики, обществознания, литературы.
В информатике рассматриваются общие подходы к созданию и использованию информационных моделей, связанные с использованием компьютерной техники.
10.2. Компьютерное моделирование
Информационные модели, реализованные с помощью систем программирования, электронных таблиц, специализированных математических пакетов или программных средств для моделирования, называются компьютерными моделями.
Компьютерное моделирование включает в себя процесс реализации информационной модели на компьютере и исследование с помощью этой модели объекта моделирования — проведение вычислительного эксперимента.
С помощью компьютерного моделирования решаются многие научные и производственные задачи:
• прогнозирование погоды и климатических изменений;
• конструирование транспортных средств и дизайн лекарственных препаратов;
• стратегическое управление организациями и прогнозирование цен на финансовых рынках;
• прогнозирование прочности конструкций и исследование поведения зданий, конструкций и деталей под механической нагрузкой;
• многие другие задачи.
Рассмотрим основные этапы компьютерного моделирования более подробно (рис. 3.1).
Рис. 3.1. Основные этапы компьютерного моделирования
На первом этапе в результате анализа условия задачи определяется объект моделирования и цель создания модели. После этого в объекте моделирования выделяются параметры (свойства, основные части), существенные с точки зрения поставленной цели. Далее уточняется, какие результаты и в каком виде должны быть получены, а также какие исходные данные для этого нужны.
На втором этапе определяются параметры модели и связи между ними; приводится математическое описание зависимостей между параметрами модели.
На третьем этапе выбирается или разрабатывается алгоритм получения из исходных данных результатов, подбираются программные средства реализации алгоритма на компьютере и создаётся компьютерная модель.
На четвёртом этапе осуществляется работа непосредственно с полученной компьютерной моделью. Сначала на заранее разработанных тестах (наборах исходных данных, для которых заранее известны результаты) осуществляется проверка правильности (тестирование) модели, и при необходимости модель дорабатывается. После тестирования, когда есть уверенность в правильности функционирования модели, переходят непосредственно к компьютерному эксперименту — целенаправленным действиям пользователя над компьютерной моделью. В ходе такого экспериментирования сознательно изменяются условия функционирования модели и накапливаются данные о её «поведении». В процессе проведения эксперимента может выясниться, что нужно усовершенствовать или изменить используемый алгоритм, уточнить информационную модель или внести изменения в постановку задачи. В таких случаях происходит возвращение к соответствующему этапу, и процесс начинается снова.
На пятом этапе результаты эксперимента анализируются, на их основе делаются выводы о моделируемом объекте. На основе всестороннего анализа полученных результатов принимается некоторое решение, что и является конечной целью моделирования.
Компьютерное моделирование даёт возможность:
• существенно расширить круг исследуемых объектов (моделирование прошлого и будущего, несуществующего или невоспроизводимого в реальных условиях);
• исследовать процессы в развитии, при необходимости ускоряя или замедляя их и проводя эксперименты многократно;
• находить оптимальные решения без затрат на изготовление пробных экземпляров;
• проводить эксперименты без риска негативных последствий для здоровья человека или окружающей среды;
• визуализировать получаемые результаты.
10.3. Списки, графы, деревья и таблицы
Между данными, используемыми в той или иной информационной модели, всегда существуют некоторые связи, определяющие ту или иную структуру данных.
Вспомните, как мы определяли структуру данных при рассмотрении алгоритмов и программ. О каких информационных моделях тогда шла речь? С какими структурами данных вы сталкивались в программировании?
Различают линейные и нелинейные структуры данных.
В курсе информатики основной школы вы познакомились с линейным односвязным списком — последовательностью линейно связанных элементов, для которых разрешены операции добавления элемента в произвольное место списка и удаление любого элемента. Связь элементов списка осуществляется за счёт того, что каждый элемент списка содержит кроме данных адрес элемента, следующего за ним в списке. В линейном списке для каждого элемента, кроме первого, есть предыдущий элемент; для каждого элемента, кроме последнего, есть следующий элемент.
Частным случаем линейного односвязного списка является стек — последовательность, в которой включение и исключение элементов осуществляются с одной и той же стороны этой последовательности.
Ещё одним частным случаем линейного односвязного списка является очередь — последовательность, у которой включение элементов производится с одной стороны последовательности, а исключение — с другой. Сторона, где происходит включение элементов, называется хвостом; сторона, где происходит исключение, — головой. Понятие очереди как структуры данных очень близко к бытовому понятию «очередь» (рис. 3.2).
Рис. 3.2. Иллюстрация понятия «очередь»
Подумайте, какая связь между стеком и следующими объектами:
Почему стек является структурой типа LIFO (от англ. Last In, Firts Out — последним пришёл, первым ушёл)?
Почему очередь является структурой типа FIFO (от англ. First In, First Out — первым пришёл, первым ушёл)?
Примеры нелинейных структур данных вам также хорошо известны — это графы и деревья (рис. 3.3).
Граф — это множество элементов (вершин графа) вместе с набором отношений между ними.
Рис. 3.3. Примеры графовых структур
Граф является многосвязной структурой, обладающей следующими свойствами:
1) на каждый элемент может быть произвольное количество ссылок;
2) каждый элемент может иметь связь с любым количеством других элементов;
3) каждая связка может иметь направление и вес.
Ненаправленная (без стрелки) линия, соединяющая вершины графа, называется ребром. Линия направленная (со стрелкой) называется дугой. При этом вершина, из которой дуга исходит, называется начальной, а вершина, куда дуга входит, — конечной. Граф называется неориентированным, если его вершины соединены рёбрами. Вершины ориентированного графа соединены дугами. Граф называется взвешенным, если его вершины или рёбра характеризуются некоторой дополнительной информацией — весами вершин или рёбер.
Графы являются основным средством для описания структур сложных объектов. С их помощью можно описать вычислительную сеть, транспортную систему, схему авиалиний и другие объекты.
Одной из разновидностей графа является дерево.
Дерево — это совокупность элементов (вершин), в которой выделен один элемент (корень), а остальные элементы разбиты на непересекающиеся множества (поддеревья). Каждое поддерево является деревом, а его корень является потомком корня дерева, т. е. все элементы связаны между собой отношением «предок — потомок». В результате образуется иерархическая структура вершин.
Частным случаем дерева является бинарное дерево, в котором каждая вершина может иметь не более двух потомков.
Деревья используются для представления родственных связей (генеалогическое дерево), для определения выигрышной стратегии в играх и т. д.
Ещё одной знакомой вам структурой данных являются таблицы, состоящие из строк и граф (столбцов, колонок), пересечение которых образуют ячейки. Таблицы применяют для наглядности и удобства сравнения показателей.
Оформляют таблицы в соответствии с рисунком 3.4.
Рис. 3.4. Оформление таблицы
Название таблицы, при его наличии, должно отражать её содержание, быть точным, кратким. Название следует помещать над таблицей.
Заголовки граф и строк таблицы следует писать с прописной буквы, а подзаголовки граф — со строчной буквы, если они составляют одно предложение с заголовком, или с прописной буквы, если они имеют самостоятельное значение. В конце заголовков и подзаголовков таблицы точки не ставят. Заголовки и подзаголовки граф указывают в единственном числе.
Если все показатели, приведённые в графах таблицы, выражены в одной и той же единице физической величины, то её обозначение необходимо помещать над таблицей справа. Если в графе таблицы помещены значения одной и той же физической величины, то обозначение единицы физической величины указывают в заголовке (подзаголовке) этой графы.
Эти и другие требования к оформлению таблиц содержатся в ГОСТ 2.105-95 «ЕСКД. Общие требования к оформлению текстовых документов».
В курсе информатики основной школы вы познакомились с таблицами типа:
• «объект — свойство», содержащими информацию о свойствах отдельных объектов, принадлежащих одному классу;
• «объект — объект», содержащими информацию о некотором одном свойстве пар объектов, принадлежащих одному или разным классам.
Таблицы, в которых отражено наличие или отсутствие связей между отдельными элементами некоторой системы, называются двоичными матрицами.
Вспомните и приведите примеры таблиц типа «объект — свойство», «объект — объект», отражающих не только количественные, но и качественные характеристики свойств (двоичные матрицы).
Табличный способ представления данных является универсальным — любую структуру данных, в том числе и представленную в форме графа, можно свести к табличной форме. Это тем более важно в связи с тем, что для компьютерной обработки табличное представление данных является предпочтительным.
Пример 1. Построим таблицу, соответствующую неориентированному графу (рис. 3.5), отражающему схему дорог между некоторыми населёнными пунктами.
Рис. 3.5. Граф схемы дорог
Строки и столбцы таблицы будут соответствовать вершинам графа. Если две вершины являются смежными (соединены ребром), то в ячейку на пересечении соответствующих столбца и строки будем записывать вес этого ребра. В противном случае (вершины не являются смежными) в ячейку будем записывать 0. Получится таблица типа «объект — объект».
Такую таблицу называют матрицей смежности. Часто в матрицах смежности вместо нуля ставят знак минус, что обеспечивает большую наглядность.
Матрица смежности неориентированного графа симметрична относительно главной диагонали, идущей от левого верхнего угла к правому нижнему углу. У матрицы смежности неориентированного графа такая симметрия отсутствует.
Пример 2. Обед в школьной столовой состоит из двух блюд и напитка. На первое можно выбрать щи или окрошку, на второе — плов или пельмени, на третье — сок или компот. Все возможные варианты представлены с помощью дерева на рисунке 3.6.
Рис. 3.6. Дерево вариантов обеда
Для того чтобы представить эту же информацию в таблице, будем двигаться по дереву от листьев к корню, описывая все возможные варианты обеда.
Получилась таблица типа «объект-свойства»: объектами в ней являются варианты обеда, а свойствами — составляющие его блюда. При этом число граф в полученной таблице соответствует числу уровней в дереве.
При решении класса задач, связанного с нахождением кратчайшего пути в ориентированном графе, можно:
1) от исходного графа перейти к матрице смежности;
2) по матрице смежности построить дерево решений;
3) по дереву решений выбрать подходящий вариант.
Пример 3. Найдём кратчайший путь от вершины А до вершины F в графе, приведённом на рисунке 3.7.
Рис. 3.7. Ориентированный граф
Составим матрицу смежности, соответствующую данному ориентированному графу:
По матрице смежности построим полное дерево перебора решений — рисунок 3.8.
Рис. 3.8. Полное дерево перебора решений
На рисунке 3.8 видно, что кратчайший путь из вершины А в вершину F равен 17 и имеет вид A-B-E-F.
Пример 4. На рисунке 3.9 представлена схема дорог, связывающих города А, Б, С, D, Е, F, G. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько разных путей существует из города А в город G?
Рис. 3.9. Схема дорог.
Существует несколько способов решения этой задачи. Рассмотрим их.
Вариант 1. По графу можно построить матрицу смежности, а на её основе построить дерево, корнем которого будет служить вершина А. Число листьев построенного дерева будет равно числу дорог из города А в город G.
Постройте дерево и подсчитайте число дорог из города А в город G самостоятельно.
Вариант 2. Пусть Кх — число путей из города А в город X.
Начнем считать число путей с конца маршрута. Так как в город G есть дороги из городов С, E, F, то KG = КC + КЕ + KF.
Таким образом, KG = 2 + 3 + 2 = 7.
Вариант 3. Можно считать число путей с начала маршрута. При этом процесс подсчёта удобно изображать на самом графе — рисунок 3.10.
Рис. 3.10. Схема дорог с подсчётом числа путей
Пример 5. На рисунке 3.11 представлена схема дорог, связывающих населённые пункты А, В, С, D, Е, F, G. В таблице содержатся сведения о длинах этих дорог (в километрах). Схему и таблицу создавали независимо друг от друга, поэтому в них используются разные обозначения. Необходимо выяснить длину пути в километрах из пункта D в пункт F.
Рис. 3.11. Схема дорог и таблица их длин
Рассмотрим имеющийся граф и выясним степень каждой вершины — число рёбер, соединяющих некоторую вершину с другими вершинами. Получим:
На основании имеющейся таблицы мы также можем сделать выводы о том, сколькими дорогами соединён тот или иной населённый пункт с другими населёнными пунктами:
Сопоставив полученную информацию, можем сказать, что через Г1 в таблице обозначен населённый пункт F, а через Г7 — D. Согласно таблице, расстояние между этими пунктами равно 25 км.
САМОЕ ГЛАВНОЕ
Модель — это новый объект, который имеет свойства данного объекта, существенные для определённого исследования. Моделирование — метод познания, заключающийся в создании и исследовании моделей. Информационная модель — описание объекта-оригинала на одном из языков кодирования информации.
В информатике рассматриваются общие подходы к созданию и использованию информационных моделей, связанные с использованием компьютерной техники.
Информационные модели, реализованные с помощью систем программирования, электронных таблиц, специализированных математических пакетов или программных средств для моделирования, называются компьютерными моделями. Компьютерное моделирование включает в себя процесс реализации информационной модели на компьютере и исследование с помощью этой модели объекта моделирования — проведение вычислительного эксперимента.
Между данными, используемыми в той или иной информационной модели, всегда существуют некоторые связи, определяющие ту или иную структуру данных. Различают линейные и нелинейные структуры данных.
Линейный односвязный список — последовательность линейно связанных элементов, для которых разрешены операции добавления элемента в произвольное место списка и удаление любого элемента. Частным случаем линейного односвязного списка является стек — последовательность, в которой включение и исключение элементов осуществляются с одной стороны этой последовательности. Ещё один частный случай линейного односвязного списка — очередь, представляющая собой последовательность, у которой включение элементов производится с одной стороны последовательности, а исключение — с другой.
Примерами нелинейных структур данных являются графы и деревья. Граф — это множество элементов (вершин графа) вместе с набором отношений между ними, называемых рёбрами (дугами) графа. Дерево — это совокупность элементов (вершин), в которой выделен один элемент (корень), а остальные элементы разбиты на непересекающиеся множества (поддеревья). Каждое поддерево является деревом, а его корень является потомком корня дерева, т. е. все элементы связаны между собой отношением «предок — потомок». Частным случаем дерева является бинарное дерево, в котором каждая вершина может иметь не более двух потомков.
Таблица — это структура данных, состоящая из строк и граф (столбцов, колонок), пересечение которых образуют ячейки. Таблицы применяют для наглядности и удобства сравнения показателей. Табличный способ представления данных является универсальным — любую структуру данных, в том числе и представленную в форме графа, можно свести к табличной форме. Это тем более важно в связи с тем, что для компьютерной обработки табличное представление данных является предпочтительным.
Вопросы и задания
1. Что такое модель? Что такое моделирование? В каких областях науки и техники оно применяется?
2. Какие модели называются натурными? Приведите примеры натурных моделей.
3. Какие модели называются информационными? Приведите примеры информационных моделей. Какова роль информатики в информационном моделировании?
4. Создайте информационную модель одной из комнат вашей квартиры с целью оклейки её обоями. Представьте информационную модель в знаковой и графической формах.
5. Какие модели называются компьютерными информационными моделями?
6. Опишите основные этапы компьютерного моделирования.
7. Приведите примеры линейных структур данных. Чем очередь отличается от стека?
8. Муравьи идут друг за другом по неровной лесной тропе. На их пути встречаются ямки, в которые могут провалиться несколько Муравьёв. Когда ямка заполняется муравьями, остальные муравьи проходят через неё, а затем по одному вытаскивают провалившихся. Например, вот как четыре муравья проходят через ямку, вмещающую двух Муравьёв:
Пусть по тропе идут 8 Муравьёв. В каком порядке они будут идти после преодоления участка с четырьмя ямками, вмещающими 2, 4, 5 и 1 муравья соответственно?
Какую структуру данных иллюстрирует данный пример? 1)
1) По материалам международного конкурса по информатике «Бобёр» (bebras.ru).
9. Выясните, что представляет собой обратная польская запись, и вычислите значение записанного с её помощью выражения:
10. Что такое граф? Какой граф называется ориентированным? Какой граф называется неориентированным? Какой граф называется взвешенным? Приведите примеры.
11. Что такое дерево? Какое дерево называется бинарным? Приведите примеры.
12. Почему графы и деревья считаются многоуровневыми структурами данных?
13. Информация о родственных связях в некоторой семье представлена следующим образом:
означает, что А является родителем В. Нарисуйте генеалогическое древо этой семьи. Сколько у Ирины племянников и племянниц?
14. В кладовке хранятся ёлочные игрушки — большие и маленькие красные и золотые шары и звёзды. При этом игрушки разного размера, цвета и формы хранятся в отдельных коробках. Например, в одной коробке — большие красные звёзды, в другой — маленькие красные звёзды и т. д. Известно, что среди игрушек нет ни маленьких шаров, ни маленьких золотых звёзд. Всего звёзд 25, а шаров — 17. Всего больших игрушек — 32; красных игрушек — 28. Золотых звёзд на 2 больше, чем золотых шаров. В скольких коробках хранятся игрушки? Сколько игрушек в каждой коробке?
Постройте граф, представляющий состав игрушек. Используйте его для решения задачи. Представьте эту же информацию в табличной форме.
15. Что с вашей точки зрения более наглядно представляет структуру системы: граф или таблица? Какая форма представления информации предпочтительна для компьютерной обработки данных?
16. Решите следующую задачу, составив двоичную матрицу. Ваня, Кирилл, Петя и Саша учатся в 5, 6, 7 и 8 классах. Как-то они отправились в лес за белыми грибами. Шестикласснику не повезло — он не нашёл ни одного гриба, а Петя с пятиклассником нашли много грибов. Ваня и семиклассник нашли куст малины и позвали Кирилла полакомиться ягодами. Восьмиклассник, шестиклассник и Кирилл объясняли Саше, как ориентироваться на местности. В каком классе учится каждый из мальчиков?
17. Как осуществляется переход от ориентированного графа к дереву решений?
18. Найдите кратчайший путь от вершины А до вершины F в ориентированном графе:
19. На рисунке представлена схема дорог, связывающих города А, В, С, D, Е, F, G, Н, I, J. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько разных путей существует из города А в город J?
20. На рисунке представлена схема дорог, связывающих населённые пункты А, В, С, D, Е, F, G. В таблице содержатся сведения о длинах этих дорог (в километрах). Схему и таблицу создавали независимо друг от друга, поэтому в них используются разные обозначения. Необходимо выяснить длину пути в километрах из пункта Е в пункт F.
§ 10. Модели и моделирование