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

Введение

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

Задачи и цели:

1. Получить знания, что такое алгоритм, основные понятия.

2. Узнать структуры алгоритмов и алгоритмические конструкции.

3. Провести сравнительный анализ.

4. Привести примеры использования алгоритмов.

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

Глава 1. Основные понятия и свойства алгоритма

Алгоритм – одно из основных понятий программирования и математики.

Современное формальное определение вычислительного алгоритма было дано в 30—50-е годы XX века в работах Тьюринга, Поста, Чёрча (тезис Чёрча — Тьюринга), Н. Винера, А. А. Маркова.

Около 1250 года английский астроном и математик Иоанн Сакробоско написал труд по арифметике Algorismus vulgaris, на столетия ставший основным учебником по вычислениям в десятичной позиционной системе счисления во многих европейских университетах.

Алгоритм – запись последовательности команд на формальном языке для исполнителя. Команды должны соответствовать системе команд исполнителя, для которого пишется алгоритм.

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

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

1. детерминированность (определенность). Предполагает получение однозначного результата вычислительного процecca при заданных исходных данных. Благодаря этому свойству процесс выполнения алгоритма носит механический характер;

---

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

3. массовость. Это свойство предполагает, что алгоритм должен быть пригоден для решения всех задач данного типа;

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

5. понятность: алгоритм составляется только из команд, входящих в СКИ исполнителя.

6. точность: каждая команда алгоритма управления определяет однозначное действие исполнителя.

7. конечность (или результативность): выполнение алгоритма должно приводить к результату за конечное число шагов.

Схема алгоритма — графическое представление алгоритма, дополняемое элементами словесной записи.

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

Каждый исполнитель характеризуется следующими параметрами:

1) Среда – условия, в которых находится и функционирует исполнитель (пример, исполнитель Черепашка функционирует в системе координат, исполнитель Робот перемещается по полю с клетками и т.д.).

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

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

Основные структуры алгоритмов — это ограниченный набор стандартных способов соединения отдельных блоков или структур для выполнения типичных последовательностей действий.

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

Обход – частный случай разветвления, когда одна ветвь не содержит никаких действий. Множественный выбор является обобщением разветвления, когда в зависимости от значения переменной (i) выполняется одно из нескольких действий. При I = 1 выполняется действие S1, при I = 2 – действие S2 и т. Д.

---

Система команд исполнителя (СКИ) - это вся совокупность команд, которые исполнитель умеет выполнять.

Команда ввода - команда, по которой значения переменных задаются через устройства ввода (например, клавиатуру).

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

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

Виды алгоритмов.

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

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

Примером может являться разветвляющийся алгоритм, изо­браженный в виде блок-схемы. Аргументами этого алгоритма являются две переменные А, В, а результатом — пере­менная X. Если условие А > В истинно, то выполняется операция X := А х В, в противном случае выполняется Х.= А + В. В резуль­тате печатается то значение переменной X, которое она получает при выполнении одной из серий команд.

Циклическим называется алгоритм, в котором некоторая последовательность операций (тело цикла) выполняется многократно. Однако «многократно» не означает «до бесконечности». Организа­ция циклов, никогда не приводящая к остановке в выполнении ал­горитма, является нарушением требования его результативности — получения результата за конечное число шагов.

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

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

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

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

---

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

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

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

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

1. Следование (линейный алгоритм) – последовательное выполнение команд (сверху вниз).

Алг программа	Название алгоритма
нач	Начало алгоритма
Вещ SR Цел A,B,C,N	Объявление переменных (цел –целых, вещ –вещественных)
A = 1	Расчетная часть (операции выполняются поочерёдно сверху вниз)
B = 2
C = 3
N = 3
SR = (A+B+C)/N
кон	Конец алгоритма

Алг программа	Название алгоритма
нач	Начало алгоритма
Цел A, B, C	Объявление переменных
A = 1	Линейная часть алгоритма
B = 2
Если A < B	Условие ветвления
То C = A	Команда (или команды), выполняемая, если условие ложно
Иначе C = B	Конец алгоритма
Кон	Конец алгоритма

2. Ветвление – команды выполняются в зависимости от истинности некоторого условия либо возможно выполнение одного из двух или более наборов команд в зависимости от истинного условия.

да

условие

нет

Блок 1

Блок 1

Блок команд

да

Условие

да

Условие

Блок команд

Блок команд

да

Условие

3. Цикл – повторение блока команд.

Цикл с предусловием (Цикл ПОКА)

---

Блок команд выполняется, пока условие остается истинным (выход из цикла – по ложности условия).

Условие

нет

да

Блок команд

Алг программа	Название алгоритма
Нач	Начало алгоритма
Цел A,B	Объявление переменных
A = 0	Линейная часть алгоритма
Ввод (B)
Нц пока B < > 0	Условие выполнение цикла
A = A+B Ввод (B)	Команды, выполняемые, пока условие истинно
Кц	Конец блока команд, составляющих цикл
Вывод (A)	Команда, которая выполняется после завершения цикла (когда условие цикла станет ложным)
кон	Конец алгоритма

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

Цикл с постусловием (цикл ДО)

Блок команд выполняется до тех пор, пока условие не станет истинным (цикл выполняется, пока условие не выполнится)

Блок команд

нет

Условие

да

Условие проверяется после выполнения цикла, поэтому тело цикла, поэтому тело цикла выполняется хотя бы один раз.

Алг программа	Название алгоритма
Нач	Начало алгоритма
Цел A, B	Объявление переменных
A = 0	Линейная часть алгоритма
Нц	Начало блока команд, составляющих цикл
Ввод (B) A = A+B	Команды, выполняемые, пока условие цикла ложно
Кц до B = 0	Конец блока команд, составляющих цикл
Вывод (А)	Команда, которая выполняется после завершения цикла(когда условие цикла станет истинным)
Кон	Конец алгоритма

Цикл с параметром (цикл со счётчиком, цикл ДЛЯ)

Блок команд выполняется количество раз, заданное начальным, конечным значениями переменной-счётчика и шагом её изменения.

I от Iн до Ik

с шагом i

Блок команд

Алг программа	Название алгоритма
Нач	Начало алгоритма
Цел A, i	Объявление переменных
A = 0	Линейная часть алгоритма
Нц для I от 1 до 10 шаг 2	Начало цикла, задание его параметров
A = A+ I	Команды, выполняемые в цикле
Кц	Конец цикла
Вывод(А)	Команда, которая выполняется после завершения цикла
Кон	Конец алгоритма

---