Понятие структур данных и алгоритмов

CТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ

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

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

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

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

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

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

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

Само по себе слово “алгоритм” (algorithm) очень интересно. Это слово еще не вошло в Webster’s New World Dictionary даже 1957 года издания. Там можно найти только старую форму “Algorism”, что означает правило выполнения арифметических действий с использованием арабских цифр. К средним векам сложились две враждующие партии среди приверженцев различных традиций счета. Абакисты считали на абаках – счетах, алгоритмики же использовали начатки математической символики. Происхождение слова algorism долгое время оставалось неясным. Языковеды пытались объяснять его, комбинируя различные слова. Наконец, историки математики обнаружили истинное происхождение слова algorism: оно произошло от имени автора известного арабского учебника по математике – Abu Ja’far Mohammed ibn Musa al-Khowarizmi (около 825 г.), означающего буквально “Отец Джафара, Магомет, сын Моисея, уроженец Ховаризма”. В настоящее время Ховаризм – город Хива. Вышеназванный уроженец Ховаризма написал знаменитую книгу “Kitab al jabr w’al-muqabala” (“Правила восстановления и преобразования”); заглавие этой книги дало начало другому слову – “алгебра”, хотя сама книга в действительности была не совсем алгебраической.

Постепенно форма и значение слова “algorism” исказились; как объясняет “Oxford English Dictionary”, слово было “ошибочно видоизменено” в результате “укоренившейся путаницы” со словом arithmetic. Изменение algorism на algoritm нетрудно понять, если учесть, что истинное происхождение слова давно было забыто.

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

1. Конечность. Алгоритм должен заканчиваться после конечного числа шагов.

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

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

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

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

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

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

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

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

Алгоритм Евклида

Даны два целых положительных числа m и n. Требуется найти их наибольщий общий делитель, т.е. наибольшее положительное целое число, которое нацело делит как m, так и n.

Шаг1. [Нахождение остатка.] Разделим m на n. Пусть остаток равен r. (Имеем 0<=r<n.)

Шаг 2. [Это нуль?] Если r = 0, алгоритм кончается; n – искомое число.

Шаг 3. [Замена.] Положите m←n, n←r и возвращайтесь к шагу 1.

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

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

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: