Файл: ТЕХНОЛОГИИ ПРОГРАММИРОВАНИЯ. Алгоритмизация как обязательный этап разработки программы..pdf
Добавлен: 13.03.2024
Просмотров: 23
Скачиваний: 0
Содержание:
Введение
Решение задач на компьютере основано на понятии алгоритма. Алгоритм – это точное предписание, которое определяет вычислительный процесс, ведущий от изменяемых исходных данных к результату.
Понятие алгоритма – одно из фундаментальных понятий, которое составляет самостоятельную дисциплину - «теорию алгоритмов». Также теорию алгоритмов можно рассматривать промежуточным звеном между двумя дисциплинами: математикой и информатикой, связанной с программированием.
Алгоритмизация относится к общим методам информатики и имеет большое значение при решении различных задач. Прежде, чем написать программу решения задачи на компьютере, необходимо проанализировать последовательность действий, которые должны быть выполнены для правильного решения рассматриваемой задачи. Разработка алгоритма является трудоемким и сложным процессом. Для решения задачи программист должен составить подробное описание последовательности действий, которые необходимо выполнить процессору компьютера. Алгоритмизация – это техника составления алгоритма для решения задач на компьютере.
Цель работы: изучение методов алгоритмизации и использование полученных знаний для решения прикладных задач.
Задачи работы:
Формирование базовых знаний по алгоритмизации, рациональные методах разработки алгоритмов;
Изучение базовых алгоритмических структур;
Изучение объектов алгоритмов.
Алгоритмические основы программирования
Прежде чем приступить описанию процесса составления алгоритмов, выясним, какие этапы составляют процесс решения задачи на ЭВМ.
I этап – постановка задачи. На данном этапе должна быть определена предметная область задачи, определены её цели, необходимый объем исходной информации, проведено описание всех исходных данных. Предложен общий подход к решению.
II этап – математическое описание задачи. Цель – создать математическую модель, которая может быть реализована на компьютере, выбрать оптимальный метод решения задачи.
Математическая модель - это описание объекта или процесса при помощи математических зависимостей, связывающих их количественные параметры.
III этап – алгоритмизация задачи. Главная особенность всех вычислений компьютера состоит в том, что в основе его работы находится программный принцип управления. Это означает, что для решения любой задачи пользователю необходимо задать перечень инструкций или команд, следуя которым шаг за шагом компьютер выдаст необходимый результат. Иными словами, для того, чтобы решать задачу на компьютере, ее необходимо сначала, алгоритмизировать. Именно алгоритмический принцип и лежит в основе работы всех вычислительных машин.
На основе математической модели разрабатывается алгоритм решения. Обычно алгоритм разрабатывается на основе блок – схемы с четко определенной последовательностью действий.
IV этап – собственно программирование. Программа – это представление алгоритма с помощью специальных операторов, воспринимаемых компьютером. Каждому блоку алгоритма соответствует определенная последовательность операторов. Программа обеспечивает возможность реализации алгоритма и, соответственно, поставленной задачи. При составлении программы возможна корректировка алгоритма.
V этап – ввод программы в вычислительную машину. На этом этапе программу необходимо набрать в среде программирования и сохранить на диске.
VI этап – разработка контрольных примеров. Для того, чтобы убедиться в правильности составленной программы, необходимо разработать комплекс тестовых задач, для проверки всех ветвей алгоритма. Это совокупность таких исходных данных, на основании которых предварительно определяются выходные данные.
VII этап – отладка программы. Программа и исходные данные контрольного примера обрабатываются на компьютере и, если контрольный пример работает неправильно, то необходимо найти ошибки, допущенные в программе и вновь выполнить её проверку.
VIII этап – получение и анализ результатов. После устранения всех ошибок, выявленных тестированием, можно перейти к получению практических результатов поставленной задачи. Полученные результаты необходимо проанализировать.
Понятие алгоритма
Для решения поставленной задачи исполнителю необходимо указать последовательность действий, которые он должен выполнить для достижения цели - получения результата. Другими словами исполнителю должен быть указан алгоритм решения задачи, представленный на понятном ему языке. Под исполнителем подразумевается как человек, так и вычислительная машина.
Перед решением любой задачи с помощью персонального компьютера, как было сказано выше, выполняются следующие этапы: постановка этой задачи, построение сценария и алгоритмизация.
Алгоритмизация задачи - процесс разработки алгоритма решения задачи с помощью компьютера на основе ее условия и требований к конечному результату.
На этапе постановки задачи описываются исходные данные, формируются правила начала и окончания решения задачи, т.е. разрабатывается информационная или математическая модель. Методом проб и ошибок ведется поиск метода решения задачи (метода вычислений, перебора вариантов, распознавания образов). На основании выбранного метода разрабатывается исходный алгоритм, реализация которого возможна с помощью компьютера. При разработке исходного алгоритма и при выборе модели пользователь должен иметь представление о математическом обеспечении компьютера.
Алгоритм - понятное и точное предписание исполнителю совершить последовательность действий, направленных на достижение указанной цели или на решение поставленной задачи.[11]
Алгоритм применительно к персональному компьютеру - точное предписание - набор операций и правил их чередования, при помощи которого, начиная с некоторых исходных данных, можно решить задачу фиксированного типа. Команда алгоритма - предписание о выполнении отдельного законченного действия исполнителя.
Сам термин алгоритм происходит от имени узбекского ученого IХ в. Аль- Хорезми, который в своем труде «Арифметический трактат» изложил правила арифметических действий над числами в десятичной системе счисления. Эти правила и были названы алгоритмами. Следовательно, правила сложения, вычитания, деления, умножения чисел, правила преобразования алгебраических выражений, правила построения геометрических фигур, грамматические правила правописания слов и предложений - все это алгоритмы. Многие правила, инструкции, записанные в различных документах и представляющие собой подробные указания, которые могут быть использованы во всевозможных ситуациях, можно также отнести к алгоритмам.
Виды алгоритмов как логико-математических средств отражают также компоненты человеческой деятельности, а сами алгоритмы в зависимости от цели, начальных условий задачи, путей ее решения и определения действий исполнителя подразделяются на [14]:
- механические, или детерминированные, жесткие алгоритмы (алгоритм работы машины, двигателя и т.п.);
- гибкие алгоритмы, например стохастические, т.е. вероятностные и эвристические.
Механический алгоритм задает определенные действия, обозначая их в единственной и достоверной последовательности, обеспечивая тем самым однозначный требуемый результат, если выполняются те условия задачи, для которых разработан алгоритм.
Вероятностный алгоритм дает программу решения задачи несколькими путями или способами, приводящими к вероятному достижению результата.
Эвристический алгоритм - это такой алгоритм, в котором достижение конечного результата программы действий однозначно не предопределено, так же как и не обозначена вся последовательность действий, не выявлены все действия исполнителя. К эвристическим алгоритмам относят, например, предписания и инструкции.
В этих алгоритмах используются универсальные логические процедуры и способы принятия решений, основанные на ассоциациях, аналогиях и прошлом опыте решения схожих задач.
Под эвристикой понимается совокупность специальных методов и приемов, позволяющих открыть новое, неизвестное, найти решение нетривиальной задачи.
Эвристика изучает продуктивное творческое мышление и на этой основе выявляет способы построения оптимальных направлений поиска решений задач, точные методы решения которых неизвестны.
Достаточно часто для получения новых алгоритмов используются уже существующие алгоритмы. Это осуществляется комбинированием известных алгоритмов или с помощью эквивалентных преобразований алгоритмов.
Алгоритмы называются эквивалентными, если результаты, получаемые с помощью этих алгоритмов для одних и тех же исходных данных, одинаковы.
Типичный пример эквивалентного преобразования алгоритмов - перевод с одного алгоритмического языка на другой.
В общем случае алгоритмизация вычислительного процесса включает следующие действия:
1) последовательную декомпозицию задачи, выделение независимых этапов вычислительного процесса и разбивку каждого этапа на отдельные шаги;
2) формальную запись содержания каждого этапа или шага;
3) определение общего порядка выполнения этапов или шагов;
4) проверку правильности алгоритма.[3]
Последовательная декомпозиция предполагает разделение сложной задачи на множество более простых подзадач.
Часто программисты не уделяют этапу алгоритмизации достаточного внимания и даже пытаются его игнорировать. В результате процесс программирования сильно усложняется.
Значительно проще решать задачу постепенно, в два этапа (при этом сложность выполнения каждого отдельного этапа получается в несколько раз меньше сложности исходной задачи).
На первом этапе необходимо наметить общую стратегию решения задачи и составить соответствующий алгоритм. При этом для сложной задачи алгоритмизация выполняется постепенно. Сначала составляется укрупненная схема решения, а затем схемы работы отдельных блоков. Также при алгоритмизации одного и того же процесса можно использовать различные способы записи.
На втором этапе остается лишь выполнить кодирование (программирование), заменив формульно-словесные инструкции алгоритма операторами конкретного языка. Эта работа уже не связана с большим умственным напряжением. При простых задачах для ее выполнения достаточно знать общие правила оформления программ, правила описания данных, основные операторы (ввода, вывода, управления, обработки). [3]
Не все задачи, которые хотелось бы решить, имеют алгоритмы решения. Задачи, в принципе не имеющие общего решения, называют алгоритмически неразрешимыми. Например, мы знаем, как решить квадратное уравнение, пользуясь одним и тем же алгоритмом. Подобные формулы существуют и для уравнений третьей и четвертой степени. Но для уравнений степени выше четвертой таких формул нет. Есть и другие алгоритмически неразрешимые задачи, например задача о трисекции угла, о квадратуре круга и др.
Свойства алгоритма - набор признаков, отличающих алгоритм от любых предписаний и обеспечивающих его автоматическое исполнение.
Алгоритмы обладают следующими свойствами [4]: понятностью, дискретностью, точностью, результативностью, массовостью.
Понятность - содержание предписания о выполнении только таких действий, которые входят в систему команд исполнителя. Алгоритм должен быть задан с помощью таких указаний, которые исполнитель (например, персональный компьютер) может воспринимать и выполнять по ним требуемые действия.
Дискретность - выполнение команд алгоритма последовательно, с точной фиксацией моментов окончания выполнения одной команды и начала выполнения следующей. Алгоритм должен содержать такую последовательность команд, каждая из которых приводит к выполнению в исполнителе одного шага.
Определенность - каждое правило алгоритма должно быть четким и однозначным. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.
Результативность - или завершение решения задачи после выполнения алгоритма, или вывод о невозможности продолжения решения по какой-либо из причин. Алгоритм должен обеспечивать возможность получения результата за конечное число шагов.
Массовость - алгоритм решения задачи разрабатывается в общем виде, он должен быть применим для некоторого класса задач, различающихся лишь исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.
Для решения одной и той же задачи можно использовать различные алгоритмы. В связи с этим необходима возможность сравнивать их между собой, а для этого нужны определенные критерии качества алгоритмов.
Временные характеристики алгоритма определяют длительность решения или временную сложность [7].
Длительность решения обычно выражается в единицах времени, но удобнее ее выражать через количество операций, так как оно не зависит от быстродействия конкретной вычислительной машины.
Временной сложностью алгоритма называют зависимость времени счета, затрачиваемого на получение результатов, от объема исходных данных.
Временная сложность позволяет определить наибольший размер задачи, которую можно решить с помощью данного алгоритма на компьютере. Каждый алгоритм можно характеризовать функцией f(n), выражающей скорость роста объема вычислений при увеличении размерности задачи - n. Если эта зависимость имеет линейный или полиномиальный характер, то алгоритм считается «хорошим», если экспоненциальный - «плохим».
