Практикум (3 курс, осенний семестр 2015 года) — различия между версиями
м (→Программа семинаров) |
м (→Программа семинаров) |
||
| Строка 7: | Строка 7: | ||
''' Семинар 2. 11 сентября ''' | ''' Семинар 2. 11 сентября ''' | ||
| − | [[Media: | + | [[Media:Survey_318_2015.pdf|Объявление результатов анкетирования и разбор вводной контрольной]]. Критерии качества программ. Стандарты оформления кода (Code style guides). [[Media:Prac_318_Style_guide.pdf|Презентация]]. |
''' Семинар 3. 18 сентября ''' | ''' Семинар 3. 18 сентября ''' | ||
| Строка 13: | Строка 13: | ||
''' Семинар 4. 2 октября. ''' | ''' Семинар 4. 2 октября. ''' | ||
| − | Системы контроля версий. Централизованные и распределенные системы контроля версий. Разработка с использованием систем контроля версий. Система контроля версий Git. Основные возможности Git. | + | Системы контроля версий. Централизованные и распределенные системы контроля версий. Разработка с использованием систем контроля версий. Система контроля версий Git. Основные возможности Git. [[Media:Prac_318_Git.pdf|Презентация]] |
''' Семинар 5. 16 октября. ''' | ''' Семинар 5. 16 октября. ''' | ||
| Строка 19: | Строка 19: | ||
''' Семинар 6. 23 октября ''' | ''' Семинар 6. 23 октября ''' | ||
| − | Тестирование программ. Введение в тестирование. Распространенные ошибки. Основные принципы и подходы к тестированию программ. Среды тестирования программ на примере CppUnit. Автоматическая документация кода. | + | Тестирование программ. Введение в тестирование. Распространенные ошибки. Основные принципы и подходы к тестированию программ. Среды тестирования программ на примере CppUnit. Автоматическая документация кода. [[Media:Prac_318_documentation.pdf|Презентация]] |
''' Семинар 7. 20 ноября ''' | ''' Семинар 7. 20 ноября ''' | ||
| − | Бинарное дерево поиска. Поиск по ключу, поиск максимума и минимума, предшествующий и последующий элементы. Вставка и удаление. Пирамида (binary heap). Свойство пирамиды. Поддержка свойства пирамиды. Создание пирамиды. Пирамидальная сортировка. Очередь с приоритетами. | + | Бинарное дерево поиска. Поиск по ключу, поиск максимума и минимума, предшествующий и последующий элементы. Вставка и удаление. Пирамида (binary heap). Свойство пирамиды. Поддержка свойства пирамиды. Создание пирамиды. Пирамидальная сортировка. [http://en.wikipedia.org/wiki/Priority_queue| Очередь с приоритетами]. |
''' Семинар 8. 27 ноября ''' | ''' Семинар 8. 27 ноября ''' | ||
| − | Система непересекающихся множеств. Представление непересекающихся множеств с помощью списков. Лес непересекающихся множеств. Корневая, весовая и ранговая эвристики. Влияние эвристик на время работы. Анализ объединения по рангу со сжатием пути. | + | [http://en.wikipedia.org/wiki/Disjoint-set_data_structure| Система непересекающихся множеств]. Представление непересекающихся множеств с помощью списков. Лес непересекающихся множеств. Корневая, весовая и ранговая эвристики. Влияние эвристик на время работы. Анализ объединения по рангу со сжатием пути. [[Media:Prac_318_DSDS.pdf|Презентация]]. |
''' Семинар 9. 4 декабря ''' | ''' Семинар 9. 4 декабря ''' | ||
| − | Способы представления графов в памяти компьютера: матрица смежности и инцидентности, списки смежности и инцидентности. Обходы графов. Поиск в ширину (BFS) и в глубину (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 как внешние итераторы для графа. [[Media:Prac_318_Graph_intro.pdf|Презентация]]. |
''' Семинар 10. 4 декабря ''' | ''' Семинар 10. 4 декабря ''' | ||
| − | Задача поиска минимального остовного дерева дерева в графе (Minimal spanning tree). Алгоритм Крускала и алгоритм Прима. | + | Задача поиска минимального остовного дерева дерева в графе (Minimal spanning tree). [http://en.wikipedia.org/wiki/Kruskal%27s_algorithm| Алгоритм Крускала] и [http://en.wikipedia.org/wiki/Prim%27s_algorithm| алгоритм Прима]. |
''' Семинар 11. 11 декабря ''' | ''' Семинар 11. 11 декабря ''' | ||
| − | Задача поиска минимальных путей в графе (Shortest path problem). Алгоритм Дейкстры. Поиск путей при наличии дополнительной информации. Алгоритм А*. | + | Задача поиска минимальных путей в графе ([http://en.wikipedia.org/wiki/Shortest_path_problem| Shortest path problem]). [http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm| Алгоритм Дейкстры]. Поиск путей при наличии дополнительной информации. [http://en.wikipedia.org/wiki/A*_search_algorithm| Алгоритм А*]. |
''' Семинар 12. 18 декабря ''' | ''' Семинар 12. 18 декабря ''' | ||
Версия 23:10, 28 декабря 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% от полученных баллов).
Второе домашнее задание. Алгоритмы на графах.
- Описание задания.
- Срок сдачи задания: до конца семестра.
