Включено в курс
12 уроков (видео и/или текст)
7 упражнений в тренажере
37 проверочных тестов
Помощь в «Обсуждениях»
Доступ к остальным курсам платформы
Чему вы научитесь
- Определять NP-полные задачи и находить приближенное решение
- Строить эффективные алгоритмы при работе с графами
- Поиску кратчайшего пути
- Различию циклических и ациклических графов
- Строить граф зависимостей
Описание
В этом курсе мы познакомимся с базовыми понятиями из теории графов: NP-полные задачи, поиск пути, жадные алгоритмы. Вы узнаете, решается ли задача коммивояжера, научитесь строить расписание, находить кратчайший путь.
Чтобы учиться было проще, рекомендуем заранее пройти курсы Основы алгоритмов и структур данных и Алгоритмы на деревьях
Программа курса
Продолжительность 11 часов
-
2
Практическое применение графов
Изучаем, какие задачи можно решить с помощью алгоритмов и графовтесты
-
5
Поиск циклов и матрица смежности
Учимся хранить графы в матрице смежности и реализовывать поиск циклов в графе -
7
Задача коммивояжера
Учимся опознавать задачу о коммивояжере и решать ее двумя способами: с помощью перебора и с помощью метода ветвей и граництесты
-
8
Алгоритм Литтла: Механизм работы
Знакомимся с алгоритмом Литтла — еще одним способом решить задачу о коммивояжеретесты
-
9
Алгоритм Литтла: реализация в коде
Учимся реализовывать алгоритм Литтла на практике -
10
Алгоритм Левенштейна
Знакомимся с алгоритмом Левенштейна и учимся распознавать задачи, которые можно решать с помощью динамического программирования -
11
Классы сложности алгоритмов и задач
Знакомимся с классами сложности алгоритмов и проблемой P-NPтесты
-
12
Эвристические алгоритмы
Разбираемся, зачем применяются эвристические алгоритмы и как они работают на практике -
13
Дополнительные материалы
Статьи и видео, подобранные командой Хекслета. Помогут глубже погрузиться в тему курса -
&.
Продолжение следует