3014 курсовая

Лабораторная работа НИС (программирование на графах) Программирование на графах 08-03-2021

Задание по ссылке: https://docs.google.com/document/d/1Duw0_yNOZQ58QP_WZxlW-Ugc8wftykU8IQvL9tSd4gQ/edit Записи лекций: 1. https://www.youtube.com/watch?v=lvkBsk6hH3Q 2. https://www.youtube.com/watch?v=_5-Wjrg39zU 3. https://www.youtube.com/watch?v=S5nkjiniCbk 4. https://www.youtube.com/watch?v=zOc4nhK5IfY 5. https://www.youtube.com/watch?v=0b_hGDV32wM 6. https://www.youtube.com/watch?v=kcyechimDXc 7. https://www.youtube.com/watch?v=nmtg4eppQAs 8. https://www.youtube.com/watch?v=NJOqnBVucVU 9. https://www.youtube.com/watch?v=bsLRrOy_ATg 10. https://www.youtube.com/watch?v=9tZmK7nHhuQ 11. https://www.youtube.com/watch?v=HOL_hut3kxY Примечание от преподавателя: Несколько замечаний, которые очень часто встречаются: 1) Слишком маленький размер стресс-тестов. Нужно, чтобы размер тестируемых графов был не меньше 1000 вершин 2) Аналогично с графиками. Какой смысл рисовать графики с графами из 50 вершин? 3) Должны быть представлены графики с плотными и разреженными графами: плотные, скажем m = n^2/5 или n^2/10, разреженные, скажем m = 3 n или 5 n Свою функцию для этого не надо писать, можете просто в мою подставить другой параметр плотности, это дело одной минуты. 4) Все алгоритмы, которые мы с Вами проходили, линейно зависят от количества вершин и ребер, то есть O(n + m). Таким образом, на разреженных графах Ваши графики должны быть линейными. Не должно быть закруглений вверх как у O(n log n) скажем. 5) Все сортировки должны быть реализованы как в лекциях: в быстрой должна быть элиминация рекурсии, в бакете провильное количество бакетов, в радикс правильное основание системы счисления, 10 - тут очень плохой выбор, как и 2, 8, 16. 6) Графики должны быть без аномалий. Бывает у кого-то одна из кривых просто лежит. Или из за того, что размеры графиков очень маленькие, график похож на расческу. Какой смысл в таких графиках, они дают информацию? Если нет, то зачем их делать?