2020-07-12
49по дисциплине "Специальные разделы математики"
СРМ -1 "Основы теории чисел"
1. Понятие множества, основные операции над множествами. Конечные и бесконечные множества, важнейшие числовые множества.
2. Отображения множеств и их классификация. Понятие композиции отображений.
3. Логические высказывания и операции над ними. Математические утверждения. Понятие обратного и противоположного утверждений, необходимого, достаточного условий и математического критерия.
4. Методы доказательства утверждений методом непосредственной проверки и “от обратного”. Метод полной математической индукции, методика его применения для доказательства математических утверждений.
5. Понятие бинарной алгебраической операции. Коммутативные и ассоциативные операции, дистрибутивность одной операции относительно другой.
6. Алгебраические системы с одной бинарной операцией. Понятие группы. Элементарные свойства групп.
7. Основные способы задания подстановок на конечном множестве (табличный, графический и в виде произведения независимых циклов). Понятие конечной группы подстановок.
8. Определение понятия кольца. Обратимые элементы кольца. Понятие группы обратимых элементов.
9. Понятие наибольшего общего делителя (НОД) целых чисел. Алгоритм Эвклида. Наименьшее общее кратное (НОК) целых чисел.
10. Основные свойства конгруэнций целых чисел. Понятие кольца вычетов по натуральному модулю. Критерий обратимости элемента кольца вычетов.
11. Понятие поля. Примеры полей. Необходимые и достаточные условия, при которых кольцо вычетов является полем.
12. Определение факториального кольца. Определение и существование НОД, НОК. Примеры.
13. Кольцо Ζ как факториальное кольцо. Основная теорема арифметики. Каноническое разложение целого числа на простые множители, разложение НОД, НОК двух чисел.
14. Понятие подгруппы, примеры. Понятие классов смежности по подгруппе, их свойства.
15. Теорема Лагранжа и ее следствия.
16. Определение циклической группы. Понятие генератора группы. Определение порядка элемента группы.
17. Теорема о свойствах циклической группы.
18. Теорема Эйлера. Малая теорема Ферма.
СРМ -2 "Математическая статистика"
19. Вероятностно-статистическая модель, понятие о событии (совместность, зависимость, противоположность).
20. Дать определение понятия дискретной случайной величины. Что такое закон распределения случайной величины.
21. Дать определение понятия математического ожидания и привести его свойства.
22. Дать определение понятия дисперсии. Привести основные свойства дисперсии.
23. Дать определение понятия дисперсии. Доказать, что 
.
24. Дать определение понятия математического ожидания. Доказать, что 
.
СРМ -3 "Дискретная математика"
25. Системы подмножеств конечного множества. Сочетания. Формула для числа сочетаний заданной мощности.
26. Основные классы отображений конечных множеств. Подстановки (перестановки) и размещения. Правила суммы и произведения. Формулы для чисел отображений, размещений и перестановок.
27. Формула включения-исключения. Примеры ее применения (число сюръективных отображений конечного множества, число подстановок с заданным числом неподвижных элементов).
28. Понятие орграфа отображений конечного множества. Цикловая структура и орграф подстановки. Формула для числа подстановок имеющих заданную цикловую структуру.
29. Понятие покрытия конечного множества ее подмножествами. Матрица инцидентности покрытия, связь между глубиной (0, 1)-матрицы и мощностью минимального покрытия конечного множества.
30. Градиентный алгоритм построения минимального покрытия конечного множества. Оценка сложности градиентного алгоритма.
31. Понятие n -мерного единичного куба и булевой функции (БФ). Табличный и геометрический способы задания БФ.
32. Аналитический способ задания БФ. Элементарные булевы функции. Совершенная дизъюнктивная нормальная форма (СДНФ) БФ.
33. Оператор двойственности. Самодвойственные булевы функции. Совершенная конъюнктивная нормальная форма (СКНФ) БФ.
34. Теорема о существовании и единственности полинома Жегалкина БФ. Алгоритм построения полинома Жегалкина БФ по ее СДНФ.
35. Понятие степени БФ, соотношение между весом и степенью БФ, аффинные и линейные булевы функции.
36. Понятие тензорного произведения матриц над полем. Тензорная степень матрицы. Матричные соотношения между векторами значений и коэффициентов полинома Жегалкина БФ.
37. Быстрый алгоритм вычисления коэффициентов полинома Жегалкина по вектору значений БФ. Временная сложность этого алгоритма.
38. Понятие суперпозиции и формулы над системой БФ. Оператор замыкания на множестве систем булевых функций.
39. Понятие замкнутой, полной и предполной системы БФ. Важнейшие замкнутые классы БФ (функции, сохраняющие 0 или 1, аффинные, самодвойственные, монотонные БФ). Формулировка критерия полноты системы БФ (теорема Поста).
40. Основные понятия теории ДНФ (импликанты, простые импликанты, сокращенная, тупиковые, минимальные и кратчайшие ДНФ булевой функции).
41. Методы построения сокращенной ДНФ булевой функции по ее конъюнктивной и дизъюнктивной нормальными формами.
42. Понятие конечномерного линейного пространства над конечным полем. Понятие подпространства, размерности подпространства и ранга системы векторов.
43. Понятие элементарного преобразования строк (столбцов) и канонической формы матрицы над конечным полем.
44. Каноническая форма матрицы над конечным полем. Метод построения канонической формы матрицы (метод Гаусса).
45. Понятие временной и емкостной сложностей вычислительного алгоритма. Сложность алгоритма умножения матрицы над конечным полем. Временная сложность алгоритмов построения канонической формы матрицы над конечным полем методом Гаусса и методом Штрассена.
