Алгоритмы и данные
Решение любой проблемы является творческим процессом, состоящим из нескольких, зачастую повторяющихся этапов. Проблемы, требующие решения средствами прикладного программного обеспечения ЭВМ, относятся к классу задач, решение которых включает большой объем рутинных операций для обработки данных или не может быть получено без использования ЭВМ. Для обоснованного решения таких проблем рекомендуется применять системный подход, основанный на понятии алгоритма.
Алгоритм — одно из основных понятий математики, которое невозможно строго определить, а можно лишь пояснить с помощью других слов. Можно сказать, алгоритм — набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий.
Алгоритмы должны обладать следующими свойствами.
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, а, б.