Page 236 - Bkhargava_-_Grokaem_algoritmy

Шпаргалка 235

о Вы когда-нибудь пользовались ключом diff (например, в команде git
diff)? Этот ключ выводит информацию о различиях между двумя фай ­
лами , а для этого он использует динамическое программирование.
о Мы также упоминали о сходстве строк. Расстояние Левенштейна оцени­
вает, насколько похожи две строки , а для его вычисления применяется
динамическое программирование . Расстояние Левенштейна использу­
ется в самых разных областях, от проверки орфографии до выявления
отправки пользователем данных, з ащищенных авторским правом.
о Вы когда- нибудь работали в приложении, поддерживающем перенос
слов, например Microsoft Word? Как определить, где следует расставить
переносы, чтобы длина строки оставалась более или менее постоянной?
Динамическое программирование!

Упражнения

9.3 Нарисуйте и заполните таблицу для вычисления самой длинной об­
щей подстроки между строками Ыие и clues.

Шпаргалка

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

о В каждом решении из области динамического программирования стро­
ится таблица.
о Значения ячеек таблицы обычно соответствуют оптимизируемой харак­
теристике.

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

о Не существует единой формулы для вычисления решений методом ди­
намического программирования .

www.trk.kg