Применение искинов - шоссе империализма (Стенгазета русификаторов ИТ) |
Привет, Гость! Войдите или зарегистрируйтесь.
Вы здесь » Применение искинов - шоссе империализма (Стенгазета русификаторов ИТ) » обучение вообще » Динамическое программирование, как ему научиться?
Можно ли такого рода деятельность автоматизировать, и какие к автоматизации есть подходы.
На текущий момент "динамическое программирование" для меня выглядит как совокупность частных задач, в которых применили кеширование при переборе. Нигде я ещё не видел теории с введением базовых терминов и методик о том, как им заниматься.
начнём со статьи динамическое программирование в википедии (так должен сделать любой любознательный негр, тянущийся к знаниям).
"способ решения сложных задач путём разбиения их на более простые подзадачи" - очень смешно. Под такое определение и функциональная декомпозиция подходит.
Оттуда нас, негров, отправляют читать английский текст Optimal substructure.
кеширование -> мемоизация
Одним из основных свойств задач, решаемых с помощью динамического программирования, является аддитивность. Неаддитивные задачи решаются другими методами.
Определение "наивные методы" разумеется не даётся. Я думаю, что сюда можно было бы впихнуть "комбинаторные методы" и "метод индукции". Почитаем пока дальше, до чего дошла российская наука. Так, ещё вспомнили теорию сложности вычислений, в качестве примера приводя сведение экспоненциальной сложности к полиномиальной.
Есть ли связь в употреблении "снизу" и "сверху" в приложении к динамическому программированию с аналогичными словами в теории парсинга?
(о роли гравитации в развитии мышления разумных существ...)
Какие приводят примеры:
1) вычисление чисел в последовательности фибоначчи
2) поиск оптимальных путей в графе
3) LCS - longes common subsequence, задача о самой длинной общей подпоследовательности символов в двух текстах (строках)
4) задача о порядке перемножения матриц (тоже не изучал, интересно - наверное как-то относится к БД)
5) ... другие
сериальное и несериальное динамическое программирование (первый раз слышу)
объяснить в чём разница википедия не смогла
что думают украинцы по этому вопросу?
http://kxtp.kpi.ua/common/shakhnovsky_- … st_l12.pdf
ДП - это метод ... (классно! метод - это замечательно, понять бы в чём его суть)
Принцип оптимальности Беллмана, 1953. Привязали сюда теорию управления, что процесс должен быть без обратной связи, иначе может произойти что? (тут какая-нибудь теория усилителей с самовозбуждением и выходом на генерацию)
2007, О.А. Щербина, Методологические аспекты динамического программирования, УДК 519.68
"ДП является чрезвычайно мощной алгоритмической парадигмой оптимизации последовательных процессов принятия решений, имеющей декомпозиционную природу"
это она мощно завернула, у меня появились сомнения о том, знаю ли я значение слова "парадигма" (от греч. παράδειγμα, «пример, модель, образец»)
"могут быть использованы известные методы оптимизации, такие как линейное, нелинейное и дискретное программирование."
"В современных учебниках по исследованию операций описываются только ставшие классическими сериальные задачи ДП, более сложные несериальные динамические системы, обладающие разветвлениями и контурами, не рассматриваются. В то же время несериальные динамические системы имеют интересные приложения в задачах оптимизации водных систем и газопроводов [9]"
"сериальное ДП состоит в погружении решаемой задачи в параметризованное семейство подзадач (что требует известного "инсайта") и последующем решении этих задач, используя рекуррентное уравнение Беллмана,
несериальное ДП использует граф взаимосвязей задачи дискретной оптимизации и последовательно элиминирует переменные."
"В работе предлагается унифицированный подход"
Отредактировано Лис (2017-08-17 19:52:18)
Привязали сюда теорию управления
Оно прямо оттуда и возникло. Программирование - частный случай управления.
Принцип оптимальности Беллмана (также известный как принцип динамического программирования), названный в честь Ричарда Эрнста Беллмана, описывает действие математического метода оптимизации, называемого динамическим программированием. Он заключается в том, что на каждом шаге следует стремиться не к изолированной оптимизации функции {\displaystyle f_{k}\left(x_{k},\xi _{k}\right)} {\displaystyle f_{k}\left(x_{k},\xi _{k}\right)}, а выбирать оптимальное управление {\displaystyle x_{k}^{*}} {\displaystyle x_{k}^{*}} в предположении об оптимальности всех последующих шагов.
Принцип оптимальности: оптимальная стратегия имеет свойство, что какими бы ни были начальное состояние и начальное решение, последующие решения должны составлять оптимальный курс действий по отношению к состоянию, полученному в результате первого решения. Иными словами оптимальная стратегия зависит только от текущего состояния и цели, и не зависит от предыстории.
"способ решения сложных задач путём разбиения их на более простые подзадачи" - очень смешно. Под такое определение и функциональная декомпозиция подходит.
ДП - построение функциональной зависимости. Возможна перестройка рекурсии в обычный цикл.
процесс должен быть без обратной связи, иначе может произойти что?
Полный перебор.
Есть ли связь в употреблении "снизу" и "сверху" в приложении к динамическому программированию с аналогичными словами в теории парсинга?
Полное подобие.
На текущий момент "динамическое программирование" для меня выглядит как совокупность частных задач, в которых применили кеширование при переборе.
Можно сказать и так. Суть сводится к ограничению передаваемого/поддерживаемого объёма данных и времени вычисления.
Отредактировано MihalNik (2017-08-17 20:59:45)
Меня смущает то, что все эти описания недостаточно развёрнутые. Нужно больше текста.
из википедии пример: вычисление числа фибонначи.
При чём там управление? Где там та система, частями которой управляют при помощи воздействий (управлений)?
Отредактировано Лис (2017-08-18 13:45:26)
"под самим динамическим программированием понимают сведение задачи к подзадачам"
подзадачи возникают потому что там есть шаги, или потому что у системы есть части системы? Или это вообще не важно?
Например - у нас есть исходная последовательность битов (текст программы), есть конечная последовательность битов (выполняемый код). Нужно преобразовать одно в другое.
И тут начинаются вопросы:
1) при чём тут вообще задача управления, если здесь нет материального объекта?
2) где тут шаги, из чего они возникают?
3) что должно быть целевой функцией и почему?
Это если в общем. А если конкретно, то непоняток ещё больше.
Отредактировано Лис (2017-08-18 13:45:37)
Меня смущает то, что все эти описания недостаточно развёрнутые. Нужно больше текста.
Если люди, которые их писали, не умеют выражать суть нужным языком, то увеличение объёма текста даст только больше путаницы.
1) при чём тут вообще задача управления, если здесь нет материального объекта?
Вам не нужно отталкиваться от теории оптимального управления, потому что понятного её изложения скорее всего не найдёте.
2) где тут шаги, из чего они возникают?
Рассматривается статичный граф решения задачи, т.е. все узлы которого в процессе решения вычисляются единократно.
Делается один или несколько его минимальных разрезов [иногда возможно регулярных]. Каждый - шаг ДП.
Например, отделение лекс. разбора можно считать одношаговым ДП.
3) что должно быть целевой функцией и почему?
Сосредоточтесь на кешировании при переборе, а не абстрактном матане.
Например - у нас есть исходная последовательность битов (текст программы), есть конечная последовательность битов (выполняемый код). Нужно преобразовать одно в другое.
Вы же сами упоминали https://ru.wikipedia.org/wiki/Алгоритм_Эрли
Отредактировано MihalNik (2017-08-18 16:16:17)
Возможна перестройка рекурсии в обычный цикл.
Это в ФП давно уже есть. Там же автоматные доказательства (потому что не каждая рекурсия может быть циклом). Scheme автоматические преобразует правильно оформленные рекурсионные вызовы в циклы во время исполнения программы.
1) при чём тут вообще задача управления, если здесь нет материального объекта?
А кто тогда одни биты в другие переводит? А где лежат сами биты? Тут аж два объекта управления - программа и комп. Программа в данном случае последовательность электронов в транзисторах ячеек памяти.
3) что должно быть целевой функцией и почему?
Ну это даже в теории языков программирования есть:
y=f(x), где y программа, х - исходный код, f - транслятор (обычно рассматривают компилятор, но строго говоря разницы нет). Есть куча выкладок по автоматическому построению f(x) и практические шаги типа того же yacc. Тут однозначно есть ответы, зависит от конкретики.
2) где тут шаги, из чего они возникают?
А это очень правильный вопрос и потому нужен программист. Часть принципов построения известна (например, в кодах какого процессора должен получиться y), а часть нет (универсальные параметры х, которые при вычислении f(x) приведут к у). Тут есть беда. Работать надо с допфункцией х=а(т),
где х - параметры для у=f(x), то есть сам исходный код
а - туева хуча функций, математическое представление программиста, ежу понятно, что а огромное число потому что сам программист это не просто конкретное значение а, а куча а1, а2, ..., аn, потому что программисты эволюционируют/деградируют - читают книги, узнают новые фишки и т.д.
т - входящая задача, цель, решить которую должна программа у. Тут прямо вот тоже огромная беда, потому что формальные правила описания целей отсутствуют.
Рассматривается статичный граф решения задачи, т.е. все узлы которого в процессе решения вычисляются единократно.
Делается один или несколько его минимальных разрезов [иногда возможно регулярных]. Каждый - шаг ДП.
По этой теме тоже есть куча матана, например, поиск оптимального пути на графе. Используется чуть более чем везде (например, в логистике). С такой точки зрения, ДП не признает циклов в пути. То есть маршрут на графе должен являться линией.
Отредактировано utkin (2017-08-19 08:24:00)
Вы здесь » Применение искинов - шоссе империализма (Стенгазета русификаторов ИТ) » обучение вообще » Динамическое программирование, как ему научиться?