Какая книга лучше всего подходит для изучения дискретной математики?

Конкретная математика: основа компьютерных наук, написанная самим Дональдом Кнутом!

Знание дискретной математики необходимо, чтобы научиться доказывать правильность и определять сложность алгоритмов и структур данных. Вас научат этому в книгах по Algo/DS, но вы можете получить математические навыки, только практикуя только дискретную математику.

Книга Кнута очень хороша для этого. Но ИМХО, он вам понадобится только для расширенных доказательств в DS/Algorithms.

Для новичка было бы здорово пройтись по «Гримальди» http://www.amazon.com/Discrete-Combinatorial-Mathematics-Applied-Introduction/dp/0201199122 , а затем быстро перейти к алгоритмам.

В противном случае вы продолжите углубляться в дискретную математику и никогда не дойдете до алгоритмов/DS.

Помните, дискретная математика не учит вас, как разрабатывать алгоритмы или структуры данных. Этого можно достичь, только практикуя проблемы с алгоритмами на topcoder, acm icpc, spoj и т. д. и читая книги по Algos/DS или курсы по ним.

Мои 2 цента.

Очень хорошим учебником по дискретной математике для студентов бакалавриата является книга Кеннета Розена под названием «Дискретная математика и ее приложения» .

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

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

Есть много разных областей дискретной математики и много хороших книг.

существует теория графов от Diestel, у которой есть бесплатная версия в формате pdf, доступная по адресу

diestel-graph-theory.com

есть генерирующая функционалология от Уилфа, бесплатная версия в формате pdf на

math.upenn.edu/~wilf/DownldGF.html

Другие хорошие книги включают перечислительную комбинаторику 1 и 2 Ричарда П. Стэнли (книга, достаточно плотная, чтобы в каждой из них было хотя бы по одному курсу анализа и алгебры).

при этом для более вводных экспозиций с точки зрения ожидаемой математической зрелости я бы предложил поискать в Интернете и просмотреть различные конспекты лекций типа «введение в комбинаторику» или «математика для компьютерных ученых». Я обнаружил, что заметки MIT OCW «Математика для компьютерных ученых» были довольно хорошими, когда я просматривал их несколько лет назад.

ocw.mit.edu/courses/электротехника-и-информатика-наука...

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

Кроме того, если вы хотите еще глубже погрузиться в дискретную математику/комбинаторику, стоит изучить немного математических основ в других областях математики. Комплексный анализ, реальный анализ (на уровне хотя бы бэби-рудина, а может быть, и до функционального анализа), может быть, какая-то вероятность до уровня формулировки его теории меры, и хотя бы капелька абстрактной алгебры. Затем вы можете заняться такими вещами, как изучение комбинаторики случайных процессов (отлично подходит для анализа рандомизированных алгоритмов) и рассмотреть интересные проблемы, такие как перколяция.

Возможно, есть и другие вещи, которые я должен предложить, но суть в том, что дискретная математика доступна без особого фона, но также вознаграждает вас за обогащение этого математического фона некоторыми удивительно красивыми вещами, которые 1) потрясающие и забавные 2) полезные.

Мне очень нравится дискретная математика Нормана Биггса . Я бы не рекомендовал второе издание. Лучше приобретите первое издание («исправленное» первое издание, если сможете). Текст претендует на самодостаточность (мне так кажется).

Поскольку в Интернете не так много информации об этом издании текста (предварительный просмотр на Amazon — это второе издание), вот схема:

Часть 1: Числа и счет

1. Целые числа (упорядочение, рекурсия, индукция, делимость, НОД, факторизация)
2. Функция и подсчет (сюръекции, инъекции, биекции, принцип сортировки, конечное против бесконечного)
3. Принципы счета (функция Эйлера, принцип сложения, слова, перестановки)
4. Подмножества и планы (биномиальная теорема, принцип решета, планы,$t$-конструкции)
5. Разбиение (отношения эквивалентности, распределения, полиномиальные числа, классификация перестановок)
6. Модульная арифметика (сравнения,$\mathbb{Z}_m$, циклические конструкции, латинские квадраты)

Часть 2: Графики и алгоритмы:

1. Алгоритмы и эффективность (доказательство правильности,$O$запись, сравнение, сортировка)
2. Графы (изоморфизм графов, валентность, пути, циклы, деревья, раскраска, жадный алгоритм)
3. Деревья, сортировка, поиск (подсчет листьев, алгоритмы сортировки, остовные деревья, задача MST, поиск в глубину, поиск в ширину, поиск кратчайшего пути)
4. Двудольные графы (отношения, раскраски ребер, паросочетания, максимальные паросочетания, трансверсали)
5. Орграфы, сети, потоки (критические пути, потоки и разрезы, теорема о максимальном потоке и минимальном разрезе, алгоритм разметки)
6. Рекурсивные методы (линейная рекурсия, рекурсивное деление пополам, рекурсивная оптимизация, динамическое программирование)

Часть 3: Алгебраические методы:

1. Группы (аксиомы, изоморфизмы, циклические группы, подгруппы, смежные классы)
2. Группы перестановок (определения, орбиты, стабилизаторы, размер/количество орбит, представление групп перестановками)
3. Кольца, поля, многочлены (алгоритм деления, алгоритм Евклида, факторизация)
4. Конечные поля (порядок, конструкция, теорема о примитивных элементах, конечная геометрия, проективные плоскости, существование)
5. Исправление ошибок (слова, коды, ошибки, линейные коды, циклические коды)
6. Производящие функции (степенные ряды, дроби, биномиальная теорема, линейная рекурсия)
7. Разделы положительного целого числа (сопряженные разделы, производящие функции, загадочное тождество)
8. Симметрия и счет (циклическая и двугранная симметрия, трехмерная симметрия, неэквивалентные раскраски, раскраски и производящие функции, теорема Полиа)

Мне очень нравится «Дискретная математика» Росса и Райта:

Математическое мышление: решение задач и доказательства.

Джон П. Д'Анджело, Дуглас Б. Уэст.

Доступно на Амазонке .

Предполагается, что это введение в математические доказательства. Таким образом, он не ограничивается дискретной математикой. Но это очень хорошая работа для дискретной математики. Вы также увидите некоторые доказательства в реальном анализе; но вы можете сосредоточиться только на дискретной части, игнорируя это.

Мне очень помогла книга «Элементы дискретной математики» К. Лью Лю .

Он находится на очень базовом уровне и отлично подходит, если вы ищете введение в дискретную математику.

Лучшие книги, насколько я знаю, это эти две:

Дискретная математика Норман Л. Биггс

или

Дискретная математика и ее приложения Кеннет Х. Розен

Лучшей книгой для изучения дискретной математики является " Дискретная математика и структуры " Сатиндера Бала Гупты . Она опубликована издательством University Science Press . Язык книги очень прост. Она содержит сотни решенных и нерешенных задач с подсказками.

Основы дискретных математических структур, 3-е издание. Он написан в соответствии с ACM-Curriculum, содержит множество вопросов уровня GATE и написан профессором компьютерных наук.