Что такое динамическое приложение
Общие сведения о веб-приложениях
Пользовательский интерфейс в Dreamweaver СС и более поздних версиях стал проще. В результате этого некоторые функции, описанные в этой статье, могут отсутствовать в Dreamweaver CC и более поздних версиях. Дополнительные сведения см. в этой статье.
Веб-приложение представляет собой веб-сайт, на котором размещены страницы с частично либо полностью несформированным содержимым. Окончательное содержимое формируется только после того, как посетитель сайта запросит страницу с веб-сервера. В связи с тем что окончательное содержимое страницы зависит от запроса, созданного на основе действий посетителя, такая страница называется динамической.
Спектр использования веб-приложений очень широк. В данном разделе рассматриваются общие вопросы использования веб-приложений, а также приводится пример простого веб-приложения.
Типичное применение веб-приложений
Использование веб-приложений приносит определенную пользу как посетителям веб-сайтов, так и их разработчикам.
Веб-приложения позволяют посетителям быстро и легко находить требуемую информацию на веб-сайтах с большим объемом информации.
Данный вид веб-приложений позволяет осуществлять поиск в содержимом, упорядочивать содержимое и перемещаться по нему удобным для посетителей способом. Примерами таких приложений могут служить внутренние сети компаний — Microsoft MSDN (www.msdn.microsoft.com) и Amazon.com (www.amazon.com).
Веб-приложения позволяют собирать, сохранять и анализировать данные, полученные от посетителей сайта.
Долгое время использовался метод, при котором данные, введенные в HTML-формы, отсылались для обработки CGI-приложениям или специально назначенным работникам в виде сообщений электронной почты. Веб-приложение позволяет сохранять данные непосредственно в базе данных, а также получать данные и формировать отчеты на основе полученных данных для анализа. В качестве примера можно привести интерактивные страницы банков, страницы для контроля товарных запасов, социологические исследования и опросы, а также формы для обратной связи с пользователями.
Веб-приложение может использоваться для обновления веб-сайтов с периодически меняющимся содержимым.
Веб-приложение освобождает веб-дизайнера от рутинной работы постоянного обновления HTML-страниц сайта. Поставщики содержимого, например редакторы новостей, отвечают за наличие свежего материала, а веб-приложение следит за автоматическим обновлением сайта. В качестве примера можно привести веб-версию журнала «The Economist» (www.economist.com) и службы новостей CNN (www.cnn.com).
Пример веб-приложения
Светлана работает веб-дизайнером и уже долгое время использует Dreamweaver в своей работе. В ее обязанности входит обеспечение работы внутрикорпоративного сайта и Интернет-сайта компании средних размеров, насчитывающей порядка 1000 сотрудников. Однажды сотрудник отдела кадров Сергей обратился к ней со своей проблемой. Отдел кадров курирует программу оздоровления сотрудников. В рамках этой программы сотрудникам начисляются специальные баллы за каждый километр, преодоленный пешком, бегом или на велосипеде. В конце месяца каждый сотрудник отсылает отчет по электронной почте Сергею с указанием общего количества километров. После этого Сергей на основе полученных электронных сообщений премирует сотрудников небольшими денежными призами в зависимости от набранных баллов.
Проблема состоит в том, что программа оздоровления стала очень популярной. В данный момент количество участников этой программы возросло до такой степени, что в конце месяца Сергей не успевает обрабатывать всю приходящую к нему электронную почту. Поэтому он обратился к Светлане с вопросом о возможности решения данной проблемы с помощью веб-технологий.
В ответ на это Светлана предложила создать веб-приложение, которое будет решать следующие задачи.
Данные о своих спортивных достижениях сотрудники будут вносить в простую HTML-форму.
Полученные данные будут сохраняться в базе данных.
Начисление баллов будет выполняться на основе полученных данных.
Каждый сотрудник может получить данные о своих результатах.
В конце каждого месяца Сергей имеет возможность получить все итоговые результаты.
В кратчайшие сроки Светлана создала и запустила требуемое приложение, поскольку Dreamweaver имеет все необходимые инструменты для быстрого и простого создания такого рода приложений.
Принципы работы веб-приложений
Любое веб-приложение представляет собой набор статических и динамических веб-страниц. Статическая веб-страница — это страница, которая всегда отображается перед пользователем в неизменном виде. Веб-сервер отправляет страницу по запросу веб-браузера без каких-либо изменений. В противоположность этому, сервер вносит изменения в динамическую веб-страницу перед отправкой ее браузеру. По причине того что страница меняется, она называется динамической.
Например, можно создать страницу, на которой будут отображены результаты программы оздоровления. При этом некоторая информация (например, имя сотрудника и его результаты) будет определяться в момент запроса страницы сотрудником.
В следующем разделе более подробно рассматриваются вопросы работы веб-приложений.
Обработка статических веб-страниц
Статический веб-сайт содержит набор соответствующих HTML-страниц и файлов, размещенных на компьютере, на котором установлен веб-сервер.
Веб-сервер — это программное обеспечение, которое предоставляет веб-страницы в ответ на запросы веб-браузеров. Обычно запрос страницы создается при щелчке ссылки на веб-странице, выборе закладки в браузере либо вводе URL-адреса в адресной строке браузера.
Окончательное содержимое статической веб-страницы определяется разработчиком и остается неизменным в процессе запроса страницы. Пример:
Весь HTML-код создается разработчиком до того момента, когда страница будет размещена на сервере. Поскольку HTML-код не меняется после размещения страницы на сервере, данная страница называется статической.
Если подходить строго, «статическая» страница может на самом деле таковой не являться. Например, замещающее изображение либо Flash-содержимое (в виде SWF-файла) позволяет «оживить» статическую страницу. Однако в данном контексте страница является статической, поскольку отсылается браузеру без изменений.
Когда веб-сервер получает запрос на выдачу статической страницы, то, после анализа запроса, сервер находит нужную страницу и отправляет ее браузеру, как показано ниже.
A. Веб-браузер запрашивает статическую страницу. B. Веб-сервер находит страницу. C. Веб-сервер отправляет страницу запросившему ее браузеру.
В случае веб-приложений некоторые участки кода страницы отсутствуют до момента запроса страницы посетителем. Отсутствующий код формируется с помощью некоторого механизма, и только после этого страница может быть отправлена браузеру. Данный механизм формирования кода рассматривается в следующем разделе.
Обработка динамических страниц
Когда веб-сервер получает запрос на выдачу статической веб-страницы, он отправляет страницу непосредственно браузеру. Однако, когда запрашивается динамическая страница, действия веб-сервера не столь однозначны. Сервер передает страницу специальной программе, которая и формирует окончательную страницу. Такая программа называется сервером приложений.
Сервер приложений выполняет чтение кода, находящегося на странице, формирует окончательную страницу в соответствии с прочитанным кодом, а затем удаляет его из страницы. В результате всех этих операций получается статическая страница, которая передается веб-серверу, который в свою очередь отправляет ее клиентскому браузеру. Все страницы, которые получает браузер, содержат только HTML-код. Схематическое изображение процесса:
A. Веб-браузер запрашивает динамическую страницу. B. Веб-сервер находит страницу и передает ее серверу приложений. C. Сервер приложений просматривает страницу на наличие инструкций и выполняет ее создание. D. Сервер приложений возвращает подготовленную страницу на веб-сервер. E. Веб-сервер отправляет подготовленную страницу запросившему ее браузеру.
Доступ к базе данных
Сервер приложений предоставляет возможность использовать такие ресурсы сервера, как базы данных. Например, динамическая страница может содержать программные инструкции для сервера приложений, следуя которым серверу необходимо получить определенные данные из базы данных и поместить их в HTML-код страницы. Подробнее см. здесь: www.adobe.com/go/learn_dw_dbguide_ru.
Хранение содержимого в базе данных позволяет отделить оформление веб-сайта от содержимого, которое будут видеть пользователи. Вместо того чтобы создавать все страницы в виде отдельных HTML-файлов, пишутся только шаблоны страниц для каждого вида представляемой информации. Затем содержимое загружается в базу данных, после чего веб-сайт будет извлекать его при запросах пользователей. Кроме того, можно обновить информацию в одном источнике и продублировать это изменение на всем веб-сайте без редактирования каждой страницы вручную. Adobe Dreamweaver позволяет создавать веб-формы для вставки, обновления и удаления информации в базе данных.
Программная инструкция, предназначенная для получения данных из базы данных, называется запросом к базе данных. Запрос состоит из критериев поиска, выраженных с помощью языка баз данных, называемого SQL (язык структурированных запросов). Текст SQL-запроса располагается в сценариях страниц на стороне сервера либо в тегах.
Сервер приложений не может непосредственно получить данные из базы, поскольку базы данных используют специфические форматы хранения данных, в результате чего попытка получения таких данных будет напоминать попытку открытия документа Microsoft Word с помощью текстового редактора Notepad или BBEdit. Поэтому для подключения к базе данных сервер приложений использует посредника — драйвер базы данных. Драйвер базы данных представляет собой программный модуль, с помощью которого устанавливается взаимодействие между сервером приложений и базой данных.
После того как драйвер установит соединение, выполняется запрос к базе, в результате чего формируется набор записей. Набор записей представляет собой множество данных, полученных из одной или нескольких таблиц базы данных. Набор записей возвращается серверу приложений, который использует полученные данные для формирования страницы.
Ниже приводится пример простого запроса к базе данных на языке SQL.
С помощью этой инструкции формируется набор записей из трех столбцов, содержащих фамилию, имя и набранные баллы всех сотрудников, сведения о которых хранятся в базе данных. Подробнее см. здесь: www.adobe.com/go/learn_dw_sqlprimer_ru.
Следующий пример демонстрирует процесс выполнения запроса к базе данных и возвращение полученных данных браузеру.
A. Веб-браузер запрашивает динамическую страницу. B. Веб-сервер находит страницу и передает ее серверу приложений. C. Сервер приложений просматривает страницу на наличие инструкций и выполняет ее подготовку. D. Сервер приложений отправляет запрос драйверу базы данных. E. Драйвер выполняет запрос в базе данных. F. Драйверу возвращается набор записей. G. Драйвер передает набор записей серверу приложений. H. Сервер приложений вставляет данные в страницу и передает страницу веб-серверу. I. Веб-сервер отправляет подготовленную страницу запросившему ее браузеру.
Для использования в веб-приложении пригодна любая база данных при условии, что на сервере установлен соответствующий драйвер базы данных.
Для создания малобюджетных приложений можно использовать файловую базу данных, например базу данных, созданную с помощью Microsoft Access. Если планируется создание надежных корпоративных приложений, рекомендуется использовать серверную базу данных, например, на основе серверов Microsoft SQL Server, Oracle 9i или MySQL.
Если база данных и веб-сервер располагаются на разных компьютерах, следует обеспечить скоростное подключение между системами, поскольку от этого будет зависеть эффективность и скорость работы всего веб-приложения.
Разработка динамических страниц
Процесс разработки динамических страниц состоит из написания базового HTML-кода и последующего создания серверных сценариев или тегов HTML-страницы, с помощью которых страница становится динамической. Если взглянуть на окончательный код, видно, что язык сценариев встроен в HTML-код страницы. Соответственно, такие языки сценариев называют языками, встроенными в HTML. В следующем примере используется язык разметки ColdFusion Markup Language (CFML).
Примечание. В Dreamweaver CC и более поздних версиях поддержка CFML отсутствует.
Встроенные в данную страницу инструкции выполняют следующие действия.
Значение «Sales» помещается в HTML-код.
Сервер приложений возвращает следующую страницу на веб-сервер:
Веб-сервер отправляет страницу браузеру, который отображает ее следующим образом.
О компании Trio Motors
Компания Trio Motors является одним из ведущих производителей автомобилей.
Не забудьте посетить страницу нашего отдела продаж.
Выбор языка сценариев либо языка, основанного на тегах, зависит от применяемых серверных технологий. Ниже приведен список языков, которые наиболее часто используются в серверных технологиях, поддерживаемых Dreamweaver.
Всё, что вы хотели знать о динамическом программировании, но боялись спросить
Я был крайне удивлён, найдя мало статей про динамическое программирование (далее просто динамика) на хабре. Мне всегда казалось, что эта парадигма довольно сильно распространена, в том числе и за пределами олимпиад по программированию. Поэтому я постараюсь закрыть этот пробел своей статьёй.
Основы
Пожалуй, лучшее описание динамики в одно предложение, которое я когда либо слышал:
Динамическое программирование — это когда у нас есть задача, которую непонятно как решать, и мы разбиваем ее на меньшие задачи, которые тоже непонятно как решать. (с) А. Кумок.
Чтобы успешно решить задачу динамикой нужно:
1) Состояние динамики: параметр(ы), однозначно задающие подзадачу.
2) Значения начальных состояний.
3) Переходы между состояниями: формула пересчёта.
4) Порядок пересчёта.
5) Положение ответа на задачу: иногда это сумма или, например, максимум из значений нескольких состояний.
Порядок пересчёта
Существует три порядка пересчёта:
1) Прямой порядок:
Состояния последовательно пересчитывается исходя из уже посчитанных.
2) Обратный порядок:
Обновляются все состояния, зависящие от текущего состояния.
3) Ленивая динамика:
Рекурсивная мемоизированная функция пересчёта динамики. Это что-то вроде поиска в глубину по ацикличному графу состояний, где рёбра — это зависимости между ними.
Элементарный пример: числа Фибоначчи. Состояние — номер числа.
Все три варианта имеют права на жизнь. Каждый из них имеет свою область применения, хотя часто пересекающуюся с другими.
Многомерная динамика
Пример одномерной динамики приведён выше, в «порядке пересчёта», так что я сразу начну с многомерной. Она отличается от одномерной, как вы уже наверно догадались, количеством измерений, то есть количеством параметров в состоянии. Классификация по этому признаку обычно строится по схеме «один-два-много» и не особо принципиальна, на самом деле.
Многомерная динамика не сильно отличается от одномерной, в чём вы можете убедиться взглянув на пару примеров:
Пример №1: Количество СМСок
Раньше, когда у телефонов были кнопки, их клавиатуры выглядели примерно так:
Требуется подсчитать, сколько различных текстовых сообщений множно написать используя не более k нажатий на такой клавиатуре.
Прямой пересчёт:
Обратный пересчёт:
При использовании обратного пересчёта всё проще: мы всегда обращаемся вперёд, так что в отрицательные элементы мы не уйдём.
5) Ответ — это сумма всех состояний.
Пример №2: Конь
4) А теперь самое интересное в этой задаче: порядок. Здесь нельзя просто взять и пройтись по строкам или по столбцам. Потому что иначе мы будем обращаться к ещё не пересчитанным состояниям при прямом порядке, и будем брать ещё недоделанные состояния при обратном подходе.
Есть два пути:
1) Придумать хороший обход.
2) Запустить ленивую динамику, пусть сама разберётся.
Если лень думать — запускаем ленивую динамику, она отлично справится с задачей.
Если не лень, то можно придумать обход наподобие такого:
Этот порядок гарантирует обработанность всех требуемых на каждом шаге клеток при прямом обходе, и обработанность текущего состояния при обратном.
Динамика и матрица переходов
Если никогда не умножали матрицы, но хотите понять этот заголовок, то стоит прочитать хотя бы вики.
А теперь, зачем всё это надо. Умножение матриц обладает свойством ассоциативности, то есть (но при этом не обладает коммутативностью, что по-моему удивительно). Это свойство даёт нам право сделать так: .
А теперь пример посерьёзнее:
Пример №3: Пилообразная последовательность
Для начала решение без матрицы перехода:
Динамика по подотрезкам
Это класс динамики, в котором состояние — это границы подотрезка какого-нибудь массива. Суть в том, чтобы подсчитать ответы для подзадач, основывающихся на всех возможных подотрезках нашего массива. Обычно перебираются они в порядке увеличения длины, и пересчёт основывается, соответственно на более коротких отрезках.
Пример №4: Запаковка строки
Вот Развернутое условие. Я вкратце его перескажу:
Необходимо по строке s узнать длину самой короткой сжатой строки, разжимающийся в неё.
Решается эта задача, как вы уже наверняка догадались, динамикой по подотрезкам.
1) Состояние динамики: d[l][r] — сжатая строка минимальной длины, разжимающаяся в строку s[l:r]
2) Начальные состояния: все подстроки длины один можно сжать только в них самих.
3) Пересчёт динамики:
У лучшего ответа есть какая-то последняя операция сжатия: либо это просто строка из заглавных букв, или это конкатенация двух строк, или само сжатие. Так давайте переберём все варианты и выберем лучший.
Пример №5: Дубы
Динамика по поддеревьям
Параметром состояния динамики по поддеревьям обычно бывает вершина, обозначающая поддерево, в котором эта вершина — корень. Для получения значения текущего состояния обычно нужно знать результаты всех своих детей. Чаще всего реализуют лениво — просто пишут поиск в глубину из корня дерева.
Пример №6: Логическое дерево
Требуется найти минимальное количество изменений логических операций во внутренних вершинах, такое, чтобы изменилось значение в корне или сообщить, что это невозможно.
Динамика по подмножествам
В динамике по подмножествам обычно в состояние входит маска заданного множества. Перебираются чаще всего в порядке увеличения количества единиц в этой маске и пересчитываются, соответственно, из состояний, меньших по включению. Обычно используется ленивая динамика, чтобы специально не думать о порядке обхода, который иногда бывает не совсем тривиальным.
Пример №7: Гамильтонов цикл минимального веса, или задача коммивояжера
Динамика по профилю
Классическими задачами, решающимися динамикой по профилю, являются задачи на замощение поля какими-нибудь фигурами. Причём спрашиваться могут разные вещи, например, количество способов замощения или замощение минимальным количеством фигур.
Профиль — это k (зачастую один) столбцов, являющиеся границей между уже замощённой частью и ещё не замощённой. Эта граница заполнена только частично. Очень часто является частью состояния динамики.
Почти всегда состояние — это профиль и то, где этот профиль. А переход увеличивает это местоположение на один. Узнать, можно ли перейти из одного профиля в другой можно за линейное от размера профиля время. Это можно проверять каждый раз во время пересчёта, но можно и предподсчитать. Предподсчитывать будем двумерный массив can[mask][next_mask] — можно ли от одной маски перейти к другой, положив несколько фигурок, увеличив положение профиля на один. Если предподсчитывать, то времени на выполнение потребуется меньше, а памяти — больше.
Пример №8: Замощение доминошками
Здесь профиль — это один столбец. Хранить его удобно в виде двоичной маски: 0 — не замощенная клетка столбца, 1 — замощенная. То есть всего профилей .
0) Предподсчёт (опционально): перебрать все пары профилей и проверить, что из одного можно перейти в другой. В этой задаче это проверяется так:
Примеры переходов (из верхнего профиля можно перейти в нижние и только в них):
Полученная асимптотика — .
Динамика по изломанному профилю
Это очень сильная оптимизация динамики по профилю. Здесь профиль — это не только маска, но ещё и место излома. Выглядит это так:
Теперь, после добавления излома в профиль, можно переходить к следующему состоянию, добавляя всего одну фигурку, накрывающую левую клетку излома. То есть увеличением числа состояний в N раз (надо помнить, где место излома) мы сократили число переходов из одного состояния в другое с до . Асимптотика улучшилась с до .
Переходы в динамике по изломанному профилю на примере задачи про замощение доминошками (пример №8):
Восстановление ответа
Иногда бывает, что просто знать какую-то характеристику лучшего ответа недостаточно. Например, в задаче «Запаковка строки» (пример №4) мы в итоге получаем только длину самой короткой сжатой строки, но, скорее всего, нам нужна не её длина, а сама строка. В таком случае надо восстановить ответ.
В каждой задаче свой способ восстановления ответа, но самые распространенные:
Небольшие оптимизации
Память
Зачастую в динамике можно встретить задачу, в которой состояние требует быть посчитанными не очень большое количество других состояний. Например, при подсчёте чисел Фибоначчи мы используем только два последних, а к предыдущим уже никогда не обратимся. Значит, можно про них забыть, то есть не хранить в памяти. Иногда это улучшает асимптотическую оценку по памяти. Этим приёмом можно воспользоваться в примерах №1, №2, №3 (в решении без матрицы перехода), №7 и №8. Правда, этим никак не получится воспользоваться, если порядок обхода — ленивая динамика.
Время
Иногда бывает так, что можно улучшить асимптотическое время, используя какую-нибудь структуру данных. К примеру, в алгоритме Дейкстры можно воспользоваться очередью с приоритетами для изменения асимптотического времени.
Замена состояния
В решениях динамикой обязательно фигурирует состояние — параметры, однозначно задающие подзадачу, но это состояние не обязательно одно единственное. Иногда можно придумать другие параметры и получить с этого выгоду в виде снижения асимптотического времени или памяти.
Пример №9: Разложение числа
Решение №1:
Решение №2:
Строки здесь обозначают слагаемые.
Первое решение последовательно добавляет по одной строчке внизу таблицы, а второе — по одному столбцу слева таблицы. Вариантов размера следующей строчки много — главное, чтобы она была больше предыдущей, а столбцов — только два: такой же как предыдущий и на единичку больше.
Заключение
Основным источником была голова, а туда информация попала с лекций в Летней Компьютерной Школе (для школьников), а также кружка Андрея Станкевича и спецкурса Михаила Дворкина (darnley).
Спасибо за внимание, надеюсь эта статья кому-нибудь пригодится! Хотя мне уже пригодилась — оказывается, написание статьи это хороший способ всё вспомнить.