Новиков Ф.А. Дискретная математика для программистов (860615), страница 4
Текст из файла (страница 4)
Каждый раздел посвящён одному конкретному вопросу темы главы и по объёмусоответствует экзаменационному вопросу. Подразделы нужны для внутреннихссылок и более детальной структуризации материала. Как правило, в подразделерассматривается какое-нибудь одно понятие, теорема или алгоритм.
Подразделы в пределах раздела упорядочены по сложности: сначала приводятся основные определения, а затем рассматриваются более сложные вопросы, которые,в принципе, при первом чтении можно пропустить без ущерба для пониманияостального материала.Главы книги более или менее независимы и могут изучаться в любом порядке, за исключением первой главы, которая содержит набор базисных определений для дальнейшего изложения, и главы 7, в которой вводится специфическаятерминология теории графов.В конце каждой главы имеются два специальных раздела: «Комментарии» и«Упражнения». В комментариях приводится очень краткий обзор литературыпо теме главы и даются ссылки на источники, содержащие более детальныеописания упомянутых алгоритмов.
Эти разделы не претендуют па статус исчерпывающего библиографического обзора, скорее это рекомендации для студентовпо чтению для самообразования. Выбор источников, как правило, отражает вкусы автора. Упражнения немногочисленны — ровно по одному на каждый раздел — и очень просты. Как правило, в упражнения выносится дополнительныйматериал, непосредственно связанный с темой раздела (например, опущенныедоказательства утверждений, аналогичных доказанным в основном тексте).Используемые обозначенияДанная книга предназначена для программистов, то есть предполагается, чточитатель не испытывает затруднений в понимании текстов программ на языке высокого уровня.
Именно поэтому в качестве нотации для записи алгоритмовиспользуется некоторый неспецифицированпый язык программирования {псевдокод), похожий по синтаксису на Паскаль (но, конечно, Паскалем пе являющийся).Ключевые слова псевдокода выделены жирным шрифтом, идентификаторы обьектов записываются курсивом, как это принято для математических объектов,примечания заключаются в фигурные скобки { }.18ВведениеВ языке используются общеупотребительные структуры управления: ветвленияв краткой (if... then ... end if) и полной (if...
then ... else ... end if) формах, циклысо счётчиком (for ... from ... to ... do ... end for), с постусловием ( repeat... until),с предусловием (while ... do ... end while) и по множеству (for ... do ... end for),а также переходы (go to ...)1.Для обозначения присваивания используется традиционный знак : =, вызов процедуры или функции ключевыми словами не выделяется, выход из процедурыимеете с возвратом значения обозначается ключевым словом return.Подразумевается строгая статическая типизация, даже приведения не используются, за исключением разыменования, которое подразумевается везде, где ононужно по здравому программистскому смыслу.
В то же время объявления локальных переменных почти всегда опускаются, если их тип ясен из контекста.Из структур данных считаются доступными массивы (array [...] of...), структуры(rccord ... end record) и указатели ( | ) .В программах широко используются математические обозначения, которые являются самоочевидными в конкретном контексте.
Например, конструкцияfor х е Л/ doРНend forозначает применение процедуры Р ко всем элементам множества М.«Лишние» разделители систематически опускаются, функции могут возвращатьнесколько значений, и вообще, разрешаются любые вольности, которые позволяют сделать тексты программ более краткими и читабельными.Особого упоминания заслуживают три «естественных» оператора, аналоги которых в явном виде редко встречаются в настоящих языках программирования.Операторselect m e Mозначает выбор произвольного элемента тп из множества М. Этот оператор частонеобходим в «переборных» алгоритмах.
Операторyield хозначает возврат значения х, но при этом выполнение функции не прекращается,а продолжается со следующего оператора. Этот оператор позволяет очень простозаписать «генерирующие» алгоритмы, результатом которых является некотороезаранее неизвестное множество значений. Операторnext for хозначает прекращение выполнения текущего фрагмента программы и продолжение выполнения со следующего шага цикла по переменной х. Этот оператордолжен находиться в теле цикла по х (на любом уровне вложенности).
Такого1«Структурных» программистов, сомневающихся в допустимости использования оператора goto вучебнике, автор отсылает к статье Д. Кнута «Structured Programming with go to statements».19Используемые обозначениярода «структурные переходы» позволяют описывать обработку исключительныхситуаций в циклах непосредственно, без введения искусственных переменных,отслеживающих состояние вычислений в цикле.Операторы select, yield и next for не являются чем-то необычным и новым:первый из них легко моделируется использованием датчика псевдослучайныхчисел, второй — присоединением элемента к результирующему множеству, а третий — переходом по метке. Однако указанные операторы сокращают запись иповышают её наглядность.Поскольку эта книга написана на «программно-математическом» языке, в ней иетолько математические обозначения используются в программах, но и некоторыепрограммистские обозначения используются в математическом тексте.Прежде всего обсудим способы введения обозначений объектов и операций.
Еслиобозначение объекта или операции является глобальным (в пределах учебника),то используется знаккоторый следует читать «по определению есть». Приэтом слева от знакаможет стоять обозначение объекта, а справа — выражение,определяющее этот объект. Например,1+ Г= {х € Ш | х > 0}.В случае определения операции в левой части стоит выражение. В этом случае левую часть следует неформально понимать как заголовок процедуры выполненияопределяемой операции, а правую часть — как тело этой процедуры. Например,формулаЛ=АсВ к В с Аозначает следующее: «чтобы вычислить значение выражения А = В, нужно вычислить значения выражений А с В w В с А, а затем вычислить конъюнкциюэтих значений».Отметим широкое использование символа присваивания : =*, который в математическом контексте можно читать как «положим».
Если в левой части такогоприсваивания стоит простая переменная, а в правой части — выражение, определяющее конкретный объект, то это имеет очевидный смысл введения локального(в пределах доказательства, определения и т. п.) обозначения.
Например, записьZ': = Zl)Zek \ {efc} означает: «положим, что Z' содержит все элементы Z и ZCk заисключением е^». Наряду с обычным для математики «статическим» использованием знака : =, когда выражению в левой части придается постоянное в данномконтексте значение (определение константы), знак присваивания используетсяи в «динамическом», программистском смысле. Например, пусть в графе G естьвершина v.
Тогда формулу G: = G — v следует читать и понимать таю «удалим вграфе G вершину v».Некоторые обозначения являются глобальными, то есть означают одно и то жев любом контексте (в этой книге). Например, буква М всегда обозначает полевещественных чисел, а пара вертикальных чёрточек слева и справа от объекта\Х\ — количество элементов в объекте X. Таких стандартных обозначений не20Введениетак уж много. Они собраны в указателе обозначений в конце книги и используются в тексте учебника без дополнительных пояснений. Если смысл какого-тообозначения не ясен и не определён в данном контексте, то следует посмотретьэто обозначение в указателе обозначений.Одной из задач книги является выработка у студентов навыка чтения математических текстов.
Поэтому, начиная с самой первой страницы, без дополнительных объяснений интенсивно используются язык исчисления предикатови другие общепринятые математические обозначения. При этом стиль записиформул совершенно свободный и неформальный, но соответствующий общепринятой практике записи формул в математических текстах. Например, вместоформулыVfc ((к < п) = • Р(к))может быть написаноVA: < п (Р{к))или дажеVfc < п Р(к)в предположении, что читатель знает или догадается, какие синтаксические упрощения используются.
В первых главах книги основные утверждения (формулировки теорем) дублируются, то есть приводятся на естественном языке и паязыке формул. Тем самым на примерах объясняется используемый язык формул.Но в последних частях книги и в доказательствах использование естественногоязыка сведено к минимуму. Это существенно сокращает объём текста, но требуетвнимания при чтении.Для краткости в тексте книги иногда используются обороты, которые подразумевают восстановление читателем опущенных слов по контексту.
Например,если символ А означает множество, то вместо аккуратного, но длинного оборота«где объект х является элементом множества А», может быть использована болеекороткая фраза «где х — элемент А» или даже формула «где х е А».В целом используемые обозначения строго следуют классическим образцам, принятым в учебной математической и программистской литературе. Непривычным может показаться только совместное использование этих обозначений в одном тексте. Но такое взаимопроникновение обозначений продиктовано основнойзадачей книги.Выделения в текстеВ учебнике имеются следующие основные виды текстов: определения, теоремы,леммы и следствия, доказательства и обоснования, замечания, отступления, алгоритмы и примеры. Фактически, обычный связующий текст сведен к минимумув целях сокращения объёма книги.Определения никак специально не выделяются, поскольку составляют львинуюдолю основного текста книги.
Вместо этого курсивом выделяются определяющие вхождения терминов, а текст, соседствующий с термином, и есть определение.Выделения в тексте21Все определяющие вхождения вынесены в предметный указатель, помещённыйв конце книги. Таким образом, если при чтении попадается незнакомый термин, следует найти его определение с помощью указателя (или убедиться, чтоопределения в книге нет). В третьем издании математические термины в предметном указателе переведены на английский язык. Автор надеется, что предметный указатель послужит читателю как краткий толковый математическийрусско-аиглийский словарь.Формулировки теорем, лемм и следствий в соответствии с общепринятой в математической литературе практикой выделены курсивом.
При этом формулировке предшествует соответствующее ключевое слово: «теорема», «лемма» или«следствие». Как правило, утверждения не нумеруются, за исключением случаеввхождения нескольких однородных утверждений в один подраздел. Для ссылок на утверждения используются либо номера подразделов, в которых утверждения сформулированы, либо собственные имена утверждений. Дело в том, что вданном учебнике теоремами оформлены как простые утверждения, являющиесянепосредственными следствиями определений, так и глубокие факты, действительно заслуживающие статуса теоремы. В последнем случае приводится собственное имя (название теоремы), которое либо выносится в название подраздела(или раздела), либо указывается в скобках после слова «теорема».Доказательства относятся к предшествующим утверждениям, а обоснования — кпредшествующим алгоритмам. В учебнике практически нет недоказанных утверждений и приведенных без достаточного обоснования алгоритмов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
