Алгоритмы и структуры данных

Оглавление

Стили программирования. 3

Формализация понятия алгоритма. Машина Поста и Тьюринга. 9

Методы анализа алгоритмов. Эффективность алгоритмов. 18

Алгоритмы сортировки. 23

Внутренняя сортировка. 23

Пузырьковая сортировка. 24

Сортировка вставками. 25

Сортировка посредством выбора. 26

Сортировка Шелла. 27

Быстрая сортировка. 29

Сортировка слиянием.. 33

Внешняя сортировка. 36

Внешняя многофазная сортировка слиянием.. 36

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

Массив как базовая структура. 41

Простейшие структуры данных. 44

Стек. 44

Стековый калькулятор и обратная польская запись формулы.. 46

Очередь. 49

Ссылочные реализации структур данных. 52

Списки. 54

Деревья и графы.. 59

Множества. 62

Бинарное дерево поиска. 64

Красно-черные деревья, AVG-деревья. 65

Хеширование. 68

Пирамиды и пирамидальная сортировка. 71

Алгоритмы поиска. 75

Метод двоичного поиска. 76

Интерполяционный поиск. 77

Динамическое программирование. 78

«Жадные алгоритмы». 79

Поиск с возвратом. 79

Поиск лексической информации. 80

Литература. 80

 

 

Стили программирования

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

На первом этапе в эпоху ЭВМ 1-го и 2-го поколения требования к алгоритмам были весьма жесткими:

· Использовать наименьшее возможное число ячеек оперативной памяти;

· Минимальное число операций.

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

· Операции присваивания;

· Простейшие арифметические операции;

· Операции сравнения чисел;

· Операторы условного и безусловного перехода;

· Операторы вызова подпрограмм.

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

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

 

С появлением массовых ЭВМ 3-го поколения подтолкнуло к разработке новых методологий программирования. Появившийся в начале 1970-х новый подход к разработке алгоритмов получил название структурного.

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

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

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

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

 

 

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

 

 

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

 

Цикл с «предусловием».

 

Цикл с «постусловием».

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

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

· Возможность создания программы несколькими программистами;

· Простота проектирования и последующих модификаций программ;

· Упрощение отладки и поиска ошибок;

· Возможность использовать готовых библиотек наиболее употребительных модулей.

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

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

На следующем этапе происходит дальнейшая детализация до уровня небольших подзадач. Которые требуют для решения небольших модулей в 3-5 строчки.

Структурное программирование, наиболее отчетливо выраженное в языке Паскаль (PASCAL), возникло в ходе развития процедурно-ориентированного подхода, заложенного в исторически первом из языков программирования – Фортране (FORNRAN). В языках данной группы программист описывает действия для реализации необходимого процесса, используя понятия команд (операторов) и данных.

Структурирование программы – это разбивка на отдельные подпрограммы. В каждом модуле может находиться произвольное количество подпрограмм.

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

Практически во всех языках программирования имеются средства структурирования. Соответственно такие языки называют процедурно-ориентированные. Pascal относится к таким языкам.

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