УГАТУ,ФИРТ
Преподаватель:Верхотурова Г.Н. Содержание:
Предмет изучения дисциплины "Структуры и алгоритмы обработки данных на ЭВМ". Абстрактные типы данных. Классификация структур данных.
Хеширование. Хеш-функции. Коллизии и методы их устранения. Сферы применения хеширования, достоинства метода.
Деревья: поисковое дерево, идеально - сбалансированное дерево, сбалансированное поисковое дерево, В-дерево. Рекурсивные методы прохождения деревьев. Алгоритмы построения деревьев.
Сферы применения графов. Способы машинного представления графов, их достоинства и недостатки. Графы и алгоритмы на графах.
Алгоритмы поиска в графе: поиск в ширину, поиск в глубину.
Эйлеров путь, эйлеров цикл, эйлеров граф. Алгоритм нахождения эйлерова цикла.
Нахождение кратчайших расстояний. Алгоритм Дейкстры.
Алгоритмы с возвратом.
Алгоритм нахождения гамильтоновых циклов в графе.
Метод ветвей и границ.
Остовные деревья графа. Алгоритмы нахождения дерева минимального веса: алгоритм Прима, алгоритм Крускала.
Эффективность алгоритмов и её составляющие. Алгоритмы и их сложность. Доминирование. О-функции и их особенности.
Правила для определения сложности. Функции, часто используемые для оценки сложности алгоритмов (список функционального доминирования). Сравнение алгоритмов с различными порядками сложности.
Анализ алгоритмов и определение их сложности по управляющим структурам. Контрольные замеры. Критический взгляд на О-анализ. (ограниченность О-анализа).
Полиномиальные алгоритмы и труднорешаемые задачи. Два аспекта труднорешаемости задач. Недетерминированное вычисление и класс NP.
Теория NP-полных задач. Структура класса NP.
Методы решения NP-полных задач. Применение теории NP-полноты для анализа задач.
Преподаватель:Верхотурова Г.Н. Содержание:
Предмет изучения дисциплины "Структуры и алгоритмы обработки данных на ЭВМ". Абстрактные типы данных. Классификация структур данных.
Хеширование. Хеш-функции. Коллизии и методы их устранения. Сферы применения хеширования, достоинства метода.
Деревья: поисковое дерево, идеально - сбалансированное дерево, сбалансированное поисковое дерево, В-дерево. Рекурсивные методы прохождения деревьев. Алгоритмы построения деревьев.
Сферы применения графов. Способы машинного представления графов, их достоинства и недостатки. Графы и алгоритмы на графах.
Алгоритмы поиска в графе: поиск в ширину, поиск в глубину.
Эйлеров путь, эйлеров цикл, эйлеров граф. Алгоритм нахождения эйлерова цикла.
Нахождение кратчайших расстояний. Алгоритм Дейкстры.
Алгоритмы с возвратом.
Алгоритм нахождения гамильтоновых циклов в графе.
Метод ветвей и границ.
Остовные деревья графа. Алгоритмы нахождения дерева минимального веса: алгоритм Прима, алгоритм Крускала.
Эффективность алгоритмов и её составляющие. Алгоритмы и их сложность. Доминирование. О-функции и их особенности.
Правила для определения сложности. Функции, часто используемые для оценки сложности алгоритмов (список функционального доминирования). Сравнение алгоритмов с различными порядками сложности.
Анализ алгоритмов и определение их сложности по управляющим структурам. Контрольные замеры. Критический взгляд на О-анализ. (ограниченность О-анализа).
Полиномиальные алгоритмы и труднорешаемые задачи. Два аспекта труднорешаемости задач. Недетерминированное вычисление и класс NP.
Теория NP-полных задач. Структура класса NP.
Методы решения NP-полных задач. Применение теории NP-полноты для анализа задач.