дискретная математика для программистов

программирования Р. ХАГГАРТИ Дискретная математика для программистов Издание 2−е, исправленное Перевод с английского под редакцией С.А. Кулешова с дополнениями А.А. Ковалева, В.А. Головешкина, М.В. Ульянова Допущено УМО вузов РФ по образованию в области прикладной математики в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлению подготовки «Прикладная математика» ТЕХНОСФЕРА Москва 2012 УДК 519.854 ББК 22.176 Х13 Х13 Хаггарти Р. Дискретная математика для программистов Издание 2-е, исправленное Москва: Техносфера, 2012. – 400 с., ISBN 978-5-94836-303-5 Основополагающее введение в дискретную математику, без знания которой невозможно успешно заниматься информатикой и программированием. Ни одно из многочисленных изданий по этой дисциплине, вышедших на русском языке, не читается с таким удовольствием и пользой. В доступной и весьма увлекательной форме автор рассказывает о фундаментальных понятиях дискретной математики – о логике, множествах, графах, отношениях и булевых функциях. Теория изложена кратко и иллюстрируется многочисленными простыми примерами, что делает ее доступной даже школьнику. После каждой главы (начиная со второй) рассматривается приложение описанных методов к информатике. Дополнения в издании на русском языке посвящены актуальным задачам теории графов, рекурсивным алгоритмам, общей проблеме перебора и задачам целочисленного программирования. Книга будет полезна студентам, изучающим курс дискретной математики, а также всем желающим проникнуть в технику написания и проверки корректности алгоритмов, включая программистов-практиков. УДК 519.854 ББК 22.176 © Pearson Education Limited 2002 This translation of DISCRETE MATHEMATICS FOR COMPUTING, First Edition is published by arrangement with Pearson Education Limited. © 2012, ЗАО «РИЦ «Техносфера», перевод на русский язык, дополнения, оригинал-макет, оформление ISBN 978-5-94836-303-5 ISBN 0-201-73047-2 (англ.) óÏÄÅÒÖÁÎÉÅ õËÁÚÁÔÅÌØ ÏÂÏÚÎÁÞÅÎÉÊ ................................................ ðÒÅÄÉÓÌÏ×ÉÅ .................................................................. 6 9 çÌÁ×Á 1. ÷×ÅÄÅÎÉÅ ........................................................................ 1.1. íÏÄÅÌÉÒÏ×ÁÎÉÅ ............................................................ 1.2. ðÓÅ×ÄÏËÏÄ ................................................................... îÁÂÏÒ ÕÒÁÖÎÅÎÉÊ 1 ........................................................... ëÒÁÔËÏÅ ÓÏÄÅÒÖÁÎÉÅ ÇÌÁ×Ù.................................................. 11 11 14 19 21 çÌÁ×Á 2. ìÏÇÉËÁ É ÄÏËÁÚÁÔÅÌØÓÔ×Ï ............................................. 2.1. ÷ÙÓËÁÚÙ×ÁÎÉÑ É ÌÏÇÉËÁ ................................................. 2.2. ðÒÅÄÉËÁÔÙ É Ë×ÁÎÔÏÒÙ ................................................. 2.3