Алгоритмические основы программирования

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

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

Алгоритмизация задачи — процесс разработки (проектирования) алгоритма решения задачи с помощью ПК на основе ее условия и требований к конечному результату.

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

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

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

Термин алгоритм происходит от имени узбекского ученого IX в. АльХорезми, который в своем труде? Арифметический трактат?, переведенном в XII в. с арабского на латынь, изложил правила арифметических действий над числами в позиционной десятичной системе счисления. Эти правила и называли алгоритмами. Таким образом, правила сложения, вычитания, деления, умножения чисел, правила преобразования алгебраических выражений, правила построения геометрических фигур, грамматические правила правописания слов и предложений — все это алгоритмы. Многие правила, инструкции, записанные в различных документах и представляющие собой подробнейшие указания, годные во всевозможных ситуациях, также можно отнести к алгоритмам.

Виды алгоритмов как логико-математических средств отражают также компоненты человеческой деятельности, а сами алгоритмы в зависимости от цели, начальных условий задачи, путей ее решения и определения действий исполнителя подразделяются на [3]:

• — механические алгоритмы, или детерминированные, жесткие (например, алгоритм работы машины, двигателя и т. п.);
• — гибкие алгоритмы, например стохастические, т. е. вероятностные и эвристические.

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

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

Эвристический алгоритм (от греческого слова? эврика? — ?Я нашел?) — это такой алгоритм, в котором достижение конечного результата программы действий однозначно не предопределено, так же как не обозначена вся последовательность действий, не выявлены все действия исполнителя. К эвристическим алгоритмам относят, например, инструкции и предписания.

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

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

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

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

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

Типичный пример эквивалентного преобразования алгоритмов — перевод с одного алгоритмического языка на другой.

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

• 1) последовательную декомпозицию задачи, выделение автономных этапов вычислительного процесса и разбивку каждого этапа на отдельные шаги;
• 2) формальную запись содержания каждого этапа и/или шага;
• 3) определение общего порядка выполнения этапов и/или шагов;
• 4) проверку правильности алгоритма.

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

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

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

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

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

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

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

Соответствующие системы правил называют языками описаний.

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