Пантелеев Евгений Рафаилович Структуры и алгоритмы обработки данных

Цель понятие алгоритмов решения сложных задач.

Литература “Структуры и алгоритмы обработки данных”.

Экзамен. Задача на компе. 2 семестра

Задачи курса:

Формализация и структуризация понятия сложность.

Абстрактные типы данных (структурная сложность).

Теория вычислительной сложности.

Методы ограниченного и полного перебора.

Приближенные методы оптимизации.

Эффективные алгоритмы оптимизации на графах.

Фактор сложности.

1. Структурная сложность – сложность моделей данных, которые используются для решения задач.

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

Абстрактные типы данных.

Абстрактный тип данных (АТД) – тип определяемый программистом в терминах операций доступа в его экземплярах. Совокупность этих операций принято называть интерфейсом абстрактных операций.

Требования к интерфейсу:

1. Функциональная полнота. Набор операций должен быть достаточен для выполнения любой из функций.

2. Простота. Должно быть минимальное кол-во операций.

3. Интерфейс должен быть независимый от реализации.

Реализация АТД – набор скрытых операций и свойств АТД, который необходим для обеспечения его интерфейса.

Реализация скрыта!!! Интерфейс открытый!!!

2 ветви абстракции КОД и ДАННЫЕ.

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

Преимущества абстракции данных:

1. Декомпозиция. Использование АТД позволяет разрабатывать сложную модель данных по частям.

2. АТД повышает повторное использование кода.

Пример АТД:

• Стек - набор данных, который поддерживает дисциплину доступа последний пришел, первый вышел.

(Last In, First Out = LIFO)

Классификация операций интерфейса.

• Конструктор – операции по выделению ресурсов экземпляру объекта и его реализации.

• Деструктор – операции применяются для текущ. Состояния.

• Селекторы - операции позволяющие узнать состояние объекта.

• Модификатор – это операция меняющая состояние объекта.

Операции интерфейса стека.

Положить в стек, взять со стека. (Модификаторы).

Пустой стек, полный стек. (Селекторы).

Конструктор и деструктор. Для создания.

Реализация стека.

В зависимости от выбора реализации может потребоваться скрытое представление тела стека (массив) и указателя на вершину стека.

Задание для самоподготовки: выполнить объектную реализацию абстрактного типа стек с учетом ограничения доступа к элементам реализации. Использовать динамический массив.

Использование АТД стек для вычисления Польской инверсной записи.

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

1+2*3 = 1 2 3 * +

Дает возможность вычислить значение за один проход.

Лексема – минимальный смысловой элемент записи.

Лексема:

• Операнд

• Операция

Алгоритм вычисления.

Пока не конец строки выполняй:

1. Читать лексему.

2. Если лексема операнд, то положить ее в стек, иначе взять со стека 2 верхних элемента и применить к ним операцию соответствующую текущей лексеме, результат положить в стек.

Алгоритм построения Польской записи.

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

2.Переместить знаки операций за соответствующие правые скобки.

3.Удалить все скобки в записи.

Преобразование из инфиксной записи в Польскую.

	+	-	*	/	(	)
Инфиксный	1	1	2	2	3	0
Стековый	1	1	2	2	0	-

В отличие от алгоритма вычисления Польской записи в стеке размещаются не числа, а символы операций.

1. Инициализировать стек операций.

2. Пока не конец инфиксной строки выполнять

   1. Читать лексему

   2. Если лексема операнд (число) то

      1. Отправить лексему в выходной поток

      2. Иначе если лексема закрывающая скобка то

         1. извлечь из стека операций все операции до открывающей скобки и отправить их кроме скобки в выходной поток.

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

3. Извлечь операции из стека и отправить ее в выходной поток.