GameDev Academy
@gamedev_academy_feedback
21 posts

21. Алгоритмизация и структуры данных. Примеры задач.

Давайте попробуем существенно ускорить стандартный алгоритм Дейкстры, используя для выбора вершины с минимальным весом из не рассмотренных двоичную кучу.

20. Двоичная куча.

Ну а напоследок, мы с вами поговорим еще про одну структуру, которая представляет из себя не очень сложно реализуемое дерево, которое используется для сортировки и быстрого извлечения элементов с максимальным приоритетом.

19. Сбалансированные деревья (общее понятие). Виды деревьев.

В программировании используют достаточно много видов деревьев:

18. Деревья. Двоичные деревья. Двоичное дерево поиска.

Давайте рассмотрим еще одну структуру данных - дерево.

17. Примеры задач на графы. Связность. Компоненты связности.

Давайте рассмотрим несколько задач, которые можно решить, изменяя рассмотренные нами поиск в ширину или глубину на графах.

16. Поиск в глубину (DFS).

Сегодня мы продолжим разбирать алгоритмы на графах. Еще один очень распространенный алгоритм – поиск в глубину (DFS). Если объяснять просто, то в поиске в ширину, если помните, у нас из каждой вершины как бы выбегала толпа народа, которая потом снова делилась на большие толпы, а в поиске в глубину бегает только один неутомимый товарищ, который должен успеть оббежать все вершины в поисках нужной и очень быстро.

15. Теория графов. Алгоритм Дейкстры.

Сегодня мы продолжим решать задачу из предыдущего занятия. Поиск в ширину отлично работает, но его можно оптимизировать. Вспомните, мы пытались двигаться из всех вершин в очереди по всем направлениям, улучшая минимальные пути и записывая одни и те же вершины в очередь по несколько раз. Алгоритм Дейкстры позволяет упростить поиск в ширину, выбирая из всех возможных направлений самое подходящее. Для алгоритма Дейкстры есть одно ограничение: вес ребер не должен быть отрицательным.

14. Теория графов. Поиск в ширину (BFS).

Сегодня все занятие мы посвятим решению одной задачи. Точнее, мы решим вроде бы только одну задачу, а потом поймем, что это же решение можно применить (практически без изменений) для решения сотен и даже тысяч очень актуальных и важных алгоритмических задач из реальной жизни.

13. Теория графов. Основные понятия теории графов. Способы представления графа в памяти компьютера.

Сегодня мы начинаем говорить о теории графов. Это не структура данных и не метод решения задача. Графы – это способ представления и обработки данных в виде не просто множества объектов заданного класса, но и с учетом связей между ними.

12. Хэш-таблицы. Коллизии. Класс Dictionary.

Продолжаем говорить о структурах данных.