Практикум (3 курс, осенний семестр 2014 года) — различия между версиями
м (→Первое домашнее задание. Лабиринт.) |
Root (обсуждение | вклад) |
||
| (не показаны 4 промежуточных версий 1 участника) | |||
| Строка 1: | Строка 1: | ||
| + | [[Категория:Семинары кафедры математической кибернетики (архив)]] | ||
| + | |||
== Общая информация == | == Общая информация == | ||
Семинар проходит по пятницам с 14:35 до 16:05 в аудитории 604. Семинары ведет [[Шуплецов Михаил Сергеевич]]. | Семинар проходит по пятницам с 14:35 до 16:05 в аудитории 604. Семинары ведет [[Шуплецов Михаил Сергеевич]]. | ||
| Строка 12: | Строка 14: | ||
Способы представления графов в памяти компьютера: [http://en.wikipedia.org/wiki/Adjacency_matrix| матрица смежности] и [http://en.wikipedia.org/wiki/Incidence_matrix| матрица инцидентности], [http://en.wikipedia.org/wiki/Adjacency_list| списки смежности] и инцидентности. Обходы графов. Поиск в ширину ([http://en.wikipedia.org/wiki/Breadth-first_search| BFS]) и в глубину ([http://en.wikipedia.org/wiki/Depth-first_search| DFS]). BFS и DFS как внешние итераторы для графа. | Способы представления графов в памяти компьютера: [http://en.wikipedia.org/wiki/Adjacency_matrix| матрица смежности] и [http://en.wikipedia.org/wiki/Incidence_matrix| матрица инцидентности], [http://en.wikipedia.org/wiki/Adjacency_list| списки смежности] и инцидентности. Обходы графов. Поиск в ширину ([http://en.wikipedia.org/wiki/Breadth-first_search| BFS]) и в глубину ([http://en.wikipedia.org/wiki/Depth-first_search| DFS]). BFS и DFS как внешние итераторы для графа. | ||
=== 3 октября === | === 3 октября === | ||
| − | Задача поиска минимальных путей в графе ([http://en.wikipedia.org/wiki/Shortest_path_problem| Shortest path problem]). [http://en.wikipedia.org/wiki/Priority_queue| Очередь с приоритетами]. Реализация очередей с | + | Задача поиска минимальных путей в графе ([http://en.wikipedia.org/wiki/Shortest_path_problem| Shortest path problem]). [http://en.wikipedia.org/wiki/Priority_queue| Очередь с приоритетами]. Реализация очередей с приоритетами при помощи [http://en.wikipedia.org/wiki/Heap_(data_structure)| бинарных куч]. Операции добавления элемента в очередь с приоритетом, удаления элемента из очереди и операция изменения приоритета. [http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm| Алгоритм Дейкстры]. Поиск путей при наличии дополнительной информации. [http://en.wikipedia.org/wiki/A*_search_algorithm| Алгоритм А*]. |
=== 10 октября === | === 10 октября === | ||
Задача поиска минимального остовного дерева дерева в графе ([http://en.wikipedia.org/wiki/Minimum_spanning_tree| Minimal spanning tree]). [http://en.wikipedia.org/wiki/Disjoint-set_data_structure| Система непересекающихся множеств]. Реализация при помощи списков и при помощи деревьев. Объединение по рангу и сжатие путей. [http://en.wikipedia.org/wiki/Kruskal%27s_algorithm| Алгоритм Крускала] и [http://en.wikipedia.org/wiki/Prim%27s_algorithm| алгоритм Прима]. | Задача поиска минимального остовного дерева дерева в графе ([http://en.wikipedia.org/wiki/Minimum_spanning_tree| Minimal spanning tree]). [http://en.wikipedia.org/wiki/Disjoint-set_data_structure| Система непересекающихся множеств]. Реализация при помощи списков и при помощи деревьев. Объединение по рангу и сжатие путей. [http://en.wikipedia.org/wiki/Kruskal%27s_algorithm| Алгоритм Крускала] и [http://en.wikipedia.org/wiki/Prim%27s_algorithm| алгоритм Прима]. | ||
| + | === 17 октября === | ||
| + | Архивация и сжатие данных. Показатели качества сжатия. Динамические ряды, интервальные и моментные показатели. Теория информации. Понятие и формула информационной энтропии (энтропии Шеннона). | ||
| + | === 24 октября === | ||
| + | Различные подходы к кодированию информации: энтропийное кодирование, арифметическое кодирование, словарное кодирование. Понятие источника и модели источника. Обновление модели источника. | ||
| + | === 31 октября === | ||
| + | Модели источника, используемые для сжатия данных. [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%81%D0%B6%D0%B0%D1%82%D0%B8%D1%8F_PPM Алгоритм сжатия PPM] ([http://en.wikipedia.org/wiki/Prediction_by_partial_matching Prediction by partial matching]). Примеры композиции моделей источника. | ||
| + | |||
| + | === 7 ноября === | ||
| + | Системы контроля версий. Централизованные и распределенные системы контроля версий. Разработка с использованием систем контроля версий. Система контроля версий Git. Основные возможности Git. | ||
| + | === 14 ноября === | ||
| + | Работа с системой контроля версий Git. Навигация по истории проекта (commit history). Работа с ветвями(branching): создание, управление и слияние. Работа с удаленным сервером. | ||
| + | === 21 ноября === | ||
| + | Автоматическая документация кода [[Media:Prac_318_documentation.pdf|Презентация]]. | ||
| + | |||
== Домашние задания == | == Домашние задания == | ||
=== Первое домашнее задание. Лабиринт. === | === Первое домашнее задание. Лабиринт. === | ||
| Строка 21: | Строка 37: | ||
* Срок сдачи задания: '''2 ноября'''. | * Срок сдачи задания: '''2 ноября'''. | ||
* Дополнительный срок сдачи задания: '''9 ноября'''(задания, присланные в дополнительный срок, оцениваются с дополнительным штрафом в 50% от полученных баллов). | * Дополнительный срок сдачи задания: '''9 ноября'''(задания, присланные в дополнительный срок, оцениваются с дополнительным штрафом в 50% от полученных баллов). | ||
| − | [[ | + | |
| + | === Второе домашнее задание. Архиватор. === | ||
| + | * [[Media:Prac_2014_318_HW2.pdf|Описание задания]]. | ||
| + | * Срок сдачи задания: '''7 декабря'''. | ||
| + | * Дополнительный срок сдачи задания: '''14 декабря'''(задания, присланные в дополнительный срок, оцениваются с дополнительным штрафом в 50% от полученных баллов). | ||
Текущая версия на 18:19, 9 февраля 2019
Общая информация
Семинар проходит по пятницам с 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% от полученных баллов).
