Зуев Ю.А. ОСНОВНЫЕ СТРУКТУРЫ.
МЕТОДЫ ПЕРЕЧИСЛЕНИЯ. БУЛЕВЫ ФУНКЦИИ. По океану дискретной математики: От перечислительной комбинаторики до современной криптографии. Том 1. Т.1. Изд. стереотип.

Оглавление

Предисловие

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

Задачи дискретной математики, которыми в XVIII веке занимался гениальный Леонард Эйлер, в течение двухсот лет оставались единичными примерами, носившими характер развлекательных головоломок, привлекших к себе внимание, в значительной мере, бл годаря имени великого математика. В XIX веке Кирхгоф, строя теорию электрических цепей, фактически работал с графами, но тогда это понятие оказалось еще недостаточно востребованным, чтобы выделить его из приложения. Даже книга Кёнига, вышедшая в Германии в 1936 году и впервые осветившая теорию графов как с мостоятельную математическую дисциплину, была по достоинству оценена лишь двумя десятилетиями позже, после того, как в 1950 году вышло её американское издание.

Создание дифференциального исчисления в конце XVII века позволило от господствовавшей в античном мире статики перейти к динамике физических процессов. XIX век стал триумфом непрерывной математики, описавшей дифференциальными уравнениями поведение м терии и электромагнитного поля, рассматриваемых как непрерывные среды. Принцип непрерывности, согласно которому физическая система переходит из одного состояния в другое путём бесконечно малых изменений, был отчётливо сформулирован Лейбницем: "Природа никогда не делает скачков". И в соответствии с этим дифференциальные уравнения надолго стали единственным матем тическим инструментом моделирования физической реальности.

В XX веке выяснилось, однако, что природа скачки делает, и идея дискретности всё настойчивее стала пробивать себе дорогу. Физик, столкнувшись с квантовыми явлениями, стала изучать атомы и элементарные частицы, возникла квантовая теория. Биология перешл от дарвинской теории непрерывного развития видов к изучению генов и кодов наследственности.

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

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

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

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

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

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

Так, более двух тысячелетий назад александрийский математик Эр тосфен отсеивал простые числа из натурального ряда методом, который ныне носит его имя. Древние греки занимались числами, не стремясь извлечь из этого какой-либо практической выгоды, а просто из любви к прекрасному. В двадцатом веке, когда теория чисел из чисто теоретической дисциплины превратилась в раздел, имеющий важные приложения, в частности, в криптографии, распозн вание в приемлемое время простоты больших по величине натур льных чисел стало практически востребованной задачей. И вот нед вно группой индийских математиков (M.Agrawal, N.Kayal, N.Saxena) для решения этой задачи найден эффективный алгоритм, позволяющий с помощью компьютера распознавать простоту чисел, десятичная запись которых составляет сотни цифр.

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

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

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

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

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

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

Основу структурного построения книги составляют главы, разбитые на разделы.

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

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

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

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

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

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

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

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

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

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

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

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

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

В выборе обозначений автор следовал традициям отечественной школы. Нумерация утверждений, лемм, теорем и рисунков начинается заново в каждом разделе каждой главы. При ссылке внутри раздела указывается лишь внутренний номер, при ссылке внутри главы – номер раздела и внутренний номер, а при ссылке из другой главы – номер главы, раздела и внутренний номер.

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

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

Как видно из вышесказанного, книга не является жёстким учебным курсом, предполагающим изучение "от корки и до корки". Предст вленный материал в основном покрывает университетский общий курс дискретной математики, а также может быть основой для аспир нтского теорминимума. При составлении же стандартного семестрового курса по дискретной математике, читаемого на втором курсе технического вуза, лектором может быть использовано четыре первых раздела глав 1 и 2, семь первых разделов главы 3 и по четыре первых раздела глав 4 и 5. Материал остальных разделов может включаться в зависимости от уровня математической подготовки аудитории, целей и задач курса. Это же относится и к "Дополнениям". Материал, не включённый в основной курс, может читаться факультативно и использоваться для спецкурсов.

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

Автор благодарит помогавших ему в работе над книгой: Н.Н.Кузюрина, с которым он постоянно консультировался в процессе работы, И.П.Чухрова, оказавшего помощь при написании Дополнения 2, В.К.Леонтьева и М.Н.Вялого, сделавших ряд ценных замечаний, а также своих друзей Ю.Г.Свириденко и А.Н.Ходатаева, без помощи которых книга не могла быть написана.

Об авторе

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