Анализ результатов решения задачи.

Тема 5. АЛГОРИТМИЗАЦИЯ

Этапы проектирования задач и разработки программ

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

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

1. Постановку задачи.

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

2. Выбор метода решения.

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

3. Определение информационного обеспечения.

На данном этапе устанавливается состав нормативно-справочной ин­формации, состав и периодичность получения оперативной информации.

4. Алгоритмизацию.

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

5. Программирование.

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

6. Тестирование и отладку.

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

Анализ результатов решения задачи.

Здесь анализируются результаты решения задачи и в случае необходи­мости осуществляется повторное выполнение этапов 2 - 5.

Начало

Да Нет

Если есть ошибки

Конец

Блок-схема разработки рабочего проекта

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

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

Понятие алгоритма

Термин «алгоритм» (Algorithm) происходит от латинской формы напи­сания имени великого математика и астронома, автора персидского учебника по математике Абу Джафара ибн Мусы аль-Хорезми (уроженца Хорезма), жившего в IX в. и сформулировавшего правила выполнения арифметических действий. Первоначально под алгоритмами и понимали только эти правила. Позже термин «алгоритм» стали использовать для обозначения любой после­довательности действий, приводящей к решению какой-либо задачи.

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

Чтобы создать программу для компьютера, недостаточно знания только языка программирования.Надо сконструировать программу, разбить ее на определенные блоки и выстроить эти блоки один за другим в соответствии с заранее заданным порядком действий (этот порядок и называется алгорит­мом программы). Алгоритм должен быть составлен таким образом, чтобы исполнитель, в расчете на которого он создан, мог однозначно и точно сле­довать командам алгоритма и эффективно получать определенный результат. Это накладывает на записи алгоритмов ряд обязательных требований. Сфор­мулируем эти требования в виде перечня свойств, которым должны удовле­творять алгоритмы, адресуемые заданному исполнителю.

1. Одно из первых требований, которое предъявляется к алгоритму, со­стоит в том, что описываемый процесс должен быть разбит на последова­тельность отдельных шагов. Возникающая в результате такого разбиения за­пись представляет собой упорядоченную совокупность четко разделенных друг от друга предписаний (директив, команд, операторов), образующих прерывную (или, как говорят, дискретную) структуру алгоритма. Только вы­полнив требования одного предписания, можно приступить к выполнению следующего. Рассмотренное свойство алгоритмов называют дискретностью. Итак: дискретность (упорядоченность) означает, что все действия исполни­теля (компьютера) в алгоритме должны быть выстроены в четком, раз и на­всегда определенном порядке через отдельные шаги.

2. Чтобы составить алгоритм для определенного исполнителя, нужно знать, какие команды он может понять и выполнить, а какие нет. У каждого исполнителя имеется своя система команд и, очевидно, что составляя запись алгоритма для него, можно использовать лишь те команды, которые имеются в системе команд исполнителя. Это свойство алгоритмов называют понятно­стью. Итак: понятность алгоритма заключается в том, что каждый шаг ал­горитма обязательно представляет собой какое-либо допустимое действие исполнителя, т.е. алгоритм состоит только из предписаний, входящих в сис­тему команд данного исполнителя.

3. Будучи понятным, алгоритм не должен содержать предписаний, смысл которых может восприниматься неоднозначно, т.е. одна и та же ко­манда, будучи понятна разным исполнителям, после исполнения каждым из них должна давать одинаковый результат. Запись алгоритма должна быть на­столько четкой, полной и продуманной в деталях, чтобы у исполнителя не могло возникнуть потребности в принятии решений, не предусмотренных со­ставителем алгоритма. Иначе говоря, алгоритм не должен оставлять места для произвола исполнителя. Кроме того, в алгоритмах недопустимы также ситуации, когда после выполнения очередной команды алгоритма исполни­телю неясно, какая из его команд должна выполняться на следующем шаге. Отмеченное свойства алгоритмов называютопределенностью или детерми­нированностью. Итак: детерминированность (определенность) имеет ввиду следующее - каждое правило должно быть однозначным, т.е. на каж­дом шаге однозначно определен способ действий.

4. Обязательное требование к алгоритмам - результативность. Смысл этого требования состоит в том, что при точном исполнении всех предписа­ний алгоритма процесс должен прекратиться за конечное число шагов и при этом должен получиться определенный результат. Итак: результативность подразумевает, что каждый шаг (и алгоритм в целом) после своего заверше­ния дает однозначно определенный результат.

5. Наиболее распространены алгоритмы, обеспечивающие решение не одной конкретной задачи, а некоторого класса задач данного типа. Это свой­ство алгоритма называютмассовостью. В простейшем случае массовость обеспечивает возможность использования различных исходных данных. Итак: массовость означает, что алгоритм должен быть как можно более уни­версальным, подходящим для решения разных типов задач.

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

На практике в качестве исполнителя алгоритмов чаще всего используют ЭВМ, поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на понятном ему языке (на первый план здесь выдвига­ется необходимость точной записи команд, не оставляющей места для про­извольного толкования их исполнителем). Короче говоря, язык для записи ал­горитмов должен быть формализован (более строго описан). Формализа­ция предполагает замену словесной формулы решаемой задачи краткими сим­вольными обозначениями, близкими к обозначениям в языках програм­миро­вания или к математическим. Такой язык принято называть языком про­граммирования, а запись алгоритма на этом языке - программой для ком­пьютера.

При построении алгоритма для сложной задачи используют системный подход: использование принципов декомпозиции (нисходящее проектиро­вание «сверху-вниз») и синтеза (программирование «снизу-вверх»). Первое предполагает первоначальную разработку алгоритма в виде укрупненных блоков (разбиение задачи на подзадачи, или модули со связями между собой) и их постепенную детализацию (пошаговое разбиение алгоритма на все бо­лее мелкие части до уровня элементарных конструкций, для которых можно составить конкретные команды). Затем (после декомпозиции) проводится сборка блоков (модулей) в единую программу (т.е. синтез). Кроме этих, при разработке алгоритмов применяется принцип «от главного к второстепен­ному», предполагающий составление алгоритма, начиная с главной конст­рукции и принцип структурирования, т.е. использования только типовых ал­горитмических структур при построении алгоритма.

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

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