Практикум (3 курс, осенний семестр 2014 года)
Содержание
Общая информация
Семинар проходит по пятницам с 14:35 до 16:05 в аудитории 604. Семинары ведет Шуплецов Михаил Сергеевич.
Программа семинаров
5 сентября
Вводный семинар. Обсуждение общего плана занятий в семестре. Анкетирование студентов. Проведение вводной контрольной.
12 сентября
Объявление результатов анкетирования и разбор вводной контрольной. Стандарты оформления кода, стили программирования (Code style guides). Презентация.
19 сентября
Автоматическая сборка проекта. Утилита GNU Make. Презентация. Автоматический разбор параметров командной строки библиотека getOpt.
26 сентября
Способы представления графов в памяти компьютера: матрица смежности и матрица инцидентности, списки смежности и инцидентности. Обходы графов. Поиск в ширину (BFS) и в глубину (DFS). BFS и DFS как внешние итераторы для графа.
3 октября
Задача поиска минимальных путей в графе (Shortest path problem). Очередь с приоритетами. Реализация очередей с приоретати при помощи бинарных куч. Операции добавления элемента в очередь с приоритетом, удаления элемента из очереди и операция изменения приоритета. Алгоритм Дейкстры. Поиск путей при наличии дополнительной информации. Алгоритм А*.
10 октября
Задача поиска минимального остовного дерева дерева в графе (Minimal spanning tree). Система непересекающихся множеств. Реализация при помощи списков и при помощи деревьев. Объединение по рангу и сжатие путей. Алгоритм Крускала и алгоритм Прима.
Домашние задания
Первое домашнее задание. Лабиринт.
- Описание задания.
- Сроки сдачи задания продлены на 1 неделю (обновленные сроки смотри ниже).
- Срок сдачи задания: 2 ноября.
- Дополнительный срок сдачи задания: 9 ноября(задания, присланные в дополнительный срок, оцениваются с дополнительным штрафом в 50% от полученных баллов).
