Лекция 1 - 2

Created Friday 10 October 2014

Определение

Задача о возврате сдачи

Aлгоритм

F(0) = 1, F(1) = 1, F(2) = 2, F(3) = 3, F(4) = 5
F(k) = ?
for i = 5 to k
F(i) = F(i-1) + F(i-2) + F(i-5)

Cложность времени работы

  1. c. = Q(k)
Для записи числа k нужен log_2(k)
Т.е., алгоритм имеет экспоненциальную сложность: Q(k) = Q(2^log_2(k))

Задача оптимизации

Формализация и решение


Домашнее задание

Решение для конкретных чисел


Задача оптимального пути


Решение проверкой всех путей

Решение динамическим программированием

В общем виде:


Cложность

Маршрут

Конкретный пример



F(1, 1) = 16

Двухмерная задача динамического программирования (2 хрустальных шара)

Пример

Формализация




Backlinks: