Часть 1. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОГО ЯЗЫКА
ДИСКРЕТНЫЕ МАТЕМАТИЧЕСКИЕ МОДЕЛИ
НАЧАЛЬНЫЕ ПОНЯТИЯ И СТАНДАРТНЫЕ ЗАДАЧИ
Учебное пособие
Александр Рубчинский
Национальный исследовательский университет «Высшая школа экономики»
Международный университет природы, общества и человека «Дубна»
Москва
ПРЕДИСЛОВИЕ
«Труден первый шаг и скучен первый путь.
Преодолел я ранние невзгоды. Ремесло
Поставил я подножием искусству;
Я сделался ремесленник: перстам
Придал послушную, сухую беглость
И верность уху»,
говорит Сальери у Пушкина. Следует подчеркнуть, что без такой, на первый взгляд, рутинной, работы невозможно не только какое-либо творчество, но даже и сколько-нибудь заметное прод-вижение в любой разумной профессиональной деятельности.
Конечно, математика не является исключением из этого общего правила. Обучаться любо-му искусству можно на примерах и подражании. И в той степени, в какой математика является искусством (а она им является, на мой взгляд, в значительной степени), именно так – на приме-рах и подражании – должно быть основано математическое образование, особенно на началь-ном и среднем уровне. Применительно к более конкретным вещам, мне представляется, что не-обходимо уделять значительно бóльшее внимание обучению техническим аспектам математи-ки. Ещё конкретнее это значит, что следует уделять внимание методам решения разнообразных стандартных задач, чтобы студент видел, что математика позволяет упрощать ситуации, а не усложнять их (если речь не идёт о наиболее «крутых» математических олимпиадах).
Несмотря на множество книг по дискретной математике и дискретным моделям (часть которых активно использовалась при подготовке предлагаемого материала), книги, в которой подробные определения основных понятий сопровождаются столь большим числом стандарт-ных заданий и поясняющих всех их примеров, просто нет. Мой опыт в преподавании большого числа курсов по этой тематике – от основ дискретной математики до математических моделей и методов принятия решений – говорит о том, что преодолеть естественный страх и скованность большинства студентов можно только одним способом. Надо давать такие задания, которые «получаются», о которых не говорят «вообще не понятно, что и как здесь делать». Только на базе освоения таких простых и подробно описанных заданий можно – для части студентов – пе-реходить к более серьёзным вещам.
Мне представляется, что приступая к написанию любого разумного материала, крайне же-лательно если не ответить, то хотя бы задать себе три взаимосвязанных вопроса. Они таковы:
1. Для кого предназначен этот материал?
2. Чему могут (или должны) научиться предполагаемые читатели?
3. Что является содержанием предлагаемого материала?
Постараюсь дать мои ответы на эти вопросы.
1. Конечно, хотелось бы сказать, что пособие может быть полезным для студентов, магис-тров и аспирантов, обучающихся по математическим, программистским, экономическим, уп-равленческим и многим гуманитарным специальностям. Но это не так. Выдающийся математик Питер Халмош в своей известной статье «Как писать математические книги» призывал авторов чётко определять предполагаемую аудиторию. Очень выразителен один из его советов по этому поводу – «книги, нужные всем, не нужны никому».
Аудитория предполагаемого пособия вполне определена. Она состоит из студентов бака-лавриата и магистратуры, обучающихся по специальностям, попадающим между точными, ес-тественными и инженерными науками, с одной стороны, и гуманитарными науками, с другой. В этих специальностях – экономике, менеджменте, социологии, политологии, государственном и муниципальном управлении, бизнес-информатике и др., – всё в бóльшей степени использует-ся не традиционная математика с точными количественными зависимостями, а формально бо-лее простая математика, оперирующая более наглядными и качественными дискретными моде-лями. В различных ВУЗах для студентов этих или близких к ним специальностей читаются кур-сы с названиями «Моделирование и управление», «Методы оптимальных решений», «Матема-тические методы моделирования социальных процессов», «Анализ политической и политологи-ческой информации», «Методы анализа и обработки данных для принятия управленческих ре-шений», «Математика конфликтов», «Интеллектуальные системы поддержки управленческих решений» и пр. Здесь перечислены только некоторые курсы, которые я читал, начиная с 2006 г. в Академии внешней торговли, университете «Дубна» и Высшей школе экономики. Учебных пособий, учитывающих реальные нужды этой аудитории и хоть как-то покрывающих указан-ные курсы, практически нет. Частичным исключением является книга Ф.Т. Алескерова, Э.Л. Хабиной и Д.А. Шварца «Бинарные отношения, графы и коллективные решения», которая выш-ла уже двумя изданиями. Однако её структура, излагаемый материал и цели отличны от струк-туры, материала и целей предлагаемого пособия. Именно это обстоятельство – отсутствие необ-ходимых для работы по реальным курсам материалов – и инициировало подготовку настоящего пособия.
2. Как уже говорилось, пособие не рассчитано на математиков и программистов. Тем не менее, представляется, что часть выпускников по упомянутым выше «промежуточным» – меж-ду математиками и гуманитариями – специальностям будет встречаться в своей профессиональ-ной деятельности – и не только в научной – с самыми различными дискретными моделями. По-этому студенты должны получить не только формальное представление о подобных моделях. Они должны привыкнуть к ним («понять – это значит привыкнуть»), не бояться их и уметь ра-ботать с ними. Конкретнее, это означает, что они могут (или должны) освоить базовые алгорит-мы, связанные с дискретными моделями. Именно поэтому центральной и наиболее важной час-тью пособия являются многочисленные таблицы и рисунки для «ручной» реализации алгорит-мов в небольших размерностях. Только проделав необходимые операции собственными рука-ми, пропустив их перед этим через собственную голову, можно действительно освоить описан-ный в пособии простой, но разнообразный и непривычный для большинства материал. И уже зная, что, как и зачем делают эти алгоритмы, можно – в дальнейшем – значительно более осо-знанно и эффективно использовать разнообразное программное обеспечение для решения тех же самых или даже других дискретных задач в реальных размерностях. Таким образом, освое-ние изложенных в пособии дискретных моделей и алгоритмов работы с ними и представляет собой ответ на второй из поставленных вопросов. Ещё раз стоит повторить, что обучение на примерах и подражании – основной путь начального освоения любой разумной области дея-тельности.
3. Ответ на третий вопрос, по сути дела, определяется ответами на первые два – кого и че-му предполагается научить. Дадим просто несколько более подробные объяснения по поводу того, что в пособии есть, и того, чего в нём нет.
Предлагаемое пособие посвящено дискретным математическим моделям – в первую оче-редь, решению разнообразных стандартных задач, в которых надо что-то посчитать, найти, по-строить и т.д., но не доказать. Я совсем не против доказательств как таковых. Но дело в том, что никакого представления о дискретных объектах: кортежах, графах, таблицах, булевых функци-ях, кодировании, бинарных отношениях, функциях выбора, индексах влияния, стратегиях в иг-рах и др. – даже у хорошего и трудолюбивого школьника, поступившего в ВУЗ, совсем нет (в отличие от интуитивного представления об «обычных» функциях вроде синуса и логарифма). И тем более нет никакого представления о том, как «работают» упомянутые (да и многие другие) дискретные понятия. Поэтому (по моему мнению) надеяться на то, что большинство студентов достаточно быстро научится решать задачи на «доказательство» (даже простые), не приходится. Сначала нужно привыкнуть к рассматриваемым понятиям.
Более того, сам характер дискретных моделей и связанных с ними рассуждений ориенти-рован больше на алгоритмы, чем на что-либо другое. Основной вопрос при изучении дискрет-ных моделей (и не только на рассматриваемом низком уровне) состоит не в том «как это дока-зать», а в том, «как это сделать». Да и сами доказательства в дискретной математике в большин-стве случаев представляют собой, по сути дела, алгоритмы. Поэтому материал пособия, кроме введения и объяснения многих новых и непривычных понятий, содержит большое число алго-ритмов – от совсем очевидных, но всё же специально выделенных именно как алгоритмы, пра-вил выполнения теоретико-множественных операций, до достаточно сложных алгоритмов Фор-да-Фалкерсона, Дейкстры, нахождения равновесий в биматричных играх, построения устойчи-вых паросочетаний, различных правил пропорционального представительства, агрегации инди-видуальных предпочтений и сравнения векторных оценок методом Подиновского. Не только упомянутые, но и все другие рассматриваемые алгоритмы не просто излагаются и поясняются, но подробно расписываются «в числах» в обозримых и доведённых до конца примерах.
Особое внимание уделяется технологии ручной реализации алгоритмов. Наиболее важные из них (алгоритмы Форда-Фалкерсона, Дейкстры, Флойда-Уоршолла, нахождение критического пути в сетевом графике, задача о замены машины) представлены в виде последовательного за-полнения однотипных таблиц, из которых в первую заносятся исходные данные (инициализа-ция), а в последнюю вписывается решение исходной задачи. Приводятся полные примеры по-следовательного заполнения таких таблиц с подробными объяснениями. Всё это позволяет сту-дентам просто скопировать из соответствующего docx-файла указанные примеры, подставлять вместо содержащихся там исходных данных свои индивидуальные варианты заданий и, следуя имеющимся там же объяснениям, провести требуемые простые однотопные операции со свои-ми данными. Можно сказать, что предлагается своего рода интегрированная система – правда, пока ещё без диагностики ошибок (хотя в принципе понятно, как это сделать). Я убеждён, что чтение готовых примеров не заменяет – с точки зрения освоения – такое выполнение алгорит-мов до самого конца по «своим» данным. Но и в тех случаях, где таблиц в явном виде нет (как в изложении алгоритма построения объясняющих цепочек в методе Подиновского), имеется под-робное изложение всех шагов на нескольких конкретных примерах, что также позволяет выпол-нить аналогичную работу самостоятельно. Естественно, что упомянутые файлы прилагаются к пособию.
Материал пособия сгруппирован в четыре части, соответствующие основным типам диск-ретных моделей и связанных с ними задач. Проблематика каждой части аннонсирована в корот-ких введениях к ним и здесь не обсуждается. Можно заметить отсутствие части, посвящённой стохастическим моделям. Это связано с особенностями таких моделей, которые, по моему мне-нию, обосновывают их выделение в отдельную область, естественно включающую в себя мате-риалы как дискретного, так и непрерывного характера. Далее, в соответствие с целями издания, в него включались только такие материалы, которые можно сопроводить простыми и техничес-ки легко выполнимыми стандартными заданиями. По этой причине, например, не был включён раздел «Метод ветвей и границ», а также материалы по линейному и целочисленному програм-мированию, многие разделы теории игр и т.д. Разумеется, есть много дискретных моделей, по которым всё же есть задания желаемого типа, но которые также не включены в пособие. Здесь можно ответить словами Козьмы Пруткова «Никто не объемлет необъятного», а также сказать о личных пристрастиях.
Как уже говорилось, пособие инициировано отсутствием изданий того типа и уровня, ко-торые, на мой взгляд, требуются для реального преподавания различных курсов, в значитель-ной степени основанных на дискретных математических моделях или тесно связанных с ними. Речь не идёт об отсутствии книг и учебных пособий по этой тематике в целом и особенно по её отдельным направлениям. Их много, и некоторые из них действительно написаны на высоком научно-методическом уровне. Однако мне представляется, что данное пособие всё же заполняет некоторую нишу, характеризующуюся как увазанным кругом специальностей, так и изложени-ем, ориентированным в первую очередь на технические аспекты дискретных моделей. Издание не предполагается использовать как базовый учебник по какому-либо конкретному курсу, но как одно из основных пособий по нескольким курсам для различных специальностей. Назову – в качестве примеров – читаемые в НИУ ВШЭ курсы «Дискретные математические модели», «Теория систем и системный анализ», «Теория игр и конфликтные ситуации», «Методы приня-тия решений», «Моделирование и управление», «Методы оптимальных решений», «Математи-ка конфликтов». Использование различных частей в различных курсах потребовало максималь-но возможной независимости материала из разных частей и глав пособия. Например, в первых четырёх главах в рамках изложения «языка математики» даётся достаточно строгое определе-ние понятия функции, наряду с понятиями формы, переменной и т.д.. Однако во всех последу-ющих главах достаточно интуитивного представления о функциях.
Стоит остановиться на некоторых технических вопросах. Пособие состоит из глав с неза-висимой нумерацией формул, примеров, рисунков и т.д. внутри каждой главы. При ссылках на материал из любой другой главы к номеру добавляется отделённый дефисом (-) номер главы. Главы сгруппированы в 4 части, но номера частей при ссылках не указываются. Списки зада-ний и предметные указатели завершают каждую главу, а небольшие списки литературы – каж-дую часть. Концы примеров, утверждений, заданий и пр. отмечены знаком ■
Почти все разделы пособия прошли «обкатку» в течение нескольких лет при преподава-нии упомянутых выше курсов. При выполнении заданий многие вопросы, казавшиеся почти очевидными, вызвали трудности у большинства студентов. Были и обратные примеры, когда некоторые задания, казавшиеся мне более сложными, проблем не вызывали. Полученный при этом очень важный опыт учтён – насколько это возможно – в предлагаемом материале.
Следует сказать, что настоящее пособие предполагает некоторое продолжение. Предпола-гается подготовка более «продвинутого» пособия по дискретным моделям, в котором будет и более сложный материал, и задачи разной степени трудности «на доказательства», и более структурированное изложение, определяемое одной основной задачей системного анализа – за-дачей достижения цели. Предполагается также и ещё одно, важное для меня (надеюсь, интерес-ное и для других) пособие, посвящённое реальным прикладным задачам и игровым лаборатор-ным работам, связанными с некоторыми из приложений. В нём предполагается отразить опыт моей (и, конечно, не только моей) работы с реальными прикладными проектами. Наконец, предполагается разработка электронной интерактивной версии настоящего пособия. Но всё это, как писал в своих дневниках Л.Н. Толстой, задумывая новые произведения – ебж (если буду жив).
И последнее. При огромном уважении и любви ко многим замечательным учёным – жи-вым и ушедшим от нас, – с которыми мне «и довелось, и посчастливилось» встречаться, я пос-вящаю этот скромный труд моим студентам – бывшим, настоящим и будущим. В конце концов, я работаю с ними и для них.
ОГЛАВЛЕНИЕ
Предисловие
Часть 1. Элементы математического языка..........................7
Глава 1. Высказывания..........................................8
Глава 2. Множества............................................18
Глава 3. Кортежи..............................................26
Глава 4. Высказывательные формы и кванторы....................34
Глава 5. Булева алгебра.......................................45
Часть 2. Оптимизация на графах..................................72
Глава 6. Элементы теории графов...............................73
Глава 7. Потоки в сетях.......................................95
Глава 8. Кратчайшие пути.....................................112
Глава 9. Паросочетания.......................................135
Глава 10. Многошаговая оптимизация...........................145
Часть 3. Взаимодействие: конфликты и сотрудничество............166
Глава 11. Матричные игры.....................................167
Глава 12. Другие игровые модели..............................183
Глава 13. Неигровые модели взаимодействия....................202
Часть 4. Принятие решений......................................224
Глава 14. Бинарные отношения.................................225
Глава 15. Бинарные отношения в критериальном пространстве....235
Глава 16. Коллективные решения...............................247
Глава 17. Функции выбора.....................................262
Часть 1. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОГО ЯЗЫКА
Начнём первую часть предлагаемого пособия с нескольких цитат из предисловия В.А. Ус-пенского к книге Ю.А. Шихановича «Введение в современную математику» (см. список литера-туры в конце части).
«… Сейчас, как никогда, становится ясным, что математика – это не только совокупность фактов, изложенных в виде теорем, но прежде всего – арсенал методов, и даже ещё прежде того – язык для описания фактов и методов самых разных областей науки и практической деятель-ности. Именно этим обстоятельством и обусловливается универсальный характер применимос-ти математики …».
«Математические методы исследования неизбежно начинаются с – явного или неявного – уточнения языка. Причём главное в этом языке … – фундамент, язык начальных понятий. К их числу и относятся, прежде всего … понятия “множество”, “кортеж”, “соответствие”, “фун-кция”, “отношение”». (В обеих цитатах разрядка В.А. Успенского).
К этим понятиям следует добавить – и даже поставить на первое место – понятие “выска-зывание”, как это и делается в вышеупомянутой книге Ю.А. Шихановича, В ней, как и во мно-гих других изданиях, включая классическую книгу Н. Бурбаки «Теория множеств» (см. список литературы в конце части), понятия высказывания, множества и кортежа считаются исходными и формально неопределяемыми. В то же время понятия графика, соответствия, функции, как и многие другие, будут формально определяться через эти исходные понятия. Именно иерархия основных понятий, связанная с определениями одних через другие, и задаёт порядок изложе-ния. Например, фраза «элемент x принадлежит множеству X» является высказыванием, и уже поэтому множества должны рассматриваться после высказываний, кортежи – после множеств, и т.д. Поэтому материал части 1 «Элементы математического языка» излагается в следующем порядке:
Понятие высказывания вводится и разъясняется (но формально не определяется просто потому, что это невозможно) в главе 1, понятие множества – в главе 2, понятие кортежа – в гла-ве 3. Конечно, вместе с этими понятиями в главах 1 – 3 вводятся и другие «сопутствующие» по-нятия – простого и составного высказывания, элемента, принадлежности и подмножества, ком-поненты кортежа и прямого (декартового) произведения множеств, и т.п. Формально определя-емые (с помощью уже введённых понятий) понятия графика, соответствия и функции также рассматриваются в главе 3. В главе 4 вводятся понятия формы, переменной и кванторов. Завер-шает эту часть глава 5, посвящённая булевым (логическим) функциям и некоторым их прило-жениям. Булевы функции используются в самых различных разделах чистой и прикладной ма-тематики, иногда даже за рамками дискретных моделей, и поэтому их также можно отнести к базовым элементам математического языка.
Многие из формальных понятий, вводимых в этой части – кортежа, графика, соответст-вия, композиции соответствий, формы, – являются обобщениями хорошо известных из обыч-ной школьной математики понятий – вектора, графика, функции, суперпозиции функций, вы-ражения. Эта связь подчёркивается при определении и обсуждении указанных понятий. Более того, во всех главах, кроме первых четырёх, достаточно интуитивного представления о функ-ции и переменных, вместо слова «кортеж» можно использовать более привычные слова «на-бор», «пара», и т.д. Это возможно, поскольку, опираясь на формализацию указанных понятий из первых четырёх глав, удаётся избежать потерь в точности и общности изложения.
Как и в других частях пособия, изложение сопровождается значительным числом приме-ров и стандартных заданий, опирающихся на эти примеры.
Глава 1. Высказывания
1. Понятие высказывания
2. Простые и составные высказывания
3. Формальные представления составных высказываний
4. Задания
5. Предметный указатель
Понятие высказывания
Относительно некоторых предложений естественного языка, при помощи которого мы об-щаемся, например, «2 ´ 2 = 5» или «Волга впадает в Каспийское море», имеет смысл задать во-прос: «Истинны они или ложны?» Ясно, что ответ на указанный вопрос относительно первого предложения будет отрицательным: «Нет, это неверно», а относительно второго - положитель-ным: «Да, это так». Легко видеть, что этим свойством обладают не все предложения естествен-ного языка, а только некоторые из них. Так, вряд ли разумно считать, что предложения: «Пе-редай мне, пожалуйста, эту книгу» или «Который час?» обладают свойством быть истинными или ложными. Те из предложений языка, для которых это так, будем называть высказывания-ми, или суждениями. Заметим, что все математические утверждения, как бы они не назывались (теоремы, леммы, предложения и пр.) являются высказываниями. Заметим, однако, что матема-тические определения не являются высказываниями в указанном смысле. Действительно, неяс-но, какое значение истинности естественно приписать фразе «Четырёхугольник, противополож-ные стороны которого попарно параллельны, называется параллелограммом». А вот фразу «В параллелограмме диагонали в точке пересечения делятся пополам» можно рассматривать как высказывание.
Следует сразу сказать, что понятие высказывания, будучи одним из самых важных в мате-матике, не является строгим математическим понятием. Как и важнейшие понятия множества и кортежа, оно не может быть выражено через другие формальные (т.е. ранее уже определённые в математике) объекты и поэтому рассматривается как исходное или базовое. Высказывание мож-но описать (не определить!) слегка детальнее, как повествовательное предложение, которому естественно сопоставить значение «истина» или «ложь». Только для того, чтобы убедиться в неочевидности этого, на первый взгляд, очевидного, понятия, попробуйте приписать разумное значение истинности предложению «Это высказывание ложно». Разумеется, истинность того или иного конкретного высказывания зачастую трудно, а иногда просто невозможно опреде-лить. Но в такой общей постановке это и не входит в задачи математики.
Для удобства дальнейшего изложения высказывания будем обозначать прописными бук-вами латинского алфавита. Более того, вместо словосочетания «высказывание, обозначенное символом А» будем говорить и писать просто «высказывание А».
Пример 1.Cледующие фразы являются высказываниями:
D- «2 ´ 2 = 4»
E- «Москва - столица России»
F- «Существуют синие яблоки»
G- «Все люди моложе 15-и лет» ■
Поскольку каждое высказывание (согласно данному описанию) может быть истинным или ложным (но не одновременно!), высказыванию естественно сопоставить его истинност-ное, или логическое значение, т.е. одно из слов -истина или ложь. Для краткости эти слова обычно сводятся к символам T и F, и даже к цифрам 1 и 0(понимаемым именно как символы, а не как числа). Математическая логика (раздел математики, занимаюшийся операциями с выска-зываниями) не занимается определением истинностных значений тех или иных конкретных высказываний. В её рамках рассматриваются другие вопросы: как «правильно» формально по-строить одни высказывания, исходя из других заданных высказываний (синтаксис) и как найти истинностные значения построенных высказываний, исходя из заданных истинностных значе-ний исходных высказываний (семантика).