Хаггарти Р. Дискретная математика для программистов ОНЛАЙН

Хаггарти Р. Дискретная математика для программистов. — 2-е изд. дополненное. — М., Техносфера, 2005. — 400с. Мир программирования
Элементарное введение в дискретную математику. Ни одно из немногочисленных изданий по этой дисциплине, вышедших на русском языке, не читается с таким удовольствием и пользой. В доступной и весьма увлекательной форме автор рассказывает о фундаментальных понятиях дискретной математики — о логике, множествах, графах, отношениях и булевых функциях. Теория изложена кратко и иллюстрируется многочисленными простыми примерами, что делает её доступной даже школьнику.

После каждой главы (начиная со второй) рассматривается приложение описанных методов к информатике.Книга будет полезна студентам, изучающим курс дискретной математики, а также всем желающим проникнуть в технику написания и проверки корректности алгоритмов, включая программистов-практиков.
Содержание
Указатель обозначений…………………………………………7
Предисловие……………………………………………………………….9
Глава 1.
Введение………………………………………………………………….11
1.1. Моделирование……………………………………………………..11
1.2. Псевдокод………………………………………………………….14
Набор упражнений 1……………………………………………………………19
Краткое содержание главы………………………………………………………21
Глава 2.
Логика и доказательство……………………………………………..23
2.1. Высказывания и логика…………………………………………….23
2.2. Предикаты и кванторы………………………………………27
2.3. Методы доказательств…………………………………………30
2.4. Математическая индукция………………………………………….32
Набор упражнений 2……………………………………………………..35
Краткое содержание главы……………………………………………….38
Приложение. Корректность алгоритмов……………………………………..39
Глава 3.
Теория множеств………………………………………………………….44
3.1. Множества и операции над ними……………………………………..44
3.2. Алгебра множеств…………………………………………………..51
3.3. Дальнейшие свойства множеств……………………………………..53
Набор упражнений 3…………………………………………………58
Краткое содержание главы………………………………………..61
Приложение. Система с базой знаний……………………………………63
Глава 4.
Отношения……………………………………………………….68
4.1. Бинарные отношения………………………………………….68
4.2. Свойства отношений…………………………………………73
4.3. Отношения эквивалентности и частичного порядка………………..77
Набор упражнений 4…………………………………………………82
Краткое содержание главы………………………………………………85
Приложение. Системы управления базами данных………………………………86
Глава 5
Функции……………………………………………………………… 91
5.1. Обратные отношения и композиция отношений……………. 91
5.2. Функции…………………………………………………………… 96
5.3. Обратные функции и композиция функций………………102
5.4. Принцип Дирихле………………………………………………… 105
Набор упражнений 5………………………………………………….. 108
Краткое содержание главы………………………………………….. 112
Приложение. Языки функционального программирования……. 113
Глава 6.
Комбинаторика……………………………………………………. 117
6.1. Правила суммы и произведения……………………………….. 117
6.2. Комбинаторные формулы………………………………………. 120
6.3. Бином Ньютона………………………………………………….. 128
Набор упражнений 6………………………………………………….. 131
Краткое содержание главы………………………………………….. 135
Приложение. Эффективность алгоритмов………………………… 136
Глава 7.
Графы…………………………………………………………………. 141
7.1. Графы и терминология………………………………………….. 142
7.2. Гамильтоновы графы……………………………………………. 147
7.3. Деревья…………………………………………………………….. 152
Набор упражнений 7………………………………………………….. 158
Краткое содержание главы………………………………………….. 163
Приложение. Сортировка и поиск………………………………….. 165
Глава 8.
Ориентированные графы…………………………………….. 171
8.1. Ориентированные графы……………………………………….. 171
8.2. Пути в орграфах…………………………………………………. 175
8.3. Кратчайший путь………………………………………………… 181
Набор упражнений 8………………………………………………….. 184
Краткое содержание главы………………………………………….. 187
Приложение. Коммуникационные сети……………………………. 189
Глава 9.
Булева алгебра……………………………………………………. 194
9.1. Булева алгебра……………………………………………………. 194
9.2. Карта Карно……………………………………………………… 200
9.3. Функциональные схемы…………………………………………. 205
Набор упражнений 9………………………………………………….. 208
Краткое содержание главы………………………………………….. 211
Приложение. Проектирование 2-битного сумматора……………. 212
Решения упражнений……………………………………………217
Дополнение к первому изданию…………………………….275
Д.1. Генератор случайных графов…………………………………. 275
Д. 1.1. Алгоритм построения случайного неориентированного графа………………………………………………….. 277
Д. 1.2. Алгоритм построения случайного ориентированного
графа………………………………………………………… 278
Д. 1.3. Алгоритм построения случайного ориентированного
бесконтурного графа……………………………………… 279
Д.2. Связность в графах…………………………………………….. 281
Д.2.1. Алгоритм Уоршелла, вычисляющий матрицу связности… 282
Д.2.2. Выделение компонент связности……………………….. 286
Д.З. Эйлеровы циклы………………………………………………… 288
Д.3.1. Алгоритм построения эйлерова цикла в графе………. 289
Д.3.2. Алгоритм Терри…………………………………………… 292
Д.4. Операции над множествами ………………………………….. 294
Д.4.1. Объединение множеств…………………………………… 300
Дополнение ко второму изданию …………………………. 305
Предисловие………………………………………………… 305
Д.5. Дополнительные главы дискретной математики………….. 305
Введение…………………………………………………….. 305
Д.5.1. Исчисление и оценка конечных сумм………………….. 306
Набор упражнений Д.5.1 …………………………………. 317
Д.5.2. Элементы теории рекурсии……………………………… 318
Набор упражнений Д.5.2…………………………………. 332
Д.5.3. Конечные разности. Разностный и суммирующий
операторы ………………………………………………….. 333
Набор упражнений Д.5.3…………………………………. 344
Д.5.4. Производящие функции и комбинаторные подсчеты.. 345
Набор упражнений Д.5.4…………………………………. 359
Д.6. Общая проблема перебора и некоторые точные методы
решения задач целочисленного программирования……….. 359
Введение…………………………………………………….. 359
Д.6.1. Понятие т-мерного евклидова целочисленного пространства ………………………….. 361
д.6.2. Общая постановка, типизация и примеры задач целочисленного программирования…………. 362
Д.6.3. NP-полные задачи и проблема перебора………………. 366
Д.6.4. Обзор точных методов решения задач целочисленного программирования……………….. 368
Д.6.5. Точное рещение задачи одномерной упаковки методом динамического программирования………. 372
Д.6.6. Метод ветвей и границ и задача коммивояжера…….. 381
Набор упражнений Д.6…………………………………….392
Литература………………………………………………………….395
Предметный указатель…………………………………………397

загрузка...
Поделиться ссылкой:
  • Добавить ВКонтакте заметку об этой странице
  • Мой Мир
  • Facebook
  • Twitter
  • LiveJournal
  • В закладки Google
  • Яндекс.Закладки
  • Сто закладок
  • Blogger
  • Блог Li.ру
  • Блог Я.ру
  • Одноклассники
  • RSS

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Наш сайт находят по фразам: