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

Введение

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

Созданием языков программирования занимаются в большинстве случаев очень квалифицированные специалисты, часто группы программистов, а иногда даже международные коллективы. Однако подавляющее большинство языков программирования умирало, едва родившись. Лишь к немногим из них был проявлен интерес, и буквально единицы получили действительно широкое распространение. К таким «счастливым» языкам принадлежит язык Паскаль, разработанный Никлаусом Виртом в 1968-1971гг. в Цюрихском Институте информатики (Швейцария). Первоначальная цель разработки языка диктовалась необходимостью инструмента «для обучения программированию как системной дисциплине». Однако очень скоро обнаружилась чрезвычайная эффективность языка Паскаль в самых разнообразных приложениях: от решения небольших задач численного характера до разработки сложных программных систем – компиляторов, баз данных, операционных систем и т.д. Существуют многочисленные реализации языка практически для всех машинных архитектур; разработаны десятки диалектов и проблемно-ориентированных расширений языка Паскаль; обучение программированию и научно-технические публикации часто базируются на этом языке.

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

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

Предметом исследования являются особенности алгоритмических структур.

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

Задачи курсовой работы:

-раскрыть понятие, способы описания алгоритмов;

-дать анализ алгоритмов;

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

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

Глава 1. Понятие алгоритмов

1.1 Понятие алгоритма

Понятие алгоритм [1] является основным для всей области компьютерного программирования, поэтому начать мы должны с тщательного анализа этого термина. Слово "алгоритм" (algorithm) уже само по себе представляет большой интерес. На первый взгляд может показаться, будто кто-то собирался написать слово "логарифм" (logarithm), но случайно переставил первые четыре буквы. Этого слова еще не было в издании словаря 'VeЬster's New World Dictionary, вышедшем в 1957 году. Мы находим там только устаревшую форму "algorism" – старинное слово, которое означает "выполнение арифметических действий с помощью арабских цифр". В средние века абакисты считали на абаках (счетных досках), а алгоритмики использовали "algorism". Наконец историки математики обнаружили истинное происхождение слова "algorism": оно берет начало от имени автора знаменитого персидского учебника по математике – Абу Абд Аллах Мухаммед ибн Муса аль-Хорезми (ок. 825 г.), означающего буквально "Отец Абдуллы, Мухаммед, сын Мусы, уроженец Хо-резма". Аральское море в Центральной Азии когда-то называлось озе-ром Хорезм, и район Хорезма (Khwarizm) расположен в бассейне реки Амударьи южнее этого моря. Аль-Хорезми написал знаменитую книгу Китаб альджебр вальмукабала – "Книга о восстановлении и противопоставлении". От названия этой книги, которая была посвящена решению линейных и квадратных уравнений, произошло еще одно слово – "алгебра".

К 1950 году слово "алгоритм" чаще всего ассоциировалось с алгоритмом Евклида, который представляет собой процесс нахождения наибольшего общего делителя двух чисел. Данный алгоритм был впервые описан в книге Евклида "Начала" (около 300 г. до н.э.) и является наиболее цитируемым при рассмотрении введение в алгоритмизацию и программирование.

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

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

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

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

2) Определенность. Каждый шаг алгоритма должен быть точно определен. Действия, которые нужно выполнить, должны быть строго и недвусмысленно определены для каждого возможного случая. На практике алгоритмы могут описываться и на обычном языке, и на формализованных псевдоязыках так и на языках программирования. Метод вычислений, выраженный на языке программирования, называется программой.

3) Ввод. Алгоритм имеет некоторое (возможно, равное нулю) число входных данных, т. е. величин, которые задаются до начала его работы или определяются динамически во время его работы. Эти входные данные берутся из определенного набора объектов. Например, в алгоритме есть два входных значения, а именно m и n, которые принадлежат множеству целых положительных чисел.

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

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

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

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

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

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

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

• аппаратное обеспечение с высокими тактовыми частотами, конвейерной обработкой и суперскалярной архитектурой;

• легкодоступные, интуитивно понятные графические интерфейсы (GUI);

• объектно-ориентированные системы;

• локальные и глобальные сети.

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

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

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

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

Одним из самых трудоемких этапов решения задачи на ЭВМ является разработка алгоритма. Человечество разработало эффективный алгоритм завязывания шнурков на ботинках. Многие дети с пятилетнего возраста могут это делать. Но дать чисто словесное описание этого алгоритма без картинок и демонстрации - очень трудно.

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

Рассмотрим два способа: графический и с помощью языков программирования.

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