Электронная библиотека
Программисту веб-дизайнеру
Другие материалы
Бесплатная электронная библиотека. Скачать книги DJVU, PDF бесплатно
С.В. Яблонский, Дискретная математика
• Бесплатно скачать книгу, объем 7.36 Мб, формат .djvu (полный базовый курс, 1986)
ЧАСТЬ I ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
Глава 1. Алгебра логики
§ 1. Функции алгебры логики
§ 2. Формулы. Реализация функций формулами
§ 3. Эквивалентность формул. Свойства элементарных
функций. Принцип двойственности
§ 4 Разложение булевых функций по переменным. Совершенная дизъюнктивная нормальная форма
§ 5. Полнота и замкнутость
§ 6. Важнейшие замкнутые классы, теорема о полноте
§ 7. Представление о результатах Поста
Глава 2. k-значная логика
§ 1. Функции k-значной логики. Формулы и реализация функций формулами
§ 2. Примеры полных систем
§ 3. Распознавание полноты. Теорема о полноте
§ 4. Некоторые свойства существенных функций. Критерий полноты
§ 5. Особенности k-значных логик
Глава 3. Ограниченно-детерминированные (автоматные)
функции с операциями
§ 1. Детерминированные функции
§ 2. Задание детерминированных функций при помощи деревьев. Вес дерева
§ 3. Ограниченно-детерминированные функции и способы их задания
§ 4. Операции над о.-д. функциями
§ 5. Примеры полных систем
§ 6. О соотношении операций
Глава 4. Вычислимые функции
§ 1. Машины Тьюринга
§ 2. Один метод построения машип Тьюринга
§ 3. Машинные коды и их преобразования
§ 4. Вычислимые функции
§ 5. Операции С и Пр
§ 6. Вычислимые функции и операции С и Пр
§ 7. Формула Клини. Частичная рекурсивность вычислимых функций. Примеры полных систем
ЧАСТЬ II КОМБИНАТОРНЫЙ АНАЛИЗ
§ 1. Комбинаторные объекты и комбинаторные числа
§ 2. Простейшие свойства комбинаторных объектов и чисел
§ 3. Методы изучения комбинаторных объектов и чисел
§ 4. Оценки а асимптотики для комбинаторных чисел
ЧАСТЬ III ГРАФЫ И СЕТИ
Глава 1. Графы
§ 1. Реализация в евклидовом пространстве. Изоморфизм
§ 2. Оценка числа трафов
Глава 2. Сети
§ 1. Сети и их свойства
§ 2. Оценка числа сетей
§ 3. Двухполюсные сети из двухобъектных наборов
§ 4. Пи-сети
ЧАСТЬ IV
ТЕОРИЯ КОДИРОВАНИЯ
§ 1. Критерий однозначности декодирования
§ 2. Алгоритм распознавания однозначности декодирования
§ 3. Об одном свойстве взаимно однозначных кодов
§ 4. Коды с минимальной избыточностью
§ 5. Самокорректирующиеся коды
ЧАСТЬ V НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ
Глава 1. Дизъюнктивные нормальные формы
§ 1. Понятие д. н. ф. Проблема минимизации булевых Функций
§ 2. Упрощение д. н. ф. и тупиковые д. н. ф. (относительно упрощения)
§ 3. Постановка задачи в геометрической форме
§ 4. Сокращенная д. и. ф
§ 5. Тупиковость на основе геометрических представлений. Методы построения тупиковых д. н. ф.
§ 6. Некоторые однозначно получаемые д. н. ф.
§ 7. Понятие локального алгоритма
Глава 2. Синтез схем из функциональных элементов
§ 1. Понятие схемы из функциональных элементов
§ 2. Проблема синтеза схем из Ф. Э.
§ 3. Элементарные методы синтеза
§ 4. Нижняя оценка для L(n)
§ 5. Оптимальный по порядку метод синтеза схем из
Ф. Э. (метод Шеннона)
§ 6. Асимптотически наилучший метод синтеза схем из Ф. Э. (метод Лупанова)
§ 7. Синтез сумматора
§ 8. Синтез схем из Ф. Э,, реализующих симметрические функции
Краткая аннотация книги
Книга является введением в дискретную математику - раздел прикладной математики, бурно развивающийся в последние годы и являющийся базой для математической кибернетики. Она написана на основе курса лекций, читавшегося автором в течение ряда лет на факультете вычислительной математики и кибернетики Московского государственного университета. Предназначается студентам факультетов прикладной математики, аспирантам, а также инженерам и специалистам, работающим в области прикладной математики.
Дискретная математика - часть математики, которая зародилась в глубокой древпости. Как говорит само заглавие, главной ее спецификой является дискретность, т. е. антипод непрерывности. В широком смысле дискретная математика включает в себя и такие сложившиеся разделы математики, как теория чисел, алгебра, математическая логика и ряд разделов, которые наиболее интенсивно стали развиваться в середине этого века в связи с внедрением ЭВМ. Научно-технический прогресс поставил проблему изучения сложных управляющих систем. В узком смысле дискретная математика ограничивается только этими новыми разделами. Именно так это понимается и в данной книге. К упомянутым новым разделам мы относим: теорию функциональных систем; теорию графов и сетей; теорию кодирования; комбинаторный анализ; целочисленное программирование и т. п.
Дискретная математика сегодня является не только фундаментом математической кибернетики, но и важным звеном математического образования. Книга содержит материал, соответствующий двум типам программ курса "Дискретная математика": стандартной программе для факультетов прикладной математики и кибернетики большинства университетов и программе соответствующего курса, читаемого в МГУ. Эти программы не ставят целью дать большое количество материала фактического и имеющего спрос в данное время. Чрезмерная детализация и привязывание программы к специальным фактам опасны тем, что лет через 10-15 (а это как раз время активной деятельности обучаемых сейчас студентов) появятся новые факты, а старые частично утратят свою значимость. Ввиду этого главная задача курса - это обучение методам и мышлению, характерным для дискретной математики. Материал, вошедший в эту книгу, знакомит читателя с узловыми задачами из нескольких разделов дискретной математики и ее приложений. Он подобран таким образом, чтобы сократить число необходимых понятий до минимума и, с другой стороны, дать небольшое количество (10-15) серьезных теорем с непохожими доказательствами, а также познакомить с применениями понятия алгоритма, владение которым особенно важно для специалистов в области прикладной математики. Содержание книги охватывает почти все основные разделы дискретной математики. При ее написании автору пришлось усовершенствовать целый ряд доказательств, в ряде случаев дать новые доказательства, которые публикуются здесь впервые.
Изложение многих вопросов из перечисленных разделов не всегда ведется па абстрактной основе: здесь широко используется геометрический язык и содержательные интерпретации. Это позволяет сочетать в построениях наглядность и известную строгость. Надо иметь в виду, что в математических статьях существуют две крайности: пренебрежение строгостью изложения и доведение строгости до абсурда. Обе указашше тенденции одинаково опасны. Строгость изложения должна соответствовать рассматриваемой задаче (и уровню аудитории), подобно тому как в приближенных вычислениях число значащих цифр получаемых результатов должно соответствовать точности исходных данных. Слишком "большой" запас строгости в этом смысле подобен вычислениям со значительным числом дополнительных разрядов. Данная кттига рассчитана на студентов, аспирантов и научных сотрудников.
Второе издание книги отличается от первого наличием дополнительной части по комбинаторному анализу, некоторой переработкой остальных частей и устранением всех вамеченных погрешностей. В этой работе автору помогли замечания многих математиков, которым автор весьма призпателен. Особую благодарность автор выражает редакторам первого и второго изданий Б, П. Липатову и В. М. Храпченко, проделавшим большую работу по улучшению изложения материала.
Примечание. Сохраняйте книги на мобильный телефон и скачивайте их с Вашего телефона на компьютер. Удобное скачивание книг через мобильный телефон (в память телефона) и на Ваш компьютер через мобильный интерфейс. Быстрый Интернет без излишних тэгов. Материал носит неофициальный характер и приведен для ознакомления. Прямые ссылки на файлы книг запрещены.