English version of this page
На главную страницу
Официальный сайт кафедры Математической теории интеллектуальных систем и
лаборатории Проблем теоретической кибернетики
механико-математического факультета МГУ им. М. В. Ломоносова
На первую страницу сервера Новости Кафедра Сотрудники Учеба Наука Исследования Журнал Культура Полнотекстовый поиск по серверу
 ТДФ Теория дискретных функций – лекции и семинары для студентов 1 курса (II поток)
 Ташкентский филиал Ташкентский филиал МГУ им. М.В. Ломоносова
 Семинары расписание специальных семинаров кафедры МаТИС
 Курсы расписание специальных курсов кафедры, программа курсов
 Практикум cпециальный математический практикум кафедры МаТИС, III курс
 Студенты список студентов кафедры по курсам и группам, расписание занятий, выпускники
 Магистратура информация для поступающих в магистратуру
 Аспирантура информация для аспирантов и поступающих в аспирантуру; списки аспирантов

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

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

Наверх

   © 2001-2015 г. Кафедра Математической теории интеллектуальных систем, лаборатория Проблем теоретической кибернетики Написать вебмастеру   
XWare
 Полнотекстовый поиск
 
Только точная форма слов      Выводить по результатов на странице
Rambler's Top100 Рейтинг@Mail.ru