Кафедра ОСУ, САОД Кафедра ОСУ, САОД1 Структуры и алгоритмы обработки данных Осенний: Лк -46, Лб-36, Пр-10, КР, Экзамен

Кафедра ОСУ, САОД Кафедра ОСУ, САОД2 Литература 1.Вирт Н. Алгоритмы+структуры данных = программы: Пер. с англ.-М.Мир, с., ил. 2.Вирт Н. Алгоритмы и структуры данных: Пер. с англ.-М.Мир, с., ил. 3.Кнут Д. Искусство программирования для ЭВМ. В 3 томах. т.1. Основные алгоритмы. М., С-П, : Вильямс, Кнут Д. Искусство программирования для ЭВМ. В 3 томах. т.3. Сортировка и поиск. М., С-П, : Вильямс, Ахо А., Хопкрофт,Д., Ульман Д. Структуры данных и алгоритмы. Вильямс, С-П, 2000

Кафедра ОСУ, САОД Кафедра ОСУ, САОД3 Литература 6. Седжвик Роберт Фундаментальные алгоритмы на C++. Анализ/Структуры данных/Сортировка/ : Пер. с англ./Роберт Седжвик. - К.: Издательство «ДиаСофт», с. ftp://exilim.osu.cctpu.edu.ru/

Кафедра ОСУ, САОД Кафедра ОСУ, САОД4 Алгоритм Алгоритм (algorithm) это любая корректно определенная вычислительная процедура, на вход (input) которой подается некоторая величина или набор величин, и результатом выполнения которой является выходная (output) величина или набор значений. Таким образом, алгоритм представляет собой последовательность вычислительных шагов, преобразующих входные величины в выходные.

Кафедра ОСУ, САОД Кафедра ОСУ, САОД5 Алгоритм:свойства 1.Конечность 2.Определенность 3.Ввод 4.Вывод 5.Эффективность

Кафедра ОСУ, САОД Кафедра ОСУ, САОД6 Анализ алгоритмов 1.Время выполнения 2.Требуемая память

Кафедра ОСУ, САОД Кафедра ОСУ, САОД7 Анализ алгоритмов Экспериментальные исследования имеют три основных ограничения: 1. эксперименты могут проводиться лишь с использованием ограниченного набора исходных данных; результаты, полученные с использованием другого набора, не учитываются; 2. для сравнения эффективности двух алгоритмов необходимо, чтобы эксперименты по определению времени их выполнения проводились на одинаковом аппаратном и программном обеспечении; 3.для экспериментального изучения времени выполнения алгоритма необходимо провести его реализацию и выполнение.

Кафедра ОСУ, САОД Кафедра ОСУ, САОД8 Анализ алгоритмов Общая методология анализа времени выполнения алгоритмов: 1.учитывает различные типы входных данных; 2.позволяет производить оценку относительной эффективности любых двух алгоритмов независимо от аппаратного и программного обеспечения; 3.может проводиться по описанию алгоритма без его непосредственной реализации или экспериментов.

Кафедра ОСУ, САОД Кафедра ОСУ, САОД Анализ алгоритмов Алгоритм arrayMax(A, n): Input:массив А, содержащий n целых чисел (n> 1). Output: элемент с максимальным значением в массиве A. currentMax А [0] for i 1 to n - 1 do if currentMax

Кафедра ОСУ, САОД Кафедра ОСУ, САОД10 Анализ алгоритмов /** * Тестирует программу алгоритма поиска максимального элемента массива. */ public class ArrayMaxProgram { /** находит элемент с максимальным значением в массиве А, * содержащем n целых чисел. */ static int arrayMax (int[ ] A, int n) { int currentMax = A[0]; // выполняется один раз for (int i=1, i < n, i++) // выполняется от 1 до n, n-1 раз // соответственно. if (currentMax < A[i]) // выполняется n-1 раз currentMax = A[i]; // выполняется максимально n-1 раз return currentMax; // выполняется один раз }

Кафедра ОСУ, САОД Кафедра ОСУ, САОД11 Анализ алгоритмов /** Тестирующий метод */ public static void main(String args[ ]) { int[ ] num = { 10, 15, 3, 5, 56, 107, 22, 16, 85 }; int n = num.length; System.out.print("Array:"); for (int j=0; i < n; i++) System.out.print("" + num[i]); System.out.println("."); System.out.println("The maximum element is" + arrayMax(num,n) + "."); } }

Кафедра ОСУ, САОД Кафедра ОСУ, САОД12 Описание алгоритмов (псевдокод) Выражения. Для написания числовых и логических выражений используются стандартные математические символы. Знак стрелки применяется в качестве оператора присваивания в командах присваивания (равнозначен оператору «=» языка Java). Знак «=» используется для передачи отношения равенства в логических выражениях (что соответствует оператору «= =» языка Java). Объявление метода. Имя алгоритма (paraml, param2,...) объявляет «имя» нового метода и его параметры. Структуры принятия решений. Условие if, then действия, если условие верно [else если условие не верно]. Отступы используются для обозначения выполняемых в том или другом случае действий. Цикл while, while условие, do - действия. Отступ обозначает действия, выполняемые внутри цикла.

Кафедра ОСУ, САОД Кафедра ОСУ, САОД13 Описание алгоритмов (псевдокод) Цикл repeat, repeat действия, которые выполняются, пока выполняется условие until. Отступ обозначает действия, выполняемые внутри цикла. Цикл for, for описание переменной и инкремента, do действия. Отступ обозначает действия, выполняемые внутри цикла. Индексирование массива. A[i] обозначает i-ую ячейку массива А. Ячейки массива А с количеством ячеек n индексируются от A[0] до A[n - 1] (как в Java). Обращения к методам, object.method (args) (часть object необязательна, если она очевидна). Возвращаемое методом значение. Значение return. Данный оператор возвращает значение, указанное в методе, вызывающим данный метод.

Кафедра ОСУ, САОД Кафедра ОСУ, САОД14 Анализ алгоритмов:аналитический подход 1. Записать алгоритм в виде кода одного из развитых языков программирования (например, Java или С++). 2. Перевести программу в последовательность машинных команд (например, байт-коды, используемые в виртуальной машине Java). 3. Определить для каждой машинной команды i время t i, необходимое для ее выполнения. 4. Определить для каждой машинной команды i количество повторений n i команды i за время выполнения алгоритма. 5. Определить произведение t i *n i всех машинных команд, что и будет составлять время выполнения алгоритма.

Кафедра ОСУ, САОД Кафедра ОСУ, САОД15 Анализ алгоритмов Основные (простейшие) операции аналоги маш.команд присваивание переменной значения вызов метода выполнение арифметической операции сравнение двух чисел индексация массива переход по ссылке на объект возвращение из метода

Кафедра ОСУ, САОД Кафедра ОСУ, САОД16 Анализ алгоритмов Например, число простейших операций t(n), выполняемых алгоритмом arrayMax, минимально равно n + 4(n -1) + 1 = 5n а максимально n + 6(n -1) + 1 = 7n - 2 те упрощенный анализ даст следующий результат: алгоритм выполняет от 5n до 7n 2 шагов при размере исходных данных n.

Кафедра ОСУ, САОД17 Временная и пространственная сложности алгоритмов Итак, для многих программ время выполнения является функцией входных данных Например, некая программа имеет время выполнения Т(n) = cn 2, где с константа. Единица измерения Т(n) точно не определена, обычно понимается под Т(n) количество инструкций, выполняемых на идеализированном компьютере.

Кафедра ОСУ, САОД18 Временная и пространственная сложности алгоритмов Для описания скорости роста функций используется О-символика. (Paul Bachman 1894г.) Когда мы говорим, что время выполнения Т(n) некоторой программы имеет порядок О(n 2 ), то подразумевается, что существуют положительные константы с и n 0 такие, что для всех n n 0, выполняется неравенство Т(n) < c n 2.

Кафедра ОСУ, САОД19 Временная и пространственная сложности алгоритмов Когда мы говорим, что Т(n) имеет степень роста O(f(n)), то подразумевается, что f(n) является верхней границей скорости роста Т(n). Чтобы указать нижнюю границу скорости роста Т(n), используется обозначение: Ω(g(n)) это подразумевает существование такой константы с, что бесконечно часто (для бесконечного числа значений n) выполняется неравенство Т(n) > cg(n).

Кафедра ОСУ, САОД20 Временная и пространственная сложности алгоритмов Временная сложность алгоритма в худшем случае функция размера входных данных, которая показывает максимальное количество элементарных операций, которые могут быть затрачены алгоритмом для решения экземпляра задачи указанного размера-O(f(n)). Аналогично определяется понятие временная сложность алгоритма в наилучшем случае- Ω(g(n)).

Кафедра ОСУ, САОД21 Временная и пространственная сложности алгоритмов

Кафедра ОСУ, САОД22 Временная и пространственная сложности алгоритмов Используя О-нотацию можно записать: Можно показать P(n) = O(n m),где P(n) многочлен степени

Кафедра ОСУ, САОД23 Временная и пространственная сложности алгоритмов можно записать 1/2n 2 + n = O(n 2 ) (1) Но ни в коем случае !!! O(n 2 ) = 1/2n 2 + n (2) Те правая часть – огрубление левой

Кафедра ОСУ, САОД24 Временная и пространственная сложности алгоритмов Некоторые операции с символом О

Кафедра ОСУ, САОД25 Временная и пространственная сложности алгоритмов По аналогии с временной сложностью, определяют пространственную сложность алгоритма, только здесь говорят не о количестве элементарных операций, а о количестве затраченной памяти

Кафедра ОСУ, САОД26 Временная и пространственная сложности алгоритмов На основе O-символики можно классифицировать сложность алгоритмов в зависимости от размера входных данных (n) Постоянные- сложность не зависит от n: O(1) Линейные – сложность O (n) Полиномиальные- сложность O (n m ) Логарифмическая сложность O (log n) Экспоненциальные- сложность O (t f(n) ), t >1 Суперполиномиальные- сложность O (с f(n) ), с- константа, f(n)- функция возрастающая быстрее постоянной, но медленнее линейной

Кафедра ОСУ, САОД27 Временная и пространственная сложности алгоритмов

Кафедра ОСУ, САОД Кафедра ОСУ, САОД28 Временная и пространственная сложности алгоритмов Примеры: Время выполнения алгоритма аггауМах, есть функция O(n). время выполнения алгоритма аггауМах для размера исходных данных n равно максимально a(7n - 2). Используя нотацию большого О для с = 7a, a n0 = 1, можно сделать вывод, что время выполнения алгоритма аггауМах является O(n).

Кафедра ОСУ, САОД Кафедра ОСУ, САОД29 Временная и пространственная сложности алгоритмов Примеры: b

Кафедра ОСУ, САОД Кафедра ОСУ, САОД30 Временная и пространственная сложности алгоритмов Внимание! Нужно осторожно и корректно использовать асимптотические нотации. нотация большого О и аналогичные ей могут привести к ошибочным результатам, если «скрываемые» ими постоянные множители достаточно велики. (например, c= hiding)

Кафедра ОСУ, САОД Кафедра ОСУ, САОД31 Введение Структура данных – общее свойство информационного объекта, с которым взаимодействует та или иная программа. Это общее свойство характеризуется: –множеством допустимых значений данной структуры; –набором допустимых операций; –характером организованности.

Кафедра ОСУ, САОД Кафедра ОСУ, САОД32 Введение Любая структура на абстрактном уровне может быть представлена в виде двойки где D – конечное множество элементов, которые могут быть типами данных, либо структурами данных, R – множество отношений, свойства которого определяют различные типы структур данных на абстрактном уровне.

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

Кафедра ОСУ, САОД Кафедра ОСУ, САОД34 Введение Матрица – структура, у которой множество R состоит из двух отношений линейного порядка. Дерево – множество R состоит из одного отношения иерархического порядка. Граф – множество R состоит из одного отношения бинарного порядка.

Кафедра ОСУ, САОД Кафедра ОСУ, САОД35 Введение Вырожденные (простейшие) структуры данных называются также типами данных. Различают следующие уровни описания данных: –абстрактный (математический) уровень –логический уровень –физический уровень Классификация СД

Кафедра ОСУ, САОД Кафедра ОСУ, САОД36 Введение

Кафедра ОСУ, САОД Кафедра ОСУ, САОД37 Категории типов данных Встроенные типы данных, т.е. типы, предопределенные в языке программирования или языке баз данных. уточняемые типы данных перечисляемый тип данных конструируемый тип (составной)

Кафедра ОСУ, САОД Кафедра ОСУ, САОД38 Категории типов Указательные типы дают возможность работы с типизированными множествами абстрактных адресов переменных, содержащих значения некоторого типа

Кафедра ОСУ, САОД Кафедра ОСУ, САОД39 Встроенные типы данных В современных компьютерах к таким "машинным" типам относятся целые числа разного размера (1-8 байтов)

Кафедра ОСУ, САОД Кафедра ОСУ, САОД40 Встроенные типы данных числа с плавающей точкой одинарной и двойной точности ( 4 и 8 байт соответственно)

Кафедра ОСУ, САОД Кафедра ОСУ, САОД41 Встроенные типы данных Тип CHARACTER (или CHAR) в разных языках - это либо набор символов из алфавита, зафиксированного в описании языка (ASCII), либо произвольная комбинация нулей и единиц, размещаемых в одном байте или 2 байтах

Кафедра ОСУ, САОД Кафедра ОСУ, САОД42 Уточняемые типы данных Type T = min..max; ПРИМЕРЫ Type year = ( ); digit = (0..9); Var y : year; d : digit;

Кафедра ОСУ, САОД Кафедра ОСУ, САОД43 Перечисляемые типы данных TYPE T = (C 1,C 2,...,Cn) где Т идентификатор нового типа, Ci идентификаторы новых констант

Кафедра ОСУ, САОД Кафедра ОСУ, САОД44 Перечисляемые типы данных ПРИМЕРЫ: Type color = (red, yellow, green); destination = (hell, purgatory, heaven); Var c: color; d: destination; … C := red; D := heaven;

Кафедра ОСУ, САОД Кафедра ОСУ, САОД45 Массивы Type t = array [Ti] of To ; Type row = array [1.. 5] of real; Type card = array [1.. 80] of char; Type alfa = array [0.. 15] of char; … Var x: row; С: int x[4] int x[] = { 0, 2, 8, 22}

Кафедра ОСУ, САОД Кафедра ОСУ, САОД46 Массивы : array [n..k] of ;

Кафедра ОСУ, САОД Кафедра ОСУ, САОД47 Массивы var m1:array[-2..2] of real;

Кафедра ОСУ, САОД Кафедра ОСУ, САОД48 Массивы Количество байтов непрерывной области памяти, занятых одновременно вектором (массивом array [n..k] of ), определяется по формуле: ByteSise = ( k - n + 1 ) * Sizeof (тип)

Кафедра ОСУ, САОД Кафедра ОСУ, САОД49 Массивы Обращение к i-тому элементу вектора выполняется по адресу вектора плюс смещение к данному элементу. Смещение i-ого элемента вектора определяется по формуле: ByteNumer = ( i - n ) * Sizeof (тип), а адрес ByteNumber имя + ByteNumber. имя - адрес первого элемента вектора.

Кафедра ОСУ, САОД Кафедра ОСУ, САОД50 Массивы Информация, содержащаяся в дескрипторе вектора, должна позволять, сократить время доступа, (A0 - n*Sizeof(тип) ) обеспечивает проверку правильности обращения (верхняя и нижняя границы массива).

Кафедра ОСУ, САОД Кафедра ОСУ, САОД51 Массивы Var A: array [-5.. 4] of Char дескриптордескриптор может выглядеть

Кафедра ОСУ, САОД Кафедра ОСУ, САОД52 Массивы (многомерные) Var Mas2D : Array [n1..k1, n2..k2] of

Кафедра ОСУ, САОД Кафедра ОСУ, САОД53 Массивы Количество байтов памяти, занятых двумерным массивом, определяется по формуле : ByteSize = (k1-n1+1)*(k2-n2+1) *SizeOf(Тип) Адресом массива является адрес первого байта начального компонента массива.

Кафедра ОСУ, САОД Кафедра ОСУ, САОД54 Массивы Смещение к элементу массива Mas[i1,i2] определяется по формуле: ByteNumber = [(i1-n1)*(k2-n2+1)+(i2-n2)] *SizeOf(Тип) его адрес + ByteNumber

Кафедра ОСУ, САОД Кафедра ОСУ, САОД55 Массивы НапримерНапример: var Mas : Array [3..5] [7..8] of Word; Этот массив будет занимать в памяти: (5-3+1)*(8-7+1)*2=12 байт; а адрес элемента

Кафедра ОСУ, САОД Кафедра ОСУ, САОД56 Массивы для двумерного массива c границами изменения индексов: [B(1)..E(1)][B(2)..E(2)], размещенного в памяти по строкам, адрес элемента с индексами [I(1),I(2)] может быть вычислен как: Addr[I(1),I(2)] = Addr[B(1),B(2)] + { [I(1)-B(1)] * [E(2)-B(2)+1] + [I(2)-B(2)] } *SizeOf(Тип)

Кафедра ОСУ, САОД Кафедра ОСУ, САОД57 Массивы для массива произвольной размерности: Mas[B(1)..E(2)][B(2)..E(2)]...[B(n)..E(n)] получим: Addr[I(1),I(2),...,I(n)]=Addr[B(1),B(2),...B(n)] + Sizeof(Тип)* [B(m)*D(m)] + Sizeof(Тип)* [I(m)*D(m)] (m=1..n) где Dm зависит от способа размещения массива. При размещении по строкам: D(m)=[E(m+1)-B(m+1)+1]*D(m+1), где m = n-1,...,1 и D(n)=1

Кафедра ОСУ, САОД Кафедра ОСУ, САОД58 Массивы При вычислении адреса элемента наиболее сложным является вычисление третьей составляющей формулы, т.к. первые две не зависят от индексов и могут быть вычислены заранее. Для ускорения вычислений множители D(m) также могут быть вычислены заранее и сохраняться в дескрипторе массива

Кафедра ОСУ, САОД Кафедра ОСУ, САОД59 Массивы Дескриптор многомерного массива, таким образом, содержит: начальный адрес массива - Addr[I(1),I(2),...,I(n)]; число измерений в массиве - n; постоянную составляющую формулы линеаризации (первые две составляющие формулы); для каждого из n измерений массива: значения граничных индексов - B(i), E(i); множитель формулы линеаризации - D(i).

Кафедра ОСУ, САОД Кафедра ОСУ, САОД60 Массивы Представление массивов с помощью векторов Айлиффа Для массива любой мерности формируется набор дескрипторов: основного и несколько уровней вспомогательных дескрипторов, называемых векторами Айлиффа Каждый вектор Айлиффа определенного уровня содержит указатель на нулевые компоненты векторов Айлиффа следующего, более низкого уровня, а векторы Айлиффа самого нижнего уровня содержат указатели групп элементов отображаемого массива.Айлиффа

Кафедра ОСУ, САОД Кафедра ОСУ, САОД61 Массивы В Java имеется большое количество классов и интерфейсов для массивов и массивоподобных структур: Arrays, Vector, Collection, Map, Hashtable, LinkedList, ArrayList

Кафедра ОСУ, САОД Кафедра ОСУ, САОД62 Массивы В JDK 5.0 ArrayList был преобразован в универсальный класс с параметром типа. Массив, предназначенный для хранения объектов Employee. ArrayList staff = new ArrayList ();

Кафедра ОСУ, САОД Кафедра ОСУ, САОД63 Записи Запись - конечное упорядоченное множество полей, характеризующихся различным типом данных. type complex = record re: real; im: real end ; var x: complex; C: struct complex { float re; float im; } struct complex x;

Кафедра ОСУ, САОД Кафедра ОСУ, САОД64 Записи struct { float re; float im; } x, y; x=y; … struct { float r; float i; } z;

Кафедра ОСУ, САОД Кафедра ОСУ, САОД65 Записи var rec: record num :byte; { номер студента } name :string[20]; { Ф.И.О. } fac, group:string[7]; math,comp,lang:byte;{оценки} end;

Кафедра ОСУ, САОД Кафедра ОСУ, САОД66 Записи Представление в виде последовательности полей, занимающих непрерывную область памяти АВТФ8В83

Кафедра ОСУ, САОД Кафедра ОСУ, САОД67 Записи в виде связного списка с указателями на значения полей записи

Кафедра ОСУ, САОД Кафедра ОСУ, САОД68 Множества Множество - такая структура, которая представляет собой набор неповторяющихся данных одного и того же типа. type T =set of To Примеры type bitset = set of (0..15); type tapestatus = set of exception; var B : bitset; t : array [1.. 6] of tapestatus;

Кафедра ОСУ, САОД Кафедра ОСУ, САОД69 Множества Множество в памяти хранится как массив битов, в котором каждый бит указывает является ли элемент принадлежащим объявленному множеству или нет. Т.е. максимальное число элементов множества 256, а данные типа множество могут занимать не более 32 байт.

Кафедра ОСУ, САОД Кафедра ОСУ, САОД70 Множества - адрес данного типа множество.

Кафедра ОСУ, САОД Кафедра ОСУ, САОД71 Множества Число байтов, выделяемых для данных типа множества, вычисляется по формуле: ByteSize = (max div 8)-(min div 8) + 1, где max и min - верхняя и нижняя границы базового типа данного множества. Номер байта для конкретного элемента Е вычисляется по формуле: ByteNumber = (E div 8)-(min div 8), номер бита внутри этого байта по формуле: BitNumber = E mod 8

Кафедра ОСУ, САОД Кафедра ОСУ, САОД72 Множества Например, S : set of byte; S:=[15,19]; Содержимое памяти при этом будет –

Кафедра ОСУ, САОД Кафедра ОСУ, САОД73 Указатели Понятие указателя в языках программирования является абстракцией понятия машинного адреса. Подобно тому, как зная машинный адрес можно обратиться к нужному элементу памяти, имея значение указателя, можно обратиться к соответствующей переменной. var ipt : ^integer; cpt : ^char; C: int *ipt; char *cpt;

Кафедра ОСУ, САОД Кафедра ОСУ, САОД74 Динамическая память ( указатели ) Статическое распределение памяти Динамическое распределение памяти Os, Finder б иблиотеки Паскаля Исходный текст Объектный код Область динамического распределения Рекурсивный стек Heap

Кафедра ОСУ, САОД Кафедра ОСУ, САОД75 Указатели Описание переменных типа указатель Type c = array [1..100] of real; Var p1 : ^integer ; p2 : ^real ; p3,p4 : ^c; a, b : integer ; p1 a p2 b p3 p4 p1 := nil ;.. p4 := nil; a := 5; b := 7;

Кафедра ОСУ, САОД Кафедра ОСУ, САОД76 Указатели Процедуры работы с указателями: New ( p )- выделить память в Heap для переменной, на которую указывает p Dispose ( p )-освободить память в Heap, выделенную для переменной, на которую указывает p Var p1, p2, p3: ^integer; begin New ( p1 ); p1^ := 10; New ( p2 ); p2^ := 53; p1 p1^ 10 p2p2^ 53 p1 p2

Кафедра ОСУ, САОД Кафедра ОСУ, САОД77 Указатели p1 := p2; Dispose ( p1 ); Dispose ( p2 ); p1 p p1 p2 p1 p2

Кафедра ОСУ, САОД Кафедра ОСУ, САОД78 Указатели Обмен данными массивов Program DemoPointer; Const n=1000; Type mas = array [ 1..n] of integer; Var p1,p2,p3 : ^mas; i : integer;

Кафедра ОСУ, САОД Кафедра ОСУ, САОД79 Указатели begin New ( p1 ); New ( p2 ); for i :=1 to n do begin Write (Введи,i, эл-т 1-го массива ); Readln (p1^[i]); Write (Введи,i, эл-т 2-го массива ); Readln (p2^[i]) end;

Кафедра ОСУ, САОД Кафедра ОСУ, САОД80 Указатели …. { обмен данными } p3 := p1; p1:= p2; p2 := p3;... Dispose ( p1 );...