E-Book Overview
Основополагающее введение в дискретную математику, без знания которой невозможно успешно заниматься информатикой и программированием. Ни одно из многочисленных изданий по этой дисциплине, вышедших на русском языке, не читается с таким удовольствием и пользой. В доступной и весьма увлекательной форме автор рассказывает о фундаментальных понятиях дискретной математики — о логике, множествах, графах, отношениях и булевых функциях. Теория изложена кратко и иллюстрируется многочисленными простыми примерами, что делает ее доступной даже школьнику. После каждой главы (начиная со второй) рассматривается приложение описанных методов к информатике. Дополнения в издании на русском языке посвящены актуальным задачам теории графов, рекурсивным алгоритмам, общей проблеме перебора и задачам целочисленного программирования. Книга будет полезна студентам, изучающим курс дискретной математики, а также всем желающим проникнуть в технику написания и проверки корректности алгоритмов, включая программистов-практиков.
E-Book Content
программирования Р. ХАГГАРТИ
Дискретная математика для программистов Издание 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