|
Чтение годового спецкурса "Комбинаторные свойства дискретных структур", лектор - доцент Ю.В.Таранников, начнется 29 сентября 2003 года в 16:20 в ауд. 13-03.
Программа 2000/2001 года (в этом году будут изменения).
1. Частично упорядоченные множества. Цепи, антицепи. Теорема Дилуорса.
2. Двудольные графы. (0,1)-матрицы. Теорема Кенига.
3. Системы различных представителей. Теорема Холла.
4. Булев куб. Существование максимального паросочетания в двух соседних слоях.
5. Неравенство Любеля-Мешалкина-Ямамото.
6. Теорема Шпернера.
7. Теорема Рамсея.
8. Числа Рамсея.
9. Теорема Эрдеша-Секереша.
10. Теорема о существовании симметрической подфункции.
11. Пример функции, заданной на q-значных наборах, q>=3, не имеющей симметрических подфункций от двух переменных.
12. Теорема Симона-Вегенера.
13. Коэффициенты Фурье и Уолша. Их взаимосвязь.
14. Формула обращения для коэффициентов Уолша.
15. Равенство Парсеваля.
16. Тождество Саркара.
17. Уравновешенные, корреляционно-иммунные и устойчивые булевы функции.
18. Неравенство Зигенталера.
19. Спектральная характеризация корреляционно-иммунных и устойчивых функций.
20. Делимость коэффициентов Уолша корреляционно-иммунных и устойчивых функций.
21. Нелинейность булевых функций. Бент функции.
22. Ограниченность числа нелинейных переменных в устойчивых функциях высокого порядка.
23. Поля Галуа.
24. Символы Лежандра.
25. Кронекерово произведение матриц.
26. Матрицы Адамара. Проблема существования матриц Адамара заданного порядка.
27. Методы построения матриц Адамара.
28. Матрицы Адамара симметрические и кососимметрического типа.
29. Построение матриц Адамара методом Вильямсона.
30. Кодовые множества. Кодовые расстояния.
31. Эквидистантные коды.
32. Неравенство Плоткина.
33. Максимальная мощность кодовых множеств в случае больших кодовых расстояний. Связь с матрицами Адамара.
34. Блок-дизайны.
35. Неравенство Фишера.
36. Разрешимые блок-дизайны.
37. Симметричные блок-дизайны. Неравенства, связывающие их параметры.
38. Аффинная плоскость. Разрешимость аффинной плоскости. Существование аффинных плоскостей порядка, равного степени простого числа.
39. Проективная плоскость. Связь с аффинной плоскостью.
40. Проективная геометрия.
41. Теорема Лагранжа о представлении в виде суммы четырех квадратов.
42. Теорема Брука-Райзера-Човлы.
43. Латинские квадраты. Ортогональные латинские квадраты. Проблема существования ортогональных латинских квадратов заданного порядка.
44. Опровержение гипотезы Эйлера о несуществовании ортогональных латинских квадратов для порядков, сравнимых с 10 по модулю 12.
45. Взаимно ортогональные латинские квадраты.
46. Связь существования n-1 взаимно ортогональных латинских квадратов порядка n с существованием аффинной плоскости порядка n.
47. Ортогональные массивы.
48. Связь взаимно ортогональных латинских квадратов с ортогональными массивами силы 2.
49. Неравенство Биербрауера-Фридмана.
50. Неравенство Рао.
51. Трансверсальные дизайны. Эквивалентность трансверсальных дизайнов и ортогональных массивов силы 2 и индекса 1.
52. Прямая конструкция ортогонального массива силы 2 и индекса 1 с числом элементов, равным степени простого числа.
53. Усеченные трансверсальные дизайны. Конструкция Вильсона.
54. Завершение опровержения гипотезы Эйлера о несуществовании ортогональных латинских квадратов.
55. Линейные коды. Базис. Дуальный код. Порождающая и проверочная матрицы. Связь кодового расстояния линейного кода с линейной независимостью столбцов его проверочной матрицы.
56. Линейный код как ортогональный массив.
57. Неравенство Варшамова-Гильберта.
58. t-Дизайны.
59. Адамаровы дизайны.
60. Двоичный код Голея и дизайны Витта.
61. Несуществование совершенного двоичного кода с кодовым расстоянием 7 длины большей чем 7 и не равной 23.
62. Троичный код Голея.
63. Существование нетривиальных t-дизайнов с повторяющимися блоками.
64. Необходимые и достаточные условия существования системы троек Штейнера.
65. Разностные множества.
66. Построение симметричных блок-дизайнов с помощью разностных множеств.
67. Разностные множества, состоящие из квадратичных вычетов.
MMOnline
|