Учебник. А. Ю. Босова Москва бином. Лаборатория знаний 2016 11 класс Базовый уровень Учебник
 Скачать 4.61 Mb.
|
|
Глава 3. информационное моделирование рис. 3.19. Позиция 15 — выигрышная для Вани Итак, Петя может выиграть, если S = 16, …, 45 — это его выигрышные по- зиции. Для выигрыша Пете достаточно увеличить количество камней в 3 раза. При меньших значениях S за один ход нельзя получить кучу, в которой будет 46 или более камней. Если же в куче будет 15 камней, то после любого хода Пети своим первым хо- дом может выиграть Ваня. Действительно, при S = 15 после первого хода Пети («Ход П») в куче будет 16, 17 или 45 камней. Любой из этих случаев является выигрыш- ным для делающего ход Вани («Ход В»), которому для победы достаточно увеличить количество камней в 3 раза (рис. 3.19). Теперь попробуем определить значения S, при которых у Пети будет выигрышная стратегия, причём Петя не сможет вы- играть первым ходом, но сможет выиграть своим вторым ходом, независимо от того, как будет ходить Ваня. Мы выяснили, что S = 15 — проигрышная позиция для лю- бого игрока. Если Петя своим первым ходом сможет перевести в неё Ваню, то что бы ни делал последний, сам он выиграть не сможет, но переведёт в выигрышную позицию своего соперника. 15 камней Петя может получить при S = 14 (+ 1), S = 13 (+ 2) или S = 5 (→× 3). Других вариантов для S нет (рис. 3.20). рис. 3.20. Позиции 5, 13, 14 — выигрышные для Пети Представим всю информацию на числовой линейке: В В В П В В В В 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 … 45 46 157 моделирование на графах §11 Найдём на ней такое значение S, при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и при этом у Вани нет стратегии, которая позволит ему гарантированно выиграть пер- вым ходом. Здесь речь идёт о проигрышной позиции для первого игрока. Следовательно, искать значение S надо среди позиций, не отме- ченных как выигрышные. Пусть S = 12. Каким бы ни был ход Пети, им он переведёт своего соперника в выигрышную позицию: 13 (12 + 1), 14 (12 + 2) или 36 (12 →× 3). В последнем случае Ваня имеет возможность вы- играть своим первым же ходом (36 ×→ 3), а в первых двух случаях он должен перевести соперника в проигрышную позицию S = 15, что обеспечит ему выигрыш вторым ходом. Следовательно, пози- ция S = 12 — проигрышная для Пети. На дереве решений наши рассуждения могут быть представлены так, как показано на ри- сунке 3.21. рис. 3.21. Позиция 12 — проигрышная для Пети Если вместо S = 12 взять S = 11, то приведёт ли любой ход Пети Ваню к выигрышу? Подойдёт ли для этой цели S = 10? Обоснуйте свой ответ. Примеры, которые мы рассмотрели, имеют самое непосредст- венное отношение к теории игр — разделу современной математи- ки, связанному с решением многих задач экономики, социологии, политологии, биологии, искусственного интеллекта и ряда других областей, где необходимо изучение поведения человека и живот- ных в различных ситуациях. Игра выступает в качестве математической модели некоторой ситуации и понимается как процесс, в котором участвуют две и 158 Глава 3. информационное моделирование более стороны, ведущие борьбу за реализацию своих интересов. При этом игра характеризуется такими признаками, как: 1) присутствие нескольких игроков; 2) неопределённость поведения игроков, связанная с имеющими- ся у каждого из них несколькими вариантами действий; 3) различие (несовпадение) интересов игроков; 4) взаимосвязанность поведения игроков (результат, получаемый каждым из них, зависит от поведения всех игроков); 5) наличие правил поведения, известных всем игрокам. Игра может быть представлена в виде дерева, каждая верши- на которого соответствует ситуации выбора игроком своей стра- тегии. Примеры, которые мы рассмотрели, относятся к так называ- емым играм с полной информацией. В играх с полной информа- цией участники знают все ходы, сделанные до текущего момента, равно как и возможные стратегии противников, что позволяет им в некоторой степени предсказать последующее развитие игры. Тем, кто хочет получить более полное представление о теории игр рекомендуем познакомиться с книгой Александра Шеня «Игры и стратегии с точки зрения математики». Электронная версия кни ги является свободно распространяемой и доступна по адресу www.mccme.ru/free-books/shen/shen-games.pdf. СамОе ГлаВнОе Графы как информационные модели находят широкое при- менение во многих сферах нашей жизни. С их помощью можно планировать оптимальные транспортные маршруты, кратчайшие объездные пути, расположение торговых точек и других объектов. Путь между вершинами А и В графа считается кратчайшим, если эти вершины соединены минимальным числом рёбер (в слу- чае, если граф не является взвешенным) или если сумма весов рёбер, соединяющих эти вершины, минимальна (для взвешенного графа). Для определения кратчайшего пути между вершинами гра- фа используются алгоритм построения дерева решений, алгоритм Дейкстры, метод динамического программирования и другие ал- горитмы. Важную роль в решении многих задач экономики, социоло- гии, политологии, биологии, искусственного интеллекта и ряда других областей, где необходимо изучение поведения человека и животных в различных ситуациях, играет теория игр. 159 моделирование на графах §11 Игра, выступающая в качестве математической модели неко- торой ситуации, характеризуется такими признаками, как: 1) присутствие нескольких игроков; 2) неопределённость поведения игроков, связанная с имеющими- ся у каждого из них несколькими вариантами действий; 3) различие (несовпадение) интересов игроков; 4) взаимосвязанность поведения игроков (результат, получаемый каждым из них, зависит от поведения всех игроков); 5) наличие правил поведения, известных всем игрокам. Игра может быть представлена в виде дерева, каждая верши- на которого соответствует ситуации выбора игроком своей стра- тегии. В играх с полной информацией участники знают все ходы, сделанные до текущего момента, равно как и возможные стра- тегии противников, что позволяет им в некоторой степени пред- сказать последующее развитие игры. Выигрышная стратегия — это правило, следуя которому иг- рок выигрывает независимо от того, как играет противник. Вопросы и задания 1. В решении каких прикладных задач используются алгорит- мы нахождения кратчайшего пути между заданными верши- нами в графе? 2. С помощью алгоритма Дейкстры найдите кратчайший путь между вершинами A и G следующего графа: 3. В материалах международного конкурса по информатике «Бобёр» есть такая задача, предложенная разработчиками из Нидерландов. Бобёр Билли любит жёлуди. Он хочет поплыть по течению и собрать все жёлуди на островах, мимо которых будет про- плывать. Увы, течение реки настолько сильное, что он мо- 160 Глава 3. информационное моделирование жет плыть только вниз по течению. Какое максимальное количество желудей он сможет собрать? Решите эту задачу, воспользовавшись методом динамическо- го программирования. 4. На столе лежит 25 спичек. Играют двое. Игроки по очереди могут взять от одной до четырёх спичек. Кто не может сде- лать ход (т. к. спичек не осталось), проигрывает. Другими словами, выигрывает взявший последнюю спичку. Выясни- те, у кого из игроков есть выигрышная стратегия. 5. Выясните, у кого из двух игроков есть выигрышная стра- тегия в такой игре: начальная позиция — на столе лежит 107 спичек, за один ход можно брать 1 или 2 спички. Вы- игрывает тот, кто взял последнюю спичку. 6. Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 2, во второй — 3 камня. У каждого игрока неограниченное количество кам- ней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает число камней в какой-то куче в 3 раза, или добавляет 3 камня в любую из куч. Выигрывает игрок, после хода которого общее число камней в двух кучах ста- новится не менее 35. Кто выигрывает — игрок, делающий ход первым, или игрок, делающий ход вторым? 7. Два игрока, Петя и Ваня, играют в следующую игру 1) . Пе- ред игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить 1) Большое количество подобных заданий вы можете найти в открытом банке заданий ЕГЭ по информатике на сайте fipi.ru. 161 база данных как модель предметной области §12 в кучу 1 камень или 5 камней. Например, имея кучу из 10 камней, за один ход можно получить кучу из 11 или 15 кам- ней. У каждого игрока, чтобы делать ходы, есть неограничен- ное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 47. Победите- лем считается игрок, сделавший последний ход, т. е. первым получивший кучу, в которой будет 47 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 46. Выполните следующие задания, в каждом случае обосновы- вая свой ответ. 1) Укажите все такие значения числа S, при которых Петя может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающие ходы. 2) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня мо- жет выиграть своим первым ходом. Опишите выигрыш- ную стратегию Вани. 3) Укажите два значения S, при которых у Пети есть вы- игрышная стратегия, причём Петя не может выиграть за один ход, но может выиграть своим вторым ходом неза- висимо от того, как будет ходить Ваня. Для указанных значений S опишите выигрышную стратегию Пети. 4) Укажите значение S, при котором у Вани есть выигрыш- ная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, однако у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Для указанного значения S опишите вы- игрышную стратегию Вани. Постройте дерево всех пар- тий, возможных при этой выигрышной стратегии Вани. § 12 база данных как модель предметной области 12.1. Общие представления об информационных системах Способность накапливать информацию и обеспечивать эффек- тивный доступ к ней является сегодня определяющим фактором развития и поддержания жизнеспособности человеческого общества. 162 Глава 3. информационное моделирование Объёмы накопленных человечеством данных неуклонно растут. В 2011 году общий мировой объём сгенерированных человечест вом данных составил более 1,8 зеттабайт (1,8 трлн Гбайт). Столь ко же «весят» 200 млн двухчасовых фильмов в формате высокой чёткости, которые можно просматривать ежедневно без перерыва в течении 47 млн лет. Ожидается, что количество данных на пла нете будет как минимум удваиваться каждые два года вплоть до 2020 года. (По материалам журнала «Суперкомпьютеры», № 1(17), 2014.) Развитие средств вычислительной техники и информационных технологий открыло новые способы хранения, представления и поиска информации, сделав возможным создание информацион- ных систем, обеспечивающих практически мгновенное получение каждым требуемой ему информации в той или иной предметной области (части реального мира). Центральной частью любой ин- формационной системы является база данных. база данных (БД) — совокупность данных, организованных по опре делённым правилам, отражающая состояние объектов и их отноше ний в некоторой предметной области (транспорт, медицина, обра зование, право и т. д.), предназначенная для хранения во внешней памяти компьютера и постоянного применения. информационная система — это совокупность содержащейся в базах данных информации и обеспечивающих её обработку инфор мационных технологий и технических средств 1) В наше время информационные системы находят широкое применение в производственной, маркетинговой, финансовой, ка- дровой и многих других сферах деятельности. Примерами информационных систем (рис. 3.22), доступными каждому пользователю, в том числе и с помощью мобильных устройств, являются: • информационные системы, обеспечивающие возможность по- лучения справочной информации о расписании самолётов, по- ездов дальнего следования, электричек и автобусов, а также покупку железнодорожных и авиабилетов; • информационные системы, позволяющие узнать наличие и цены на медикаменты в аптеках, места в отелях города (ре- гиона) и др.; 1) Закон Российской Федерации «Об информации, информационных техноло- гиях и о защите информации». 163 база данных как модель предметной области §12 • разнообразные поисково-информационные картографические службы; • порталы, содержащие информацию нормативно-правового ха- рактера и др. Узнайте, для чего предназначены информационные системы, пред ставленные на рисунке 3.22. рис. 3.22. Примеры информационных систем 12.2. Предметная область и её моделирование Предметная область — это часть реального мира, рассматри- ваемая в рамках определённой деятельности. Например, можно рассматривать такие предметные области, как школа, библиотека, поликлиника, кинотеатр, склад и т. д. В предметной области можно выделить некоторые объекты (классы объектов) и зафиксировать их свойства (атрибуты). Объект предметной области — это факт, лицо, событие, предмет, о котором могут быть собраны данные. Информационный объект или сущность — это описание не- которого класса реальных объектов в виде совокупности свойств. 164 Глава 3. информационное моделирование Сущность предметной области — это класс объектов предметной области; по сути, это совокупность однотипных объектов. Примерами объектов (с точки зрения внешнего мира) или сущностей (с точки зрения БД) являются ученик, класс, кабинет, время занятий и т. д. Сущность УЧЕНИК может быть представле- на в БД с помощью следующих атрибутов: номер личного дела, фамилия, имя, отчество, год рождения. Это можно записать так: УЧЕНИК (НОМЕР ЛИЧНОГО ДЕЛА, ФАМИЛИЯ, ИМЯ, ОТЧЕСТВО, ГОД РОЖДЕНИЯ). Между объектами, а следовательно, и между соответствую- щими им сущностями могут существовать связи одного из сле- дующих типов: • «один к одному» (обозначается 1 : 1); • «один ко многим» (обозначается 1 : М); • «многие к одному» (обозначается М : 1); • «многие ко многим» (обозначается М : М). Связь 1 : 1 имеет место, когда одному экземпляру одной сущно сти соответствует один экземпляр другой сущности. Такая связь может быть установлена между сущностями ВЫПУСКНИК_ ШКОЛЫ и АТТЕСТАТ: каждый выпускник школы получает ат- тестат о среднем образовании и каждый аттестат принадлежит одному выпускнику. Связь 1 : М имеет место, когда одному экземпляру одной сущности может соответствовать несколько экземпляров другой сущности. Например, у матери может быть несколько детей; в одном кинотеатре может быть несколько залов; в одном классе, как правило, множество учеников. Связь М : 1 является противоположной к связи 1 : М; она имеет место, когда нескольким экземплярам одной сущности со- ответствует один экземпляр другой сущности. Например, несколь- ко учеников учатся в одном классе. Связь М : М имеет место, когда нескольким экземплярам од- ной сущности соответствует несколько экземпляров другой сущ- ности. Например, многие ученики получают много разных оце- нок; каждый учитель, преподающий в 11 классе, обучает многих учащихся, а каждый учащийся 11 класса обучается у нескольких учителей; один автор может написать несколько книг, и, в то же время, одна книга может быть написана несколькими авторами. 165 база данных как модель предметной области §12 Существуют связи, которыми каждый экземпляр одной сущ- ности обязательно связан с одним или несколькими экземплярами другой сущности. Например, связь между сущностями КЛАСС и УЧЕНИК такова, что каждый ученик принадлежит к определён- ному классу, и каждый класс состоит из определённой группы учеников. Возможны связи, при которых каждый экземпляр од- ной сущности не обязательно связан хотя бы с одним экземпля- ром другой сущности. Для создания БД необходимо, прежде всего, построить мо- дель её предметной области, определив, данные о каких объек- тах будут в ней храниться и какие связи между этими данными необходимо учесть. Модель предметной области, включающую в себя сущности, их атрибуты и связи между сущностями называют моделью «сущность– связь», или ERмоделью (от англ. Entity–Relationship — сущность– связь). Для большей наглядности при создании моделей «сущность– связь» пользуются условными графическими обозначениями: сущ- ности изображаются в виде прямоугольников, атрибуты — в виде эллипсов, связи — в виде ромбов. Построим модель «сущность–связь» для предметной области «Авиаперелёты», в которой рассмотрим две сущности: ПАССА- ЖИР и БИЛЕТ (рис. 3.23). рис. 3.23. Модель «сущность–связь» предметной области «Авиа- перелёты» 166 Глава 3. информационное моделирование Каждый пассажир, собирающийся лететь, например, в Париж, имеет билет. Двух одинаковых билетов, как и двух одинаковых пассажиров, не существует. Сущность ПАССАЖИР в данной мо- дели характеризуется свойствами: ФАМИЛИЯ, ИМЯиДОКУ- МЕНТ, удостоверяющий личность. Атрибуты сущности БИЛЕТ — РЕЙС, ДАТА, ВРЕМЯ, РЯД, МЕСТОи НОМЕРБИЛЕТА. Между сущностями ПАССАЖИР и БИЛЕТ существует связь Имеет. Это связь «один к одному»; соответствующие обозначения находятся над линиями связи возле прямоугольников сущностей. Эта связь является обязательной (сплошная линия на схеме) для сущности ПАССАЖИР (для того чтобы быть пассажиром, человек должен иметь билет) и необязательной (пунктирная линия на схеме) для сущности БИЛЕТ, поскольку не все билеты на рейс могут быть проданы. 12.3. Представление о моделях данных модель данных — это совокупность структур данных и операций их обработки. С помощью модели данных могут быть представлены сущно- сти и взаимосвязи между ними. Выделяют три основных типа моделей данных: иерархическую, сетевую и реляционную. Иерархическая модель данных определяет организацию дан- ных об объектах в виде дерева. В иерархической модели дан- ных у каждого объекта есть только один объект высшего уровня, которому он подчинен (родительский), и может быть несколько подчиненных объектов (потомков). Исключение составляет толь- ко наивысший по иерархии объект — у него нет родительского объекта. В иерархической модели данных каждый родительский объект в совокупности с подчиненными объектами (потомками) можно рассматривать как отдельное дерево. Пример иерархической организации данных представлен на рисунке 3.24. Информация БД «Школа» структурирована в виде иерархических деревьев, количество которых равно количеству подразделений (НАЧАЛЬНАЯ ШКОЛА, ОСНОВНАЯ ШКОЛА, СТАРШАЯ ШКОЛА). На первом уровне находится сущность ПОД РАЗДЕЛЕНИЕ (НОМЕР, НАЗВАНИЕ, РУКОВОДИТЕЛЬ). Сущ- ности второго уровня — КЛАССЫ (КОД КЛАССА, КЛАССНЫЙ 167 база данных как модель предметной области §12 РУКОВОДИТЕЛЬ), сущности третьего уровня — УЧЕНИКИ (ЛИЧНОЕ ДЕЛО, ФАМИЛИЯ). Подчёркиванием выделен атрибут, который однозначно определяет каждый экземпляр сущности. рис. 3.24. Пример иерархической организации данных Для обработки данныхв иерархической модели данных ис- пользуется следующий набор команд: • найти указанное дерево (например, дерево 1); • перейти от одного дерева к другому (например, от дерева 11А к дереву 10А); • перейти от родительского объекта к объекту-потомку внутри дерева (например, от объекта 11А к объекту К-18); • перейти от одного объекта к другому в порядке, предусмо- тренном иерархической структурой (например, от объекта 9А к объекту 10А); • вставить новый объект в указанном месте; • удалить текущий объект и др. Модель данных должна обеспечивать целостность данных, иначе говоря, в представленных с её помощью данных не долж- но быть противоречий. Свойство целостности должно сохраняться при любых действиях с данными. Основное правило обеспечения целостности в иерархической модели данных состоит в том, что ни один подчиненный объект (потомок) не может существовать без родительского объекта, за исключением одного основного родительского объекта. |