Структуры и алгоритмы обработки данных

Тема 14. Файлы: организация и обработка, представление деревьями 
Организация данных во внешней памяти: файлы и их организация на
устройствах внешней памяти; обработка последовательных файлов; 
организация библиотечных файлов; индексно-последовательные файлы, их 
структура; Представление индексно-последовательных файлов деревьями. 
Файлы прямого доступа; Прямая и косвенная адресация; Метод 
хеширования. Методы управления переполнением. Обработка файлов прямого 
доступа. Организация данных во внешней памяти. Виртуальная память. Типы 
систем виртуальной памяти. Страничная организация памяти. Алгоритмы 
замещения страниц. 
Тема 15. Сетевые структуры и алгоритмы их обработки 
Графы и их представление в ЭВМ (матрицы инциденций, матрицы 
смежности, 
список 
пар, 
списки 
инцидентности). 
Преобразования 
представлений. Остовные деревья графа. Минимальное остовное дерево. 
Жадный алгоритм (Краскала). Алгоритм ближайшего соседа (Прим, Дейкстра). 
Задача коммивояжера. Поиск в графе: поиск в ширину; поиск в глубину. 
Кратчайшие пути в орграфе. Алгоритм отыскания кратчайшего пути. 
Кратчайший путь от фиксированной вершины: алгоритм Форда-Беллмана. 
Кратчайший путь в графе с неотрицательными весами: алгоритм Дейкстры. 
Кратчайшие пути в безконтурном графе. Кратчайшие пути между всеми 
парами вершин: алгоритм Флойда. Алгоритмы нахождения остовного дерева 

---

14 
наименьшей стоимости (алгоритмы Прима и Краскала). Алгоритм Уоршалла. 
Задача о потоках. Алгоритм Форда-Фалкерсона. Разновидности потоковых 
задач и алгоритмов. Навыки моделирования, анализа и использования 
формальных методов конструирования программного обеспечения (ПК-12). 
Тема 16. Теория сложности алгоритмов: NP-сложные и труднорешаемые 
задачи. 
Связь NP-полных задач Задача 3-выполнимости. Связь задач по 
сложности NP-трудные задачи. Класс языков P-SPACE. Связь ДМТ и НМТ по 
емкостной сложности. Связь классов языков P-SPACE, P, NP-полных и NP-
трудных. Различные формы постановки задач комбинаторной оптимизации: 
оптимизационная, вычислительная, форма распознавания. Примеры. Классы P 
и NP задач. Полиномиальная преобразуемость задач. NP-трудные и NP-полные 
задачи. Теорема Кука о задаче выполнимости булева выражения. 
Доказательство NP-полноты задачи о выполнимости. Преобразуемость задачи о 
выполнимости в задачу о 3-выполнимости. Полиномиальность задачи о 2-
выполнимости. Задача о клике графа. Преобразуемость задачи о 3-
выполнимости в задачу о клике. Задача о многопроцессорном расписании 
(МПР). Преобразуемость задачи о клике в задачу о МПР. Практическое 
решение NP-полных задач. 
Обосновывание принимаемых проектных решений, осуществление 
постановка и выполнение экспериментов по проверке их корректности и 
эффективности (ПК-4); 

---

15