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

Алгоритмы и данные

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

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

Алгоритмы должны обладать следующими свойствами.

1. Конечность — работа алгоритма должна заканчиваться за конечное число шагов, хотя некоторые из шагов могут повто­ряться многократно.

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

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

4. Результативность — алгоритм должен приводить к дос­тижению поставленной цели за конечное число шагов, он не мо­жет быть прерван из-за непредвиденных ситуаций.

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

Основными этапами подготовки задачи к решению на ЭВМ, которые связаны с построением алгоритма, являются:

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

2. Построение модели задачи.

3. Разработка алгоритма.

4. Реализация алгоритма в виде программы.

5. Проверка правильности алгоритма.

6. Анализ сложности алгоритма.

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

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

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

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

В ячейках памяти размещаются либо данные, либо команды (коды программы). Таким образом, каждая ячейка имеет свой адрес и некоторое содержимое. По содержимому ячейки невоз­можно определить, что там хранится: данные, команда или их части. Например, содержимое байта ‘00110001’ может трактовать­ся как символ «1», десятичное число «31», двоичное число, равное 49, и т.д. Из вышеизложенного следует, что в модели ЭВМ на машинном уровне определены только базовые типы данных, которые, естественно, в большинстве случаев не совпадают с типа­ми данных, полученными при абстрагировании. Следовательно, существует разрыв между двумя уровнями представления данных. Этот разрыв постепенно устраняется на последующих этапах подготовки к решению задачи.

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

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

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

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

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

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

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

Парадигмы программирования — это модели разработки и ре­ализации программ. Разные модели приводят к разным приемам программирования, они обычно не противоречат друг другу, а являются взаимодополняющими.

Язык процедурного программирования базируется на моде­ли построения программы как совокупности функций, а абстрак­ция данных базируется на структурах данных. Объектно-ориен­тированное программирование базируется на модели построе­ния программ как набора объектов абстрактного типа данных.

В каждом языке программирования имеются средства пред­ставления данных различных типов. Тип данных определяет, ка­кие значения могут принимать данные этого типа и допустимые операции над ними. Абстрактные типы данных, определенные на этапах разработки модели и алгоритма, представляются те­перь средствами языка программирования в виде синтаксических конструкций, т.е. получают программную реализацию. Это про­межуточный уровень представления данных. Затем в результате трансляции программы данные представляются в виде последо­вательностей битов — это физический уровень представления дан­ных. Таким образом, в процессе последовательных преобразова-ний структуры данных из одного вида представления переводят­ся в другие (рис. 1.1).

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

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

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

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

Алгоритм, реализующий решение задачи, можно задать различными способами на основе различных языковых средств: графических, текстовых, табличных. Графические средства представления алгоритмов имеют ряд преимуществ, благодаря визуальности и явному отображению процесса решения задачи. Алгоритмы, представленные на языке графических объектов, получили название визуальные алгоритмы. Текстовое описание алгоритма является достаточно компактным и может быть реализовано на абстрактном или реальных языках программирования в виде программы для ЭВМ. Таблицы значений представляют алгоритм неявно, как некоторое преобразование конкретных исходных данных в выходные. Табличный способ описания алгоритмов может быть с успехом применен для проверки правильности функционирования разработанного алгоритма на конкретных тестовых наборах входных данных, которые вместе с результатами выполнения алгоритма фиксируются в «таблицах трассировки».

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

Рассмотрим общие правила при проектировании визуальных алгоритмов:

 в начале алгоритма должны быть блоки ввода значений входных данных;

 после ввода значений входных данных могут следовать блоки обработки и блоки условия;

 в конце алгоритма должны располагаться блоки вывода значений выходных данных;

 в алгоритме должен быть только один блок начала и один блок окончания;

 связи между блоками указываются направленными или ненаправленными линиями.

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

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

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

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

Циклические алгоритмы являются наиболее распространенным видом алгоритмов, в них предусматривается повторное выполнение определенного набора действий в зависимости от некоторого условия, называемого условием окончания повторений. Такое повторное выполнение называют циклом. Повторяющиеся действия в цикле называются «телом цикла». Существуют два основных вида циклических алгоритмов: циклические алгоритмы с предусловием, циклические алгоритмы с постусловием. Они отличаются друг от друга местоположением условия выхода их цикла. Цикл с предусловием (цикл ПОКА) начинается с проверки условия выхода из цикла. Это логическое выражение, например I <= 6 (эквивалентно математическому выражению I ≤ 6). Пока оно истинно, то выполняются действия цикла, которые должны повторяться. Если при изменении переменной I логическое выражение I <= 6 станет ложным, то есть I станет больше 6, то цикл с предусловием прекратит свои действия. Цикл с постусловием (цикл ДО ТЕХ ПОР) функционирует иначе. Сначала выполняются один раз те действия, которые подлежат повторению, затем проверяется логическое выражение, определяющее условие выхода из цикла, например, I > 6. Цикл повторяет действия, указанные в теле цикла, до тех пор, пока условие выхода не станет истинным, в противном случае происходит повторение действий, ука- занных в цикле. Разновидности циклов приведены на рис. 10, а, б.