Решение задач с помощью компьютера

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

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

1. Может ли компьютер решить данную задачу в принципе?

2. Как «объяснить» (точнее, «приказать» – компьютер не способен «отказаться»), что надо сделать, чтобы решить данную задачу.

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

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

Обычно работа по решению задачи на компьютере проходит через следующие этапы:

1. постановка задачи;

2. математическая формализация (моделирование);

3. построение алгоритма;

4. составление программы на языке программирования;

5. отладка и тестирование программы;

6. проведение расчетов и анализ полученных результатов.

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

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

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

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

Построение алгоритма - важный этап решения задачи, предшествующий составлению программы. Наличие ошибок в алгоритме неизбежно влечёт за собой ошибки в программе. От правильности алгоритма зависит трудоёмкость программирования и отладки программы. Поэтому ещё на этом этапе должна планироваться система тестов, на которых нужно проверять создаваемую программу, и должно проводиться «ручное тестирование» алгоритма.

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

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

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

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

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

Данное пособие посвящено построению алгоритмов - важному этапу решения задачи, предшествующему составлению программы.

Понятие алгоритма

Понятие алгоритма является одним из базовых, первичных понятий математики (откуда пришло само слово) и информатики. Слово «алгоритм» происходит от algorithmi – латинского написания имени аль-Хорезми, под которым в средневековой Европе знали величайшего математика из Хорезма (город в современном Узбекистане) Мухаммеда бен Мусу, жившего в 783-850 гг. В своей книге «Об индийском счете» он сформулировал правила записи натуральных чисел с помощью арабских цифр и правила действий над ними. Словом «алгоритм» и стали обозначать эти правила вычислений. В дальнейшем это слово получило более широкий смысл.

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

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

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

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

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

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

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

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

Массовость (универсальность) – алгоритм должен быть применим к разным наборам исходных данных из некоторого множества корректно заданных исходных данных.

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

Виды алгоритмов.

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

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

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

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

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

– следование (процесс) – соответствует линейному алгоритму;

– выбор (ветвление, решение) – соответствует разветвляющемуся алгоритму;

– повторение (цикл) – соответствует циклическому алгоритму.

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

Способы записи алгоритмов

Алгоритмы можно записывать разными способами:

· вербальным − на естественном языке, такой способ применяют обычно на начальном этапе составления алгоритма;

· в виде псевдокодов;

· графическим − в виде структурной схемы;

· в виде программы на каком-либо языке программирования.

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

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

Описание алгоритма с помощью структурных схем (иногда их называют блок-схемами) осуществляется рисованием последовательности геометрических фигур, каждая из которых подразумевает выполнение действия определенного типа. Порядок выполнения действий указывается линиями, которые могут снабжаться стрелками. Если линия направлена сверху вниз или слева направо, стрелку на ней можно не ставить, в противном случае стрелка обязательна. Данный способ является исключительно наглядным и простым способом записи алгоритмов. Запись алгоритмов с помощью структурных схем регламентируется Государственным стандартом ГОСТ 19.701-90 “Схемы алгоритмов, программ, данных и систем”. Внешний вид основных блоков, применяемых при создании схем алгоритмов, приведен в таблице:

Название	Обозначение	Пояснение
Процесс		Действие или последовательность действий по обработке данных, приводящих к их изменению
Решение		Проверка условия - операция с одним входом и несколькими альтернативными выходами
Границы цикла		Начало и конец цикла. Условия для инициализации, приращения и завершения помещаются внутри символа начала или конца в зависимости от расположения операции, проверяющей условие
Предопределенный процесс		Процесс, состоящий из операций, описанных в другом месте (на другой схеме) – обращение к вспомогательному алгоритму.
Ввод-вывод		Ввод-вывод в общем виде
Пуск-останов		Начало, конец алгоритма, вход в подпрограмму и выход

 

Все блоки имеют по одному входу. Количество выходов также равно одному, и только блок «решение» может иметь два, три или больше выходов.

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