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

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

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

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

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

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

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

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

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

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

В течение всего периода преподавания информатики в школе актуальность темы «Алгоритмизация и программирование» претерпела значительные изменения.

В силу некоторых обстоятельств: наличия теоретической базы предмета и технического обеспечение кабинета информатики, значимость преподавания темы в период с 2005 года по 2010 год значительно снизилась. Точнее надо сказать, уменьшилось количество уроков, отводимых на изучение этой темы в старших классах.

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

Объект данной курсовой работы – это алгоритмическая содержательная линия информатики.

Предмет – это особенности алгоритма непосредственно в базовом курсе информатики.

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

Для решения поставленной цели решается ряд задач:

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

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

Работа состоит из введения, заключения, 4 глав и списка использованных источников.

1 ПОНЯТИЕ АЛГОРИТМА И ЕГО СВОЙСТВА

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

Слово «алгоритм» появилось в средние века, когда европейцы познакомились со способами выполнения арифметических действий в десятичной системе счисления, описанными узбекским математиком Муххамедом бен Аль-Хорезми («аль-Хорезми» - человек из города Хорезми; в настоящее время город Хива в Хорезмской области Узбекистана) [12]. Слово алгоритм – есть результат европейского произношения слов аль-Хорезми. Первоначально под алгоритмом понимали способ выполнения арифметических действий над десятичными числами. В дальнейшем это понятие стали использовать для обозначения любой последовательности действий, приводящей к решению поставленной задачи [7].

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

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

Таким образом, алгоритм характеризуется следующими свойствами: дискретность, масса, определенность, эффективность, формальность.

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

2 СПОСОБЫ ОПИСАНИЯ АЛГОРИТМОВ

Существуют следующие способы описания алгоритма: словесное описание, псевдокод, блок-схема, программа.

Вербальное описание представляет собой структуру алгоритма на естественном языке. Например, любой прибор (утюг, электропила и др.) имеет инструкцию по эксплуатации, т. е. словесное описание алгоритма, согласно которому данное устройство должно использоваться [6].

Нет никаких правил для составления словесного описания. Алгоритм написан в любой форме на естественном, например, русском языке. Данный метод описания не находит широкого применения, так как не является строго формализованным (формальным - означает, что описание является абсолютно полным и учитывает все возможные ситуации, которые могут возникнуть в процессе принятия решения); допускает неоднозначность толкования при описании некоторых действий; страдает многословием [13].

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

Для написания псевдокода не существует строгих синтаксических правил. Это упрощает написание алгоритма при проектировании и позволяет описать алгоритм с помощью любого набора команд. Однако псевдокод обычно использует некоторые конструкции, присущие формальным языкам, что облегчает переход от псевдокода к написанию алгоритма на языке программирования. Не существует единого или формального определения псевдокода, поэтому возможны различные псевдокоды, отличающиеся набором используемых слов и конструкций [6].

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

Рассмотрим некоторые из основных конструкций, используемых для построения блок-схем (рисунок 1-10).

Рисунок 1. Блок, характеризующий начало/конец алгоритма (для подпрограмм - вызов/возврат)

Рисунок 2. Блок - процесс, предназначенный для описания

отдельных действий

Рисунок 3. Блок - предопределенный процесс, предназначенный для обращения к вспомогательным алгоритмам (подпрограммам)

Рисунок 4. Блок - ввода/вывода с неопределенного носителя

Рисунок 5. Блок - ввод с клавиатуры

Рисунок 6. Блок - вывод на монитор

Рисунок 7. Блок - вывод на печатающее устройство

Рисунок 8. Блок - решение (проверка условия или условный блок)

Рисунок 9. Блок, описывающий цикл с параметром

Рисунок 10. Блок - границы цикла, описывающий циклические

процессы типа: «цикл с предусловием», «цикл

с постусловием»

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

3 ОСНОВНЫЕ АЛГОРИТМИЧЕСКИЕ КОНСТРУКЦИИ

Элементарные шаги алгоритма могут быть объединены в следующие алгоритмические конструкции: линейную (последовательную), ветвящуюся и циклическую.

Линейным называют вычислительный процесс, в котором операции выполняются последовательно, в порядке их записи. Каждая операция независима, не зависит от каких-либо условий [11].

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

На рисунке 11 показан пример линейного алгоритма, определяющего процесс вычисления арифметического выражения y=(b²-A*C) / (a+C).

Разветвляющейся (или ветвящейся) называется алгоритмическая конструкция, обеспечивающая выбор между двумя альтернативами в зависимости от значения входных данных. При каждом конкретном наборе входных данных разветвляющийся алгоритм сводится к линейному. Различают неполное (если - то) и полное (если - то - иначе) ветвления [8]. Полное ветвление позволяет организовать две ветви в алгоритме (то или иначе), каждая из которых ведет к общей точке их слияния, так что выполнение алгоритма продолжается независимо от того, какой путь был выбран (рисунок 12).

Рисунок 11. Линейный алгоритм

Ложь (Нет) Истина (Да)

Рисунок 12. Полное ветвление

Неполное ветвление предполагает наличие некоторых действий алгоритма только на одной ветви (то), вторая ветвь отсутствует, т.е. для одного из результатов проверки никаких действий выполнять не надо, управление сразу переходит к точке слияния (рисунок 13).

Истина (Да) Ложь (Нет)

Рисунок 13. Неполное ветвление

В зависимости от типа и числа проверяемых условий различают:

- ветвление с простым условием (условие - выражение отношения);

- ветвление с составным условием (условие - логическое выражение);

- сложное ветвление (несколько условий).

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