Файл: Алгоритмизация как обязательный этап разработки программы (Основные алгоритмические конструкции. Понятие компьютерной программы).pdf

Введение

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

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

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

Теория алгоритмов оказывает непосредственное влияние на

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

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

Глава 1. Алгоритмизация и алгоритмы

1.1 Понятие алгоритмизации и алгоритмов

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

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

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

Термин «алгоритм» - транскрипция имени великого узбекского математика Мухаммеда аль-Хорезми (Мухаммеда из Хорезма, область в нынешней республике Узбекистан). Мухаммед аль-Хорезми еще в IX веке разработал правила вычета четырех действий арифметики. Многие годы понятие «алгоритм» использовалось математиками для описания правил решения математических задач. Например, существует алгоритм вычисления квадратного корня положительного числа, алгоритм нахождения наибольшего общего делителя двух чисел и многие другие. Однако не следует считать алгоритм чисто математическим понятием.

Каждый из нас с раннего детства, даже не замечая этого, ежедневно решает задачи, для описания которых использует тот или иной алгоритм, сформулированный в виде конечной последовательности однозначных предписаний. Входя в кабину телефона-автомата, вы видите на стене четкий алгоритм, однозначно описывающий ваши действия, цель которых - разговор с другом: снять трубку, опустить монету, набрать номер и т.д. Носителями алгоритмов являются фоторецепторные справочники, инструкции по использованию бытовой аппаратуры (от телевизора до стиральной машины), медицинские рекомендации и описания гимнастических упражнений, даже емкости и упаковки с продуктами (например, приготовленная чашка кофе - готовый результат выполнения алгоритма). Все алгоритмы создаются конкретным автором (человеком или группой людей) в результате обобщения прошлого опыта или технологических разработок и рассчитан на конкретного исполнителя. Алгоритмы «бытовой сферы» всегда предполагают конкретный уровень предварительной подготовки исполнителя и потому излагаются без перечисления ряда промежуточных операций, метод выполнения которых (тоже алгоритм!) избирается самим исполнителем. Автор кулинарного рецепта предполагает, что хозяйка умеет включать и выключать газовую или электроплиту, регулировать нагрев; в инструкции декоративной шпатлевки не описан метод вскрытия упаковки (разрезать бумагу острым предметом или вскрыть металлическую банку консервным ножом…) и т.д.

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

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

2) составление программы задания (задачи).

При таком подходе необходимо:

1) создать строгую систему условных обозначений для записи команд в понятной для человека форме (язык программ);

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

Рассмотрим пример алгоритма для нахождения середины отрезка при помощи циркуля и линейки.

Алгоритм деления отрезка АВ пополам:

1) поставить ножку циркуля в точку А;

2) установить раствор циркуля равным длине отрезка АВ;

3) провести окружность;

4) поставить ножку циркуля в точку В;

5) провести окружность;

6) через точки пересечения окружностей провести прямую;

7) отметить точку пересечения этой прямой с отрезком АВ.

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

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

1.2.1 Массовость

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

1.2.2.Понятность

Чтобы алгоритм можно было выполнить, он должен быть понятен исполнителю. Понятность алгоритмаозначает знание исполнителя о том, что надо делать для исполнения этого алгоритма.

Дискретность.

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

1.2.3 Конечность

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

1.2.4 Определенность

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

1.2.5 Эффективность

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

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

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

Построение такого формального определения было начато с формализации объектов (операндов) алгоритма, так как в интуитивном понятии алгоритма его объекты могут иметь произвольную природу. Ими могут быть, например, числа, показания датчиков, фиксирующих параметры производственного процесса, шахматные фигуры и позиции и т.п. Однако предполагая, что алгоритм имеет дело не с самими реальными объектами, а с их изображениями, можно считать, что операнды алгоритма— слова в произвольном алфавите. Тогда получается, что алгоритм преобразует слова в произвольном алфавите в слова того же алфавита. Дальнейшая формализация понятия алгоритма связана с формализацией действий над операндами и порядка этих действий. Одна из таких формализаций была предложена в 1936 году английским математиком А. Тьюрингом, который формально описал конструкцию некоторой абстрактной машины (машины Тьюринга) как исполнителя алгоритма и высказал основной тезис о том, что всякий алгоритм может быть реализован соответствующей машиной Тьюринга. Примерно в это же время американским математиком Э. Постом была предложена другая алгоритмическая схема —машина Поста, а в 1954 году советским математиком А. А. Марковым была разработана теория классов алгоритмов, названных им нормальными алгорифмами, и высказан основной тезис о том, что всякий алгоритм нормализуем.

1.3 Алгоритмические схемы эквиваленты

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

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