Комбинаторика и комбинаторные алгоритмы - polpoz.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Программа дисциплины «Алгоритмы и структуры данных» 3 260.07kb.
Комбинаторика занимается различного вида соединениями, которые можно... 1 415.63kb.
Логико-комбинаторные методы анализа социологических данных: эвристический... 1 394.39kb.
Основные комбинаторные объекты. Размещения. Число размещений 1 38.04kb.
Картопостроение в геологии и эксперт. Гибкие алгоритмы 1 34.74kb.
«Методы и алгоритмы защиты информации» для направления 231000 1 89.06kb.
Направление «Математика. Информационные технологии» 1 75.1kb.
Рік 2008 Номер журналу 1 29.71kb.
Алгоритмы решения задачи составления оптимального расписания без... 1 283.39kb.
Алгоритмы оценки гепато- и нефропатологии при бабезиозе собак 1 371.06kb.
Быстрые алгоритмы сортировки 1 137.23kb.
Конструирование из строительного материала 1 29.17kb.
1. На доске выписаны n последовательных натуральных чисел 1 46.11kb.

Комбинаторика и комбинаторные алгоритмы - страница №1/1

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


1. Предварительные понятия и принципы комбинаторики. Принципы перечисления Числа Белла. Числа Стирлинга-2. Подстановки и их перечисление. Числа Стирлинга-1. Алгоритмы порождения подстановок и сочетаний.

2. Методы перечисления. Метод включения-исключения. Метод рекуррентных соотношений. Метод производящих функций. Числа Каталана. Формулы обращения.

3. Методы теории графов. Основные понятия. Пути. Связность, Эйлеровы и Гамильтоновы графы. Деревья и их применения. Остовные деревья и их число. Теоремы Кэли и Кирхгофа. Эйлеровы циклы в орграфах и их число. Теорема BEST. Планарность графов. Теорема Эйлера. Толщина графа. Потоки в сетях. Теорема Форда-Фалкерсона.

4. Трансверсали и перманенты. Теорема Холла. Оценки числа трансверсалей. Латинские прямоугольники и квадраты, их существование и оценки. Декомпозиция неотрицательных матриц, теорема Биркгофа. Перманенты и их вычисление. Формула Райзера. Оценки перманентов. Проблема Ван дер Вардена. Блок-схемы и их построение. Конечные геометрии. Ортогональные латинские квадраты и их построение. Матрицы с ограничениями на суммы в строках и столбцах. Теорема Райзера-Гейла.



5. Перечисление относительно групп преобразований. Лемма Бернсайда. Теорема Пойа. Применение теоремы Пойа к классификации функций.

6. Комбинаторные алгоритмы и сложность. Полиномиальные и экспоненциальные алгоритмы. NP-полнота. Основные NP-полные задачи комбинаторики. Сложностная классификация графических задач. Методы построения быстрых алгоритмов. Рекурсия. Комбинаторные задачи оптимизации и матроиды. Приближенные алгоритмы.


izumzum.ru