Skip to content

2 Типы и структуры данных

Jump to bottom
Winterpuma edited this page Jun 27, 2021 · 1 revision

ДИСЦИПЛИНА 2.
Типы и структуры данных

Понятие стека, дека, очереди. Алгоритмы включения, исключения элементов в этих структурах. Сравнение эффективности конкретных реализаций данных структур. Алгоритмы включения и исключения элемента из двусвязного списка. Рекурсия и рекурсивные типы данных. Рекурсивные процедуры и функции. Разработка рекурсивных и итеративных алгоритмов. Оценка эффективности алгоритмов. Принципы выбора различных по эффективности алгоритмов для решения конкретных задач. Разреженные матрицы. Понятие абстрактных типов данных. Принципы создания алгоритмов с использованием абстрактных типов данных. Деревья. Алгоритм Прима. Использование различных видов деревьев для поиска и сортировки. Сравнение различных методов поиска в массивах, деревьях, хэш- таблицах. Поиск в графах. Алгоритмы поиска в ширину и глубину, построение каркасов графа. Пути в графах. Алгоритмы поиска Эйлерова и Гамильтонова пути. Алгоритмы поиска минимальных путей.

Перечень вопросов.

  1. Понятие списка, стека, дека, очереди. Основные алгоритмы включения, исключения элементов в этих структурах. Сравнительный анализ эффективности конкретных реализаций данных структур. Алгоритмы включения и исключения элемента из двусвязного списка.

  2. Понятие рекурсии. Рекурсивные типы данных. Рекурсивные процедуры и функции. Критерии выбора для разработки рекурсивных или итеративных алгоритмов.

  3. Оценка эффективности алгоритмов. Принципы выбора различных по эффективности алгоритмов для решения конкретных задач.

  4. Разреженные матрицы. Методы хранения и расчета разреженных матриц. Использование разреженных матриц.

  5. Понятие абстрактных типов данных. Принципы создания алгоритмов с использованием абстрактных типов данных.

  6. Деревья. Виды деревьев. Остовное дерево. Использование различных видов деревьев для поиска и сортировки. Сравнение различных методов поиска в массивах, деревьях, хэш-таблицах

  7. Базовые понятия теории графов. Поиск в графах. Алгоритмы поиска в ширину и глубину, построение каркасов графа. Пути в графах. Алгоритмы поиска Эйлерова и Гамильтонова пути. Алгоритмы поиска минимальных путей. Раскраска графов. Планарность графов.

Основная учебная литература.

  1. Кормен Т., Лейзерсон Ч., Ривест Р., Щтайн К. Алгоритмы: Построение и анализ. 2-е изд. — М.: Издат. дом «Вильямс», 2012. -1296 с.
Clone this wiki locally