Файл: Основные структуры алгоритмов сравнительный анализ и примеры их использования.pdf

Введение

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


Цель этой курсовой работы изучить основные структуры алгоритмов и применить их с помощью языка Паскаля и провести сравнение базовых структур алгоритмов.

2

1. Основная концепция алгоритмов

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

---

3

1.2 Алгоритм и его свойства

Алгоритм-четкое описание последовательности действий, которые необходимо выполнить для получения результата. Термин "алгоритм" происходит от Латинской формы имени среднеазиатского математика Аль-Хорезми – Algorithmi. Алгоритм является одним из основных понятий информатики и математики. Основные свойства алгоритмов включают:

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

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

3) Производительность (конечность) - алгоритм должен привести к решению задачи для конечного числа шагов.

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

Правила выполнения арифметических операций или геометрических конструкций-это алгоритмы. При этом остается без ответа вопрос, в чем отличие понятия алгоритма от таких понятий, как «метод», «метод», «правило». Можно даже встретить утверждение, что слова «алгоритм», «метод», «правило» выражают одно и то же (то есть являются синонимами), хотя такое утверждение явно противоречит “свойствам алгоритма”.

4

Выражение «свойства алгоритма " само по себе не совсем правильно. Свойства имеют объективно существующие реальности. Можно говорить, например, о свойствах вещества. Алгоритм-это искусственная конструкция, которую мы строим для достижения определенных целей. Чтобы алгоритм выполнял свое предназначение, он должен быть построен по определенным правилам. Поэтому нужно говорить не о свойствах алгоритма, а о правилах построения алгоритма, или требованиях, предъявляемых к алгоритму.

Первое правило заключается в том, что при построении алгоритма в первую очередь необходимо определить множество объектов, с которыми будет работать алгоритм. Формализованное (закодированное) представление этих объектов называется данными. Алгоритм начинает работать над набором данных, называемым входом, и в результате его работы создает данные, называемые выходом. Таким образом, алгоритм преобразует вход в выход. Это правило позволяет сразу отделить алгоритмы от "методов"и " методов". Пока у нас нет формализованного ввода, мы не можем построить алгоритм.

---

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

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

Третье правило-скрытность. Алгоритм строится из отдельных шагов (действий, операций, команд). Много шагов, из которых составлен алгоритм, конечно.
5

Четвертое правило-детерминизм. После каждого шага необходимо указать следующий шаг или дать команду на остановку.

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

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

6

1.3 Методы изображения алгоритмов

Словесное описание алгоритма

Этот метод был гораздо менее распространен из-за его многословия и отсутствия видимости.

Рассмотрим пример алгоритма, чтобы найти максимум из двух значений:

Мы определяем форматы переменных Х, У, М, где Х и у значения для сравнения, М является переменной для хранения максимального значения;

получаем два значения чисел х и у Для сравнения; сравниваем х и у.

если Х меньше у, это означает большее число у. поместите значение у в переменную М.

Если Х не меньше (больше) у, это означает, что число х больше. Поместите значение x в переменную M.

---

Вербальный метод не получил широкого распространения по следующим причинам:

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

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

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

7

Блок-схема алгоритма

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

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

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

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

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

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

основные соглашения, используемые при графическом написании алгоритма.(рис.1)
8

рис 1


9

Псевдокод

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

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

---

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

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

10

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

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

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

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


11

1.4 Алгоритмы и исполнители

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

Исполнитель — это некоторый объект (человек, животное, техническое устройство), способный выполнять определённый набор команд.

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

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

Система команд исполнителя. Различают команды-приказы и команды-запросы. Предписание исполнителю о выполнении отдельного законченного действия отдаётся командой-приказом. Команды-запросы позволяют узнать текущие характеристики среды исполнителя. Совокупность всех команд, которые могут быть выполнены некоторым исполнителем, образует систему команд данного исполнителя (СКИ). Алгоритм составляется с учётом возможностей конкретного исполнителя, иначе говоря, в системе команд исполнителя, который будет его выполнять.

---