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

Программа экзамена по курсу "Комбинаторные методы дискретной математики" (для группы 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–формул. Классы Шиффера. Теорема Шеффера.

Наверх