-
Notifications
You must be signed in to change notification settings - Fork 0
2 Типы и структуры данных
ДИСЦИПЛИНА 2.
Типы и структуры данных
Понятие стека, дека, очереди. Алгоритмы включения, исключения элементов в этих структурах. Сравнение эффективности конкретных реализаций данных структур. Алгоритмы включения и исключения элемента из двусвязного списка. Рекурсия и рекурсивные типы данных. Рекурсивные процедуры и функции. Разработка рекурсивных и итеративных алгоритмов. Оценка эффективности алгоритмов. Принципы выбора различных по эффективности алгоритмов для решения конкретных задач. Разреженные матрицы. Понятие абстрактных типов данных. Принципы создания алгоритмов с использованием абстрактных типов данных. Деревья. Алгоритм Прима. Использование различных видов деревьев для поиска и сортировки. Сравнение различных методов поиска в массивах, деревьях, хэш- таблицах. Поиск в графах. Алгоритмы поиска в ширину и глубину, построение каркасов графа. Пути в графах. Алгоритмы поиска Эйлерова и Гамильтонова пути. Алгоритмы поиска минимальных путей.
-
Понятие списка, стека, дека, очереди. Основные алгоритмы включения, исключения элементов в этих структурах. Сравнительный анализ эффективности конкретных реализаций данных структур. Алгоритмы включения и исключения элемента из двусвязного списка.
-
Понятие рекурсии. Рекурсивные типы данных. Рекурсивные процедуры и функции. Критерии выбора для разработки рекурсивных или итеративных алгоритмов.
-
Оценка эффективности алгоритмов. Принципы выбора различных по эффективности алгоритмов для решения конкретных задач.
-
Разреженные матрицы. Методы хранения и расчета разреженных матриц. Использование разреженных матриц.
-
Понятие абстрактных типов данных. Принципы создания алгоритмов с использованием абстрактных типов данных.
-
Деревья. Виды деревьев. Остовное дерево. Использование различных видов деревьев для поиска и сортировки. Сравнение различных методов поиска в массивах, деревьях, хэш-таблицах
-
Базовые понятия теории графов. Поиск в графах. Алгоритмы поиска в ширину и глубину, построение каркасов графа. Пути в графах. Алгоритмы поиска Эйлерова и Гамильтонова пути. Алгоритмы поиска минимальных путей. Раскраска графов. Планарность графов.
- Кормен Т., Лейзерсон Ч., Ривест Р., Щтайн К. Алгоритмы: Построение и анализ. 2-е изд. — М.: Издат. дом «Вильямс», 2012. -1296 с.