Документ взят из кэша поисковой машины. Адрес оригинального документа : http://new.math.msu.su/content_root/programs/kaf/special/matis/komb.doc Дата изменения: Mon Nov 10 08:55:21 2008 Дата индексирования: Sun Apr 10 02:58:02 2016 Кодировка: koi8-r

КОМБИНАТОРИКА И КОМБИНАТОРНЫЕ АЛГОРИТМЫ

1. Предварительные понятия и принципы комбинаторики. Принципы
перечисления Числа Белла. Числа Стирлинга-2. Подстановки и их перечисление.
Числа Стирлинга-1. Алгоритмы порождения подстановок и сочетаний.
2. Методы перечисления. Метод включения-исключения. Метод рекуррентных
соотношений. Метод производящих функций. Числа Каталана. Формулы обращения.
3. Методы теории графов. Основные понятия. Пути. Связность, Эйлеровы и
Гамильтоновы графы. Деревья и их применения. Остовные деревья и их число.
Теоремы Кэли и Кирхгофа. Эйлеровы циклы в орграфах и их число. Теорема
BEST. Планарность графов. Теорема Эйлера. Толщина графа. Потоки в сетях.
Теорема Форда-Фалкерсона.
4. Трансверсали и перманенты. Теорема Холла. Оценки числа трансверсалей.
Латинские прямоугольники и квадраты, их существование и оценки.
Декомпозиция неотрицательных матриц, теорема Биркгофа. Перманенты и их
вычисление. Формула Райзера. Оценки перманентов. Проблема Ван дер Вардена.
Блок-схемы и их построение. Конечные геометрии. Ортогональные латинские
квадраты и их построение. Матрицы с ограничениями на суммы в строках и
столбцах. Теорема Райзера-Гейла.
5. Перечисление относительно групп преобразований. Лемма Бернсайда.
Теорема Пойа. Применение теоремы Пойа к классификации функций.
6. Комбинаторные алгоритмы и сложность. Полиномиальные и экспоненциальные
алгоритмы. NP-полнота. Основные NP-полные задачи комбинаторики. Сложностная
классификация графических задач. Методы построения быстрых алгоритмов.
Рекурсия. Комбинаторные задачи оптимизации и матроиды. Приближенные
алгоритмы.