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

Дополнительная литература

Основная литература

Структуры данных

Конспект лекций

Лекция 1

Введение. Концепция структур данных и алгоритмов их обработки

Научный редактор доц., д-р техн. наук Л.Г. Доросинский

Екатеринбург

Содержание

Рекомендуемая литература. 3

1. Основная литература. 3

2. Дополнительная литература. 3

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

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

2. Классификация структур данных. 10

3. Операции над структурами данных. 14

4. Структурность данных и технология программирования. 16

Рекомендуемая литература

1. Н.Вирт. Алгоритмы и структуры данных.-М.:"Мир",1989. - 408 с.: ил.

2. М.Сибуя, Т.Ямамото. Алгоритмы обработки данных.-М.:"Мир",1986. - 208 с.: ил.

3. Костин А.Е., Шаньгин В.Ф. Организация и обработка структур данных в вычислительных системах: Учеб. пособ. для вузов. – М.: Высш. шк., 1987. –248 с.: ил.

4. Кнут Д. Искусство программирования. Том 1: Основные алгоритмы. 2-е изд. – Пер. с англ. – Вильямс, 2006. - 720 с.: ил.

5. Кнут Д. Искусство программирования. Том 2: Получисленные алгоритмы. 2‑е изд. – Пер. с англ. – Вильямс, 2007. - 832 с.: ил.

6. Кнут Д. Искусство программирования. Том 3: Сортировка и поиск. 2-е изд. – Пер. с англ. – Вильямс, 2007. - 824 с.: ил.

7. Левитин А.В. Алгоритмы: введение в разработку и анализ. – Вильямс, 2006 - 408 с.: ил.

8. Т. Х. Кормен, Ч.И. Лейзерсон, Р.Л. Ривест, К. Штайн. Алгоритмы: построение и анализ. – Вильямс, 2006 - 1296 с.: ил.

9. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. – Вильямс, 2000. - 384 с.: ил.

1. Дейкстра Э. Дисциплина программирования.. Мир – М., 1978. - 208 с.: ил.

2. Оре О. Приглашение в теорию чисел. Наука – М., 1980. - 100 с.

3. Кушниренко А.Г., Лебедев Г.В. Программирование для математиков. Наука, 1988

4. Арсак Ж. Программирование игр и головоломок. Наука, 1990 - 208 с.: ил.

5. Малоземов В.Н. Рекурентные вычисления. Издательство Ленинградского университета 1976. - 176 с.: ил.

6. Порублев И.Н., Ставровский А.Б. Алгоритмы и программы. Решение олимпиадных задач. – Диалектика, 2007. - 480 с.: ил.

7. Г.С. Уоррен Алгоритмические трюки для программистов. Исправленное издание. Вильямс, 2007.- 288 с.: ил.

8. Смит.Б. Методы и алгоритмы вычислений на строках. Теоретические основы регулярных вычислений. – Вильямс, 2006. - 496 с.: ил.

9. Кнут Д. Искусство программирования. Том 4, выпуск 2. Генерация всех кортежей и перестановок. – Пер. с англ. – Вильямс, 2007. - 160 с.: ил.

10. Кнут Д. Искусство программирования. Том 4, выпуск 3. Генерация всех сочетаний и разбиений. – Пер. с англ. – Вильямс, 2007. - 208 с.: ил.

11. Кнут Д. Искусство программирования. Том 4, выпуск 4. Генерация всех деревьев. История комбинаторной генерации. – Пер. с англ. – Вильямс, 2007. - 160 с.: ил.

В последние годы программирование стало не только средством, владение которым оказывается решающим для успешной работы во многих прикладных областях, а так же предметом научного изучения. Программирование стало академической дисциплиной. Первые крупные шаги в этом направлении были сделаны в работах Э. Дейкстры и К. Хора. “Заметки по структурному программированию” Дейкстры определили новый взгляд на программирование как на предмет научного изучения и поле для интеллектуальной деятельности; этот подход получил название “революции” в программировании. В статье “Аксиоматическая основа программирования для вычислительных машин” Хоор продемонстрировал, что программы поддаются точному анализу, основанному на математических рассуждениях. В этих работах убедительно показано, что можно избежать многих ошибок программирования, если программист со знанием дела будет применять те методы и приемы, которые ранее использовались интуитивно и часто неосознанно. Основное внимание в них уделено построению и анализу программ, или, более конкретно, структуре алгоритмов, представленных текстами программ. Причем совершенно ясно, что систематический и научный подход к построению программ важен в первую очередь в случае больших программ со сложными данными. Таким образом, методы программирования включают так же и все варианты структурирования данных.

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

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

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

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

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

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

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

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

" Алгоритмы + структуры данных = программы ".

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

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

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

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

Слово algorithm произошло от имени автора известного арабского учебника по математике – Abu Ja’far Mohammed ibn Musa al-Khovarizmi (ок. 825г.), означающего: «Отец Джафара, Магомет, сын Моисея, уроженец Хорезма». В настоящее время Хорезм – это узбекский город Хива. Аль-Хорезми написал знаменитую книгу «Kitab al jabr w’al-muqabala» («Правила восстановления и преобразования»), заглавие которой дало начало другому слову – алгебра.

В средние века вместо термина algorithm употреблялась форма «algorism», что означает выполнение арифметических действий с использованием арабских цифр. Постепенно форма и значение слова «Algorism» исказилось. Согласно «Oxford English Dictionary», слово было «ошибочно видоизменено» в результате «укоренившейся путаницы» со словом arithmetic.

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

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

и для .

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

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

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

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

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

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

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

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

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

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

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

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

Дата добавления: 2014-01-11