Программа, 2-й курс, дискретная математика. ЛЭТИ, ФЭА 2008.
Теория множеств. Операции над множествами: дополнение; объединение, пересечение, прямое произведение, мощности результатов. Конечнозначные функции на конечном множестве: мощность их мн-ва, индикаторы частей. Бинарное отношение, отношение эквивалентности.
Комбинаторика. Комбинаторные структуры, классы и числа, правила суммы и произведения. Сочетания, размещения перестановки, композиции. Метод производящих ф-ий для сочетаний.
Булева алгебра. Булевы константы, функции: таблица истинности, единичный набор, существенные и фиктивные переменные, операции, базисные функции. Булева формула, соотношения между функциями и формулами, эквивалентности формул, правила подстановки. Законы булевой алгебры. Приведение формулы к атомарному виду, к ДНФ и КНФ.
Разложение булевых функций по переменным, приведение к СДНФ, базисность набора {,/\,\/}, приведение к СКНФ.
Формульные алгоритмы приведения к СДНФ и СКНФ. Проблема минимизации ДНФ: индекс простоты, минимальные ДНФ тупиковые формулы, метод Блейка.
Теория алгоритмов. Вычислительный метод, алгоритм, общие характеристики. Временная сложность алгоритма и задачи Р и NP-трудные задачи. Алгоритм Эвклида для нахождения НОД. Алгоритмы сортировки: метод частичных минимумов, метод слияния. Алгоритмы 1-мерной локализации и поиска.
Теория графов. Простой неориентированный граф: вершины, ребра, смежность, инцидентность, соседи, локальные степе» лемма о рукопожатиях. Другие типы графов, сети. Часть графа, остовная часть, индуцированный подграф. Операции над графами. Изоморфизм графов, число помеченных непомеченных графов порядка n, критерий изоморфности в терминах матриц смежности. Связность: аниклический/циклический маршрут, цепь, цикл, простая цепь, простой цикл, длина маршрута в неориентир. графе и орграфе. Простая цепь в маршруте, простой цикл в цикл. маршруте, объединение несовпадающих цепей с общими концами, удаление общего ребра двух контуров. Области и компоненты связности, связность дополнения несвязного графа. Удаление ребра связного графа, мосты. Оценки числа ребер графа при заданных n. k. необходимое /достаточное условия связности. Деревья: характеристическая теорема, оценка снизу числа концевых вершин. Остов, цикломагическое число, критерии ацикличности / наличия единственного цикла, достаточный признак наличия цикла. Теорема о замене остова, алгоритм построения остова, базис циклов. Метрические характеристики графа, системы уровней. Волновой алгоритм, применения. Критерий Кенига двудольности графа, способ распознавания. Матриц ассоциированные с графом, их свойства. Представление матрицы Кирхгофа. Матричный индикатор остова, матричная теорема Кирхгофа, теорема Кали. Остов минимального веса: алгоритм Прима. Кратчайшие пути во взвешенном орграфе: алгоритм Дийкстра.
Вопросы.
Операции над множествами, мощности результатов. Число частей конечного множества. Функции на конечном множестве со значениями в конечном множестве. Бинарное отношение, отношение эквивалентности. Правила суммы и произведения. Размещения, перестановки. Сочетания, композиции. Метод производящих функций для сочетаний. Булевы функции и операции. Булева формула. Эквивалентные преобразования, правила подстановки Законы булевой алгебры. Приведение формулы к атомарному виду, к ДНФ и КНФ. Разложение булевых функций, но переменным. Приведение к СДНФ. СКНФ. Проблема минимизации ДНФ. метод Блейка. Общие характеристики алгоритма. Алгоритмы 1-мерной локализации и поиска. Временная сложность алгоритма и задачи. Анализ алгоритма Эвклида для нахождения НОД. Сложность алгоритма сортировки слиянием. Лемма о рукопожатиях. Часть графа, индуцированный подграф. Изоморфизм графов, критерий в терминах матриц смежности. Маршрут, цепь, цикл. Простая цепь в маршруте. Объединение цепей с общими концами. Удаление общего ребра двух контуров. Области и компоненты связности. Связность дополнения несвязного графа. Теорема о мостах. Оценки числа ребер графа при заданных n. k. Достаточные/необходимые условия связности. Деревья, характеристическая теорема: импликации 1=>2=>3=>4. Деревья, характеристическая теорема: импликации 4=>5=>1. Оценка снизу числа концевых вершин дерева. Остов, цикломатическое число, критерии ацикличности/наличия единственного цикла. Достаточный признак наличия цикла. Теорема о замене остова, алгоритм построения остова, базис циклов. Метрические характеристики графи. Системы концентрических уровней. Волновой алгоритм; применения. Критерий двудольности графа; способ распознавания. Матрица Кирхгофа, свойства, алгебраические дополнения. Представление матрицы Кирхгофа. Матричный индикатор остовного дерева Матричная теорема Кирхгофа. Теорема Кэли. Анализ алгоритма Прима. Анализ алгоритма Дийкстра.