Саод, семестр 1
Темы выносимые на зачет в 1 семестре:
САОД, семестр 1 1
Абстрактные типы данных 1
Абстрактный тип данных в списках 6
Сравнение последовательного и связанного распределения 7
Стек, очередь, дек 8
Классификация алгоритмов сортировки 14
Постановка задачи сортировки 14
Алгоритм Шелла 16
Быстрая сортировка Хоару 18
Пирамидальная сортировка. Выбор из дерева 21
Класс сортировок слиянием 25
Абстрактные типы данных
«Математика» САОД Программирование
Абстрактный тип данных – это математическая модель с совокупностью операторов или операций определенных в рамках данной модели. Абстрактным типам данных соответствует понятие класса в объектно-ориентированном программирование. К АТД применимы понятия инкапсуляции, абстрагирования (обобщение), наследования:
1. Абстракция или обобщение в том смысле, что АТД можно рассматривать как обобщение типа данных.
2. Наследование применимо в том смысле, что одни абстрактные типы данных могут быть реализованы новые АТД, реализация которых уже осуществлена в базовых АТД.
3. Инкапсуляция АТД инкапсулирует типы данных в том смысле, что методы и свойства располагаются вместе (объединены понятием) для выполнения операция (определенных в рамках модели) достаточно знать лишь имя (так как реализация оператора скрыта), не вдаваясь в реализацию содержание скрыто или она тривиальна и не представляет трудностей для последующего перевода в программный код.
Таким образом, при помощи операций АТД, реализованных в функциональные назначения математической модели.
Типы, структуры данных и атд
В языке программирования под типом данных понимают как понятие, определяющее диапазон значений, который может принимать данная переменная , которому соответствует достаточный объем памяти для хранения, выделяемый компилятором.
Для представления АТД используют структуры данных - совокупность или набор переменных, быть может, различных типов данных, объединенных определенным образом. Структура данных, как правило, агрегирует ячейки. В качестве простейшего механизма агрегирования можно использовать:
1) массив
2) структура данных. (struct, record)
3) Файл
Заметим, что 1 и 2 механизм реализует произвольный доступ к ячейкам (модель с произвольным доступом данных), а файлы – последовательный доступ.
Как средство агрегирования, можно рассматривать указатели и курсоры в том смысле, что они могут указывать или определять целые области ячеек . И то и другое – указатели на ячейку или область, т.е. хранят адрес начала области с той лишь разницей, что указатель – физический адрес в оперативной памяти ЭВМ, а курсор – адрес (номер ячейки) внутри локальной области данных, например в массиве курсором будет выступать индекс элемента. Курсор – это, как правило, целочисленная переменная, хранящая номер в элементе массива.
Время выполнения программы
С точки зрения жизненного цикла ПО можно выделить следующие временные отрезки:
1. Разработка
2. Тестирование, отладка
3. Эксплуатация
4. Сопровождение
Из этих четырех этапов наиболее дорогостоящие являются этапы 1,2,3, которые выполняют программисты, так как время работы программиста стоит намного дороже себестоимости выполнения программы на компьютере. Кроме того время работы программы намного меньше времени работы программиста над программой. Из двух программ программист выберет ту, которая наиболее проще для понимая, сопровождения, зачастую не обращая внимания на эффективность реализации. В теории сложности алгоритма рассматривают методы анализа и способы построения алгоритмов время выполнения, которых может заранее определено (в том числе и на основе исходного текста программ). Например, можно определить множество задач, которые на одном исходном наборе работают за исходное время, а на другом наборе данных по длине время год, день и события. Поэтому при выборе алгоритма кроме себестоимости разработки и поддержки необходимо обращать внимание на сложность в смысле вычислительной трудоемкости алгоритмов.
Время ввода исходных данных, эффективность кода.
Оптимизация кода компилятора с учетом ОС и архитектуры ЭВМ.
Архитектура ЭВМ машинного кода (инструкция), аппаратно ускоряющее время выполнения кода.
Временная сложность алгоритма, соответствующей программы.
Под временной сложностью алгоритма понимается число или количество элементарной инструкции или шагов алгоритма, которые нужно выделить для достижения результата.
Время выполнения программы…
Время выполнения алгоритма…
Число инструкций определяется как исходными данными, так и структурой алгоритма. Однако набор исходных данных программиста – аналитика остается неизвестным, поэтому мы имеем время алгоритма как функцию от исходных данных. Причем эту зависимость можно разделить на количественную и качественную. Например, алгоритм количество инструкций переменной N от конкретного его значения, т.е. f(N) от одной переменной.
(3(3 +1)) + (2(3 + 1)) + (1(3 + 1)) = 24 операции
Увеличим длину последовательности на 1 элемент, тогда число операций будет равно:
(4(3 +1)) + (3(3 + 1)) + (2(3 + 1)) + (1(3 +1)) = 40, таким образом, увеличивая число элементов на один, число операций увеличилось в несколько раз. Это показывает, что число операций выполнения время зависит от длины исходной последовательности количества элементов, задаваемые пользователем, т.е. в обоих примерах определяется значение числа N, которое объединяет эти примеры. Поэтому в общем случае говорят, что время выполнения алгоритма зависит от длины исходной последовательности. Вкладывая тот смысл, что он зависит как от количества элементов (массива), так и от количества переменных подобных 1 первому примера.
Говорят, что время выполнения программы имеет порядок T(n) от входных данных порядка (длины) n. Например, T(n) = C * n² определенно так, где С – некоторая константа, которая не зависит от входных данных, а определяет некоторое количество операторов, выполняемых в не зависимости от конкретного значения n. Например, быстродействие выполнения отдельной операции на данном компьютере.
C = (T(n))/n² , на данный коэффициент влияет ОС, архитектура ЭВМ, качество оператора и т.д. И физически представляет собой эффективность перехода от алгоритма его реализации (к фактическому).