что такое модель что такое моделирование в каких областях науки и техники оно применяется
Что такое модели и моделирование — 5 этапов моделирования, когда и какие модели применяются
Здравствуйте, уважаемые читатели блога KtoNaNovenkogo.ru. Что общего между девушкой на подиуме, игрушечной машинкой и изображением атома на экране монитора? Во всех случаях мы говорим о моделях.
Это понятие плотно вошло в повседневную речь, но немногие понимают его подлинное значение и умеют применять осознанно.
Без всякого занудства я расскажу о моделях и моделировании все, что нужно знать.
Что такое модель
Термин образовался от латинского слова modulus — «мера, аналог, образец».
Под «моделью» понимается образ некого объекта или явления, который отражает лишь отдельные свойства.
Например, глобус – это модель земного шара. Он статичен, а не вращается вокруг солнца. Не может похвастаться собственной силой притяжения. Не имеет атмосферы. На поверхности глобуса не живут крошечные человечки. Он воспроизводит внешний вид нашей планеты, не затрагивая другие характеристики.
Военачальник разрабатывает план сражения. Чтобы обозначить ландшафт, он создает модель поля боя на своем столе. Вот этот камень будет горой, коробок спичек – вражеским танком, а зеленый платок – лесом.
При моделировании важна степень соответствия модели и реального объекта.
Поставив камешек не туда, можно проиграть настоящую битву.
Но избыточная схожесть также вредит делу — усложняет процесс и отвлекает от сути.
Стратег слишком увлекся, потратил время на воспроизведение полной копии танка в миниатюре. Враг начал наступление, застал военачальника врасплох, пока тот собирал макет.
Американский словарь английского языка дает такое определение:
«Модель — это упрощенное описание сложного объекта или явления».
Земля имеет шарообразную форму, но для простоты говорят, что она круглая.
Моделирование — это.
Моделирование — это метод познания. Он заключается в исследовании предметов, систем, процессов и явлений на основе их моделей.
Вот мы возвели небоскреб в зоне с высокой сейсмической активностью. Теперь хотим выяснить, выдержит ли постройка толчки земной коры. Как это сделать? Проведем эксперимент: произведем подрыв, чтобы вызвать землетрясение. Если здание устоит — все хорошо.
Но вот проблема — затея дорогостоящая, может привести к человеческим жертвам, уничтожить сам предмет исследования. Гораздо проще создать модель небоскреба в компьютерной программе, задать силу виртуального землетрясения и проверить устойчивость, не вставая с дивана.
Что можно моделировать:
5 этапов моделирования
Процесс состоит из 5 этапов:
Исследователь выбирает те части, которые его интересуют, а остальные отбрасывает, чтобы не мешались. Один объект может иметь несколько моделей, каждая из которых отображает некоторые из его особенностей.
Например, мы хотим изучить человека:
Получаются 3 разных описания человека, которые только частично замещают оригинал.
Моделирование — это циклический процесс. Исследователь возвращается к самому началу, снова строит модель, но уже более точную.
С каждым кругом он получает все больше информации о предмете изучения.
Моделирование – это воссоздание и изучение фрагмента реальности для исследовательских целей.
Метод применяется, когда необходимо:
Когда применяется моделирование
Зачем экспериментировать с моделями, когда есть оригинал?
Существуют ситуации, когда без построения модели не обойтись:
Какие бывают модели (их виды)
По своему характеру они делятся на 2 вида: материальные и информационные.
Материальные модели можно потрогать, увидеть, услышать, понюхать. Они воспроизводят физические особенности изучаемой системы, явления или процесса.
Деревянный макет здания – это изделие, которое отражает некоторые свойства реальной постройки. Плюшевый мишка – упрощенное представление большого медведя. Маленький ребенок приходит в зоопарк и легко узнает в грозном животном прообраз своей игрушки.
Информационные модели не существуют в реальном мире. Это набор информации, выраженный определенным образом – вербальным или знаковым.
Примерами знакового обозначения могут быть математические формулы, схемы, графики и рисунки. Вербальное представление – это слова или мысли. Например, модель поведения при переходе регулируемого перекрестка: посмотреть на светофор, если горит зеленый человечек, нужно убедиться, что нет машин. Только потом можно идти.
Более подробно на эту тему смотрите в видео:
Удачи вам! До скорых встреч на страницах блога KtoNaNovenkogo.ru
Эта статья относится к рубрикам:
Комментарии и отзывы (2)
Компьютерное моделирование вряд ли сможет заменить полноценный эксперимент с физической моделью, тем более, что программу пишут люди, а они могут ошибаться. На модели же можно проверить, к примеру, аэродинамические качества объекта, поместив уменьшенную копию в аэродинамическую трубу, чего нельзя сделать с реальным объектом, например, пассажирским самолётом. Потому модели будут существовать всегда.
Раньше и дети моделированием увлекались, самолеты небольшие конструировали, а сейчас только в компьютерные стрелялки играют.
Естествознание. 10 класс
Конспект урока
Естествознание, 10 класс
Урок 8. Моделирование в науке
Перечень вопросов, рассматриваемых в теме:
Модель (франц. modele, от лат. modulus мера, образец, норма) – это форма отображения определённого фрагмента действительности (предмета, явления, процесса, ситуации), который содержит существенные свойства моделируемого объекта и может быть представлен в абстрактной (мысленной или знаковой) или материальной (предметной) форме.
Моделирование – метод теоретического познания, состоящий в исследовании каких-либо явлений, процессов или систем путем построения и изучения их моделей; использование моделей для определения поведения и характеристик реальных систем.
Математическая модель – модели, построенные с использованием математических понятий и инструментария (формул, графиков, систем уравнений и т.д.)
Основная и дополнительная литература по теме урока (точные библиографические данные с указанием страниц):
Открытые электронные ресурсы по теме урока :
Теоретический материал для самостоятельного изучения
Реальные объекты исследования не всегда доступны для исследователя или в их функционирование нельзя вмешиваться. В этом случает можно заменить «оригинал» соответствующим аналогом (моделями), пользуясь которым можно провести эксперимент, изучать его поведение при изменениях параметров внешней и внутренней среды. В воспроизведении свойств объекта изучения на специально устроенном его аналоге-модели заключается суть процесса моделирование. Сама модель — это всегда упрощенное отражение объекта, копия реального объекта, обладающая его основными характеристиками и способная имитировать его поведение.
Модели могут быть реальными (материальными), например, модели самолетов, макеты зданий, фотографии, протезы, куклы и т.п., а также теоретическими (идеальными или абстрактными), создаваемые средствами языка (как естественного человеческого языка, так и специальных языков, например, языком математики. В этом случае мы имеем математическую модель, которая описывает взаимосвязи в изучаемой системе).
Математическое моделирование – инструмент познания, изучения и исследования сложных систем. Эти системы сложны потому, что либо состоят из большого числа структурных компонентов, либо находятся под влиянием большего числа внешних факторов. В этом случае ученые создают модели – упрощенные копии систем, отражающие их структуру и функциональные взаимосвязи. В логике исследования под особым вниманием находятся лишь некоторые компоненты системы и ее взаимосвязи. Математические модели могут быть представлены в виде математических формул, систем уравнений, графиков и т.д. Например, системы дифференциальных уравнений в модели Лотки-Вольтерра, изучающей системы «паразит-хозяин» и «хищник-жертва» или графический образ экологических пирамид (масс, энергий) и др.
Выделяют три функции моделирования:
Познавательная функция заключается в том, что за счет абстрагирования модели позволяют достаточно просто объяснить наблюдаемые на практике явления и процессы (другими словами, они дают ответ на вопрос «почему мир устроен так»).
Прогностическая функция моделирования отражает его возможность предсказывать будущие свойства и состояния моделируемых систем, то есть отвечать на вопрос «что будет?».
Нормативная функция моделирования заключается в получении ответа на вопрос «как должно быть?» – если, помимо состояния системы, заданы критерии оценки ее состояния, то возможно не только описать существующую систему, но и построить ее нормативный образ – желательный с точки зрения субъекта, интересы и предпочтения которого отражены используемыми критериями.
Примеры моделей различных типов в естественных науках
Учитель информатики
Сайт учителя информатики. Технологические карты уроков, Подготовка к ОГЭ и ЕГЭ, полезный материал и многое другое.
§13. Модели и моделирование.
Информатика. Учебник для 9 класса (по учебнику К. Ю. Полякова, Е.А. Еремина, базовый уровень)
§13. Модели и моделирование.
Что такое модель?
Ключевые слова:
При слове «модель» у многих, наверное, появляется мысль о моделях самолётов, кораблей, танков и другой техники, которые стоят на полках магазинов. Однако слово «модель» имеет более широкое значение. Например, игрушки, в которые играют дети всех возрастов, — это модели реальных объектов, с которыми они сталкиваются в жизни (или столкнутся в будущем).
Говоря о модели, мы всегда указываем на какой-то другой объект (процесс, явление), например: «Глобус — это модель Земли». Здесь другой объект — это Земля, он называется оригиналом. Объект становится моделью только тогда, когда есть оригинал, модели без оригинала не существует.
Зачем вообще нужны модели? Они появляются тогда, когда мы хотим решить какую-то задачу, связанную с оригиналом, а изучать оригинал трудно или даже невозможно:
• оригинал не существует; например, учебники истории — это модели общества, которого уже нет; возможные последствия ядерной войны учёные изучали на моделях, потому что ставить реальный эксперимент было бы безумием;
• исследование оригинала дорого или опасно для жизни, например, при управлении ядерным реактором, испытании скафандра для космонавтов, создании нового самолёта или корабля;
• оригинал сложно или невозможно исследовать непосредственно, например Солнечную систему, молекулы и атомы, очень быстрые процессы в двигателях внутреннего сгорания, очень медленные движения материков;
• нас интересуют только некоторые свойства оригинала; например, чтобы испытать новую краску для самолёта, не нужно строить самолёт.
Итак, модель всегда связана не только с оригиналом, но и с конкретной задачей, которую мы хотим решить с помощью модели.
Вместе с тем одна и та же модель может описывать множество самых разных оригиналов. Например, в различных задачах атом, муха, человек, автомобиль, высотное здание, даже планета Земля могут быть представлены как материальные точки (если размеры соседних объектов и расстояния между ними значительно больше).
Модель — это объект, который обладает существенными свойствами другого объекта или процесса (оригинала) и используется вместо него.
Назовите свойства самолёта, существенные с точки зрения:
а) конструктора;
б) дизайнера;
в) экономиста;
г) лётчика;
д) бортпроводника;
е) пассажира.
Практически всё, что мы делаем с помощью компьютеров, — это моделирование. Например, база данных библиотеки — это модель реального хранилища книг, компьютерный чертёж — это модель детали и т.д.
Моделирование — это создание и исследование моделей для изучения оригиналов.
С помощью моделирования можно решать задачи четырёх типов:
• изучение оригинала (в научных и учебных целях);
• анализ («что будет, если …») — прогнозирование влияния различных воздействий на оригинал;
• синтез («как сделать, чтобы …») — управление оригиналом;
• оптимизация («как сделать лучше всего …») — выбор наилучшего решения в данных условиях.
Назовите задачи, которые решаются в каждом случае.
а) Даниил считает, как купить новый планшетный компьютер по минимальной цене.
б) Кирилл выясняет, будет ли плавать в воде кусок пластика.
в) Константин проверяет, выдержит ли верёвка вес альпиниста.
г) Василий хочет сделать такой стол, который выдержит нагрузку в 200 кг.
д) Алёна изучает строение молекулы воды.
Какие бывают модели?
Существует множество классификации моделей, каждая из которых отражает какое-то одно свойство. Универсальной классификации моделей нет.
По своей природе модели делятся на материальные (физические, предметные) и информационные.
Материальные модели «можно потрогать» — это игрушки, уменьшенные копии самолётов и кораблей, чучела животных, учебные модели молекул и т. п.
Информационные модели — это информация о свойствах оригинала и его связях с внешним миром. Среди них выделяют вербальные модели (словесные, мысленные) и знаковые модели, записанные с помощью какого-то формального языка:
• графические (схемы, карты, фотографии, чертежи);
• табличные;
• математические (формулы);
• логические (варианты выбора на основе анализа условий);
• специальные (ноты, химические формулы и т. п.).
Различают статические и динамические модели.
В статических моделях предполагается, что интересующие нас свойства оригинала не изменяются во времени.
Динамические модели описывают движение, развитие, изменение.
Какие из этих моделей статические, а какие — динамические:
а) модель полёта шарика;
б) фотография;
в) видеозапись;
г) история болезни;
д) анализ крови;
е) модель молекулы воды;
ж) модель развития землетрясения;
з) модель вращения Луны вокруг Земли?
Динамические модели могут быть дискретными и непрерывными.
Модель называется дискретной, если она описывает поведение оригинала только в отдельные моменты времени. Например, модель колонии животных определяет их численность один раз в год.
Непрерывная модель описывает поведение оригинала для всех моментов времени из некоторого временного промежутка. Например, формула у = sin х и график этой функции — это непрерывные модели. Так как компьютер работает только с дискретными данными, все компьютерные модели — дискретные.
По характеру связей модели делятся на детерминированные и вероятностные.
В детерминированных моделях связи между исходными данными и результатами жёстко заданы, при одинаковых исходных данных всегда получается один и тот же результат (например, при расчёте по известным формулам).
Вероятностные модели учитывают случайность событий в реальном мире, поэтому при одних и тех же условиях результаты нескольких испытаний модели могут отличаться. К вероятностным относятся модели броуновского движения частиц, полёта самолёта с учётом ветра, движения корабля при морском волнении, поведения человека. В результате эксперимента с такими моделями определяют некоторые средние величины по результатам серии испытаний, например среднюю скорость движения частиц, среднее отклонение корабля от курса и т. п. Несмотря на случайность, эти результаты достаточно стабильны, т. е. мало меняются при повторных испытаниях.
Используя дополнительные источники, выясните, от каких иностранных слов произошли слова «вербальный», «статический», «динамический», «детерминированный».
По материалам параграфа составьте в тетради схемы различных классификаций моделей.
Имитационные модели используются в тех случаях, когда поведение сложной системы нельзя (или крайне трудно) предсказать теоретически, но можно смоделировать её реакцию на внешние условия. Для того чтобы найти оптимальное (самое лучшее) решение задачи, нужно выполнить моделирование при многих возможных вариантах и выбрать наилучший из них. Такой метод часто называют методом проб и ошибок.
Имитационные модели позволяют очень точно описать поведение оригинала, но полученные результаты справедливы только для тех случаев, которые мы моделировали (что случится в других условиях — непонятно). Примеры использования имитационных моделей:
• испытание лекарств на мышах, обезьянах, группах добровольцев;
• модели биологических систем;
• экономические модели управления производством;
• модели систем массового обслуживания (банки, магазины и т. п.). Для понимания работы процессора можно использовать его имитационную модель, которая позволяет вводить команды в определённом формате и выполнять их, и показывает изменение значений регистров (ячеек памяти) процессора. Подобные модели применяют в том случае, когда нужно написать программу для системы, на которой её невозможно отлаживать (например, для микропроцессора, встроенного в бытовую технику). Такой подход называют кросс-программированием: программа пишется и отлаживается в одной системе, а работать будет в другой. В этом случае другую систему приходится моделировать с помощью имитационной модели.
Игровые модели позволяют учитывать действия противника, например, при моделировании военных действий, соревнований, конкуренции в бизнесе. Задача игрового моделирования — найти лучшую стратегию в игре — план действий, который даёт наилучшие результаты даже в том случае, когда противник играет безошибочно. Этими вопросами занимается теория игр — раздел математики, одним из создателей которого был американский учёный Джон фон Нейман.
Адекватность моделей
Итак, при моделировании мы заменяем один объект (объект — оригинал) другим. Поэтому всегда возникает вопрос, можно ли верить полученным результатам. Иначе говоря, будет ли оригинал вести себя так же, как и модель?
Адекватность модели — это совпадение существенных свойств модели и оригинала в рассматриваемой задаче.
Используя дополнительные источники, выясните, от какого иностранного слова произошло слово «адекватный».
Адекватность означает, что результаты моделирования:
• не противоречат выводам теории, например законам сохранения (вещества, энергии и т. п.);
• подтверждаются экспериментом с оригиналом.
Таким образом, адекватность модели окончательно можно доказать только экспериментом: если результаты нашего моделирования близки к наблюдаемым на практике, это означает, что модель адекватна.
Для того чтобы вычислить ошибку моделирования, нужно модуль разности между результатом моделирования X и результатом эксперимента X* разделить на результат эксперимента и умножить на 100%:
Величина «дельта икс» — называется относительной ошибкой. На практике модель обычно считается адекватной, если относительная ошибка не превышает 10%.
Феофан построил математическую модель, которая позволяет прогнозировать изменение веса кошки. Для какого периода времени модель Феофана адекватна?
Нужно понимать, что любая модель отличается от оригинала, поэтому она может быть адекватна только при определённых условиях — в той задаче, для решения которой она создавалась. Например, модель деления амёб (через некоторый интервал времени каждая амёба делится надвое) адекватна только при малом количестве амёб и небольших интервалах наблюдения, иначе амёбы заполнили бы всё пространство.
Во многих случаях результаты моделирования — это некоторые числа, измеренные или рассчитанные по результатам эксперимента с моделью. Это могут быть, например, сила, расстояние, скорость, ускорение, давление и др. Чаще всего эти величины для модели и оригинала будут различаться, поэтому нужно уметь пересчитывать «модельные» данные в соответствующие значения для оригинала. Этими вопросами занимается теория подобия. Простейший пример — работа с картой. Расстояние, измеренное по карте, нужно умножить на масштабный множитель, тогда получится соответствующее расстояние на реальной местности.
Выводы
• Модель — это объект, который обладает существенными свойствами другого объекта, процесса или явления (оригинала) и используется вместо него.
• Моделирование — это создание и исследование моделей для изучения оригиналов.
• С помощью моделирования можно решать задачи четырёх типов:
1) изучение оригинала;
2) анализ — прогнозирование влияния различных воздействий на оригинал;
3) синтез — управление оригиналом;
4) оптимизация — выбор наилучшего решения в данных условиях.
• Универсальной классификации моделей нет. По своей природе модели делятся на материальные и информационные.
• Адекватность модели — это совпадение существенных свойств модели и оригинала в рассматриваемой задаче. Проверить адекватность можно только путём эксперимента с оригиналом.
Нарисуйте в тетради интеллект-карту этого параграфа.
Вопросы и задания
1. Что вы думаете по поводу другого определения модели: «Модель — это упрощённое представление реального объекта, процесса или явления»?
2. Приведите примеры разных моделей человека. Для решения каких задач они предназначены?
3. Приведите примеры моделей, с которыми мы работаем на компьютерах.
4. К какому типу (типам) можно отнести следующие модели?
Используйте разные классификации.
5. Какую модель — вероятностную или детерминированную — вы рекомендуете выбрать для исследования движения судна в шторм? Почему?
6. Сравните достоинства и недостатки имитационных и теоретических моделей (например, записанных в виде формул).
7. Верно ли, что модели, используемые при создании компьютерных игр, это игровые модели? Обоснуйте вашу точку зрения.
8. Как можно доказать, что модель неадекватна?
9. Почему ни одна модель не может быть полностью адекватна оригиналу?
10. Выполните по указанию учителя задания в рабочей тетради.
Подготовьте сообщение
а) «Анализ и синтез»
б) «Детерминированные и вероятностные модели»
в) «Игровые модели»
г) «Адекватность моделей»
Учитель информатики
Сайт учителя информатики. Технологические карты уроков, Подготовка к ОГЭ и ЕГЭ, полезный материал и многое другое.
Модели и моделирование
§ 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. Модели и моделирование