Алгоритмы и структуры данных 2 2021/2010-1
Материал из Wiki - Факультет компьютерных наук
Версия от 23:30, 6 октября 2021; Lll-phill-lll (обсуждение | вклад)
Страничка для материалов семинаров курса АиСД 21-22 группы БПМИ2010-1.
Содержание
- 1 Семинары
- 1.1 Материалы семинаров
- 1.1.1 Жадные алгоритмы (07.09.2021)
- 1.1.2 Префикс-функция и Алгоритм Ахо-Корасик (10.09.2021)
- 1.1.3 Сжатие и кодирование данных: алгоритмы Хаффмана и Лемпела-Зива, кодирование с исправлением ошибок (14.09.2021)
- 1.1.4 Персистентные структуры (17.09.2021)
- 1.1.5 Параллельность в C++ (Параллельные алгоритмы) (21.09.2021)
- 1.1.6 Параллельность в C++ (Параллельные алгоритмы) (24.09.2021)
- 1.1.7 Потоки в графах, метод Форда-Фалкерсона (Паросочетания, алгоритм Куна) (28.09.2021)
- 1.1.8 P, NP (01.10.2021)
- 1.1.9 P, NP (05.10.2021)
- 1.2 Оценка за семинар
- 1.3 Бонусы
- 1.4 Ссылки
- 1.1 Материалы семинаров
Семинары
Материалы семинаров
Жадные алгоритмы (07.09.2021)
Условия семинарских задач, код и заметки
Префикс-функция и Алгоритм Ахо-Корасик (10.09.2021)
Условия семинарских задач, код и заметки
Сжатие и кодирование данных: алгоритмы Хаффмана и Лемпела-Зива, кодирование с исправлением ошибок (14.09.2021)
Условия семинарских задач, код и заметки
Персистентные структуры (17.09.2021)
Условия семинарских задач, код и заметки
Текстовое описание персистентной очереди (6 стеков)
Видео с очень понятным объяснением персистентной очереди (с 55:23)
Параллельность в C++ (Параллельные алгоритмы) (21.09.2021)
Прошлый год: лекция, презентация, код, код с семинара
Запуск кода
- Установить g++9 (ubuntu): sudo apt-get install g++-9 libstdc++-9-dev libtbb-dev
- При компиляции линковать с ltbb и lpthread: g++ file.cpp --std=c++17 –ltbb –lpthread
По 5 контесту
- Засчитывается любое решение, которое «...на достаточно больших векторах выигрывает у стандартного однопоточного решения с деревом отрезков в среднем минимум на 30 %» То есть в целом не обязательно делать реализацию параллельной. Сравнивать мы будем с какой-то нашей реализацией дерева отрезков.
- Проверять мы будем руками. Есть надежда, что корректность реализации будет проверяться в контесте, но пока это так не работает. Можно попробовать проверить реализацию вне контеста, например, тут: RMQ (я не успел проверить, насколько корректно проверяется по ссылке, как проверю, отпишу дополнительно сюда, если кто-то уже попробовал посдавать, отпишите мне)
- После дедлайна досдать можно будет только на половину балла. Даже если проверка домашки произошла после дедлайна. Имейте это в виду.
Параллельность в C++ (Параллельные алгоритмы) (24.09.2021)
Запуск кода
Потоки в графах, метод Форда-Фалкерсона (Паросочетания, алгоритм Куна) (28.09.2021)
P, NP (01.10.2021)
P, NP (05.10.2021)
Оценка за семинар
За каждый семинар можно получить 1, 0.5 или 0.
- 0 - не прийти на семинар
- 0.5 - прийти на семинар
- 1 - прийти и проявить активность на семинаре
Формула оценки такая:
min(1, sum(scores) / (seminar_number - 1)) * 10