Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике ОНЛАЙН

Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике: Учеб. пособие. — 3-е изд., перераб. — М.: ФИЗМАТЛИТ, 2005. — 416 с.
В пособие включены задачи и упражнения по конечнозначным логикам (в том числе по алгебре логики), по теории автоматов, теории алгоритмов, теории графов и сетей, теории кодирования, комбинаторике, минимизации булевых функций и синтезу схем и формул, реализующих булевы функции. Имеются задачи, предназначенные для первоначальной проработки и освоения методов дискретной математики, а также задачи для углубленного изучения предмета.

загрузка...

Второе издание — 1992 г.
Для студентов и преподавателей университетов и технических вузов, в которых изучается дискретная математика.
ОГЛАВЛЕНИЕ
Предисловие к третьему изданию ……………………………….. 6
Предисловие ко второму изданию ……………………………….. 7
Глава I. Способы задания и простейшие свойства функций алгебры логики
§ 1. Функции алгебры логики и способы их задания. Операция суперпозиции………………….. 9
1. Основные понятия и факты, связанные с булевым кубом и булевыми функциями (9). 2. Элементы булева куба. Первичные представления о булевых функциях (15). 3. Формулы. Реализация булевых функций формулами (23). 4. Двойственные функции. Принцип двойственности (31). 5. Фиктивные и существенные переменные. Отождествление переменных у булевых функций (33).
§ 2. Специальные представления булевых функций ……………….. 39
1. Разложения булевых функций по переменным. Совершенные дизъюнктивная и конъюнктивная нормальные формы (39). 2. Дизъюнктивные и конъюнктивные нормальные формы (47). 3. Полиномы Жегалкина (52).
Глава II. Замкнутые классы и полнота систем функций алгебры логики
§ 1. Понятия функциональной замкнутости и полноты …………………………..60
§ 2. Класс самодвойственных функций ……………………………………..64
§ 3. Класс линейных функций …………………………………68
§ 4. Классы функций, сохраняющих константы ………………………….72
§ 6. Полнота и замкнутые классы …………………………………..81
Глава III. k-значные логики
§ 1. Представление функций k-значных логик формулами …………. 88
1. Элементарные функции k-значных логик и соотношения между ними (88). 2. Разложение функций k-значных логик в первую и вторую формы (91).
§ 2. Замкнутые классы и полнота в k-значных логиках…………… 92
1. Некоторые замкнутые классы k-значных логик. Представление функций из Рк полиномами по модулю k (92). 2. Исследование систем функций k-значной логики на полноту (97).
Глава IV. Ограниченно-детерминированные функции
§ 1. Отображения последовательностей …………………………. 102
1. Основные понятия и факты, связанные с заданием детерминированных функций (102). 2. Типовые примеры (105). 3. Выявление свойства детерминированности функции. Эквивалентность детерминированных функций. Остаточные функции (111). 4. Выявление свойства ограниченной детерминированности функции. Порожденные и автономные функции. Строение классов эквивалентности. Мощности некоторых множеств отображений (119).
§ 2. Диаграммы, таблицы, канонические уравнения, схемы……….. 126
1. Диаграммы Мура, канонические таблицы и канонические уравнения (126). 2. Операции над детерминированными функциями (145). 3. Реализация ограниченно-детерминированных функций схемами (159). 4. Замкнутые классы и полнота в множествах детерминированных и ограниченно-детерминированных функций (171).
Глава V. Элементы теории алгоритмов
§ 1. Машины Тьюринга и операции над ними. Функции, вычислимые на машинах Тьюринга ………….. 178
1. Простейшие свойства машин Тьюринга (178). 2. Операции над машинами Тьюринга (186). 3. Вычислимые функции (190).
§ 2. Классы вычислимых и рекурсивных функций ………………. 195
1. Операции суперпозиции, примитивной рекурсии и минимизации (195). 2. Некоторые специальные свойства рекурсивных функций (201).
Глава VI. Графы и сети
§ 1. Основные понятия теории графов ………………………….. 203
1. Простейшие свойства графов. Изоморфизм графов (203). 2. Ориентированные графы (210).
§ 2. Планарность и раскраска графов …………………………… 215
§ 3. Деревья и сети……………………………………………. 219
1. Корневые деревья (219). 2. Двухполюсные сети (223).
Глава VII Элементы теории кодирования
§ 1. Алфавитное кодирование. Критерий однозначности кодирования . 230
§ 2. Коды с минимальной избыточностью …………………………235
§ 3. Самокорректирующиеся коды………………………………..241
1. Расстояние Хэмминга, шары, сферы и циклы в n-мерном кубе (241). 2. Коды, обнаруживающие и исправляющие ошибки (244).
§ 4. Линейные коды ……………………………………………. 249
Глава VIII. Элементы комбинаторики
§ 1. Перестановки и сочетания. Свойства биномиальных коэффициентов …………… 253
§ 2. Формула включений и исключений ………………………….. 262
§ 3. Возвратные последовательности, производящие функции, рекуррентные соотношения…….265
§ 4. Теория Пойа ………………………………………………. 273
§ 5. Асимптотические оценки и неравенства ……………………… 277
§ 6. Оценки в теории графов и сетей …………………………….. 284
Глава IX Минимизация булевых функций
§ 1. Структура граней n-мерного куба. Покрытия и тесты для таблиц 290
§ 2. Методы построения сокращенной д. н. ф ……………………… 296
§ 3. Методы построения тупиковых, минимальных и кратчайших д.н.ф………………….301
Глава X. Реализация булевых функций схемами и формулами
§ 1. Схемы из функциональных элементов ……………………….. 306
§ 2. Контактные схемы и формулы……………………………….312
Ответы, указания, решения ………………………………….. 324
Список литературы………………………………………….. 412
Предметный указатель ………………………………………. 414
загрузка...
Поделиться ссылкой:
  • Добавить ВКонтакте заметку об этой странице
  • Мой Мир
  • Facebook
  • Twitter
  • LiveJournal
  • В закладки Google
  • Яндекс.Закладки
  • Сто закладок
  • Blogger
  • Блог Li.ру
  • Блог Я.ру
  • Одноклассники
  • RSS

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

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

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