Перейти к полному списку специальных курсов кафедры

Программа экзамена по курсу "Комбинаторные методы дискретной математики" (для группы 505) на 2007-2008 уч.год

Билет ?1
1 Принципы комбинаторики. Числа инъекций, сюръекций и биекций конечных множеств.
2 Системы различных представителей. Теорема Холла.

Билет ?2
1 Числа Стирлинга-2.
2 Ортогональные латинские квадраты. Теорема Манна.

Билет ?3
1 Числа Белла.
2 Конечные проективные плоскости и их существование.

Билет ?4
1 Гармонические числа.
2 Число систем различных представителей семейства множеств.

Билет ?5
1 Числа Стирлинга-1
2 Матроиды и их свойства.

Билет ?6
1 Числа Дилуорса
2 Теорема Радо-Эдмонса о матроидах.

Билет ?7
1 Быстрое преобразование Фурье
2 Перманенты и их свойства.

Билет ?8
1 Подстановки булевского куба. Критерий Хаффмана.
2 Метод включения-исключения. Формула Райзера для перманентов

Билет ?9
1 Числа Гаусса и числа Галуа
2 Сложность умножения матриц

Билет ?10
1 Числа Шпернера и числа Анселя.
2 Сложность сортировки чисел

Билет ?11
1 Число булевских функций без фиктивных переменных.
2 Сложность умножения битовых чисел

Билет ?12
1 Число подстановок без единичных циклов.
2 Сложность умножения многочленов

Билет ?13
1 Число булевских функций с заданным значением коэффициента Фурье
2 Формула Райзера для перманентов.

Билет ?14
1 Представление булевских функций рядом Фурье
2 Латинские квадраты и их пополнение .

Билет ?15
1 Лемма Бернсайда
2 Формула обращения Мебиуса. Число неприводимых многочленов .

Билет ?16
1 Теорема Шеннона о числе классов эквивалентности булевских функций
2 Матрицы Адамара и их существование.

Билет ?17
1 Циклы прямого произведения подстановок.
2 Коды Адамара и их корректирующие свойства.

Билет ?18
1 Типы полиномиальных оценок сложности для рекурсивных алгоритмов.
2 Счетчиковые автоматы и их построение

Билет ?19
1 Классы сложности Р и NP и их связь.
2 Разностные характеристики подстановок. Теорема Холла.

Билет ?20
1 Класс сложности НРС. Теорема Кука.
2 Критерий БПИ для автоматов.

Билет ?21
1 Задача Клика и ее NP-полнота.
2 Критерий регулярности для автоматов.

Билет ?22
1 Задача о рюкзаке и ее NP-полнота
2 Латинские квадраты над булевским кубом.

Билет ? 23
1 Графы де Брейна. Теорема де Брейна о числе эйлеровых циклов.
2 Число типов булевских функций в группе отрицаний переменных.

Билет ? 24
1 Метод рекуррентных соотношений. Решения линейных соотношений
2 Декомпозиция дважды стохастических матриц. Теорема Биркгофа.

Билет ?25
1 Метод производящих функций. Числа Каталана.
2 Задача выполнимости F-формул. Классы Шиффера. Теорема Шеффера.

Наверх