Динамическая разработка: особенности и языки

Программирование – задача по созданию компьютерных программ и приложений. Включает в себя алгоритмы и структуры данных. Такое определение программированию дал один из основателей ЯП – Никлаус Вирт.

Программирование базируется на языках программирования. С их помощью пишется программный код для решения той или иной задачи. При обработке получившейся записи на выходе получается готовое приложение.

Существует еще одно понятие, которое применяется относительно написания программ – разработка. Это процедура создания приложения «с нуля». Алгоритм, характеризующийся полноценным написанием ТЗ, а также тестирование и формирование кода. Более широкое понятие. Программист создает решение для конкретной задачи, узконаправленно, разработчик – для всего проекта. Далее предложенные термины будем использовать в значении «написание кода».

Программирование и разработка бывают разными: динамическими, функциональными, объектно-ориентированными. Данная статья расскажет о первом варианте. Алгоритм динамического программирования тесно связан с решением математических задач. Он широко применяется в разработке программного обеспечения.

Определение

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

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

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

Историческая справка

Термин «динамическое программирование» (ДП) появилось в 1940-х годах. Оно было использовано Ричардом Беллманом. Так он описывал процесс нахождения решения задачи, где ответ на один вопрос может быть получен только после предыдущего.

К 1953 году Ричард изменил определение, приведя его к современному толкованию. С тех самых пор термин применим не только к математике, но и к разработке. Здесь «программирование» к непосредственному написанию кода не имеет никакого отношения. Это понятие обозначает оптимальную последовательность действий для получения результирующей по тому или иному вопросу. Пример – определенное расписание событий на выставке.

Какие задачи решает

При помощи ДП можно решать разные вопросы – не только в обыденной жизни, но и в непосредственной разработке ПО:

1. Задачи комбинаторики. Они отвечают на вопрос о том, сколько существует объектов с теми или иными свойствами, или сколько элементов существует с заданными параметрами.
2. Задачи оптимизации. Они связаны с максимизацией или минимизацией целевой функции. Пример – максимизировать вероятность того, что имеющаяся система не выйдет из строя, максимизировать математическое ожидание получения доходов.

Получаемые решения можно использовать в обыденной жизни и в разработке ПО. Примеры из реальной жизни:

1. Построение маршрута. Алгоритм позволяет построить путь через несколько заданных точек. Такая концепция встречается в онлайн-картах и программах вызова такси.
2. Компьютерные сети. Если нужно получить решение о выборе пути доставки пакета информации по нескольким адресам. При использовании ДП производятся необходимые расчеты, а на выходе получается последовательность передачи.
3. Сжатие изображений. Суть данного процесса заключается в уменьшении изначального размера файла за счет выделения схожих областей картинки. Это означает, что при реализации задачи содержимое изображения будет меняться, но ее внешний вид должен оставаться неизменным. Подобного результата добиться проблематично.

При помощи динамического программирования можно значительно ускорить решение алгоритмических задач. Объем используемой памяти в соответствующем вопросе не является константой. Для решения больших задач придется увеличить соответствующий параметр.

Ключевые идеи

Для того, чтобы решить поставленную задачу, обычно нужно разделить ее на отдельные части – подзадачи. Далее – объединить их решения в одно общее. Некоторые подзадачи оказываются одинаковыми. Алгоритмы в динамическом программировании заключаются в том, чтобы решить каждую подзадачу только один раз и сократить за счет этого количество вычислений. Существуют ключевые понятия, помогающие усвоить рассматриваемый термин:

1. Метод динамического программирования сверху – это простое запоминание результатов решения подзадач, которые могут повторно встретиться.
2. Метод ДМ снизу. Это преобразование сложной задачи в рекурсивную последовательность более простых решений.
3. Оптимальная подструктура – указывает на то, что оптимальное решение подзадач меньшего объема может быть использовано для первоначально поставленной цели.
4. Перекрывающие подзадачи – подзадачи, которые используются для решения некоторого количества задач (более одной) большего размера. Яркий пример – вычисление чисел Фибоначчи.
5. Мемоизация – сохранение решений ранее известных подзадач и их извлечение из памяти в случае обнаружения аналогичных алгоритмов для вычислений.

При помощи ДП можно решить множество разнообразных задач – не только в математике, но и в разработке ПО. Оно обладает несколькими свойствами, а также подходами к достижению обозначенных изначально целей.

Свойства и концепции

На основании изученной информации можно сделать вывод о том, что динамическое программирование пользуется следующими свойствами задачи:

• перекрывающиеся подзадачи;
• оптимальная подструктура;
• возможность сохранения решения часто встречающихся подзадач.

Подходов к разработке решений несколько:

1. Нисходящее ДП. В данном случае «цель» разбивается на задачи меньшего размера. Они решаются, после чего комбинируются для получения итогового решения. Здесь используется запоминание алгоритмов уже решенных подзадач.
2. Восходящее ДП. При нем все подзадачи, которые позже пригодятся для решения исходной задачи, просчитываются заранее.

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

Что нужно для формирования решения

 Основные концепции в динамическом программировании задач рассмотрены. Данная «схема» в разработке позволяет дробить задание на более мелкие (два и более) компоненты. Соответствующий принцип можно применять повсеместно, особенно при решении сложных вопросов.

Для того, чтобы использовать ДП при разработке алгоритмов, потребуется:

1. Идея или цель. То, что будет разделяться на несколько маленьких шагов.
2. Исходные данные.
3. Таблица, в которую будут вноситься промежуточные результаты. Один из них станет результирующим.
4. Правила по заполнению пустых ячеек таблицы. Они опираются на значение в уже заполненных блоках. Для каждой цели применяется свой подход по поиску оптимального решения.
5. Принцип выбора алгоритма, который нужно применять для достижения изначально обозначенной цели.

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

Преимущества и недостатки

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

Плюсы

Основные преимущества:

1. Скорость. ДП выступает весьма эффективным подходом при решении самых разных вопросов. Вычислительная способность остается на достойном уровне даже в сложных задачах.
2. Универсальность. Для любого сложного вопроса обязательно можно найти более мелкие и простые подзадачи, способные помочь в получении желаемого результата.
3. Точность. Это главное преимущество, которым обладает динамическое программирование. Оно позволяет охватить все возможные варианты развития событий. Такая схема дает возможность обозначить наиболее оптимальное решение без погрешностей и неоднозначностей.

Динамическое программирование, несмотря на свои преимущества, все равно остается неидеальным. Иногда его применение оказывается нецелесообразным из-за ряда недостатков соответствующей концепции.

Минусы

Рассматриваемый алгоритм широкой распространен в реальной жизни и создании программного обеспечения. При динамическом программировании задач необходимо учитывать следующие минусы схемы:

1. Когнитивная нагрузка. Компактная система правил, позволяющая обнаружить наиболее оптимальную работающую схему для достижения поставленной цели привлекает, но она часто увеличивает нагрузку. Требуется обладать соответствующим навыком мышления (математическим, логическим), чтобы сопоставлять системы таблиц и разбираться в них.
2. Память. Особо актуальная проблема для каждого старого аппарата. Все устройства обладают определенной памятью, за счет которой обеспечивается скорость его работы. Если вычислительная способность компьютера небольшая, а обозначенная проблема выражена крупным приложением, результат окажется печальным. Программа начнет потреблять много памяти, тормозить, а иногда – работать с ошибками.

Теперь можно сделать простой вывод – нельзя использовать ДП при разработке особо крупных проектов, если для запуска используется маломощный аппарат. Чем выше вычислительная способность, тем лучше и быстрее будет работать запущенный алгоритм.

Реализации и языки

С ДП удалось разобраться должным образом, поэтому теперь можно рассмотреть примеры реализации и языки, использующие соответствующую концепцию.

Языками динамической разработки (программирования) тех или иных задач (ДЯ) называется класс языков разработки высокого уровня. Они при запуске выполняют большинство общих программных алгоритмов.

ДЯ – это язык разработки, позволяющий определять типы данных и производить синтаксический анализ, а также компиляцию сразу, непосредственно при выполнении написанной программы. Используется для быстрого формирования готового к функционированию кода проекта.

Методы динамической разработки (программирования) используются в языках:

• Ruby;
• Smalltalk;
• TCL;
• Perl;
• PHP;
• Python;
• JavaScript.

Некоторые черты рассмотренной концепции имеет Visual Basic. Разработчики иногда характеризуют ДП как классический подход создания скриптов.

Реализации

Во время изучения ДП и ДЯ нужно обратить внимание на то, какие реализации можно использовать:

1. Функция eval. Она встречается в некоторых языках. Принимает строки и выполняет их. Если принятый код включает в себя выражение, будет рассчитан результат, после чего он вернется в качестве результирующего значения. Eval может использоваться для замены функций высшего порядка.
2. Изменение среды выполнения объекта. Во время выполнения кода тип или объект можно изменять. Данный момент применим относительно деревьев типов, а также к наследованию. Вследствие этого меняется поведение изначально заданных элементов кода.
3. Переменное распределение памяти. Статические языки разработки требуют заблаговременного выделения памяти перед компиляцией. При использовании ДП нельзя сделать это заранее. Память должна быть посчитана и выделена в соответствие с непосредственно выполняемыми операциями (в динамике по ходу работы кода).
4. Отражение. Присутствует во многих ДЯ. Подразумевает анализ типов и метаданных общей или полиморфной информации. Может включать в себя полную оценку и изменение кода в виде функции для анализа S-выражений.
5. Макросы. Некоторые ДЯ предоставляют функции, сочетающие интроспекцию и eval-функции. Они называются макросами. В C++ и C макросы являются статическими функциями, которые поддерживают исключительно строковые подстановки в тексте программы. Задачи динамического программирования требуют от них обеспечения доступа ко внутренней работе аппарата (компилятора), а также полный доступ к интерпретатору, виртуальной мине или среде выполнения.

На основе предложенного материала можно сделать вывод о том, что макросы в ДЯ – это алгоритм, состоящий из языковых конструкций, позволяющих оптимизировать исходный код программы, а также корректировать синтаксис и грамматику языка.

Классические примеры

Чтобы лучше разобраться в изучаемой теме, рекомендуется рассмотреть примеры задач по динамической разработке (программированию). Далее будут представлены несколько классических проблем, а также коды для их решения. За основу будет взята последовательность Фибоначчи.

Нахождение чисел Фибоначчи – это классическая задача ДП. Она задается формулой:

Fn = Fn-1 + Fn-2, где n>1, F1 = 1, F2 = 1.

F_n необходимо найти по заданному программисту номеру. Самый логичный и эффективный прием – это использование ре курсии. Выглядит данный подход так:

int F(int n) {

 if (n < 2) return 1;

 else return F(n - 1) + F(n - 2);

}

При использовании соответствующей функции происходит «расчет с конца». Шаг за шагом значение n уменьшается до известных параметров.

Недостаток подхода – сложность. Если n = 50 или 40, приложение будет работать достаточно долго. Связано это с тем, что одни и те же промежуточные данные вычисляются несколько раз.

Избавиться от данного недостатки можно за счет сохранения уже найденных промежуточных значений для повторного использования. В виде кода это выглядит так:

int F(int n) {

 if (A[n] != -1) return A[n];

 if (n < 2) return 1;

 else {

  A[n] = F(n - 1) + F(n - 2);

  return A[n];

 }

}

Последняя схема является корректной и эффективной, но для обнаружения последовательности Фибоначчи есть и другой алгоритм. Он выглядит так:

F[0] = 1;

F[1] = 1;

for (i = 2; i < n; i++) F[i] = F[i - 1] + F[i - 2];

Это – пример расчетов «с начала». Изначально происходит заполнение известными значениями, а затем производится первое неизвестное, второй и так далее. Делается это до тех пор, пока приложение не достигнет нужного компонента.

Секрет быстрого изучения

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

Здесь:

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

По завершении курсов пользователи получают электронные сертификаты установленного образца. С их помощью удастся подтвердить приобретенный спектр навыков и знаний в выбранном направлении.

Хотите освоить современную IT-специальность? Огромный выбор курсов по востребованным IT-направлениям есть в Otus!