4.1. Тематический план

№	Раздел дисциплины	Лекции	ПЗ или С	ЛР
1	Структуры данных.	16	4	10
2	Программная реализация алгоритмов	18	4	12
3	Оценки сложности работы алгоритма	2	2	2
4	Алгоритмы сортировки.	4	2	4
5	Алгоритмы поиска.	4	2	2
6	Алгоритмы на графах.	6	2	4
7	Генерация псевдослучайных последовательностей и алгоритмы порождения перестановок.	4	2	2

4.2. Содержание разделов дисциплины

Раздел 1. Структуры данных.

1. Цели и задачи курса. Место дисциплины в учебном процессе. Методические рекомендации по изучению курса. Обзор литературы.

2. Элементарные и простые структуры данных. Сложные структуры данных.

3. Указатели и ссылки.

4. Статические и динамические структуры.

5. Файловые структуры.

6. Контейнерные классы библиотеки std языка C++..

Раздел 2. Программная реализация алгоритмов.

2.1. Базовые операторы языков программирования.

2.2. Функции.

2.3. Структурные и объектные принципы программной реализации.

2.4. Косвенное обращение и полиморфизм в классах.

2.5 Реализация и интерфейсы.

2.6.Причины возникновения и обработка исключительных ситуаций.

Раздел 3. Алгоритмы сортировки.

3.1. Понятие модели вычислений и оценки сложности алгоритмов.

3.2. Основные понятия и стратегии сортировки. Алгоритмы сортировки вставками, выбором, слиянием, обменная сортировка, распределяющая сортировка. Оценка сложности работы алгоритмов внутренней сортировки.

3.3. Основные понятия внешней сортировки. Алгоритмы многофазного и каскадного слияния.

Раздел 4. Алгоритмы поиска.

4.1. Основные понятия. Алгоритмы исчерпывающего поиска.

4.2.Поиск в последовательно организованном файле.

4.3.Поиск в деревьях. Оптимальные деревья двоичного поиска. Сбалансированные деревья.

4.4. Хеширование. Разрешение коллизий.

Раздел 5. Алгоритма на графах.

5.1. Возможные представления графов в ЭВМ.

5.2. Остовные деревья. Алгоритмы поиска связных и двусвязных компоненит в неорентированных графах. Алгоритм поиска сильносвязных компонент в ориентированных графах.

5.3.Алгоритмы нахождение остовного дерева минимального веса, определения кратчайших расстояний между вершинами графа.

Раздел 6. Генерация псевдослучайных последовательностей и алгоритмы порождения перестановок.

6.1. Моделирование равномерно распределенных случайных величин. Методы моделирования дискретных и непрерывных случайных величин.

6.2. Алгоритмы порождения перестановок в лексикографическом порядке, циклическим сдвигом и в порядке минимального изменения. Коды Грея.

6.3. Итоги изучения курса. Методические рекомендации по применению полученных знаний, умений и навыков при изучении последующих курсов.

5. Лабораторный практикум

№ п/п	№ раздела дисциплины	Наименование лабораторных работ
1	1	Знакомство со средой программирования.
2	1	Объявление и инициализация простых данных. Запись констант. Внутреннее представление и доменные области. Операции с битами.
3	1	Создание структур данных с использованием статических массивов и перечисляемых типов.
4	2	Вычисление арифметических и логических выражений. Циклы. Условные операторы.
5	2	Функции. Определение и описание. Рекурсивный вызов функций.
6	2	Обработка файловых структур данных Ввод/вывод для двоичных файлов и использование стандартных функций времени на примере реализации регистрации событий.
7	2	Проектирование иерархий классов. Создание объектов с использованием конструкторов разных семантических типов.
8	2	Реализация методов классов с использованием механизма перегрузки операций.
9	2	Массив указателей типа абстрактного класса и полиморфное поведение объектов классов потомков.
10	2	Определение, генерация и обработка исключений.
11	2	Реализация шаблонного контейнерного класса.
12	3	Реализация алгоритма сортировки на примере массивов.
13	3	Реализация алгоритма сортировки на примере списков и ассоциативных массивов.
14	4	Поиск в файле, отсортированном по ключу поиска и с использованием таблицы индексов.
15	4	Балансировка двоичного дерева
16	5	Реализация алгоритма Крускала для поиска минимального остовного дерева неориентированного графа.
17	6	Моделирование нормального распределения случайной величины

6. Учебно-методическое обеспечение дисциплины