Алгоритмы и структуры данных 2 2021/2010-1 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
(→Материалы семинаров) |
|||
(не показано 20 промежуточных версии этого же участника) | |||
Строка 10: | Строка 10: | ||
=== Префикс-функция и Алгоритм Ахо-Корасик (10.09.2021) === | === Префикс-функция и Алгоритм Ахо-Корасик (10.09.2021) === | ||
[https://github.com/lll-phill-lll/hse_algorithms_seminars/tree/master/2sem-aho-korasick Условия семинарских задач, код и заметки] | [https://github.com/lll-phill-lll/hse_algorithms_seminars/tree/master/2sem-aho-korasick Условия семинарских задач, код и заметки] | ||
+ | |||
[https://disk.yandex.ru/i/o_6O8gPrkgkmKw Запись консультации] | [https://disk.yandex.ru/i/o_6O8gPrkgkmKw Запись консультации] | ||
=== Сжатие и кодирование данных: алгоритмы Хаффмана и Лемпела-Зива, кодирование с исправлением ошибок (14.09.2021) === | === Сжатие и кодирование данных: алгоритмы Хаффмана и Лемпела-Зива, кодирование с исправлением ошибок (14.09.2021) === | ||
[https://github.com/lll-phill-lll/hse_algorithms_seminars/tree/master/3sem-coding Условия семинарских задач, код и заметки] | [https://github.com/lll-phill-lll/hse_algorithms_seminars/tree/master/3sem-coding Условия семинарских задач, код и заметки] | ||
+ | |||
+ | === Персистентные структуры (17.09.2021) === | ||
+ | |||
+ | [https://github.com/lll-phill-lll/hse_algorithms_seminars/tree/master/4sem-persistent Условия семинарских задач, код и заметки] | ||
+ | |||
+ | [https://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%B5%D1%80%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BD%D1%82%D0%BD%D0%B0%D1%8F_%D0%BE%D1%87%D0%B5%D1%80%D0%B5%D0%B4%D1%8C Текстовое описание персистентной очереди (6 стеков)] | ||
+ | |||
+ | [https://youtu.be/9lPLshWk3Lk?t=3323 Видео с очень понятным объяснением персистентной очереди (с 55:23)] | ||
+ | |||
+ | === Параллельность в C++ (Параллельные алгоритмы) (21.09.2021) === | ||
+ | |||
+ | [https://github.com/lll-phill-lll/hse_algorithms_seminars/tree/master/5sem-parallel Гитхаб с кодом и пояснениями] | ||
+ | |||
+ | Прошлый год: [https://www.youtube.com/watch?v=tyAFU7H_Z-E&list=PLEwK9wdS5g0rBPRiw6jl6fnIMY2vne-hM&index=14 лекция], | ||
+ | [https://drive.google.com/file/d/19oARvl7S7vraE2wACS75qxf8Bf_HxMT7/view?usp=sharing презентация], | ||
+ | [https://drive.google.com/file/d/1Jp7lyIv1xgnrWE7nG6KSIWG4gD1Y50ql/view?usp=sharing код], | ||
+ | [https://drive.google.com/file/d/1eNE-vxRH2UeSUXqJelvtDIyluThkLC5K/view?usp=sharing код с семинара] | ||
+ | |||
+ | ==== Запуск кода ==== | ||
+ | |||
+ | # Установить 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 %» То есть в целом не обязательно делать реализацию параллельной. Сравнивать мы будем с какой-то нашей реализацией дерева отрезков. | ||
+ | # Проверять мы будем руками. Есть надежда, что корректность реализации будет проверяться в контесте, но пока это так не работает. Можно попробовать проверить реализацию вне контеста, например, [https://informatics.msk.ru/mod/statements/view.php?id=597&chapterid=752#1 тут]: RMQ (я не успел проверить, насколько корректно проверяется по ссылке, как проверю, отпишу дополнительно сюда, если кто-то уже попробовал посдавать, отпишите мне) | ||
+ | # После дедлайна досдать можно будет только на половину балла. Даже если проверка домашки произошла после дедлайна. Имейте это в виду. | ||
+ | |||
+ | === Параллельность в C++ (Параллельные алгоритмы) (24.09.2021) === | ||
+ | |||
+ | [https://github.com/lll-phill-lll/hse_algorithms_seminars/tree/master/6sem-parallel Гитхаб с кодом и пояснениями] | ||
+ | |||
+ | ==== Запуск кода ==== | ||
+ | # [https://colab.research.google.com/drive/1_XmRWgpsLu4XmbachJ0oq9lsfbwqTueh?usp=sharing Пример] с запуском C++ кода в колабе (установка нужных либ) | ||
+ | # Также ноутбук доступен на [https://github.com/lll-phill-lll/hse_algorithms_seminars/tree/master/6sem-parallel гитхабе] | ||
+ | |||
+ | === Потоки в графах, метод Форда-Фалкерсона (Паросочетания, алгоритм Куна) (28.09.2021) === | ||
+ | |||
+ | [https://github.com/lll-phill-lll/hse_algorithms_seminars/tree/master/7sem-flows Гитхаб с кодом и пояснениями] | ||
+ | |||
+ | === P, NP (01.10.2021) === | ||
+ | |||
+ | [https://github.com/lll-phill-lll/hse_algorithms_seminars/tree/master/8sem-P-NP Гитхаб с кодом и пояснениями] | ||
+ | |||
+ | [https://disk.yandex.com/i/FRkCs5rZyt0F-w Запись консультации (p1)] | ||
+ | |||
+ | [https://disk.yandex.com/i/aN0wN4qn0KQPBg Запись консультации (p2)] | ||
+ | |||
+ | === Эвристики в рекурсивном переборе (05.10.2021) === | ||
+ | |||
+ | [https://github.com/lll-phill-lll/hse_algorithms_seminars/tree/master/9sem-optimized-brute-force Гитхаб с кодом и пояснениями] | ||
+ | |||
+ | === Вычислительная геометрия (08.10.2021) === | ||
+ | |||
+ | [https://github.com/lll-phill-lll/hse_algorithms_seminars/tree/master/10sem-geometry Гитхаб с с конспектом] | ||
+ | |||
+ | [https://codeforces.com/problemset?order=BY_SOLVED_DESC&tags=geometry Задачи с Codeforces по геометрии] | ||
== Оценка за семинар == | == Оценка за семинар == | ||
За каждый семинар можно получить 1, 0.5 или 0. | За каждый семинар можно получить 1, 0.5 или 0. | ||
− | * 0 - не прийти на семинар | + | * 0 - не прийти на семинар |
* 0.5 - прийти на семинар | * 0.5 - прийти на семинар | ||
− | * 1 - прийти и проявить активность на семинаре | + | * 1 - прийти и проявить активность на семинаре |
Формула оценки такая: | Формула оценки такая: | ||
Строка 33: | Строка 93: | ||
[https://docs.google.com/spreadsheets/d/1lFaDg0LRsjrzTit4pNLeUS8lwy-XHBzOeZxjx2eZrnA/edit?usp=sharing Таблица с оценками] | [https://docs.google.com/spreadsheets/d/1lFaDg0LRsjrzTit4pNLeUS8lwy-XHBzOeZxjx2eZrnA/edit?usp=sharing Таблица с оценками] | ||
+ | |||
+ | [https://forms.gle/8RpsNWa7nypRpMkdA Обратная связь (анонимно)] |
Текущая версия на 15:17, 9 октября 2021
Страничка для материалов семинаров курса АиСД 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 Эвристики в рекурсивном переборе (05.10.2021)
- 1.1.10 Вычислительная геометрия (08.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)
Эвристики в рекурсивном переборе (05.10.2021)
Вычислительная геометрия (08.10.2021)
Задачи с Codeforces по геометрии
Оценка за семинар
За каждый семинар можно получить 1, 0.5 или 0.
- 0 - не прийти на семинар
- 0.5 - прийти на семинар
- 1 - прийти и проявить активность на семинаре
Формула оценки такая:
min(1, sum(scores) / (seminar_number - 1)) * 10