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

Содержание

1 Общая информация
2 Программа семинаров
3 Домашние задания
- 3.1 Первое домашнее задание. Лабиринт.
- 3.2 Второе домашнее задание. Архиватор.

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

Семинар проходит по пятницам с 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). Система непересекающихся множеств. Реализация при помощи списков и при помощи деревьев. Объединение по рангу и сжатие путей. Алгоритм Крускала и алгоритм Прима.

17 октября

Архивация и сжатие данных. Показатели качества сжатия. Динамические ряды, интервальные и моментные показатели. Теория информации. Понятие и формула информационной энтропии (энтропии Шеннона).

24 октября

Различные подходы к кодированию информации: энтропийное кодирование, арифметическое кодирование, словарное кодирование. Понятие источника и модели источника. Обновление модели источника.

31 октября

Модели источника, используемые для сжатия данных. Алгоритм сжатия PPM (Prediction by partial matching). Примеры композиции моделей источника.

7 ноября

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

14 ноября

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

21 ноября

Автоматическая документация кода Презентация.

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

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

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

Второе домашнее задание. Архиватор.

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