Тема 5. Алгоритмическое решение задач

Анализ алгоритмической сложности.

Стратегия решения задач.

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

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

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

На рис. 5.1. этапы решения задач представлены в виде схемы технологического процесса разработки программных средств.

Рис. 5.1. Схема технологического процесса разработки программных средств задачи.

Первый этап. Постановка задачи. На этом этапе:

- раскрывается организационно-экономическая сущность задачи, т.е. формируется цель ее решения;

- определяется взаимосвязь с другими задачами;

- указывается периодичность ее решения;

- рассматриваются состав и форма представления входной, промежуточной и результатной информации;

- характеризуются формы и методы контроля достоверности информации на ключевых этапах решения задачи;

- специфируются формы взаимодействия пользователя с ЭВМ в ходе решения задачи.

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

- форма представления отдельных реквизитов (цифровая, символьная и т.д.). Для цифровой информации указывается целочисленный или дробный характер реквизита;

- количество знаков (разрядов), выделяемых для записи реквизитов, исходя из их максимальной значности;

- вид реквизита в процессе решения задачи (первичный, расчетный, нормативный, справочный и т.д.)

- источник (документ) возникновения реквизита.

Важной особенностью экономических задач является использование в процессе их решения массивов условно-постоянной информации.

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

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

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

На втором этапе выполняется формализованное описание задачи, т.е. устанавливаются и формируются средствами языка математики логико-математические зависимости между исходными и результатными данными.

В процессе подготовки экономико-математического описания (модели) задачи используются различные разделы математики, особенно прикладной. Прирешении задач используются модели:

- аналитические (вычислительные);

- матричные (балансовые);

- графические (сетевые).

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

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

- обеспечивает необходимую точность получаемых результатов;

- позволяет использовать уже стандартные готовые программы для решения задачи или ее отдельных фрагментов;

- ориентирован на минимальный объем исходной информации;

- обеспечивает наиболее быстрое получение искомых результатов решения.

Третий этап - алгоритмизация ее решения, т.е. составление алгоритма (алгоритм - точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату). Свойства алгоритма:

· детерминированность;

· массовость;

· результативность;

· дискретность.

Способы описания алгоритмов:

- словесный,

- формульно-словесный,

- графический (метод блок-схемы),

- средствами специального языка операторных схем,

- псевдокод,

- с помощью языка программирования.

При создании нового алгоритма предоставляется так называемый, "базовый" алгоритм, что является минимально необходимым логическим набором для проведения элементарных действий с данными. "Базовый" алгоритм состоит из четырех элементов:

1) начало алгоритма,

2) ввод данных,

3) элемент расчета,

4) конец алгоритма.

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

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

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

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

После завершения процесса тестирования и отладки программные средства вместе с сопроводительной документацией передаются пользователю для эксплуатации. Этап эксплуатации делится на экспериментальную (опытную) и промышленную эксплуатацию.

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