Практикум (3 курс, осенний семестр 2015 года)

Общая информация

Занятия проходят по пятницам с 14:35 до 16:10 в аудитории 604. Занятия ведет Шуплецов Михаил Сергеевич.

Программа семинаров

Семинар 1. 4 сентября. Вводный семинар. Обсуждение общего плана занятий в семестре. Анкетирование студентов. Проведение вводной контрольной.

Семинар 2. 11 сентября Объявление результатов анкетирования и разбор вводной контрольной. Критерии качества программ. Стандарты оформления кода (Code style guides). Презентация.

Семинар 3. 18 сентября Автоматическая сборка проекта. Утилита GNU Make. Презентация. Автоматический разбор параметров командной строки библиотека getOpt.

Семинар 4. 2 октября. Системы контроля версий. Централизованные и распределенные системы контроля версий. Разработка с использованием систем контроля версий. Система контроля версий Git. Основные возможности Git.

Семинар 5. 16 октября. Работа с системой контроля версий Git. Навигация по истории проекта (commit history). Работа с ветвями(branching): создание, управление и слияние. Работа с удаленным сервером. Системы управления проектом. Обзор возможностей системы GitLab.

Семинар 6. 23 октября Тестирование программ. Введение в тестирование. Распространенные ошибки. Основные принципы и подходы к тестированию программ. Среды тестирования программ на примере CppUnit. Автоматическая документация кода.

Семинар 7. 20 ноября Бинарное дерево поиска. Поиск по ключу, поиск максимума и минимума, предшествующий и последующий элементы. Вставка и удаление. Пирамида (binary heap). Свойство пирамиды. Поддержка свойства пирамиды. Создание пирамиды. Пирамидальная сортировка. Очередь с приоритетами.

Семинар 8. 27 ноября Система непересекающихся множеств. Представление непересекающихся множеств с помощью списков. Лес непересекающихся множеств. Корневая, весовая и ранговая эвристики. Влияние эвристик на время работы. Анализ объединения по рангу со сжатием пути.

Семинар 9. 4 декабря Способы представления графов в памяти компьютера: матрица смежности и инцидентности, списки смежности и инцидентности. Обходы графов. Поиск в ширину (BFS) и в глубину (DFS). BFS и DFS как внешние итераторы для графа.

Семинар 10. 4 декабря Задача поиска минимального остовного дерева дерева в графе (Minimal spanning tree). Алгоритм Крускала и алгоритм Прима.

Семинар 11. 11 декабря Задача поиска минимальных путей в графе (Shortest path problem). Алгоритм Дейкстры. Поиск путей при наличии дополнительной информации. Алгоритм А*.

Семинар 12. 18 декабря Кратчайшие пути между всеми парами вершин. Алгоритм Флойда. Транзитивное замыкание. Подведение итогов. Финальное анкетирование.

Домашние задания

Первое домашнее задание. Лабиринт.

• Описание задания.
• Срок сдачи задания: 1 ноября.
• Дополнительный срок сдачи задания: 8 ноября(задания, присланные в дополнительный срок, оцениваются с дополнительным штрафом в 50% от полученных баллов).

Второе домашнее задание. Алгоритмы на графах.

• Описание задания.
• Срок сдачи задания: до конца семестра.