Файл: Алгоритмизация как обязательный этап разработки программы ( Свойства алгоритма ).pdf

Введение

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

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

Но есть немало таких действий, выполняя которые мы тщательно следуем той или иной инструкции. Это главным образом непривычные действия, профессионально несвойственные нам. Например, если вы фотографируете один-два раза в год, то, купив проявитель для плёнки, будете весьма тщательно следовать инструкции (алгоритму) по его приготовлению: «Содержимое большого пакета растворить в 350 мл воды при температуре 18-20 С. Там же растворить содержимое малого пакета. Объём раствора довести до 500 мл. Раствор профильтровать. Проявлять 3-4 роликовых фотоплёнки». Второй пример. Если вы никогда раньше не пекли торт, то, получив рецепт (алгоритм) его приготовления, постараетесь выполнить в указанной последовательности все его предписания.

Актуальность изучения алгоритмов обусловлена следующими причинами:

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

Во-вторых, алгоритмы играют ключевую роль в современных технологических инновациях.

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

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

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

1. Основы алгоритмизации

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

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

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

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

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

1.1. Структурная организация данных

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

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

Основные понятия структур данных

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

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

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

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

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

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

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

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

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

Классификация структур данных по признаку изменчивости

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

Вектор (одномерный массив) - структура данных с фиксированным числом элементов одного и того же типа.

Массив - последовательность элементов одного типа, называемого базовым.

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

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

Таблица - последовательность записей, которые имеют одну и ту же организацию.

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