Основные этапы решения задач на компьютере

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

Рассмотрим эти этапы на примере решения квадратного уравнения.

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

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

Третий этап – алгоритмизация задачи. На основе математического описания необходимо разработать алгоритм решения.

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

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

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

2. Детерминированность – на каждом шаге одно­значно определено преобразование объектов среды исполнителя, полученной на предыдущих шагах алгоритма. Если алгоритм многократно применяется к одному и тому же набору исходных данных, то на выходе он получает каждый раз один и тот же результат.

Замечание. Свойство детерминированности объединяет в себе одновременное выполнение свойств точности и понятности. Поясним эти свойства.

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

Понятность (для данного исполнителя) – алгоритм не должен содержать предписаний, смысл которых мо­жет восприниматься неоднозначно. Это означает, что одно и то же предписание после исполнения должно давать один и тот же результат. То есть запись алгоритма должна быть настолько четкой и полной, чтобы у исполнителя не возникало потребности в принятии каких-либо самостоятельных решений, не предусмотренных составителем алгоритма. Алгоритм всегда рассчитан на выполнение «не размышляющего» исполнителя.

Рассмотрим известный пример «бытового» алгоритма – алгоритм перехода улицы: «Посмотри налево. Если машины нет – дойди до середины улицы. Если есть – подожди, пока они проедут». И т.д. Представьте себе ситуацию: машина слева есть, но она не едет – у нее меняют колесо. Если вы думаете, что надо ждать, то вы поняли этот алгоритм. Если же вы решили, что улицу переходить можно, считая алгоритм подправленным ввиду непредвиденных (по вашему мнению!) обстоятельств, то вы не усвоили понятие алгоритма.

3. Результативность – каждый шаг (и алгоритм в целом) после своего завершения дает среду, в которой все объекты однозначно определены. Если это по каким-либо причинам невозможно, то алгоритм должен сообщать, что решение задачи не существует. При точном исполнении команд алгоритма процесс должен прекратиться за конечное число шагов, и при этом должен быть получен ответ на вопрос задачи. В качестве одного из возможных ответов может быть и установление того факта, что задача решений не имеет.

4. Конечность – завершение работы алгоритма за конечное число шагов. Информатика оперирует только с конечными объектами и конечными процессами, поэтому вопрос о рассмотрении бесконечных алгоритмов остается за рамками теории алгоритмов.

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

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

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

Элементарные шаги алгоритма при укрупнении объе­диняются в алгоритмические конструкции: линейные (последовательные), ветвящиеся, циклические, рекурсивные. В 1969 году Эдсгер В. Дейкстра в статье «Структуры данных и алгоритмы» доказал, что для записи любого алгоритма достаточно трех основных алгоритмических конструкций: линейных (последовательных), ветвящихся, циклических.

Алгоритм Р реализован через последовательную алгоритмическую конструкцию, если каждый шаг алгоритма Р выполняется один раз, причем после каждого i-го шага выполняется (i+1)-й шаг, если i-й шаг – не конец алгоритма.

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

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

Алгоритм Rназывается рекурсивным, если на каком-либо шаге он прямо или косвенно обращается сам к себе.

существует много разных возможностей для представления (описания) одного и того же алгоритма:

• словесное описание;

• псевдокод;

• запись в виде блок-схемы;

• запись алгоритма на каком-либо языке программирования;

• формальное представление алгоритма в виде машины Тьюринга или машины Поста.

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

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

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

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

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

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

Блок-схема представляет собой изображение алгоритма в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. Этот способ имеет ряд преимуществ. Благодаря наглядности, он обеспечивает «читаемость» алгоритма и явно отображает порядок выполнения отдельных команд. В блок-схеме каждой формальной конструкции соответствует определенная геометрическая фигура или связанная линиями совокупность фигур.

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

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