Раздел «Образование».FIVTLecturesTerm3Lecture3:
<< Список лекций ФИВТ, 3-й семестр, 2009 г.

Лекция 3. Проверочная работа. Жадные алгоритмы и динамическое программирование. Задача о рюкзаке (целые массы с ограниченной суммой)

Подсчет числа правильных скобочных выражений

Подсчет числа путей в графе

Теггирование методов решения задач

local, greedy, decompose, cache

Задача о рюкзаке

Задача о рюкзаке: дано N золотых предметов с массами m(1), m(2), .., m(N). Необходимо найти подмножество максимальной массы, которая меньше либо равна заданного M. Решение задачи для случая, когда массы натуральные и их сумма ограничена числом 100000.

Другие примеры применения жадных алгоритмов

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

Пример NP-сложной задачи: Упорядочить вершины ориентированного графа, чтобы максимальное число ребер было направлено из большей вершины в меньшую.

Проверочная работа

  1. Что такое вычислительная сложность?
  2. Ключевые различия шаблонов set, vector, map (для каких разных целей они используются)?
  3. Какова сложность задачи об атлетах?
  4. Что такое жадные алгоритмы?
  5. Какая была последняя задача, рассмотренная на семинаре?

Задание на семинар