x-uni.com
регистрация / вход
сейчас на линии 105 чел.
x-uni.com
x-uni.com
 
Математика
Биология
Литература
Русский язык
ВИДЕО
Физика
Химия
История
Английский
 
ВИДЕО
 
 
регистрация / вход
сейчас на линии 105 чел.
Введение в дискретную математику, Ландо С.К., 2014

Введение в дискретную математику, Ландо С.К., 2014

Введение в дискретную математику, Ландо С.К., 2014.

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

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

Как правило, задача перечислительной комбинаторики «в принципе» разрешима: для каждого множества из семейства можно выписать все его элементы и таким образом узнать их число. Проблема, однако, состоит в том, чтобы найти «хорошее» решение, не требующее выписывания всех элементов изучаемых множеств. При этом понять, что такое хорошее решение, довольно трудно. Зачастую удается лишь сравнить два решения и сказать, какое из них лучше.

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

Оглавление
От автора
Часть I Элементы перечислительной комбинаторики
Глава 1. Элементарные производящие функции
§1.1. Перестановки и сочетания
§1.2. Бином Ньютона
§1.3. Экспонента
§1.4. Производящие функции и действия над ними
§1.5. Дифференцирование и интегрирование производящих функций
§1.6. Алгебра и топология формальных степенных рядов
§1.7. Задачи
Глава 2. Рациональные производящие функции
§2.1. Геометрическая прогрессия
§2.2. Последовательность Фибоначчи
§2.3. Рекуррентные соотношения и рациональные производящие функции  
§2.4. Неоднородные рекуррентные соотношения
§2.5. Произведение Адамара рациональных производящих функций
§2.6. Асимптотика коэффициентов рациональных функций
§2.7. Задачи
Глава 3. Перечисление путей на графах
§3.1. Пути в графах
§3.2. Пути, перечисляемые рациональными производящими функциями  
§3.3. Числа Каталана
§3.4. Задачи
Глава 4. Производящие функции нескольких переменных
§4.1. Треугольник Паскаля
§4.2. Экспоненциальные производящие функции  
§4.3. Треугольник Дика
§4.4. Треугольник Бернулли—Эйлера и перечисление up-down-перестановок  
§4.5. Числа Эйлера в треугольнике Дика с кратностями
§4.6. Производящая функция для треугольника Дика с кратностями
§4.7. Задачи
Глава 5. Теневое исчисление
§5.1. Определения и примеры
§5.2. Применения биномиальных последовательностей
§5.3. Биномиальные последовательности и сдвиги  
§5.4. Явное построение биномиальных последовательностей
§5.5. Последовательности Шеффера
§5.6. Коалгебра многочленов
§5.7. Задачи
Глава 6. Разбиения
§6.1. Разбиения и разложения
§6.2. Тождество Эйлера
§6.3. Разбиения множеств в треугольнике Моцкина с кратностями
§6.4. Задачи
Глава 7. Производящие функции Дирихле
§7.1. Принцип включения-исключения
§7.2. Производящие функции Дирихле и действия над ними
§7.3. Обращение Мобиуса
§7.4. Мультипликативные последовательности
§7.5. Задачи
Часть II Графы, их перечисление и инварианты
Глава 8. Перечисление деревьев и лесов
§8.1. Перечисление помеченных деревьев
§8.2. Леса и многочлены Абеля
§8.3. Перечисление посаженных лесов  
§8.4. Обращение функции и суммирование по деревьям
§8.5. Задачи
Глава 9. Числа Гурвица
§9.1. Графы и перестановки  
§9.2. Числа Гурвица
§9.3. Уравнение транспозиции
§9.4. Задачи
Глава 10. Соотношение удаление-стягивание и теорема Татта
§10.1. Графы, изоморфизм и инварианты  
§10.2. Хроматический многочлен
§10.3. Немного о топологии графа
§10.4. Многочлен Пенроуза
§10.5. Соотношения Татта
§10.6. Теорема Татта
§10.7. Доказательство теоремы Татта
§10.8. Новые примеры инвариантов Татта
§10.9. Задачи
Глава 11. Алгебра Хопфа графов
§11.1. Алгебра Хопфа графов
§11.2. Примитивные элементы  
§11.3. Факторалгебры биалгебры графов
§11.4. 4-инварианты
§11.5. Оснащенные модификации графовых алгебр
§11.6. Задачи
Часть III Языки, грамматики, автоматы
Глава 12. Языки и конечные автоматы
§12.1. Язык Дика
§12.2. Конечные автоматы
§12.3. Автоматы со стеком
§12.4. Задачи
Глава 13. Языки и формальные грамматики с однозначным выводом
§13.1. Правила вывода в языке Дика
§13.2. Формальные грамматики с однозначным выводом
§13.3. Производящие функции регулярных языков  
§13.4. Представления производящих функций в виде непрерывных дробей  
§13.5. Сравнения в последовательностях
§13.6. Задачи
Ответы, указания, решения
Решения задач главы 1  
Решения задач главы 2
Решения задач главы 3
Решения задач главы 4
Решения задач главы 5
Решения задач главы 6
Решения задач главы 7
Решения задач главы 8
Решения задач главы 9
Решения задач главы 10
Решения задач главы 11
Решения задач главы 12
Решения задач главы 13
Контрольные задания
Задачи зачета
Домашняя работа
Задачи экзамена
Библиографические замечания  
Литература  
Предметный указатель.

Предложения интернет-магазинов

Учебно-тематическое планирование курса "Введение в экономику". 10-11 классы. Пособие для учителя

Автор(ы): Чуканова Маргарита Михайловна   Издательство: Вита-Пресс, 2002 г.  Серия: Экономика

Цена: 41 руб.   Купить

Пособие входит в учебно-методический комплект, состоящий из учебника В. С. Автономова "Введение в экономику" и методического пособия Л. Б. Азимова "Преподавание курса "Введение в экономику"". В нем раскрыты особенности планирования курса, рассчитанного на двухгодичное изучение (64 ч). Дано краткое руководство по использованию материала учебника с "горизонтальным" делением текста. Приведены итоговые тесты для проверки знаний учащихся в 9-м и 10-м классах. 2-е издание.


Естествознание. Введение в естественно-научные предметы. 5 класс. Атлас. ФГОС

  Издательство: Дрофа, 2015 г.  Серия: Атласы и контурные карты

Цена: 146 руб.   Купить

Естествознание. Введение в естественно-научные предметы. 5 класс. Атлас. Входит в учебно-методический комплекс по естествознанию, рекомендованный Министерством образования и науки Российской Федерации. 3-е издание, стереотипное.


Введение в биологию. 5 класс. Тематические тесты. Синий. Вертикаль. ФГОС

Автор(ы): Сонин Николай Иванович   Издательство: Дрофа, 2015 г.  Серия: Биология

Цена: 181 руб.   Купить

Тематические тесты являются частью учебного комплекса А. А. Плешакова, Н. И. Сонина "Биология. Введение в биологию. 5 класс". Пособие предназначено для проверки знаний учащихся по каждой теме курса.


Введение в биологию. 5 класс. Тематические тесты. Красная. Вертикаль. ФГОС

Автор(ы): Сонин Николай Иванович   Издательство: Дрофа, 2015 г.  Серия: Биология

Цена: 181 руб.   Купить

Тематические тесты являются частью учебного комплекса А. А. Плешакова, Н. И. Сонина "Биология. Введение в биологию. 5 класс". Пособие предназначено для проверки знаний учащихся по каждой теме курса.

ПЕДСОВЕТ / ФОРУМ

Новости образования

Новости науки

флаг италииX-UNI рекомендует репетитора итальянского языка: yuliyavenezia (Скайп).

Репетитор по Скайпу без посредников

Неограниченная аудитория, свободный график. Начните свой бизнес здесь!