В.2. Виды вычислений и алгоритмов

Известно большое разнообразие вычислений, связанных с числами; однако это узкий смысл термина "вычисление". Современное понимание этого термина подразумевает обработку данных, для представления ко-торых применимы математические абстракции (модели). Это могут быть транспонирование матрицы, сортировка и поиск определённых сведений в базах данных, нахождение наилучшего расположения некоторых объектов, получение оптимальной схемы соединения выводов микросхем на плате, представление на экране дисплея заданного разреза некоторой конструкции и др., а также разнообразные формирования и преобразования образов (све-товых, цветовых, звуковых и музыкальных) в мультимедиа.

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

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

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

Этим видам вычислений соответствуют свои модели вычислений, предназначенные для исследования и описания фундаментальных свойств основных видов вычислительных процессов: рекурсивные функции и ассоци-ативные исчисления. Для исследования и описания процесса переработки дискретной информации подходящими являются автоматные модели и их развитие - машины Тьюринга; последние используются при проверке суще-ствования алгоритма для определённого класса задач.

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

Алгоритмы (вычислительные процессы) могут быть представлены следующими способами: 1) словесным описанием; 2) схемой; 3) програм-мой на подходящем языке.

Наиболее полное и однозначное представление даётся конкретной программой (собственно программа и позволяет реализовать данный вычислительный процесс на ЭВМ); наиболее ёмкое - словесное описание (обычно при этом излагается только идея организации вычислительного процесса, расписанная по пунктам, число которых невелико); наиболее наглядное - с помощью схемы алгоритма (СА). В то же время одна и та же СА может соответствовать различным вычислительным процессам; СА совместно с её интерпретацией (толкованием, раскрытием терминов, про-цедур, обозначений и т.п.) и является представлением конкретного вычис-лительного процесса. Степень подробности СА и близости её к данному вычислительному процессу может быть различной и определяется целью представления СА.

В рассмотренном выше примере даётся словесное описание алгоритма.

Решение некоторой задачи на ЭВМ осуществляется в такой последо-вательности (см. также [2], где подробно описывается полное построение алгоритма). В соответствии с постановкой задачи и выбранной её моделью составляется либо выбирается стандартное словесное описание алгоритма, по которому строится и оптимизируется СА, а затем пишется программа на одном из языков высокого уровня (Паскаль, С и т.д.) или на машинном языке – Ассемблере. За этим следует отладка (проверка правильности, верификация) программы на ЭВМ, для чего используется так называемый контрольный пример, который придуман самим программистом по результатам анализа задачи и может быть проверен вручную. Контрольный пример должен проверять все возможные ветви программы (схемы алгоритма); следует также убедиться, что программа адекватна алгоритму. Анализируется алгоритм и его сложность (выявляются узкие места в программе и определяется эффективность алгоритма, для чего проводится тестирование). И только после успешного решения контрольного примера и получения приемлемых ре-зультатов тестирования можно вводить данные своей задачи и запускать её на выполнение. Важным этапом решения задачи является составление документации по всем предыдущим этапам (помните золотое правило: оформляйте свои программы в таком виде, в каком вам хотелось бы видеть программы, написанные другими!).

Итак, алгоритмом является всякая последовательность действий, выполнение которой можно поручить вычислительной машине; подготовка и решение задачи на ЭВМ сводятся к разработке, описанию и выполнению алгоритма.

Дата добавления: 2014-01-14