15. Алгоритмы и алгоритмизация вычислительных задач

Языки для создания программ. Вычислительный алгоритм и его свойства. Классические этапы подготовки и решения вычислительных задач.

В настоящее время в мире существует несколько сотен реально используемых языков программирования. Для каждого есть своя область применения. В зависимости от степени детализации предписаний обычно определяется уровень языка программирования — чем меньше детализация, тем выше уровень языка. По этому критерию можно выделить следующие уровни языков программирования: 1) машинные; 2) машинно-оpиентиpованные (ассемблеpы); 3) машинно-независимые (языки высокого уровня). Машинные языки и машинно-ориентированные языки — это языки низкого уровня, требующие указания мелких деталей процесса обработки данных. Языки же высокого уровня имитируют естественные языки, используя некоторые слова разговорного языка и общепринятые математические символы. Эти языки более удобны для человека. Языки высокого уровня делятся на: 1) алгоритмические (Basic, Pascal, C и др.), которые предназначены для однозначного описания алгоритмов; 2) логические (Prolog, Lisp и др.), которые ориентированы не на разработку алгоритма решения задачи, а на систематическое и формализованное описание задачи с тем, чтобы решение следовало из составленного описания; 3) объектно-ориентированные (Object Pascal, C++, Java и др.), в основе которых лежит понятие объекта, сочетающего в себе данные и действия над нами. Программа на объектно-ориентированном языке, решая некоторую задачу, по сути, описывает часть мира, относящуюся к этой задаче. Описание действительности в форме системы взаимодействующих объектов естественнее, чем в форме взаимодействующих процедур. Основные преимущества алгоритмических языков перед машинными: 1) алфавит алгоритмического языка значительно шире алфавита машинного языка, что существенно повышает наглядность текста программы; 2) набор операций, допустимых для использования, не зависит от набора машинных операций, а выбирается из соображений удобства формулирования алгоритмов решения задач определенного класса; 3) формат предложений достаточно гибок и удобен для использования, что позволяет с помощью одного предложения задать достаточно содержательный этап обработки данных; 4) требуемые операции задаются с помощью общепринятых математических обозначений; 5) данным в алгоритмических языках присваиваются индивидуальные имена, выбираемые программистом; 6) в языке может быть предусмотрен значительно более широкий набор типов данных по сравнению с набором машинных типов данных. Таким образом, алгоритмические языки в значительной мере являются машинно-независимыми. Они облегчают работу программиста и повышают надежность создаваемых программ. Алгоритмом называется точное и понятное предписание исполнителю совершить последовательность действий, направленных на решение поставленной задачи. Слово «алгоритм» происходит от имени математика Аль Хорезми, который сформулировал правила выполнения арифметических действий. Первые алгоритмы появились вместе с математикой, а теория алгоритмов появилась только в 30-х г нашего века. Математики, решая задачи, строя алгоритмы, позволяющие находить их решения, не уточняли самого понятия алгоритма, т.к. в этом не было необходимости: под алгоритмом всегда понималась процедура, которая позволяла путём выполнения последовательности элементарных шагов получать однозначный результат, независящий от того, кто именно выполнял эти шаги. Долгое время речь шла лишь об алгоритмах производящих вычисления, и набор элементарных шагов был ясен. В него входили все арифметические операции, а также проверки равенств, неравенств и др. Часто алгоритмы задавались в виде формул, в которых с помощью скобок определялся порядок выполнения элементарных шагов в процессе вычисления. Но к 20 в. стали усложняться объекты, с которыми оперировали алгоритмы. Появилась необходимость выполнять операции над векторами, матрицами и т.д. Возникла масса вопросов, одни из них были связаны с трактовкой элементарности тех или иных шагов, а другие – с оценкой конечности, однозначности алгоритма. Стала возникать мысль, что не для всех математических задач вообще можно найти процедуру решения, которая являлась бы алгоритмом. Для этого необходимо было дать точное понятие алгоритма, без которого речь о существовании и не существовании его теряли всякий смысл. Так возникла необходимость в точном понятии: “любой алгоритм”, т.е. о максимально общем понятии алгоритма, под которое подходили бы любые мыслимые виды алгоритмов. Когда началось бурное развитие вычислительной техники и наук, связанных с её использованием, то выяснилось, что в основе этих наук должна лежать теория алгоритмов, т.к. ЭВМ может реализовать только такие процедуры, которые представлены в виде алгоритмов. В теории алгоритмов используется идея построения конкретных алгоритмических моделей, каждая из которых содержит конкретный набор элементарных шагов. С теоретической точки зрения наибольший интерес представляют модели, которые были бы одновременно универсальными и простыми, содержащими минимум необходимых средств. Поиск теоретических моделей алгоритма происходит в 3 направлениях, которые и определили 3 основных класса таких моделей. Первое направление основано на арифметизации алгоритма. Ясно, что любые данные можно закодировать в числах, и тогда всякое их преобразование станет арифметически вычислимым. Всякий алгоритм в таких моделях вычисляет значения некоторых числовых функций, а его элементарные шаги – это арифметические операции. Последовательности шагов определяются с помощью 2 основных способов. 1 способ: Суперпозиция, т.е. подстановка функций в функцию, порождающая математические формулы, в которых порядок действия определяется расстановкой скобок. Например: a*b+c/d, a*b=x, c/d=y, получаем х+у. 2 способ: Менее известен, хотя встречается в элементарной математике – это рекурсия, т.е. определение очередного значения функции через ранее вычисленные значения этой же функции. Пример: n!=1*2*3…*n. С помощью суперпозиции факториал через арифметические операции определить нельзя. Дело в том, что обычные суперпозиционные формулы содержат фиксированное число операций для любых значений элементов, а при вычислении факториала число усложнений растёт с ростом n. 0!=1;(n+1)!=1*2*3…*n*(n+1): n!=(n+1)!/n=1. Структура такого определения функции (примитивно-рекурсивное) состоит из 2-х частей: определить значения функции f для начального значения аргумента. В нашем случае это 0. И определяется f(n+1) через f(n) и другую функцию, которая считается определённой ранее. У нас в примере эту функцию играет умножение. Для вычисления f(n+1) надо для этого вычислить f в предыдущих точках: 1, 2, 3, …, n. Функции, которые можно построить из целых чисел и арифметических операций с помощью суперпозиции и рекурсивных определений, называются рекурсивными функциями. Они являлись исторически первым уточнением понятия алгоритма, т.е. первой универсальной алгоритмической моделью. Использовал эту модель австр. математик Гёдель, доказывая свою знаменитую теорему о принципиальной полноте формальной теории. Второе направление основано на простейшей идее: для того, чтобы алгоритм определялся однозначно, а каждый его шаг можно было считать элементарным и выполнимым, он должен быть представлен так, чтобы его могла выполнять машина. Чем проще структура машины и её действия, тем убедительней выглядит утверждение, что её работа и есть выполнение некоторого алгоритма, при этом структура машины должна быть универсальной, такой чтобы на ней можно было выполнять любой алгоритм. Эта идея привела к концепции абстрактной машины, как универсальной алгоритмической модели. Она была выдвинута А. Тьюрингом и В. Постом. Действия абстрактной машины сводятся к тому, что она обозревает символы, записанные в памяти, например, на ленте, и в зависимости от своего состояния и того, каков обозреваемый символ, она стирает его и заменяет другим символом или какой-то последовательностью символов, после чего читает следующий символ. Наибольшую известность среди моделей такого типа получила модель Тьюринга, за которой закрепилось название «машина Тьюринга». Третье направление связано с уточнением понятия алгоритм, близко ко 2-му. Если рассмотреть механические формальные преобразования данных, не употребляя машинные терминологии, здесь применяется следующее: память, понятие машин, считывание, – то описание действующей машины превращается в систему подстановок, которые указывают, какие замены символов надо произвести и в каком порядке использовать сами подстановки. Наиболее известная алгоритмическая модель этого типа: «Нормальные алгоритмы Маркова». Появление точного понятия алгоритма позволило сформировать понятие алгоритмически неразрешимой проблемы, т.е. задачи, для решения которой не возможно построить алгоритмы. Задача называется алгоритмически неразрешимой, если не существует машины Тьюринга (или рекурсивной функции) или алгоритма Маркова, которые её решили бы. Выделяют 3 крупных класса алгоритмов. Вычислительные алгоритмы, работающие со сравнительно простыми видами данных (числа, матрицы и т.п.), хотя сам процесс может быть долгим и сложным. Информационные – набор сравнительно простых процедур, работающих с большим объемом информации (алгоритмы баз данных). Управляющие – генерируют различные управляющие воздействия на основе данных, полученных от внешних процессов, которыми они управляют. Говоря об алгоритме вычислительного процесса, необходимо понимать, что объектами, к которым применялся алгоритм, являются данные. Алгоритм решения вычислительной задачи представляет собой совокупность правил преобразования исходных данных в результатные. Основными свойствами алгоритма являются: 1) детерминированность (определенность). Предполагает получение однозначного результата вычислительного процесса при заданных исходных данных. Благодаря этому свойству процесс выполнения алгоритма носит механический характер; 2) результативность. Указывает на наличие таких исходных данных, для которых реализуемый по заданному алгоритму вычислительный процесс должен через конечное число шагов остановиться и выдать искомый результат; 3) массовость. Это свойство предполагает, что алгоритм должен быть пригоден для решения всех задач данного типа; 4) дискретность. Означает расчлененность определяемого алгоритмом вычислительного процесса на отдельные этапы, возможность выполнения которых исполнителем (компьютером) не вызывает сомнений. Алгоритм должен быть формализован по некоторым правилам посредством конкретных изобразительных средств. На практике наиболее распространены следующие формы представления алгоритмов: 1) словесная (записи на естественном языке); 2) графическая (изображения из графических символов); 3) псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.); 4) программная (тексты на языках программирования). Наибольшее распространение благодаря своей наглядности получил графический (блок-схемный) способ записи алгоритмов. Блок-схема – графическое изображение логической структуры алгоритма, в котором каждый этап процесса обработки информации представляется в виде геометрических символов (блоков), имеющих определенную конфигурацию в зависимости от характера выполняемых операций. Перечень символов, их наименование, отображаемые ими функции, форма и размеры определяются ГОСТами. Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке. Словесный способ не имеет широкого распространения по следующим причинам: такие описания строго не формализуемы; страдают многословностью записей; допускают неоднозначность толкования отдельных предписаний. Псевдокод представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов. Он занимает промежуточное место между естественным и формальным языками. С одной стороны, он близок к обычному естественному языку, поэтому алгоритмы могут на нем записываться и читаться как обычный текст. С другой стороны, в псевдокоде используются некоторые формальные конструкции и математическая символика, что приближает запись алгоритма к общепринятой математической записи. При всем многообразии алгоритмов решения задач в них можно выделить три основных вида вычислительных процессов: линейный; ветвящийся; циклический. Линейным называется такой вычислительный процесс, при котором все этапы решения задачи выполняются в естественном порядке следования записи этих этапов. Ветвящимся называется такой вычислительный процесс, в котором выбор направления обработки информации зависит от исходных или промежуточных данных (от результатов проверки выполнения какого-либо логического условия). Циклом называется многократно повторяемый участок вычислений. Вычислительный процесс, содержащий один или несколько циклов, называется циклическим. По количеству выполнения циклы делятся на циклы с определенным (заранее заданным) числом повторений и циклы с неопределенным числом повторений. Количество повторений последних зависит от соблюдения некоторого условия, задающего необходимость выполнения цикла. При этом условие может проверяться в начале цикла — тогда речь идет о цикле с предусловием, или в конце — тогда это цикл с постусловием. Этапы подготовки и решения вычислительных задач. 1) Постановка задачи: сбор информации; формулировка условия задачи; определение конечных целей; определение формы выдачи результатов; описание данных (их типов, диапазонов величин, структуры и т.п.). 2) Анализ и исследование задачи, модели: анализ существующих аналогов; анализ технических и программных средств; разработка математической модели; разработка структурных данных. 3) Разработка алгоритма: выбор метода проектирования алгоритма; выбор формы записи алгоритма (блок-схемы, псевдокод и др.); выбор тестов и метода тестирования; проектирование алгоритма. 4) Программирование: выбор языка программирования; уточнение способа организации данных; запись алгоритма на выбранном языке программирования. 5) Тестирование и отладка: синтаксическая отладка; отладка семантической и логической структуры; тестовые расчеты и анализ результатов тестирования; совершенствование программы. 6) Анализ результатов решения задачи и уточнение в случае необходимости математической модели с повторным выполнением этапов 2-5. 7) Сопровождение программы: доработка программы для решения конкретных задач; составление документации к решенной задаче, к математической модели, к алгоритму, к программе, к набору тестов, к использованию.