Новиков Ф.А. Дискретная математика для программистов (860615), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Общееколичество изменений значительно больше количества страниц. Если пользоваться жаргоном программистов, которым адресована эта книга, то можно сказать, что проведён «рефакторипг» всего материала.Третье издание прошло профессиональное научное редактирование, за что авторвыражает глубокую благодарность научному редактору.Ф. А. НовиковПредисловие ко второмуизданиюВ 2000 году издательство «Питер» выпустило в свет учебник Ф. А. Новикова«Дискретная математика для программистов». Книга оказалась удачной, о чёмсвидетельствуют тиражи и письма читателей.

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

Сохранена ориентация на программистов: описание объектов дискретной математики в большинстве случаев доводится до кодаалгоритмов работы с этими объектами. Устранены замеченные ошибки: за тригода автор, рецензенты, студенты и читатели заметили более 200 фактическихнеточностей и опечаток в книге — все замеченные опечатки устранены. Измененасистема обозначений с целью устранения излишних вольностей.В первом издании книги было 12 глав, во втором их десять. Сокращение количества глав по сравнению с первым изданием не означает сокращения объёмарассматриваемого материала. Это продиктовано желанием автора сделать структуру книги более уравновешенной.

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

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

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

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

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

Поучительно также краткое, но в большинстве случаев достаточноубедительное, обоснование правильности предлагаемых алгоритмов.Профессор, д.т.и., чл.-корр. РАНС. С.ЛавровВведениеВ этой книге рассматриваются некоторые элементарные понятия «дискретной»,или «конечной», математики, то есть математики, прежде всего изучающей конечные множества и различные структуры па них. Это означает, что понятиябесконечности, предела или непрерывности не являются предметом изучения, хотя могут использоваться как вспомогательные средства. Дискретная математикаимеет широкий спектр приложений, прежде всего в областях, связанных с информационными технологиями и компьютерами. В самом первоначальном, нынередко используемом названии компьютера — «электронная цифровая вычислительная машина» - слово «цифровая» указывает на принципиально дискретныйхарактер работы данного устройства.

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

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

Липского «Комбинаторика для программистов» [8],перевод которой выдержал уже дьа издания в России, и всеобъемлющую энциклопедию Д. Кнута «Искусство программирования для ЭВМ» [14]-[16]. Перваяиз упомянутых книг очень невелика по объёму и в значительной степени пересекается по выбранному материалу с данным учебником. Вторая отличается16Введениемаксимальной глубиной изложения и большим объёмом, но не затрагивает некоторых важных для программистов разделов дискретной математики.

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

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

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

Разбор доказательств приведенных утверждений и выполнение упражнений позволят студенту овладеть методами дискретной математики, наиболее употребительными при решении практических задач.3. Пополнить запас примеров нетривиальных алгоритмов. Изучение алгоритмоврешения типовых задач дискретной математики и способов представления математических объектов в программах абсолютно необходимо практикующемупрограммисту, поскольку позволяет уменьшить трудозатраты на «изобретениевелосипеда» и существенно обогащает навыки конструирования алгоритмов.Структура книгиКнига содержит 10 глав, которые, фактически, делятся на три группы.

Первая группа, несколько большая по объёму (главы 1, 2 и 5), содержит самыеобщие сведения из основных разделов дискретной математики. Доля алгоритмов в главах первой группы несколько меньше, а доля определений несколькоИспользуемые обозначения17больше, чем во второй и третьей группах. В второй группе (главы 3, 4 и 6)собраны различные специальные разделы, которые можно включать или не включать в учебный курс в зависимости от конкретных обстоятельств. Третья группа глав (главы 7-10) целиком посвящена теории графов, поскольку связанные с пей вопросы (в частности, алгоритмы над графами) являются разделами дискретной математики, наиболее широко применяющимися в практическомпрограммировании.Главы делятся на разделы, которые, в свою очередь, делятся па подразделы.

Характеристики

Список файлов книги