Алгоритмы и структуры данных 2 2021/2010-1 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
Строка 64: Строка 64:
  
 
[https://disk.yandex.com/i/aN0wN4qn0KQPBg Запись консультации (p2)]
 
[https://disk.yandex.com/i/aN0wN4qn0KQPBg Запись консультации (p2)]
 +
 +
=== P, NP (05.10.2021) ===
 +
 +
[https://github.com/lll-phill-lll/hse_algorithms_seminars/tree/master/9sem-optimized-brute-force Гитхаб с кодом и пояснениями]
  
 
== Оценка за семинар ==
 
== Оценка за семинар ==

Версия 23:30, 6 октября 2021

на страницу курса

Страничка для материалов семинаров курса АиСД 21-22 группы БПМИ2010-1.

Семинары

Материалы семинаров

Жадные алгоритмы (07.09.2021)

Условия семинарских задач, код и заметки

Префикс-функция и Алгоритм Ахо-Корасик (10.09.2021)

Условия семинарских задач, код и заметки

Запись консультации

Сжатие и кодирование данных: алгоритмы Хаффмана и Лемпела-Зива, кодирование с исправлением ошибок (14.09.2021)

Условия семинарских задач, код и заметки

Персистентные структуры (17.09.2021)

Условия семинарских задач, код и заметки

Текстовое описание персистентной очереди (6 стеков)

Видео с очень понятным объяснением персистентной очереди (с 55:23)

Параллельность в C++ (Параллельные алгоритмы) (21.09.2021)

Гитхаб с кодом и пояснениями

Прошлый год: лекция, презентация, код, код с семинара

Запуск кода

  1. Установить g++9 (ubuntu): sudo apt-get install g++-9 libstdc++-9-dev libtbb-dev
  2. При компиляции линковать с ltbb и lpthread: g++ file.cpp --std=c++17 –ltbb –lpthread

По 5 контесту

  1. Засчитывается любое решение, которое «...на достаточно больших векторах выигрывает у стандартного однопоточного решения с деревом отрезков в среднем минимум на 30 %» То есть в целом не обязательно делать реализацию параллельной. Сравнивать мы будем с какой-то нашей реализацией дерева отрезков.
  2. Проверять мы будем руками. Есть надежда, что корректность реализации будет проверяться в контесте, но пока это так не работает. Можно попробовать проверить реализацию вне контеста, например, тут: RMQ (я не успел проверить, насколько корректно проверяется по ссылке, как проверю, отпишу дополнительно сюда, если кто-то уже попробовал посдавать, отпишите мне)
  3. После дедлайна досдать можно будет только на половину балла. Даже если проверка домашки произошла после дедлайна. Имейте это в виду.

Параллельность в C++ (Параллельные алгоритмы) (24.09.2021)

Гитхаб с кодом и пояснениями

Запуск кода

  1. Пример с запуском C++ кода в колабе (установка нужных либ)
  2. Также ноутбук доступен на гитхабе

Потоки в графах, метод Форда-Фалкерсона (Паросочетания, алгоритм Куна) (28.09.2021)

Гитхаб с кодом и пояснениями

P, NP (01.10.2021)

Гитхаб с кодом и пояснениями

Запись консультации (p1)

Запись консультации (p2)

P, NP (05.10.2021)

Гитхаб с кодом и пояснениями

Оценка за семинар

За каждый семинар можно получить 1, 0.5 или 0.

  • 0 - не прийти на семинар
  • 0.5 - прийти на семинар
  • 1 - прийти и проявить активность на семинаре

Формула оценки такая:

min(1, sum(scores) / (seminar_number - 1)) * 10

Бонусы

Ссылки

Что разобрать подробнее

Таблица с оценками

Обратная связь (анонимно)