Прверка статистических гипотез по критериям. Ошибки первого и второго рода. Уровень значимости. Проверка гипотез о совпадении математических ожиданий по критерию Стьюдента. Проверка гипотез о совпадении дисперсий по критерию Фишера. Общий статистический критерий Пирсона.
РАЗДЕЛ 8. Теория графов.
Тема 21. Основные понятия и определения теории графов.
Определение графа. Ориентированные и неориентированные графы. Мультиграфы. Степени и полустепени вершин. Понятие пути, цепи, контура, цикла. Связные графы и сети. Полные графы. Изоморфизм графов. Подграфы. Деревья и их свойства.
Тема 22. Эйлеровы и гамильтоновы графы. Теорема Эйлера.
Определение эйлерова цикла и графа. Теорема Эйлера четности вершин эйлерова графа. Гамильтоновы циклы и графы. Достаточные условия гамильтоновости графа.
Тема 23. Планарные или плоские графы. Теорема Куратовского.
Определение планарного (плоского) графа. Графы, расположенные на сфере и их связь с планарными. Доказательство теоремы об эйлеровой характеристике выпуклого многогранника. Теорема Куратовского о неплоских графах.
Тема 24. Матрицы инцидентности и смежности.
Определение матрицы инцидентности и матрицы смежности графа. Связь матриц и графов. Построение графа по его матрице.
Тема 25. Теорема Холла.
Двудольные графы. Теорема Холла о максимальном парасочетании для двудольных графов. Ее связь с другими теоремами теории графов.
Тема 26. Потоки в сетях. Теорема Форда - Фалкерсона
О максимальном потоке.
Различные определения сети. Потоки в сетях. Мощность потока. Разрезы и их пропускные способности. Доказательство теоремы Форда - Фалкерсона о максимальном потоке. Ранги вершин, цепи повышающие поток, алгоритм пометок.
РАЗДЕЛ 9. Булевы алгебры и функции.
Тема 27. Булевы алгебры. Примеры.
Определение булевой алгебры как структуры (решетки). Примеры булевых алгебр: теория множеств, исчисление высказываний. Алгебраическое определение булевой алгебры. Формулировка основной теоремы о представлении булевой алгебры.
Тема 28. Булевы функции.
Дизъюнктивная и конъюнктивная нормальные формы.
Булев куб и булевы функции. Частичный порядок на булевом кубе. Различные классы булевых функций. Стандартные булевы функции двух булевых аргументов. Полиномы Жегалкина.
Тема 29. Теорема о полных классах булевых функций.
Замкнутые и полные классы булевых функций двух переменных. Примеры полных систем булевых функций. Формулировка теоремы о полных классах булевых функций произвольного числа аргументов.
Дата добавления: 2015-09-12; просмотров: 26 | Поможем написать вашу работу | Нарушение авторских прав |