Авдошин С., Дискретная математика. Алгоритмы: теория и практика
ДМК Пресс, 2019 г., 978-5-97060-688-9
Наличие в интернет-магазинах
Описание книги
Книга содержит основные сведения из теории алгоритмов: частично-рекурсивные функции, машины Тьюринга, а также элементы комбинаторики, графы и алгоритмы на графах, потоки в транспортных сетях, рекуррентные последовательности, частично упорядоченные...
Купить эту книгу можно в интернет-магазинах
- 1474 руб.
- 2409 руб.
- 2409 руб.
Страница товара выбранного интернет-магазина откроется в новом табе
Поделиться ссылкой на книгу
Содержание книги
Предисловие
Введение
1. Множество
2. Функция
3. Отношение
4. Отношение эквивалентности
5. Каноническое разложение функции
6. Мощность множества. Счетные и несчетные
множества
7. Мощность континуума
8. Кардинальные числа. Сравнение мощностей
Часть I. ТЕОРИЯ АЛГОРИТМОВ
Глава 1. Частично рекурсивные функции
1.1. Арифметические функции и операции над ними
1.2. Примитивно рекурсивные функции
1.3. Функции, представимые термами
1.4. Конечная сумма и произведение
1.5. Примитивно рекурсивные предикаты
1.6. Ограниченные кванторы
1.7. Ограниченный оператор u
1.8. Подстановка функций в предикат
1.8.1. Кусочное задание функции
1.8.2. Примитивная рекурсивность некоторых
функции и предикатов
1.9. Частично рекурсивные функции
Глава 2. Машины Тьюринга
2.1. Вычисления на машинах Тьюринга
2.2. Синтез машин Тьюринга
2.2.1. Композиция машин
2.2.2. Ветвление машин
2.2.3. Итерация машины
2.3. Машины Тьюринга в однобуквенном алфавите
2.4. Правильно вычислимые функции
2.4.1. Суперпозиция правильно вычислимых
функций
2.4.2. Примитивная рекурсия правильно
вычислимых функций
2.4.3. Минимизация правильно вычислимых
функций
2.4.4. Правильная вычислимость частично
рекурсивных функций
2.5. Частичная рекурсивность правильно
вычислимых функций
2.5.1. Геделева нумерация ситуаций машины
Тьюринга
2.5.2. Функции программы машины Тьюринга
2.5.3. Функции вычисления по программе машины
Тьюринга
2.5.4. Функция ситуаций машины Тьюринга
2.6. Универсальная частично рекурсивная
функция
2.6.1. Геделева нумерация машин Тьюринга
2.6.2. Функции ситуации машины Тьюринга с
номером k
2.6.3. Построение универсальной функции
2.7. Теорема Клини о неподвижной точке и теорема
Раиса.
2.8. Сложность алгоритмов
Глава 3. Рекурсивная перечислимость и
разрешимость
3.1. Общерекурсивные функции и предикаты
3.2. Нумерации наборов натуральных чисел
3.2.1. Нумерации пар натуральных чисел
3.2.2. Нумерация наборов натуральных чисел
длины k
3.2.3. Нумерация конечных последовательностей
натуральных чисел
3.3. Рекурсивно перечислимые множества
3.4. Рекурсивно перечислимые множества наборов
натуральных чисел
3.5. Общерекурсивные предикаты
3.6. Общерекурсивные множества наборов
натуральных чисел
3.7. Функции с рекурсивно перечислимым графиком
3.8. Примеры алгоритмически неразрешимых
проблем
3.9. Варианты уточнения понятия алгоритма
3.9.1. Ассоциативные исчисления
3.9.2. Системы подстановок Туэ
3.9.3. Алгоритмическая неразрешимость проблемы
тождества полугрупп и логики предикатов
3.9.4. Грамматики
3.9.5. Продукции Поста
3.9.6. Нормальные алгоритмы Маркова
3.9.7. Операторные алгоритмы
Глава 4. Гедель о неполноте формальных систем
4.1. Аксиоматическая арифметика
4.2. Алгоритмическая неразрешимость
содержательной арифметики
4.3. Алгоритмическая неразрешимость логики
предикатов второго порядка
4.4. Нумерическая выразимость
Часть II. АЛГОРИТМЫ НА ГРАФАХ Глава 5. Способы
задания графов
5.1. Графы, мультиграфы, псевдографы
5.2. Задание графов
5.3. Операции над графами
5.4. Маршруты, цепи, циклы, связность
5.4.1. Алгоритм построения кратчайшей цепи в
графе
5.4.2. Алгоритм поиска кратчайшего пути в
ориентированном графе
Глава 6. Обходы графов
6.1. Эйлеровы графы
6.2. Алгоритм построения эйлерова цикла
6.3. Полные циклы и последовательности де
Брюйна
6.4. Гамильтоновы графы
6.5. Коды Грея
Глава 7. Деревья
7.1. Деревья и лес
7.2. Характеристические свойства деревьев
7.3. Каркасы и хорды в связном графе
Глава 8. Циклы в графах
8.1. Линейное пространство двоичных наборов
8.2. Линейное пространство подграфов данного
графа
8.3. Подпространство четных подграфов
8.4. Циклический ранг графа
8.5. Матричная теорема о деревьях
Глава 9. Двудольные графы и паросочетания
9.1. Двудольные графы
9.2. Паросочетания
9.3. Алгоритм построения совершенного
паросочетания
Для двудольного графа
9.4. Системы различных представителей
9.5. Сети Петри
9.5.1. Описание сети Петри
9.5.2. Определение сети Петри
Глава 10. Пленарные графы
10.1. Плоские графы
10.2. Формула Эйлера для плоских графов
Глава 11. Раскраска графов
11.1. Хроматическое число и хроматический класс
11.2. Раскраска вершин
11.3. Верхняя и нижняя оценки хроматического
числа
11.3.1. Внутренне устойчивые множества вершин
графа
11.3.2. Алгоритм вычисления всех наибольших
внутренне устойчивых множеств вершин графа
11.3.3. Внешне устойчивые множества вершин
графа
11.3.4. Алгоритм вычисления всех наименьших
внешне устойчивых множеств вершин графа
11.4. Оптимальная раскраска вершин графа
11.5. Раскрашивание планарных графов
Глава 12. Потоки в транспортных сетях
12.1. Двухполюсные сети
12.2. Дивергенция
12.3. Потоки в сетях
12.4. Сечения в сетях
12.5. Величина потока и пропускная способность
сети
12.6. Максимальный поток
12.6.1. Алгоритм Форда-Фалкерсона
12.6.2. Помечпвающий алгоритм
Форда-Фалкерсона
Глава 13. Перечисление графов
13.1. Число помеченных графов
13.2. Графы и группы подстановок
13.2.1. Группы подстановок и лемма Бернсайда
13.2.2. Теорема Пойа
13.2.3. Раскраска вершин куба
13.2.4. Составление ожерелий
Часть III. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ
Глава 14. Порождение комбинаторных
конфигураций и их пересчет
14.1. Размещения, перестановки, сочетания
14.2. Правило суммы и правило произведения
14.3. Подсчет числа размещений, перестановок,
сочетаний
14.3.1. Число размещений и перестановок без
повторений
14.3.2. Число размещений с повторениями
14.3.3. Число сочетаний без повторений
14.3.4. Число сочетаний с повторениями
14.3.5. Число перестановок данной спецификации
14.3.6. Число размещений данной спецификации
Глава 15. Производящие функции для
комбинаторных конфигураций и для их чисел
15.1. Аппарат формальных степенных рядов
15.2. Производящие функции для сочетаний
15.2.1. Сочетания без повторений
15.2.2. Сочетания с повторениями с ограничениями
начисто повторений
15.2.3. Сочетания с повторениями без ограничений
начисто повторений
15.3. Производящие функции для размещений с
повторениями
15.4. Числа Стирлинга, Белла, Каталана
Глава 16. Комбинаторно-логический аппарат
16.1. Включения и исключения
16.2. Приложения формулы включений и
исключений
16.2.1. Задача о беспорядках
16.2.2. Задача о встречах
Глава 17. Рекуррентные последовательности
17.1. Конечные разности
17.2. Рекуррентные уравнения
17.3. Линейные рекуррентные уравнения с
переменными коэффициентами
17.4. Метод Лагранжа вариации произвольных
постоянных вычисления частного решения
неоднородного уравнения
17.5. Линейные рекуррентные уравнения с
постоянными коэффициентами
Глава 18. Частично упорядоченные множества,
решетки, булевы алгебры
18.1. Отношение частичного порядка
18.2. Топологическая сортировка вершин
бесконтурного орграфа
18.3. Решетки
18.4. Изоморфизм решеток
18.5. Булевы алгебры
Приложения
1. Графы
2. Комбинаторика
Литература
Обозначения
Введение
1. Множество
2. Функция
3. Отношение
4. Отношение эквивалентности
5. Каноническое разложение функции
6. Мощность множества. Счетные и несчетные
множества
7. Мощность континуума
8. Кардинальные числа. Сравнение мощностей
Часть I. ТЕОРИЯ АЛГОРИТМОВ
Глава 1. Частично рекурсивные функции
1.1. Арифметические функции и операции над ними
1.2. Примитивно рекурсивные функции
1.3. Функции, представимые термами
1.4. Конечная сумма и произведение
1.5. Примитивно рекурсивные предикаты
1.6. Ограниченные кванторы
1.7. Ограниченный оператор u
1.8. Подстановка функций в предикат
1.8.1. Кусочное задание функции
1.8.2. Примитивная рекурсивность некоторых
функции и предикатов
1.9. Частично рекурсивные функции
Глава 2. Машины Тьюринга
2.1. Вычисления на машинах Тьюринга
2.2. Синтез машин Тьюринга
2.2.1. Композиция машин
2.2.2. Ветвление машин
2.2.3. Итерация машины
2.3. Машины Тьюринга в однобуквенном алфавите
2.4. Правильно вычислимые функции
2.4.1. Суперпозиция правильно вычислимых
функций
2.4.2. Примитивная рекурсия правильно
вычислимых функций
2.4.3. Минимизация правильно вычислимых
функций
2.4.4. Правильная вычислимость частично
рекурсивных функций
2.5. Частичная рекурсивность правильно
вычислимых функций
2.5.1. Геделева нумерация ситуаций машины
Тьюринга
2.5.2. Функции программы машины Тьюринга
2.5.3. Функции вычисления по программе машины
Тьюринга
2.5.4. Функция ситуаций машины Тьюринга
2.6. Универсальная частично рекурсивная
функция
2.6.1. Геделева нумерация машин Тьюринга
2.6.2. Функции ситуации машины Тьюринга с
номером k
2.6.3. Построение универсальной функции
2.7. Теорема Клини о неподвижной точке и теорема
Раиса.
2.8. Сложность алгоритмов
Глава 3. Рекурсивная перечислимость и
разрешимость
3.1. Общерекурсивные функции и предикаты
3.2. Нумерации наборов натуральных чисел
3.2.1. Нумерации пар натуральных чисел
3.2.2. Нумерация наборов натуральных чисел
длины k
3.2.3. Нумерация конечных последовательностей
натуральных чисел
3.3. Рекурсивно перечислимые множества
3.4. Рекурсивно перечислимые множества наборов
натуральных чисел
3.5. Общерекурсивные предикаты
3.6. Общерекурсивные множества наборов
натуральных чисел
3.7. Функции с рекурсивно перечислимым графиком
3.8. Примеры алгоритмически неразрешимых
проблем
3.9. Варианты уточнения понятия алгоритма
3.9.1. Ассоциативные исчисления
3.9.2. Системы подстановок Туэ
3.9.3. Алгоритмическая неразрешимость проблемы
тождества полугрупп и логики предикатов
3.9.4. Грамматики
3.9.5. Продукции Поста
3.9.6. Нормальные алгоритмы Маркова
3.9.7. Операторные алгоритмы
Глава 4. Гедель о неполноте формальных систем
4.1. Аксиоматическая арифметика
4.2. Алгоритмическая неразрешимость
содержательной арифметики
4.3. Алгоритмическая неразрешимость логики
предикатов второго порядка
4.4. Нумерическая выразимость
Часть II. АЛГОРИТМЫ НА ГРАФАХ Глава 5. Способы
задания графов
5.1. Графы, мультиграфы, псевдографы
5.2. Задание графов
5.3. Операции над графами
5.4. Маршруты, цепи, циклы, связность
5.4.1. Алгоритм построения кратчайшей цепи в
графе
5.4.2. Алгоритм поиска кратчайшего пути в
ориентированном графе
Глава 6. Обходы графов
6.1. Эйлеровы графы
6.2. Алгоритм построения эйлерова цикла
6.3. Полные циклы и последовательности де
Брюйна
6.4. Гамильтоновы графы
6.5. Коды Грея
Глава 7. Деревья
7.1. Деревья и лес
7.2. Характеристические свойства деревьев
7.3. Каркасы и хорды в связном графе
Глава 8. Циклы в графах
8.1. Линейное пространство двоичных наборов
8.2. Линейное пространство подграфов данного
графа
8.3. Подпространство четных подграфов
8.4. Циклический ранг графа
8.5. Матричная теорема о деревьях
Глава 9. Двудольные графы и паросочетания
9.1. Двудольные графы
9.2. Паросочетания
9.3. Алгоритм построения совершенного
паросочетания
Для двудольного графа
9.4. Системы различных представителей
9.5. Сети Петри
9.5.1. Описание сети Петри
9.5.2. Определение сети Петри
Глава 10. Пленарные графы
10.1. Плоские графы
10.2. Формула Эйлера для плоских графов
Глава 11. Раскраска графов
11.1. Хроматическое число и хроматический класс
11.2. Раскраска вершин
11.3. Верхняя и нижняя оценки хроматического
числа
11.3.1. Внутренне устойчивые множества вершин
графа
11.3.2. Алгоритм вычисления всех наибольших
внутренне устойчивых множеств вершин графа
11.3.3. Внешне устойчивые множества вершин
графа
11.3.4. Алгоритм вычисления всех наименьших
внешне устойчивых множеств вершин графа
11.4. Оптимальная раскраска вершин графа
11.5. Раскрашивание планарных графов
Глава 12. Потоки в транспортных сетях
12.1. Двухполюсные сети
12.2. Дивергенция
12.3. Потоки в сетях
12.4. Сечения в сетях
12.5. Величина потока и пропускная способность
сети
12.6. Максимальный поток
12.6.1. Алгоритм Форда-Фалкерсона
12.6.2. Помечпвающий алгоритм
Форда-Фалкерсона
Глава 13. Перечисление графов
13.1. Число помеченных графов
13.2. Графы и группы подстановок
13.2.1. Группы подстановок и лемма Бернсайда
13.2.2. Теорема Пойа
13.2.3. Раскраска вершин куба
13.2.4. Составление ожерелий
Часть III. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ
Глава 14. Порождение комбинаторных
конфигураций и их пересчет
14.1. Размещения, перестановки, сочетания
14.2. Правило суммы и правило произведения
14.3. Подсчет числа размещений, перестановок,
сочетаний
14.3.1. Число размещений и перестановок без
повторений
14.3.2. Число размещений с повторениями
14.3.3. Число сочетаний без повторений
14.3.4. Число сочетаний с повторениями
14.3.5. Число перестановок данной спецификации
14.3.6. Число размещений данной спецификации
Глава 15. Производящие функции для
комбинаторных конфигураций и для их чисел
15.1. Аппарат формальных степенных рядов
15.2. Производящие функции для сочетаний
15.2.1. Сочетания без повторений
15.2.2. Сочетания с повторениями с ограничениями
начисто повторений
15.2.3. Сочетания с повторениями без ограничений
начисто повторений
15.3. Производящие функции для размещений с
повторениями
15.4. Числа Стирлинга, Белла, Каталана
Глава 16. Комбинаторно-логический аппарат
16.1. Включения и исключения
16.2. Приложения формулы включений и
исключений
16.2.1. Задача о беспорядках
16.2.2. Задача о встречах
Глава 17. Рекуррентные последовательности
17.1. Конечные разности
17.2. Рекуррентные уравнения
17.3. Линейные рекуррентные уравнения с
переменными коэффициентами
17.4. Метод Лагранжа вариации произвольных
постоянных вычисления частного решения
неоднородного уравнения
17.5. Линейные рекуррентные уравнения с
постоянными коэффициентами
Глава 18. Частично упорядоченные множества,
решетки, булевы алгебры
18.1. Отношение частичного порядка
18.2. Топологическая сортировка вершин
бесконтурного орграфа
18.3. Решетки
18.4. Изоморфизм решеток
18.5. Булевы алгебры
Приложения
1. Графы
2. Комбинаторика
Литература
Обозначения
Об авторе
Последние поступления в рубрике "Тематика определяется"
 |
Ритуальный оракул Магия зеркал, 53 карты + инструкция
Представляем вам новую профессиональную колоду Любови Никифоровой (Отилы), являющуюся продолжением ранее изданной и уже популярной колоды «Ритуальный Оракул». В ней вы познакомитесь с азами работы с зеркалами, видами магических воздействий и способами их снятия.... |
|
Оракул Норн. Нити судьбы, 45 карт+инструкция
Оракул Норн: нити судьбы - действительно уникальная колода. Предсказывать будущее или узнавать обстоятельства прошлого и настоящего помогают Боги, Богини и герои Древней Скандинавии. Они дают подробное описание грядущих событий, которое напрямую зависит не только от обстоятельств, но и от характера человека, который хочет узнать свое будущее.... |
|
Оракул Вселенской любви Ангелов, 72 карты + инструкция
Оракул Вселенских Ангелов — это уникальная колода карт, созданная для тех, кто ищет направление и поддержку в области любви и добра от духовного мира Ангелов. Колода состоит из 72 карт, на каждой из которых изображен Ангел.... |
Если Вы задавались вопросами "где найти книгу в интернете?", "где купить книгу?" и "в каком книжном интернет-магазине нужная книга стоит дешевле?", то наш сайт именно для Вас. На сайте книжной поисковой системы Книгопоиск Вы можете узнать наличие книги Авдошин С., Дискретная математика. Алгоритмы: теория и практика в интернет-магазинах. Также Вы можете перейти на страницу понравившегося интернет-магазина и купить книгу на сайте магазина. Учтите, что стоимость товара и его наличие в нашей поисковой системе и на сайте интернет-магазина книг может отличаться, в виду задержки обновления информации.
