Практикум (3 курс, осенний семестр 2015 года) — различия между версиями

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
м (Второе домашнее задание.)
м (Программа семинаров)
Строка 28: Строка 28:
  
 
''' Семинар 9. '''
 
''' Семинар 9. '''
Способы представления графов в памяти компьютера: матрица смежности и инцидентности, списки смежности и инцидентности. Boost Graph Library (BGL). Основы работы с графами в BGL. Создание и модификация графов. Доступ к элементам графа: итераторы вершин и ребер. Добавление свойств к элементам графа.
+
Способы представления графов в памяти компьютера: матрица смежности и инцидентности, списки смежности и инцидентности. Обходы графов. Поиск в ширину (BFS) и в глубину (DFS). BFS и DFS как внешние итераторы для графа.
  
 
''' Семинар 10. '''
 
''' Семинар 10. '''
Обходы графов. Поиск в ширину (BFS) и в глубину (DFS). BFS и DFS как внешние итераторы для графа. Неявное задание графа при обходе. Реализация обходов графа в BGL.
+
Задача поиска минимального остовного дерева дерева в графе (Minimal spanning tree). Алгоритм Крускала и алгоритм Прима.
  
 
''' Семинар 11. '''
 
''' Семинар 11. '''
Задача поиска минимального остовного дерева дерева в графе (Minimal spanning tree). Алгоритм Крускала и алгоритм Прима.
+
Задача поиска минимальных путей в графе (Shortest path problem). Алгоритм Дейкстры. Поиск путей при наличии дополнительной информации. Алгоритм А*.
  
 
''' Семинар 12. '''
 
''' Семинар 12. '''
Задача поиска минимальных путей в графе (Shortest path problem). Алгоритм Дейкстры. Поиск путей при наличии дополнительной информации. Алгоритм А*.
+
Кратчайшие пути между всеми парами вершин. Алгоритм Флойда. Транзитивное замыкание. Подведение итогов. Финальное анкетирование.
 
+
''' Семинар 13. '''
+
Кратчайшие пути между всеми парами вершин. Алгоритм Флойда. Транзитивное замыкание.
+
 
+
''' Семинар 14. '''
+
Подведение итогов. Финальное анкетирование.
+
  
 
== Домашние задания ==
 
== Домашние задания ==

Версия 13:50, 12 декабря 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. Бинарное дерево поиска. Поиск по ключу, поиск максимума и минимума, предшествующий и последующий элементы. Вставка и удаление. Пирамида (binary heap). Свойство пирамиды. Поддержка свойства пирамиды. Создание пирамиды. Пирамидальная сортировка. Очередь с приоритетами.

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

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

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

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

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

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

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

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

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

Третье домашнее задание.

TBA