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

Содержание:

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Программа— описание структуры алгоритма на языке алгоритмического программирования. Выше отмечалось, что один и тот же алгоритм может статься записан по-разному. Можно записывать алгоритм естественным языком. В таком варианте мы используем рецепты, инструкции и т. п. Для записи алгоритмов, специализированных формальным исполнителям, разработаны особые языки программирования. Любой алгоритм можно описать графически в виде блок-схемы. Чтобы достичь желаемого результата изобретена особая система обозначений (Приложение № 1)

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

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

Следовательно, язык для записи алгоритмов обязан быть формализован.

Такой язык принято называть языком программирования, а запись алгоритма на данном языке — программой для компьютера.

1.3. Виды структур алгоритмов и примеры их использования

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

Линейный алгоритм – это алгоритм, в котором действия выполняются однократно и строго последовательно.

Самый простой пример реализации линейного алгоритма – путь из университета домой.

Словесный способ записи данного алгоритма:

выйти из университета на остановку;

подождать нужный автобус;

сесть на нужный автобус;

оплатить проезд;

выйти на требуемой остановке;

дойти до дома.

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

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

В алгоритме разветвленной структуры (ветвлении) в зависимости от истинности или ложности некоторого условия выбирается одна из двух серий команд.

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

Например вы отправляетесь в кино. Подойдя к кинотеатру, вы обнаруживаете, что сегодня идут два фильма: новая серия «Гарри Поттера» и новый боевик с Сильвестром Сталлоне. Если есть билеты на первый, то пойдете смотреть его, иначе будете смотреть боевик.

Рис. 1 Пример разветвляющегося алгоритма

Идти в кино

Есть билеты на Гарри Потера?

Купить билет на этот фильм

Купить билет на боевик

Идти смотреть фильм

Идти смотреть боевик

Циклический алгоритм – это алгоритм, команды которого повторяются некое количество раз подряд.

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

Рис. 2 Пример циклического алгоритма

Открыть книгу

Книга не закончилась

Нет

Да

Прочесть страницу

Перевернуть страницу

Закрыть книгу

1.4. Обзор программных и аппаратных средств

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

Паскаль был создан Никлаусом Виртом в 1968-69 годах после его участия в работе комитета разработки стандарта языка Алгол-68. Он был опубликован в 1970 году Виртом как небольшой и эффективный язык, чтобы способствовать хорошему стилю программирования, использовать структурное программирование и структурированные данные.

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

Компилятор Паскаля был написан на самом Паскале c использованием метода раскрутки.

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

Тем не менее, первоначально язык имел ряд ограничений: невозможность передачи функциям массивов переменной длины, отсутствие нормальных средств работы с динамической памятью, ограниченная библиотека ввода-вывода, отсутствие средств для подключения функций написанных на других языках, отсутствие средств раздельной компиляции и т. п. Подробный разбор недостатков языка Паскаль того времени был выполнен Брайаном Керниганом в статье «Почему Паскаль не является моим любимым языком программирования» (эта статья вышла в начале 1980-х, когда уже существовал язык Модула-2, потомок Паскаля, избавленный от большинства его пороков, а также более развитые диалекты Паскаля). Некоторые недостатки Паскаля были исправлены в ISO-стандарте 1982 года, в частности, в языке появились открытые массивы, давшие возможность использовать одни и те же процедуры для обработки одномерных массивов различных размеров.

Необходимо заметить, что многие недостатки языка не проявляются или даже становятся достоинствами при обучении программированию. Кроме того, по сравнению с основным языком программирования в академической среде 1970-х (которым был Фортран, обладавший гораздо более существенными недостатками), Паскаль представлял собой значительный шаг вперёд. В начале 1980-х годов в СССР для обучения школьников основам информатики и вычислительной техники академик А.П. Ершов разработал алголо-паскалеподобный «алгоритмический язык».

Наиболее известной реализацией Паскаля, обеспечившая широкое распространение и развитие языка, является Turbo Pascal фирмы Borland, выросшая затем в объектный Паскаль для DOS (начиная с версии 5.5) и Windows и далее в Delphi, в которой были внедрены значительные расширения языка.

Диалекты Паскаля, применяемые в Turbo Pascal для DOS и Delphi для Windows, стали популярны из-за отстутствия других успешных коммерческих реализаций.

Описание каждого элемента языка задается его синтаксисом и семантикой. Синтаксические определения устанавливают правила построения элементов языка. Семантика определяет смысл и правила использования тех элементов языка, для которых были даны синтаксические определения. Паскаль, в его первоначальном виде, представляет собою чисто процедурный язык и включает в себя множество алголоподобных структур и конструкций с зарезервированными словами наподобие if, then, else, while, for, и т. д. Тем не менее, Паскаль также содержит большое количество возможностей для структурирования информации и абстракций, которые отсутствуют в изначальном Алголе-60, такие как определение типов, записи, указатели, перечисления, и множества. Эти конструкции были частично унаследованы или инспирированы от языков Симула-67, Алгол-68, созданного Никлаусом ВиртомAlgolW и предложены Хоаром.

В современных диалектах (Free Pascal) доступны такие операции как перегрузка операторов и функций.

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

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

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

· проведения однотипных расчетов над большими наборами данных;

· автоматизации итоговых вычислений;

· решения задач путем подбора значений параметров, табулирования формул;

· обработки результатов экспериментов;

· проведения поиска оптимальных значений параметров;

· подготовки табличных документов;

· построения диаграмм и графиков по имеющимся данным.

Одним из наиболее распространенных средств работы с документами, имеющими табличную структуру, является программа Microsoft Excel.

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

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

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

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

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

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

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

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

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

· ввод на компьютере разнообразных математических выражений (для дальнейших расчетов или создания документов, презентаций, Web-страниц);

· проведение математических расчетов;

· подготовка графиков с результатами расчетов;

· ввод исходных данных и вывод результатов в текстовые файлы или файлы с базами данных в других форматах;

· подготовка отчетов работы в виде печатных документов;

· подготовка Web-страниц и публикация результатов в Интернете;

· получение различной справочной информации из области математики.

Со всеми этими (а также некоторыми другими) задачами с успехом справляется Mathcad:

· математические выражения и текст вводятся с помощью формульного редактора Mathcad, который по возможностям и простоте использования не уступает, к примеру, редактору формул, встроенному в Microsoft Word;

· математические расчеты производятся немедленно, в соответствии с введенными формулами;

· графики различных типов (по выбору пользователя) с богатыми возможностями форматирования вставляются непосредственно в документы;

· возможен ввод и вывод данных в файлы различных форматов;

· документы могут быть распечатаны непосредственно в Mathcad в том виде, который пользователь видит на экране компьютера, или сохранены в формате RTF для последующего редактирования в более мощных текстовых редакторах (например Microsoft Word);

· возможно полноценное сохранение документов Mathcad 11 в формате Web-страниц (генерация вспомогательных графических файлов происходит автоматически);

· имеется опция объединения разрабатываемых Вами документов в электронные книги, которые, с одной стороны, позволяют в удобном виде хранить математическую информацию, а с другой — являются полноценными Mathcad-программами, способными осуществлять расчеты;

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

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

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

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

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

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

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

Одним из наиболее важных аспектов алгоритма является его скорость. Часто бывает легко придумать алгоритм решающий задачу, но если алгоритм слишком медленный, то он возвращается на доработку. Поскольку точная скорость алгоритма зависит от того где запускается алгоритм, а также деталей реализации, компьютерные специалисты обычно говорят о времени выполнения относительно входных данных. Например, если вход состоит из N целых чисел, то алгоритм может иметь время выполнения пропорциональное N2, что представляется как O(N2). Это означает, что если вы запустите реализацию алгоритма на компьютере с входом размером в N, то это займет C*N2 секунд, где C-некоторая константа, которая не меняется с изменением размера входа.

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

Сортировка является хорошим примером алгоритма, который часто используется программистами. Самый простой способ отсортировать группу элементов это начать с удаления наименьшего элемента из группы, и поставить его первым. Затем удаляется второй по величине элемент и ставится вторым и т.д. К сожалению, время работы этого алгоритма составляет O(N2), а это означает, что потребуется количество времени пропорциональное количеству элементов в квадрате. Если бы нам пришлось сортировать млрд. элементов, то этот алгоритмы бы потребовал 1018 операций. Если считать что обычные настольные ПК делают примерно 109 операций в секунду, то потребуются годы чтобы закончить сортировку этого млрд. элементов.

К счастью существует ряд более совершенных алгоритмов, например, быстрая сортировка (quicksort), пирамидальная сортировка (heapsort) и сортировка слияния(mergesort). Эти алгоритмы имеют время выполнения O(N * Log(N)). Таким образом, число операций необходимых для сортировки млрд. элементов сокращается до таких разумных пределов, что даже самый дешевый настольный ПК способен провести такую сортировку. Вместо млрд. в квадрате операций (1018) эти алгоритмы требуют только 10 млрд. операций (1010), т.е. в 100 млн. раз быстрее.

Алгоритмы поиска кратчайшего пути из одной точки в другую исследуются уже на протяжении многих лет. Примеров прикладного применения этих алгоритмов предостаточно, однако для простоты изложения будем придерживаться следующей постановки: требуется найти кратчайший путь из точки А в точку Б в городе с несколькими улицами и перекрестками. Существует много разных алгоритмов для решения этой задачи и все они со своими преимуществами и недостатками. Прежде чем мы углубимся в их изучение, давайте рассмотрим время выполнения простого алгоритма перебором. Если алгоритм рассматривает каждый возможный путь от А до Б (который не образует циклов) он вряд ли закончится при нашей жизни, даже если А и Б находятся в маленьком городке. Время выполнения этого алгоритма является экспоненциальным, что обозначается как O(CN) для некоторого C. Даже для малых значений C, CN становится астрономическим числом, когда N принимает умеренно большое значение.

Один из самых быстрых алгоритмов для решения этой задачи имеет время выполненияO(E+V*Log(V)), где E число дорожных сегментов, а V число пересечений. Алгоритм займет около 2 секунд времени, для поиска кратчайшего пути в городе из 10000 пересечений и 20000 дорожных сегментов (обычно бывает около 2 дорожных сегментов на одно пересечение). Этот алгоритм известен как алгоритм Дейкстры, он является довольно таки сложным и требует использования структуры данных очередь с приоритетом (priority queue). Однако в некоторых случаях даже такое время выполнения является слишком медленным (взять например нахождение кратчайшего пути от Нью-Йорка до Сан-Франциско - в США есть миллионы пересечений), в таких случаях программисты пытаются улучшить время выполнения с помощью так называемой эвристики. Эвристика - это приближенное значение чего-то, что имеет отношение к задаче. В задаче поиска кратчайшего пути, например, может оказаться полезным знать, как далеко находится точка от пункта назначения. Зная это можно разработать более быстрый алгоритм (например алгоритм поиска А* в некоторых случаях работает значительно быстрее чем алгоритм Дейкстры). Такой подход не всегда улучшает время выполнения алгоритма в наихудшем случае, но в большинстве реальных приложений алгоритм начинает работать быстрее.

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

На самом деле есть немало важных задач, для которых известные на сегодня алгоритмы выдают оптимальный результат слишком медленно. Наиболее известная группа из этих задач называется NP (non-deterministic polynomial). Если задача называется NP-полной или NP-трудной, то это означает, что никто не знает достаточно хорошего способа для получения оптимального решения. Кроме того, если кто-то разработает эффективный алгоритм для решения одной NP-трудной задачи, то этот алгоритм можно будет применить ко всем NP-трудным задачам.

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

Еще один подход, применяемый для решения некоторых задач, заключается в том, чтобы сделать алгоритм случайным. Данный подход не улучшает время алгоритма в худшем случае, но довольно часто хорошо работает в среднем случае. Алгоритм быстрой сортировки является хорошим примером использования рандомизации. В худшем случае, алгоритм быстрой сортировки сортирует группу элементов за O(N2), где N количество элементов. Если в этом алгоритме использовать рандомизацию, то шансы на худший случай становятся незначительно малыми, и в среднем случае алгоритм быстрой сортировки работает за время O(N*Log(N)). Другие алгоритмы даже в худшем случае гарантируют время работы O(N*Log(N)), однако они медленнее в среднем случае. Хотя оба алгоритма имеют время работы пропорциональное N*Log(N), алгоритм быстрой сортировки имеет более меньший постоянный коэффициент (constant factor) - т.е. он требует C*N*Log(N), в то время как другие алгоритмы требуют более 2*C*N*Log(N) операций.

Другой алгоритм, использующий случайные числа ищет медиану для группы чисел и его время работы в среднем случае составляет O(N). Это намного быстрее по сравнению с алгоритмом, который сортирует числа и выбирает среднее, и работает за O(N*Log(N)). Существуют детерминированные алгоритмы (не случайные) которые позволяют найти медиану за время O(N), однако случайный алгоритм проще для понимания и часто работает быстрее этих детерминированных алгоритмов.

Основная идея алгоритма поиска медианы это выбрать среди чисел случайное, и посчитать, сколько чисел в группе меньше чем выбранное число. Допустим, есть N чисел, K из них меньше или равно выбранному числу. Если K меньше чем половина N, тогда мы знаем что медиана это (N/2-K)-е число которое больше чем случайно выбранное число, так что мы отбрасываем K чисел меньших или равных случайному числу. Теперь допустим мы хотим найти (N/2-K)-е наименьшее число, вместо медианы. Алгоритм такой же, мы просто случайно выбираем число и повторяем описанные шаги.

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Основы алгоритмизации и программирования: учеб. пособие / Т.А. Жданова, Ю.С. Бузыкова. – Хабаровск : Изд-во Тихоокеан. гос.ун-та, 2011. – 56 с. Режим доступа: http://pnu.edu.ru/media/filer_public/2013/02/25/book_basics.pdf.

2. Программирование и основы алгоритмизации: Для инженерных специальностей технических университетов и вузов. /А.Г. Аузяк, Ю.А. Богомолов, А.И. Маликов, Б.А. Старостин. Казань: Изд-во Казанского национального исследовательского технического ун-та - КАИ, 2013, 153 с. Режим доступа: http://au.kai.ru/documents/Auzyak_Progr_osn_alg_C_2013.pdf.

3. Основы алгоритмизации и программирования : учебное пособие / Г. Р. Кадырова. – Ульяновск : УлГТУ, 2014. – 95 с. . Режим доступа: http://venec.ulstu.ru/lib/disk/2014/137.pdf

4. Основы алгоритмизации и программирования. Курс лекций. Режим доступа: http://lib.ssga.ru/fulltext/UMK/исходные%20для%20Кацко/заменить%20полно стью/Информатика/лекции/13%20Основы%20алгоритмизации%20и%20прог раммирования.pdf

5. Белов П.М. Основы алгоритмизации в информационных системах: Учебн. Пособие.- Спб.: СЗТУ, 2003. – 85с. Режим доступа: http://www.ict.edu.ru/ft/005406/nwpi225.pdf

6. Основы алгоритмизации и программирования: Метод. указ. / Сост.: И.П. Рак, А.В. Терехов, А.В. Селезнев. Тамбов: Изд-во Тамб. гос. техн. ун-та. Режим доступа: http://www.ict.edu.ru/ft/004758/terehov.pdf.

7. Макаров В.Л. Программирование и основы алгоритмизации.: учебн. пособие.-Спб., СЗТУ, 2003, - 110с. Режим доступа: http://window.edu.ru/resource/126/25126/files/nwpi223.pdf

8. Российская Государственная Библиотека - https://www.rsl.ru/

ПРИЛОЖЕНИЯ

Приложение № 1.

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

Приложение № 2