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

ВВЕДЕНИЕ

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

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

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

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

Цель работы: узнать, что есть алгоритмы, изучить их структуру.

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

1. Изучить понятие «алгоритм».

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

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

Предмет данного исследования – алгоритмы.

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

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

1.1. Понятие алгоритма и его свойства

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

1) создание в зрительном режиме элементов графического интерфейса программы;

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

Начало к пониманию значимости исследованья и знания алгоритмов это дать четкое определение тому, что подразумевается под алгоритмом.

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

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

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

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

Дискретность (разрывность — обратно непрерывности) — это свойство алгоритма, характеризующее его структуру: всякий алгоритм складывается из отдельных законченных действий («Делится на шаги»).

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

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

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

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

Само слово «свойства алгоритма» до некоторой степени корректно. Свойствами обладают объективно имеющиеся реальности. Может идти речь, например, о свойствах какого-нибудь вещества.

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

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

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

Это правило разрешает сразу отделить алгоритмы от “методов” и “способов”. Пока мы не имеем формализованных входных данных, мы не можем построить алгоритм.

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

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

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

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

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

Часто возникают статьи вида «нужны ли программисту алгоритмы», и все они имеют примерно одинаковый шаблон. Создатель статьи в большинстве случаев пишет: «Я N лет пишу сайты/скрипты в 1С, и никогда не пользовался алгоритмами либо структурами данных. Не мешкая приводятся в пример красно-чёрные деревья либо какие-то другие экзотические структуры. Такие статьи объединяются к тому, что в определенной области программисты не используют сложные структуры данных не решают NP задач.

Сама установка такового вопроса во всех отношениях не верна. Количество специальностей в промышленности растёт постоянно, и человек, который пишет страницы сайтов на . net будет заниматься абсолютно иными вещами, чем человек, создающий драйвера для сенсоров на ARM архитектуре под экзотической ОС. Ведь действительно, чтобы писать наипростейшие страницы сайтов и скрипты, не имеет смысла особенного знания алгоритмов и структур данных. Либо всё-таки нужно?

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

1.2. Способы описания алгоритмов

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

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

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

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

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

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

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