Файл: Lektsii_Informatika_Ekonom.doc

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

2. Используемые на практике алгоритмы составляются с ориентацией на опреде­ленного исполнителя. Чтобы составить для него алгоритм, нужно знать, какие команды этот исполнитель может понять и исполнить, а какие - не может. Состав­ляя запись алгоритма для определенного исполнителя, можно использовать лишь те команды, которые имеются в его ски. Это свойство алгоритмов будем называть понятностью.

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

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

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

Достаточно распространенным способом представления алгоритма является его запись на алгоритмическом языке, представляющем в общем случае систему обозна­чений и правил для единообразной и точной записи алгоритмов и исполнения их. Отметим, что между понятиями «алгоритмический язык» и «языки программирова­ния» есть различие; прежде всего, под исполнителем в алгоритмическом языке может подразумеваться не только компьютер, но и устройство для работы «в обстановке». Программа, записанная на алгоритмическом языке, не обязательно предназначена компьютеру. Практическая же реализация алгоритмического языка - отдельный вопрос в каждом конкретном случае. Как и каждый язык, алгоритмический язык имеет свой словарь. Основу этого словаря составляют слова, употребляемые для записи команд, входящих в систему команд исполнителя того или иного алгоритма. Такие команды называют просты­ми командами. В алгоритмическом языке используют слова, смысл и способ упот­ребления которых задан раз и навсегда. Эти слова называют служебными. Исполь­зование служебных слов делает запись алгоритма более наглядной, а форму пред­ставления различных алгоритмов - единообразной. Алгоритм, записанный на алгоритмическом языке, должен иметь название. На­звание желательно выбирать так, чтобы было ясно, решение какой задачи описыва­ет данный алгоритм. Для выделения названия алгоритма перед ним записывают служебное слово алг (алгоритм). За названием алгоритма (обычно с новой строки) записывают его команды. Для указания начала и конца алгоритма его команды заключают в пару служебных слов нач (начало) и кон (консц). Команды записывают последовательно.

Последовательность записи алгоритма:

Алг название алгоритма

Нач

Серия команд алгоритма

Кон

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

Алг движение

Нач

Вперед

Вперед

Вправо

Движение

Кон

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

Если условие если условие если край

То серия1 то серия то вправо

Иначе серия2 все иначе вперед

Все все

Ниже приводится запись на алгоритмическом языке команды выбора (см. Рис.3, б), являющейся развитием команды ветвления:

Выбор

При условие 1: серия 1

При условие 2: серия 2

. . . . . . . . . .

При условие n: серия n

Иначе серия n+1

Все

Алгоритмы, при исполнении которых отдельные команды или серии команд выполняются неоднократно, называют циклическими. Для организации цикличе­ских алгоритмов в алгоритмическом языке используют специальную составную команду цикла. Она соответствует блок-схемам типа «итерация» и может прини­мать следующий вид:

Пока условие нц

Нц серия

серия до условие

Кц кц

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

Известно несколько подходов к формализации понятия «алгоритм»:

• Теория конечных и бесконечных автоматов;

• Теория вычислимых (рекурсивных) функций;

• Λ -исчисление черча.

Все эти возникшие исторически независимо друг от друга подходы оказались впоследствии эквивалентными. Главная цель формализации понятия алгоритма такова: подойти к решению проблемы алгоритмической разрешимости различных математических задач, т.е. Ответить на вопрос, может ли быть построен алгоритм, приводящий к решению задачи. Формализацию понятия алгоритма можно рассмотреть в теории автоматов на примере машин поста, тьюринга, а также нормальных алгоритмов маркова. Идеи λ-исчислений черча реализованы в языке программирования lisp.Вместе с тем, формально определенный любым из известных способов алгоритм не может в практическом программировании заменить то, что мы называли алго­ритмами. Основная причина состоит в том, что формальное определение резко сужает круг рассматриваемых задач, делая многие практически важные задачи недоступными для рассмотрения.

Основные принципы разработки и анализа алгоритмов

При построении алгоритма для сложной задачи используют системный подход с использованием декомпозиции (нисходящее проектирование сверху-вниз) и синтеза (восходящее программирование снизу-вверх). Как и при разработке структуры любой сложной системы, при формировании алгоритма используют дедуктивный и индуктивный методы. При дедуктивном подходе рассматривается частный случай общеизвестных ал­горитмических моделей. Здесь при заданных предположениях известный алгоритм приспосабливается к условиям решаемой задачи. В настоящее время получили распространение специализи­рованные пакеты, позволяющие решать многие задачи (mathcad, eureka, reduce, autocad и т.п.).Индуктивный способ предполагает эвристический системный подход (декомпо­зиция - анализ - синтез). В этом случае общих и наиболее удачных методов не сущест­вует. Возможны некоторые подходы, позволяющие в каждом конкретном случае находить и строить алгоритмы. Методы разработки алгоритмов можно разбить на методы частных целей, подъема, отрабатывания назад, ветвей и границ и т.п.Одним из системных методов разработки алгоритмов является структурное про­граммирование. Структурное программирование основано на использовании блок-схем, форми­руемых с помощью управляющих структурных элементов. Выделяют три базовых структурных элемента (управляющие структуры): композицию, альтернативу, итерацию.

рис. 5. Функциональные (а), предикатные (б) и объединяющие (в) вершины

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

Рис. 6. Структура «композиция»

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

Рис. 7. Структура «альтернатива». Здесь в — условие (логическое выражение)

Итерация - это циклическая конструкция алгоритма, которая, вообще говоря, является составной структурой, состоящей из композиции и альтернативы. Итера­ции, могут быть представлены в двух формах: с предусловием (а) и с постусловием (б) (рис.8).Каждая из рассмотренных структур имеет один вход и один выход. Поэтому любая компьютерная программа может быть представлена блок-схемой, сформиро­ванной из представленных трех управляющих структур.