Дискретная математика (998286), страница 3
Текст из файла (страница 3)
Липского «Комбинаторика для программистов» (14], перевод которой выдержал уже два издания в России. Данный учебник принадлежит именно к такому жанру математической литературы, в котором математическое изложение доводится до уровня практически исполнимых программ. Он отличается большей широтой, но, пожалуй, меньшей глубыной охвата материала. Учебник основан на лекционном курсе, который автор уже в течение четырнадцати лет читает студентам кафедры Прикладная математика» Санкт-Петербургского государственного технического университета, что наложило определенный отпечаток на состав материала.
Учебник охватывает почти все основные разделы дискретной математики: наивную теорию множеств, математическую логику, общую алгебру, комбинаторику и теорию графов. Из основных разделов отсутствуют теория алгоритмов и (машинная) арифметика, равно как и некоторые необходимые для программиста, но более специальные разделы, такие как теория формальных грамматик, вычислительная геометрия и теория конечных автоматов. Это объясняется тем, что данные разделы студенты изучают в специальных курсах. В то же время в учебник 14 Введение включены такие специальные разделы, как теория булевых функций и теория кодирования, поскольку по этим темам специальных курсов не предусмотрено. В целом учебник преследует три основные цели.
1. Познакомить читателя с максимально широким кругом понятий дискретной математики. Количество определяемых и упоминаемых понятий и специальных терминов намного превышает количество понятий, обсуждаемых более детально, Тем самым у студента формируется терминологический запас, необходимый для самостоятельного изучения специальной математической и теоретико-программистской литературы. 2.
Сообщить читателю необходимые конкретные сведения из дискретной математики, предусматриваемые стандартной программой технических высших учебных заведений. Разбор доказательств приведенных утверждений и выполнение упражнений позволят студенту овладеть методами дискретной математики, наиболее употребительными при решении практических задач. 3.
Пополнить запас примеров нетривиальных алгоритмов. Изучение алгоритмов решения типовых задач дискретной математики и способов представления математических объектов в программах абсолютно необходимо практикующему программисту, поскольку позволяет уменьшить трудозатраты на «изобретение велосипеда» и существенно обогащает навыки конструирования алгоритмов, Структура книги Фактически весь материал делится на две части, соответствующие двум семестрам курса, Первая часть, несколько большая по объему (главы 1-6), содержит самые общие сведения из различных разделов дискретной математики. Доля алгоритмов в первой части несколько меньше, а доля определений несколько больше, чем во второй части.
Вторая часть (главы 7-12) целиком посвящена теории графов, поскольку связанные с ней вопросы (в частности, алгоритмы на графах) являются наиболее широко применяющимися в практическом программировании разделами дискретной математики. Тексты алгоритмов на графах, некоторые нз которых весьма нетривиальны, составляют почти половину объема материала второй части.
Главм делятся,на разделы, которые, в свою очередь, делятся на подразделы. Каждый раздел посвящен одному конкретному вопросу темы главы и по объему соответствует экзаменационному вопросу. Подразделы нужны для внутренних эсылок и более детальной структуризации материала. Как правило, в подразделе рассматривается какое-нибудь одно понятие, теорема или алгоритм. Главы книги более или менее независимы и могут изучаться в любом порядке, га исключением первых глав каждой части, которые содержат набор базисных зпределений для дальнейшего изложения. 4спол»зуемые обозначения В конце каждой главы имеются два специальных раздела: «Комментарии» и «Упражнения». В разделах первого типа приводится очень краткий обзор литературы по теме главы и даются ссылки на источники, содержащие более детальные описания упомянутых алгоритмов. Эти разделы не претендуют на статус исчерпывающего библиографического обзора, скорее это рекомендации для студентов по чтению для самообразования.
Упражнения немногочисленны — ровно по одному на каждый раздел — и очень просты. Как'правило, в упражнения выносится дополнительный материал, непосредственно связанный с темой рэздлаа (например, опущенные доказательства утверждений, аналогичных доказанным в основном тексте). Используемые обозначения Данная книга предназначена для программистов, то есть предполагается, что читатель не испытывает затруднений в понимании текстов программ на языке высокого уровня.
Именно поэтому в качестве нотации для записи алгоритмов используется некоторый неспецифицированный язык программирования, похожий по синтаксису на Паскаль (но, конечно, Паскалем не являющийся). В программах широко используются математические обозначения, которые являются самоочевидными в конкретном контексте. Например, конструкция Еог х е М до Р(х) епо гог означает применение процедуры Р ко всем элементам множества М. «Лишние» разделители систематически опускаются, функции могут возвращать несколько значений, и вообще, разрешаются любые вольности, которые позволяют сделать тексты программ более краткими и читабельными.
Особого упоминания заслуживают два «естественных» оператора, аналоги которых в явном виде редко встречаются в настоящих языках программирования. Оператор зе!если» Е М означает выбор произвольного элемента гп из множества М. Этот оператор часто необходим в «переборных» алгоритмах. Оператор у(е!д х означает возврат значения х, но при этом выполнение функции не прекращается, а продолжается со следующего оператора. Этот оператор позволяет очень просто записать «генерирующие» алгоритмы, результатом которых является некоторое заранее неизвестное множество значений. Поскольку данная книга написана на «программно-математическом» языке, в ней не только математические обозначения используются в программах, но и некоторые программистские обозначения используются в математическом тексте.
Введение 1б Прежде всего, отметим широкое использование символа присваивания: =, который в математическом контексте можно читать как «по определению» или «положим». Если в левой части такого присваивания стоит простая переменная, то это имеет очевидный 'смысл введения обозначения. Но в левой части может стоять и выражение. В этом случае левую часть следует понимать как заголовок процедуры вычисления значения выражения, а правую часть — как тело этой процедуры. Например, формула А = В:=А с ВЙВ с А означает следующее: «для того чтобы вычислить значение выражения А = В, нужно вычислить значения выражений А с В и В с А, а затем вычислить конъюнкцию этих значений». Наряду с обычным для математики «статическим» использованием знака: =, когда выражению в левой части придается постоянное значение (определение константы), знак присваивания используется и в «динамическом», программистском смысле.
Например, пусть в графе С есть вершина е. Тогда формулу С: = С ~ (е) следует понимать так: «удалим в графе С вершину н», Кроме того, в книге используются и другие приемы, хорошо известные программистам. Например, описание структуры формул задается с помощью формальной грамматики в общепринятых обозначениях. Одной из задач книги является выработка у студентов навыка чтения математических текстов. Поэтому, начиная с самой первой страницы, интенсивно используются без дополнительных объяснений язык исчисления предикатов и другие общепринятые математические обозначения.
При этом стиль записи формул совершенно свободный и неформальный. Например, вместо формулы Ч й ((й < и) =» Р(й)) может быть написано Чй ( и Р(й) в предположении, что читатель знает или догадается, какие синтаксические упрощения используются. В первых главах книги основные утверждения (формулировки теорем) дублируются, то есть приводятся на естественном языке и на языке формул. Тем самым на примерах объясняется используемый язык формул. Но в последних частях книги и в доказательствах использование естественного языка сведено к минимуму.
Это существенно сокращает объем текста, но требует внимания при чтении. В целом используемые обозначения строго следуют классическим образцам, принятым в учебной математической и программистской литературе. Непривычным может показаться только совместное использование этих обозначений в одном тексте. Но такое взаимопроникновение обозначений продиктовано основной задачей книги.
выделения з тексте Выделения в тексте В учебнике имеются следующие основные виды текстов: определения, теоремы, леммы и следствия, доказательства и обоснования, замечания, отступления, алгоритмы и примеры. Фактически, обычный связующий текст сведен к минимуму в целях сокращения объема книги. Определения никак специально не выделяются, поскольку составляют львиную долю основного текста книги.
Вместо этого курсивом выделяются определяющие вхождения терминов, а текст, соседствующий с термином, н есть определение. Все определяющие вхождения вынесены в алфавитный указатель, помещенный в конце книги. Таким образом, если при чтении попадается незнакомый термин, следует найти его определение с помощью указателя (или убедиться, что определения в книге нет). Формулировки теорем, лемм и следствий, в соответствии с общепринятой в математической литературе практикой, выделены курсивом. При этом формулировке предшествует соответствующее ключевое словес «теорема», «лемма», «следствие». Как правило, утверждения не нумеруются, за исключением случаев вхождения нескольких однородных утверждений в один подраздел. Для ссылок на утверждения используются номера подразделов, в которых утверждения сформулированы.
Доказательства относятся к предшествующим утверждениям, а обосиования— к предшествующим алгоритмам. В очевидных случаях они опускаются илн выносятся в упражнения. Доказательства н обоснования начинаются с соответствующего ключевого слова («доказательство» или «обоснование») и заканчиваются специальным значком П. Замечания и оклстунлвния также начинаются с соответствующего ключевого слова: «замечание» или «отступление», Назначение этих абзацев различно. Замечание сообщает некоторые специальные нли дополнительные сведения, прямо относящиеся к основному материалу учебника. Отступление не связано непосред'ственно с основным материалом, его назначение — расширить кругозор читателя и показать связь основного материала с вопросами, лежащими за пределами курса.
ЗАМЕЧАНИЕ В очень редких случаях курсив используется не для выделения определяющих вхождений терминов н формулировок утверждений, а для того, чтобы сделать эмфатнческое ударение на кзком-то слове з тексте. ОТСТУПЛЕНИЕ Использование отступлений необходимо, з противном случае у читателя может сложиться ошибочное впечатление о замкнутости нзучаемого предмета н его оторванности от дрУгих областей знания.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
