Комбинаторные алгоритмы
Дисциплина «Дискретная математика» Экзаменационные вопросы (2012 — 2013) УГГУ
Элементы теории множеств
О понятии множества. Принадлежность элемента множеству. Конечные и бесконечные множества. Универсум. Мощность множества. Пустое множество. Способы задания множеств. Свойства множеств. Равенство двух множеств. Подмножества. Теоретико - множественные операции. Свойства операций над множествами. Вектор. Декартово произведение множеств. Изоморфизм теоретико-множественных и логических операций.
Отношения
Определение бинарного отношения. Задание отношений. Задание графа через отношение. Свойства отношений. Отношение эквивалентности. Отношение порядка. Функция. Отношение как базовое понятие в реляционных базах данных. Поле. Запись. Операции над таблицами.
Элементы теории графов
Определение графа. Смежность. Инцидентность. Изоморфизм. Мультиграф. Псевдограф. Подграф. Полный граф. Двудольный граф. Планарный граф. Степень вершины. Теорема Эйлера. Маршрут. Цепь. Простая цепь. Цикл. Простой цикл. Ориентированный граф. Полустепени исхода и захода. Ориентированный маршрут. Путь. Контур. Длина маршрута. Взвешенный граф. Сеть. Преобразование произвольного графа к сети. Матрица смежностей. Матрица инциденций. Связный граф. Компоненты связности. Остов. Минимальный остов. Дерево. Размещение дерева по уровням. Параметры дерева: корень, отец, сыновья, братья, листья. Глубина дерева. Бинарное дерево. Полное и почти полное бинарное дерево. Поддерево. Раскрашенный граф. Хроматическое число. Представление графа в компьютере. Представление матрицей смежностей, массивами ребер, списками смежностей. Реализация списков смежностей упакованным массивом. Достоинства и недостатки различных форм представления.
Структуры данных
Типы данных и способы их определения. Необходимость объявления типа данных. Концепция типа данных Н.Вирта. Понятие структуры данных в программировании. Структуры, поддерживаемые языками высокого уровня. Одномерный и двумерный массивы. Логическая и физическая организация данных. Стек. Множество. Список. Запись. Очередь. Параметры очереди. Использование очереди при моделировании. Дерево. Основные параметры дерева. Размещение дерева по уровням. Понятие файла. Достоинства и недостатки различных структур данных.
Комбинаторные алгоритмы
Интуитивное понятие алгоритма. Свойства алгоритма. Вычислительные и комбинаторные алгоритмы. Понятие жадного и эвристического алгоритмов. Схема поиска решения комбинаторной задачи. Асимптотические оценки сложности алгоритма. Пространственная и временная эффективность алгоритмов. Виды оценок сложности. Их достоинства и недостатки. Комбинаторный взрыв. Жадные алгоритмы. Нахождение минимального остовного дерева. Жадный алгоритм. Алгоритм Прима. Поиск кратчайших путей между двумя заданными вершинами графа. Алгоритм Дейкстра. Алгоритм Уоршолла построения транзитивного замыкания. Эвристические алгоритмы. Основные правила. Последовательный алгоритм раскраски графа. Алгоритм раскраски А.П. Ершова. Необходимость сортировки. Пузырьковая сортировка. Сортировки выбором и вставкой. Быстрая сортировка. Идея пирамидальной сортировки. Пирамида. Свойства пирамиды. Реализация пирамидальной сортировки. Сортировка подсчётом. Её асимптотическая сложность и особенности. Достоинства и недостатки различных методов сортировки. Основная теорема сортировки. Поиск заданного элемента в одномерном неупорядоченном и отсортированном массиве. Бинарный поиск. Обходы графа поиском в глубину и ширину. Поиск в строке текста заданного фрагмента. Последовательный поиск. Метод Боуэра и Мура. Параметры сетевого планирования: ранние и поздние сроки свершения событий, полный и свободный резервы времени, критический путь и его длина. Вычисление основных параметров сетевого графика, график Ганта. ©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.
|