Файл: АЛГОРИТМИЗАЦИЯ КАК ОБЯЗАТЕЛЬНЫЙ ЭТАП РАЗРАБОТКИ ПРОГРАММЫ (составление алгоритмов).pdf

ВВЕДЕНИЕ

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

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

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

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

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

1. АЛГОРИТМИЗАЦИЯ

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

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

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

2. ПОНЯТИЕ АЛГОРИТМА

Алгоритм – это ин­струк­ция, точ­ное опи­са­ние спо­со­ба дей­ст­вия с ис­поль­зо­ва­ни­ем про­стых, об­ще­по­нят­ных эле­мен­тов (напр., опе­ра­ций). ^[[2]]

Понятие является одним из основных понятий современной математики. Еще на самых ранних ступенях развития математики (Древний Египет, Вавилон, Греция) в ней стали возникать различные вычислительные процессы чисто механического характера. С их помощью искомые величины ряда задач вычислялись последовательно из исходных величин по определенным правилам и инструкциям. Со временем все такие процессы в математике получили название алгоритмов (алгорифмов).

Термин алгоритм происходит от имени средневекового узбекского математика Аль-Хорезми, который еще в IX в. (825 г) дал правила выполнения четырех арифметических действий в десятичной системе счисления. Процесс выполнения арифметических действий был назван алгоризмом.

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

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

Под алгоритмом понимали конечную последовательность точно сформулированных правил, которые позволяют решать те или иные классы задач. Такое определение алгоритма не является строго математическим, так как в нем не содержится точной характеристики того, что следует понимать под классом задач и под правилами их решения. ^[[3]]

Исполнитель алгоритма – это абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом.

Каждый исполнитель может выполнить команды только из некоторого строго заданного списка – системы команд исполнителя. Для каждой команды должны быть заданы условия применимости и описаны результаты выполнения команды. Говорят, что исполнитель действует формально, т.е. не отвлекается на содержание поставленной задачи, а только строго выполняя команды. Это очень важная особенность алгоритмов. ^[[4]]

2.1 СВОЙСТВА И ВИДЫ АЛГОРИТМОВ

Основные свойства алгоритмов:

а) понятность – исполнителю алгоритма должна быть известна система команд исполнителя;

б) дискретность (прерывность, раздельность) – алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) команд;

в) определенность – каждое правило алгоритма должно быть четким и однозначным. Алгоритм должен иметь одно начало и один конец. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче;

г) результативность (или конечность) состоит в том, что алгоритм должен приводить к решению задачи за конечное число шагов;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

– алгоритм, повторение и же действия и тех же операций над данными. К сводится вычислений, .

Цикл – команд (, цикла), выполняться ( новых ) до выполнения .

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

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

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

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

В общем вычислительного следующие :

1) овательную , выделение вычислительного и каждого на шаги;

2) содержания и или шага;

3) порядка и или шагов;

4) алгоритма.

предполагает задачи на простых .

начинающие не этапу внимания и его игнорировать. В программирования .

Значительно задачу , в два (при выполнения этапа в раз меньше задачи).

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

На остается кодирование (), формульно-словесные операторами . Эта работа уже не с умственным . При задачах для ее знать оформления , описания , операторы (, , управления). ^[[7]]

В алгоритма . Если в не просматривается идея, , вы для ее выражения низкого . ^[[8]]

3. ОПИСАНИЯ

по оформлению , программ, и состоят из , заданное , пояснительного и линий. Эти государственными :

19.701-90 ( Схемы , , данных и . обозначения и . Единая документации. ^[[9]]

Схемы и . Обозначения . Единая документации. ^[[10]]

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

К описания следующие их представления: , ; псевдокоды; . На используются так же и описания: ( истинности); ; циклограммы . ^[[11]]