Формы и способы представления и записи алгоритмов
Формы и способы представления и
записи алгоритмов
ВВЕДЕНИЕ
алгоритм программа массив уравнение
Сегодня большинство людей считает, что алгоритмы используются только
математиками и программистами, однако это совсем не так. Каждый из нас, начиная
от агронома и заканчивая топ-менеджером, ежедневно сталкивается с алгоритмами.
Данный факт обусловлен тем, что весь мир в настоящее время переживает эпоху
глобальной информатизации. Современная цивилизация представляет собой
цивилизацию алгоритмов, которые тесно связаны с любой человеческой
деятельностью [14, с.6].
Процесс решения большинства задач современного человека предполагает
выполнение ряда подзадач, отвечающих определенным правилам. Подобные правила
могут быть сформулированы для человека заранее, или же получены им
непосредственно в процессе решения задачи. Эффективность правил зависит от их
уровня детализации - чем яснее сформулированы правила, тем быстрее человек
сможет ими овладеть и грамотно применить для решения проблемы.
Сегодня большинство задач человек перекладывает на вычислительную
технику. При этом компьютеру или какому-либо другому вычислительному устройству
передается специальное предписание - последовательность действий, в результате
которой должен быть получен необходимый человеку результат. Данное предписание
называется программой. Оно должно очень точно отражать последовательность
действий, выполняемых машиной. Для того чтобы человек мог объяснить машине
последовательность действий, необходимых для решения той или иной задачи, были
разработаны специальные языки описания.
Так сформировалась наука алгоритмизация - это особый раздел информатики,
который изучает приемы и методы построения алгоритмов, а также их свойства [3,
с.3].
Актуальность данной работы очевидна - в современном мире любой человек
ежедневно сталкивается с алгоритмами, сам того не замечая. Кроме того, основным
направлением науки и техники сегодня является автоматизация, позволяющая
перекладывать большинство рутинных задач на выполнение компьютеру. Для того
чтобы задача была решена за оптимальный промежуток времени и не содержала
ошибок, необходимо заложить в нее оптимальный алгоритм выполнения этой задачи.
Объектом исследования в данной работе является алгоритм.
Предмет исследования - формы и способы представления алгоритмов, способы
записи алгоритмов.
Цель работы - раскрыть тему, описать различные способы представления
алгоритмов, привести примеры наиболее известных и распространенных алгоритмов.
Для достижения поставленной цели предстоит решить ряд задач:
- проанализировать литературу по заданной теме;
- дать понятие алгоритма;
- определить свойства алгоритма;
- изучить формы представления алгоритмов;
- изучить способы записи алгоритмов;
- привести примеры известных алгоритмов.
В качестве опорных источников при выполнении данной работы были
использованы следующие материалы, которые наиболее полно раскрывают данную тему
и содержат яркие примеры: М.П. Белов - «Основы алгоритмизации в информационных
системах» и Т.А. Волосатова - «Информатика. Программирование на VBA. Учебное пособие для лабораторного
практикума и подготовки к тестированию».
1. АЛГОРИТМ
1.1 Понятие и свойства
В настоящее время для решения рутинных вычислительных задач все чаще
применяются компьютеры. Кроме того, современные компьютеры способны решать не только
математические задачи на вычисление каких-либо величин, но и даже управлять
каким-либо оборудованием, например, станками или ракетами. Сюда же стоит
отнести задачи планирования и прогнозирования, а также задачи справочного
обслуживания пользователей.
Для решения задачи при помощи компьютера, ему необходимо объяснить - как
именно эту задачу нужно выполнять для достижения желаемого результата. Другими
словами - необходимо придумать правильный порядок действий, понятный
компьютеру, т.е. алгоритм.
Под алгоритмом принято понимать четкую конечную систему правил,
определяющую последовательность действий, которая за конечное число шагов
способна привести к достижению поставленной цели [11, с.10].
Сам термин «алгоритм» пошел от имени мыслителя Мухаммеда аль Хорезми,
проживающего в средние века. Именно он является родоначальником алгебры -
науки, в которой были сформулированы правила математических вычислений в
позиционных системах счисления. В Европе эти правила получили название
алгоритмов (от латинского написания имени аль Хорезми - «algoritmi»).
Исполнителем алгоритма является тот объект, для управления действиями
которого этот алгоритм составлен. Чтобы исполнитель мог выполнить тот или иной
алгоритм, он должен четко понимать все шаги алгоритма. Набор команд исполнителя,
которые он способен понимать и выполнять, принято называть системой команд
исполнителя [13, с.5].
Разработка алгоритма предполагает разбиение одной большой задачи на
несколько мелких, более простых.
Из определения алгоритма формируются его свойства:
- результативность - в результате выполнения алгоритма должен
быть получен успешный результат решения поставленной задачи, либо информация о
том, что данный алгоритм не подходит для решения этой задачи;
- дискретность - алгоритм должен представлять собой конечную
последовательность шагов, при этом выполнение очередного шага начинается только
после завершения предыдущего;
- детерминированность - любой шаг алгоритма должен однозначно
определяться исполнителем алгоритма, другими словами, шаги алгоритма не должен
быть двусмысленными;
- конечность - любой шаг алгоритма, а также сам алгоритм должны
иметь возможность завершения;
- корректность - решение, полученное в соответствии с
применяемым алгоритмом, должно быть правильным, относительно конкретной задачи;
- массовость - алгоритм должен разрабатываться для решения
целого класса задач, которые отличаются только исходными данными;
- эффективность - время выполнения алгоритма должно быть
сравнительно небольшим, при этом должен выбираться наиболее простой и короткий
способ решения задачи [7, с.11-12].
.2 Виды
Как говорилось ранее, алгоритм представляет собой четкую
последовательность действий, приводящую к решению поставленной задачи.
В зависимости от цели и начальных условий существует несколько видов
алгоритмов (см. рисунок 1):
Рисунок 1 - Виды алгоритмов
- механические (детерминированные) алгоритмы - алгоритмы,
задающие выполняемые действия в единой достоверной последовательности;
- гибкие (эвристические) алгоритмы - алгоритмы, дающие решение
задачи несколькими способами. Пользуясь такими алгоритмами, достижение
конечного результата однозначно не определено. Примерами эвристических
алгоритмов являются предписания и инструкции.
В основе всех алгоритмов лежат универсальные способы принятия решений и
логические функции, которые строятся по опыту решения предыдущих задач
аналогичного типа [2, с.7-8].
Любой алгоритм разбивается на определенные шаги - алгоритмические
конструкции. Наиболее распространенными являются следующие конструкции:
- следование - определяет линейные алгоритмы, определяющие
последовательное выполнение шагов, независимо от исходных данных и
промежуточных вычислений;
- ветвление - определяет алгоритмы ветвления, предполагающие
выполнение того или иного действия в зависимости от какого-либо условия.
Принято выделять полное и неполное ветвление. В первом случае алгоритм
предусматривает все возможные варианты условия. На естественном языке это можно
записать следующим образом: если условие выполняется, то необходимо запустить
процесс 1, иначе - запустить процесс 2. Вариант неполного ветвления: если
условие выполняется, то необходимо запустить вычислительный процесс. Кроме
того, существуют алгоритмы, содержащие более двух ветвей в блоке ветвления;
- цикл - определяет циклические алгоритмы - это такие
алгоритмы, в которых одни и те же операторы выполняются многократно. Выполнение
цикла состоит из нескольких этапов:
o подготовка - на данном этапе происходит установка начального
значения параметра цикла;
o тело цикла - непосредственное выполнение каких-либо действий;
o подготовка к следующему циклу - предполагает изменение
значения параметра цикла;
o проверка условия - признак выхода из цикла.
Операторы цикла бывают нескольких видов:
o цикл с предусловием - проверка условия выполняется сразу же
после установки значения параметра цикла;
o цикл с постусловием - проверка условия выполняется после
прохода тела цикла. Такие циклы всегда отрабатывают как минимум один раз;
o цикл с параметром - цикл, в котором изначально задается число
необходимых итераций [17, с. 7-9].
.3 Характеристики
Как правило, для решения одной и той же задачи могут применяться
различные алгоритмы. Это говорит о том, что алгоритмы могут быть сравнимы между
собой. Для сравнения алгоритмов существуют специальные критерии качества
алгоритмов (см. рисунок 2).
Самая важная характеристика алгоритма - временная, отвечающая за
продолжительность выполнения алгоритма. Другое название данной характеристики -
временная сложность, которая выражается в единицах времени. Однако, в
большинстве случаев, данную характеристику выражают через число операций. Это
вызвано тем, что количество операций не зависит от быстродействия компьютера,
выполняющего алгоритм.
Рисунок 2 - Характеристики алгоритмов
Временная сложность алгоритма отражает максимальный размер задачи,
которая может быть решена при помощи конкретного алгоритма на компьютере. Любой
компьютер при этом характеризуется функцией f(n), показывающей
зависимость скорости роста объема вычислений от размерности задачи,
обозначенной через n. В том случае,
когда данная зависимость носит линейный или полиномиальный характер, алгоритм
считается эффективным.
Очень важное значение эта характеристика имеет при решении сложных задач,
потому что ее изменение сильно влияет на время, затрачиваемое на выполнение
алгоритма. Так, например, при зависимости (1)
f(n) = 2n (1)
увеличение производительности в 10 раз приводит к увеличению размерности
задачи, решаемой за то же самое время, всего на 15%.
Другой тип характеристик алгоритма - объемные характеристики. Данные
характеристики отвечают за информационную сложность. Эта сложность может быть
связана с несколькими процессами:
- описание данных;
- накопление данных;
- хранение данных.
В большинстве случаев объем алгоритма определяется числом операторов,
которые используются при его записи.
Объемная характеристика алгоритма влияет на количество внутренней и
внешней памяти, необходимой для правильного выполнения. В случае недостатка
памяти принято пользоваться сегментацией программ.
Отдельно стоит выделить сложность структуры алгоритма - это
характеристика, определяемая числом возможных путей, по которым может быть
реализован алгоритм, с учетом сложности каждого отдельно взятого пути [3,
с.9-10].
1.4 Роль алгоритма в построении программы
Наиболее эффективное применение алгоритмы нашли в области
программирования. Сегодня с их помощью создаются как простые, так и очень
сложные программы, при помощи которых выполняются громоздкие вычисления, а
также процессы управления различными устройствами. Для того чтобы определить
место алгоритма в написании программы, необходимо полностью рассмотреть этапы
решения задачи на компьютере (см. рисунок 3):
- постановка задачи - первый этап, на котором человек
однозначно формулирует цель задачи, дает ей четкое словесное описание, а также
предлагает некоторый общий подход для решения;
- математическая формализация - на данном этапе формируется
математическая модель задачи, которая может быть передана компьютеру. Здесь
важно четко определить все необходимые параметры, проанализировать их сущность
и характер. Важно, чтобы модель адекватно отражала поставленную задачу и не
была перегружена параметрами. На этом же этапе создается математическое
описание модели при помощи формул, отражающих существующие взаимосвязи между
параметрами. После получения модели предлагаются различные варианты решения
задачи, оценивается их эффективность и сложность;
Рисунок 3 - Этапы решения задачи на компьютере
- построение алгоритма - в зависимости от выбранного варианта
решения задачи, составляется алгоритм, четко описывающий процесс решения;
- составление программы на языке программирования - на данном
этапе готовый алгоритм преобразуется в код программы. При этом можно выделить
несколько стадий выполнения:
o выбор языка программирования;
o уточнение способов организации данных;
o запись алгоритма на выбранном языке программирования;
- тестирование и отладка программы - цель данного этапа -
проверить логическую и синтаксическую правильность полученной программы, а
также определить ее выполнение на всей области входных данных. Данный этап
также разбивается на ряд более мелких:
o трансляция исходного текста программы;
o компоновка;
o выполнение программы с целью выявления логических ошибок;
o тестирование на контрольных примерах (контрольные примеры
предполагают выполнение всех возможных путей алгоритма);
- проведение расчетов - данный этап заключается в исполнении
программы и последующих расчетов для различных входных параметров;
- анализ данных - на этом этапе человек, сформулировавший
задачу, анализирует данные, полученные при ее решении программным путем. На
основе этого анализа формируются решения и рекомендации по дальнейшим
действиям. В некоторых случаях анализ полученных данных может привести к
пересмотру подхода к постановке и решению задачи;
- сопровождение программы - данный этап является
оптимизационным и заключается в поддержке программы после сдачи в эксплуатацию.
Здесь происходит устранение неисправностей, выявленных в процессе использования
программы, добавление каких-либо новых функциональных возможностей, а также
повышение удобства использования в соответствии с пожеланиями пользователей [7,
с. 4-6].
.5 Краткие выводы
В рамках данной главы рассмотрено понятие алгоритма, а именно:
- определение термину «алгоритм» как четкой конечной системы
правил, определяющей последовательность действий, которая за конечное число
шагов способна привести к достижению поставленной цели;
- описание основных свойств алгоритма;
- виды алгоритмов (детерминированные и эвристические);
- характеристики, отражающие эффективность применения
алгоритмов;
- роль алгоритма при написании программы.
2. ПРЕДСТАВЛЕНИЕ И ЗАПИСЬ АЛГОРИТМОВ
2.1 Словесный способ
Словесный способ записи алгоритма отражает собой последовательность
действий, необходимых для решения задачи, записанных на естественном языке в
произвольном изложении.
Для примера рассмотрим словесную форму алгоритма нахождения наибольшего
общего делителя двух натуральных чисел А и В:
- проверить числа на равенство. Если они равны, в качестве
ответа можно взять любое из этих чисел, если нет, то продолжить выполнение
алгоритма;
- определить, какое число больше - А или В;
- заменить число с предыдущего шага модулем разности чисел А и
В;
- повторить действия.
В основе словесного способа записи алгоритмов лежат общепринятые средства
общения между людьми. Запись такого алгоритма достаточно проста и понятна. Свое
применение словесный способ находит на начальных этапах решения задачи.
Недостатки словесного метода:
- полное описание сложных алгоритмов является достаточно
объемным;
- запись на естественном языке может являться причиной
двусмысленности некоторых шагов алгоритма;
- при переходе к этапу программирования необходимо проводить
дополнительную работу, которая заключается в формализации алгоритма [3,
с.10-11].
2.2 Графический способ
Графический способ записи алгоритма отражает выполнение
последовательности шагов в виде некоторого изображения. Подобную запись можно
встретить на инструкциях по сборке чего-либо, на упаковках с едой и т.п. (см.
рисунок 4) [13. с. 7].
Рисунок 4 - Графическая форма записи алгоритма
Частным (и наиболее популярным) графическим способом является блок-схема,
где алгоритм изображается в виде функциональных блоков, логически связанных
между собой. При этом каждому отдельному действию соответствует своя
геометрическая фигура. Определение этих фигур можно найти в ГОСТ 19.701-90 (ИСО
5807-85) «Единая система программной документации». Наиболее распространенные
символы приведены на рисунке 5 [2, с.
11]:
- «Начало алгоритма» и «Конец алгоритма» - применяются для
обозначения начала, конца, а также прерывания процесса обработки данных или же
исполнения программы;
Рисунок 5 - Операторы блок-схем
- «Ввод (вывод) данных» - применяется с целью преобразования
данных в форму, которая пригодна для отображения или обработки результатов.
Различным устройствам ввода/вывода компьютера соответствует различная
геометрическая форма данного блока, при этом принято отображать тип
используемого устройства или файла с данными, а также тип используемой
информации и вид операции обмена;
- «Операция» - данный блок используется для обозначения
некоторой последовательности действий, основной задачей которых является
изменение значения, размещения или формы представления данных. В большинстве
случаев несколько таких одинаковых блоков, идущих друг за другом, принято
объединять в один;
- «Разветвление» - применяется с целью обозначения условных
переходов. Внутри такого блока обязательно должно указываться условие, в
зависимости от значения которого осуществляется переход по той или иной ветке.
Кроме того, стрелки, которые выходят из данного блока, обязательно должны иметь
метки с возможными вариантами ответа, например, «да» и «нет», учитывая при этом
все возможные исходы;
- «Цикл» - применяется для выполнения операций, повторяющихся
многократно. Внутри такого блока обязательно необходимо отражать параметр цикла
- условие, по которому определяется выход из блока. Линии переходов в рамках
данного блока отражают порядок действий. По стандарту их следует располагать
сверху вниз и слева направо;
- «Ссылка» - данный оператор применяется в том случае, когда
невозможно напрямую отразить переход к блоку, следующему в алгоритме, например,
при разрыве страницы. Используя данный блок, важно давать ему метку, являющуюся
ссылкой на следующий для исполнения блок;
- «Соединитель» - применяется в тех случаях, когда схема
алгоритма представляет собой отдельные автономные части, либо в случаях, когда
разработчик алгоритма старается избежать излишних пересечений в линиях перехода
между блоками. Важно, чтобы блоки соединителей не нарушали структурность при
отображении схем;
- «Комментарий» - отражает пояснения разработчика к блокам
схемы. Не рекомендуется часто использовать комментарии, т.к. они сильно
загромождают схему и делают ее менее наглядной [3, с. 11-14].
В промышленных системах применяются особые виды графических схем:
- диаграммы - описывают какие-либо зависимости входных и
выходных переменных, отражают пошаговый процесс выполнения процесса и т.п.;
- схемы блокировки - служат для изображения взаимосвязанности
процессов включения/выключения (см. рисунок 6);
Рисунок 6 - Схема блокировки
структурные схемы - отражают структуру и описывают функционирование
непрерывных систем (см. рисунок 7);
Рисунок 7 - Структурная схема
- графы автоматов - описывают дискретные состояния системы, а
также возможные переходы между ними вместе с изменяющимися параметрами и
условиями переходов между состояниями (см. рисунок 8);
Рисунок 8 - Граф автомата
- сети Петри - представляют собой аппарат для моделирования
дискретных динамических систем. При помощи сетей Петри можно определить какие
именно действия происходят в системе, какие состояния может принимать система
после этих действий и т.п. [5, с.123].
Пример сети Петри приведен на рисунке 9;
Рисунок 9 - Сеть Петри
схемы работы - схемы, описывающие процессы, которые протекают линейно и
соответствуют системам управления (см. рисунок 10) [3, с.16-18].
Рисунок 10 - Схема работы
2.3 Табличный способ
В табличной форме записи все шаги алгоритмов заносятся в таблицу, которая
отражает изменение значений входных данных, а также промежуточных значений и
результата.
В качестве примера рассмотрим табличную форму записи алгоритма нахождения
площади прямоугольника. При этом входными данными являются длины сторон, а
результатом - величина площади (см. таблицу 1) [13, с.7].
Таблица 1 - Пример табличной записи алгоритма
|
№ шага
|
Входные данные
|
Результат
|
Примечания
|
b
|
S
|
|
|
1
|
5
|
7
|
|
Ввод данных
|
|
2
|
|
|
35
|
Вычисление площади
|
|
3
|
|
|
|
Вывод результата S = 35
|
2.4 Псевдокод
Псевдокодом принято называть систему правил и обозначений, целью которых
является создание единообразной записи алгоритмов. Фактически, псевдокод
находится между формальным и естественным языком. В алгоритмах-псевдокодах нет
строгих синтаксических правил, что облегчает их запись, а также дает
возможность применять широкий набор команд. Для записи алгоритмов псевдокоды
используют служебные слова. Ярким примером псевдокода является алгоритмический
язык (АЯ), построенный на базе алфавита, содержащего ряд символов, допустимых
при записи алгоритма. Кроме символов АЯ содержит служебные слова,
использующиеся для формирования типовых конструкций и способные делать алгоритм
понятным. Перечень данных конструкций приведен в таблице 2.
Таблица 2 - Ключевые слова алгоритмического языка АЯ
|
Основные
|
Дополнительные
|
|
алг (алгоритм) рез
(результат) нач (начало) кон (конец) арг (аргумент) знач (значение) тип: вещ
(вещественный) цел (целый) лит (литерный) таб (таблица) сим (символьный) не
то если и все или выбор иначе нц (начало цикла) кц (конец цикла) от до шаг
для пока при да нет := (оператор присваивания)
|
запись истина лог
(логический) ложь массив множество функция дано надо ввод вывод утв
(утверждение)
|
Типовой алгоритм, записанный в псевдокоде, выглядит следующим образом [3,
с.18-20]:
алг
название алгоритма
дано условия
надо цель
начописание
промежуточных величин
тело алгоритма
кон
.5 Краткие выводы
В данной главе были описаны основные существующие формы записи
алгоритмов, а именно:
- словесный;
- графический;
- табличный;
- псевдокод.
3. ПРИМЕРЫ ИЗВЕСТНЫХ АЛГОРИТМОВ
3.1 Операции над массивами
.1.1 Нахождение суммы элементов
Очень часто при решении практических задач необходимо посчитать общую
сумму какого-либо массива, например, значение «Итого» в кассовом чеке. Для
этого необходимо воспользоваться алгоритмом, представленным на рисунке 11.
Рисунок 11 - Блок-схема алгоритма нахождения суммы элементов
массива
3.1.2 Поиск максимального элемента массива
Другой распространенной задачей является поиск максимума в массиве,
например, рассматривая тот же кассовый чек - узнать самую дорогую покупку.
Алгоритм нахождения максимума в массиве элементов приведен на рисунке 12
[20, с.10-12].
Рисунок 12 - Блок-схема поиска максимального элемента массива
3.1.3 Сортировка массивов
Сортировкой называется процесс перегруппировки элементов заданного
множества в некотором определенном порядке [4, с. 4].
Рассмотрим наиболее популярные методы сортировки:
.1.3.1 Метод пузырька
Алгоритм пузырьковой сортировки предполагает сравнение соседних элементов.
В том случае, если их последовательность неверная, они меняются местами.
Сортировка осуществляется путем многократного прохождения по имеющемуся массиву
элементов. Свое имя сортировка получила из-за сравнения с пузырьком воздуха в
воде - в процессе сортировки по возрастанию элементы с наименьшими значениями
поднимаются вверх в начало списка, аналогично пузырьку [19, с.107].
Блок-схема алгоритма сортировки массива методом пузырька приведена на
рисунке 13.
Рисунок 13 - Сортировка массива методом пузырька
Главным недостатком данного алгоритма является его производительность,
т.к. в том случае, когда массив еще не просмотрен до конца, но уже
отсортирован, алгоритм будет работать «в холостую», затрачивая время [18, с.
6].
.1.3.2 Сортировка выбором
Данный метод предполагает выбор максимального или минимального элемента
массива (в зависимости от вида сортировки - по возрастанию или по убыванию).
Для начала в массивы отыскивается самый большой элемент, затем он
меняется местами с последним элементом. Далее эти действия повторяются, каждый
раз уменьшая рассматриваемую длину массива на 1 до тех пор, пока число
рассматриваемых элементов не будет равно 1.
Блок-схема данного алгоритма приведена на рисунке 14 [1, с.204-206].
Рисунок 14 - Сортировка выбором
3.2 Уточнение корней уравнения
Как известно, для большинства трансцендентных и алгебраических уравнений
не всегда можно получить аналитическое решение. Для этого применяются
приближенные итерационные методы, в которых решение уравнения ищется при помощи
уточнений.
Рассмотрим пример нахождения наименьшего положительного корня уравнения x-tgx=0 с точностью 0.00001. Блок-схема решения данной задачи
приведена на рисунке 15 - изначально задается грубое значение корня, затем
вычисляется новое, и выполняется проверка достижения точности. В том случае,
если точность не достигнута, происходит итерация цикла, иначе - выход [15, с.
27-28].
Рисунок 15 - Нахождение приближенного значения уравнения
Наиболее простым методом уточнения корней является метод дихотомии -
деления отрезка пополам. Общая схема данного алгоритма описывается ниже:
- находится отрезок [a, b], на котором функция принимает
нулевое значение;
- в качестве начального приближения x0 выбирается середина отрезка [a; b];
- вычисляется значение функции в точках a, b, и x0;
- отрезок сужается таким образом, чтобы на его концах функция
принимала разные по знаку значения;
- операции повторяются до тех пор, пока не будет достигнута
заданная точность.
Геометрическая интерпретация данного метода приведена на рисунке 16 [10,
с.11]
Рисунок 16 - Геометрическая интерпретация метода половинного
деления
Блок-схема данного алгоритма приведена на рисунке 17 [9, с.10-12].
Рисунок 17 - Блок-схема метода половинного деления
Другим часто используемым методом является метод хорд. В данном методе
также выбирается отрезок [a, b], на концах которого функция
принимает разные по знаку значения. Кроме того, предполагается, что на малых
участках функция изменяется линейно, а значит, может быть заменена хордой. За
начальное приближение берется точка пересечения первой хорды с осью ox. Каждая итерация предполагает
построение новой хорды (см. рисунок 18).
Рисунок 18 - Геометрическая интерпретация метода хорд
Блок-схема алгоритма приведена на рисунке 19.
Важно отметить, что метод хорд похож на метод дихотомии, однако, метод
хорд обладает большей сходимостью итерационного процесса [12, с.13-15].
Рисунок 19 - Блок-схема алгоритма метода хорд
3.3 Краткие выводы
В данной главе были приведены примеры следующих алгоритмов:
- алгоритмы работы с массивами:
- алгоритмы численных методов уточнения корней уравнений.
ЗАКЛЮЧЕНИЕ
В рамках выполнения данной работы было раскрыто понятие алгоритма. Под
алгоритмом принято понимать конечную последовательность общепонятных
предложений, точное исполнение которых приводит к решению задачи некоторого класса
за конечное число шагов [6, с.32].
В первой главе описываются основные свойства алгоритма, а именно:
- результативность - алгоритм должен приводить к решению
задачи;
- дискретность - алгоритм должен содержать конечное число
шагов;
- детерминированность - каждая итерация алгоритма должна
однозначно определяться исполнителем;
- конечность - каждая итерация алгоритма должна иметь
завершение;
- корректность - полученное решение должно быть правильным;
- массовость - алгоритм должен быть универсальным для конкретного
класса задач;
- эффективность - выполнение алгоритма не должно занимать много
времени [16, с.33].
Кроме того, описаны такие виды алгоритмов как:
- линейные - отражающие последовательно выполняющиеся операции;
- разветвленные - алгоритмы, проверяющие какое-либо заданное
условие;
- циклические - алгоритмы, операторы в которых повторяются
некоторое число раз.
Вторая глава посвящена способам записи алгоритмов. Рассмотрены следующие
способы:
- словесный - запись алгоритма на естественном языке;
- графический - при помощи рисунков или блок-схем;
- табличный - в виде таблицы;
- псевдокод - с использованием алгоритмических конструкций,
содержащих в себе элементы естественного языка [8, с.7].
В третьей главе приведены примеры известных алгоритмов:
- алгоритмы работы с массивами:
o нахождение суммы элементов;
o нахождение максимального элемента;
o пузырьковая сортировка;
o сортировка выбором;
- алгоритмы численных методов уточнения корней уравнений:
o метод половинного деления;
o метод хорд.
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
1. Алексеев Е.Р. Free Pascal и Lazarus:
Учебник по программированию / Е.Р. Алексеев, О.В. Чеснокова, Т.В. Кучер - М.: ALT Linux; Издательский дом ДМК-Пресс, 2010. - 440 с.
. Аузяк А.Г. Программирование и основы алгоритмизации:
Для инженерных специальностей технических университетов и вузов. / А.Г. Аузяк,
Ю.А. Богомолов, А.И. Маликов, Б.А. Старостин. Казань: Изд-во Казанского
национального исследовательского технического ун-та - КАИ, 2013. - 153 с.
. Белов М.П. Основы алгоритмизации в информационных
системах: Учеб. пособие. - СПб.: СЗТУ, 2003. - 85 с.
. Беннер В.М. Методы сортировок / В.М. Беннер, Г.Т.
Варкентина. - Барнаул: Изд-во БГПУ, 2001. - 25 с.
. Бобков С.П. Моделирование систем: учеб. пособие /
С.П. Бобков, Д.О. Бытев; Иван. гос. хим.-технол. ун-т. - Иваново, 2008. - 156
с.
. Былкин В.Д. Алгоритмизация и программирование:
учебное пособие. - Пенза: Изд-во Пенз. гос. технол. акад. - 249 с.
. Волосатова Т.А. Информатика. Программирование на VBA. Учебное пособие для лабораторного
практикума и подготовки к тестированию: учебное пособие. - Ростов н/Д: Рост.
гос. строит. ун-т, 2013. - 132 с.
. Давыдова Н.А. Программирование: учебное пособие /
Н.А. Давыдова, Е.В. Боровская. - М.: БИНОМ. Лаборатория знаний, 2015. - 21 с.
. Кузьменко Е.А. Информатика. Численные методы решения
прикладных задач. Лабораторный практикум: учебное пособие / Е.А. Кузьменко,
Н.И. Кривцова, О.Е. Мойзес; Национальный исследовательский Томский
политехнический университет. - Томск: Изд-во Томского политехнического университета,
2012. - 144 с.
. Левицкий А.А. Информатика. Основы численных методов:
Лабораторный практикум; Красноярск: ИПЦ КГТУ, 2005. - 111 с.
. Мансуров К.Т. Основы программирования в среде Lazarus, 2010. - 772 с.
. Мокрова Н.В. Основы численных методов: Учебное
пособие / Н.В. Мокрова, Л.Е. Суркова; Моск. гос. ун-т инж. экологии, ф-т АИТ,
кафедра «Прикладная математика и информатика» - М.: МГУИЭ, 2006. - 90 с.
. Немчанинова Ю.П. Алгоритмизация и основы
программирования на базе KTurtle
(ПО для обучения программированию Kturtle): Учебное пособие. - Москв-: 2008. - 50 с.
. Паронджанов В.Д. Учись писать, читать и понимать
алгоритмы. Алгоритмы для правильного мышления. Основы алгоритмизации. - М.: ДМК
Пресс, 2012. - 520 с.
. Петрова М.В. Алгоритмизация и программирование
задач: Методические указания. - Ульяновск: УлГТУ, 2003. - 32 с.
. Толстяков Р.Р. Информатика: учебное пособие / Р.Р.
Толстяков, Т.Ю. Забавникова, Т.В. Попова. - Тамбов: Изд-во ФГБОУ ВПО «ТГТУ»,
2011. - 112 с.
. Топольский Д.В. Прикладное программирование: учебное
пособие. / Д.В. Топольский, И.Г. Топольская. - Челябинск: Издательский центр
ЮУрГУ, 2013. - 25 с.
. Учебно-методические указания к лабораторной работе
№7 по курсу Информатика. Разработка программы сортировки элементов массива.
Томск, 2011. - 15 с.
. Шестакович В.П. Учебно-методический комплекс по
дисциплине «Основы алгоритмизации и программирования». Минск, 2007. - 181 с.
20. Щапова И.Н. Программные средства реализации
алгоритмов. Алгоритмизация и программирование задач по обработке массивов: метод.
указания к выполнению лаб. работ по дисциплине «Информатика» - Пермь: Изд-во
Перм. нац. исслед. политехн. ун-та, 2015. - 35 с.