«Дискретная математика. Тест.»

eu.iit.csu.ru, примерно 20 вопросов, ограничение по времени: 1 ч. 30 мин., набрать проходной балл.

Итоговый тест по следующим темам: Тема 11 Графы. Алгебраические свойства графов. Гомеоморфизм. Дополнение графа. Ориентированные графы. Диаграммы Гессе. Тема 12 Эйлеровы графы. Пути Эйлера. Циклы Эйлера. Свойства. Матрицы смежности и инцидентности. Гиперкубы и код Грея. Тема 13 Гамильтоновы графы. Пути и циклы Гамильтона. Взвешенные графы. Кратчайший путь. Алгоритм поиска кратчайшего пути. Алгоритмы Дейкстры, Флойда-Уоршолла. Тема 14 Планарные графы. Свойства. Теорема Куратовского. Раскраска графов. Свойства. Задача Бирхгофа. Хроматический многочлен. Тема 15 Деревья. Корневое ориентированное дерево. Высота дерева. m-арное дерево. Свойства деревьев. Ориентированное дерево. Сбалансированное дерево. Гомоморфизм. Изоморфизм. Бинарное дерево поиска. Тема 16 Взвешенные деревья. Дерево и код Хаффмана. Остовные деревья. Разрезающее множество. Построение остовного дерева в ширину и в глубину. Обратное дерево. Формула Кэли. Алгоритм преобразования остовного дерева в последовательность. Алгоритм перевода последовательности в дерево. Матричная формула Кирхгофа. Тема 17 Теория кодов. Криптография. Определения и свойства кодов. Код Хаффмана. Код Морзе. Код Грея. Порождающие матрицы. Лидер смежных классов. Синдромы. Тема 18 Сети и потоки. Определения и свойства. Принцип сохранения потока. Пропускная способность. Минимальное сечение. Максимальный поток. Алгоритм Форда-Фалкерсона. Сетевой график. Тема 19 Кольца. Области целостности. Поля. Определения. Свойства. Главный идеал. Делители единицы. Полиномы. Степень полинома. Коэффициенты полинома. Символ Кронекера.