Тип данных.Структура данных.Абстрактный тип данных (АТД).

Информатика Алгоритмы и структуры данных Программирование Основные термины Тип данных. Структура данных. Абстрактный тип данных (АТД). Основные термины Тип данных. Структура данных. Абстрактный тип данных (АТД). … Тип данных определяет множество значений и операции над ними… + способ размещения данных в памяти. Структура данных определяет способ хранения/размещения элементов данных в памяти и связи между ними. АТД – определяет совокупность операций, способ реализации не учитывается (описывает что нужно сделать, но не декларирует как). Примеры АТД Вектор… Список… Дерево… ? Список разделов курса АиСД 1. 2. 3. 4. 5. 6. 7. Вводная часть. Базовые понятия. Анализ алгоритмов. Линейные структуры данных. Деревья, графы, многосвязные списки. Сортировка. Поиск (сбалансированные деревья, хеш-таблицы). Алгоритмы на графах. Строковые алгоритмы. Литература Романов Е. Л. - Практикум по программированию на C++. Ахо А.В., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. Вирт Н. Алгоритмы+структуры данных = программы. Кнут, Д. Э. Искусство программирования. Седжвик Р. Фундаментальные алгоритмы на С++. Анализ. Структуры данных. Сортировка. Поиск. Каррано Ф.М., Причард Дж. Абстракция данных и решение задач на C++. Стены и зеркала. АНАЛИЗ АЛГОРИТМОВ Критерии оценки эффективности: Временная сложность измеряется количеством операций совершаемых для решения поставленной задачи. Пространственная сложность – это объем затраченной алгоритмом памяти. Различают оценки в лучшем, худшем и среднем случае. Для оценки в среднем требуется модель входного потока. При значительном увеличении объема входных данных вклад постоянных множителей и слагаемых низших порядков становится ничтожным. Поэтому обычно используют асимптотические оценки: O-большое – верхняя асимптотическая оценка;  (омега большое) – нижняя;  (тетта)– верхняя и нижняя (асимптотически точная). Пример f (n) ( g (n)) C2  g (n) f (n)  O( g (n)) f ( n) C  g (n) f (n) ( g (n)) f ( n) f ( n) C1  g (n) n C  g (n) n n Определения Пусть f(n) и g(n) – положительные функции положительного аргумента. f (n) ( g (n)) : C  0, n0  0 : (n  n0 ) f (n)  C  g (n) f (n) ( g (n)) : C  0, n0  0 : (n  n0 ) C  g (n)  f (n) f (n) ( g (n)) : C1  0, C2  0, n0  0 : (n  n0 ) C1  g (n)  f (n)  C2  g (n) Запись O(g(n)) обозначает класс функций, таких, что все они растут не быстрее, чем функция g(n) с точностью до постоянного множителя. Основные правила асимптотического анализа 1. Постоянный множитель отбрасывается:(C  f (n))  ( f (n)), где C – константа. 2. Оценка сложности произведения или частного: ( g (n)  f (n))  ( f (n)) ( g (n)), ( g (n) / f (n))  ( f (n)) / ( g (n)). 3. Оценка сложности суммы: ( g (n)  f (n))  max[( f (n)), ( g (n))]. Наиболее распространенные классы сложности: O(1) – константная сложность; O(n) – линейная сложность; O(log(n)) – логарифмическая сложность; O(n2) – квадратичная сложность; O(nc) –полиномиальная сложность, где c – константа (c> 1); O(cf(n)) – экспоненциальная сложность, где c – константа (c> 1), f(n) –полиномиальная функция; O(n!) – факториальная сложность. В логарифмических оценках основание логарифма не указывают, это связанно со следующим свойством: log b ( x) log a ( x)  log b (a) Способы записи алгоритмов 1. 2. 3. 4. Описание на естественном языке. Графически: блок-схемы, UML-диаграммы и т.п. Псевдокод. Язык программирования. i  1, n i  1, n j  1, n j  i, n … … а Рисунок 2.3. Вложенные циклы. б Начало function(n) нет n 1 … … да Конец Рисунок 2.4. Пример рекурсии. n function     2 … … Начало Начало func1(n) нет n 1 func1 n  1 func2(n) нет func2  n  1 n 1 да да Конец Конец а б Рисунок 2.5. Примеры рекурсии. func2  n  1 Схемы структур данных Для наглядной иллюстрации на схемах и используются стрелки. Стрелки проводятся из ячеек указателей, курсоров или ссылок к данным на которые они указывают (ссылаются) Линейные структуры данных и АТД с линейным порядком элементов Массивы - последовательности однотипных элементов расположенных непосредственно друг за другом. 1 n 1 ... 2 int a[3]; int *a= new int[3]; a int a[3][3]; a[0][0] a[0][1] a[0] a[1] a[0][2] a[1][0] Двумерный массив – массив массивов. a[2] a[2][2] Списки (связные списки) - последовательности элементов размещенных в памяти произвольным образом и связанных указателями, которые определяют логический порядок. Односвязный список. head tail Двусвязный список. head Циклический список. Стек - линейная последовательность элементов, добавление и удаление в которую осуществляется с одного конца, называемого вершиной. Операторы: PUSH(x, S) – помещает значение x в стек S; POP(S) – извлекает элемент из стека S; TOP(S) – возвращает значение элемента в вершине стека S; CLEAR(S) – удаляет все элементы из стека S; ISEMPTY(S) – возвращает значение «истина» если стек S пустой, «ложь» в противном случае. POP(S ) x PUSH( x, S ) x Стек может быть эффективно реализован с помощью массива: Зафиксировав «дно» стека как начало массива, можно использовать курсор или указатель top, определяющий положение вершины. 1 ... top Последний элемент Первый элемент n Реализация стека с помощью массива. Очередь - линейная последовательность элементов, добавление с одного конца – заднего (rear), а удаление с другого – переднего (front). ENQUEUE(x, Q) – помещает значение x в очередь Q; DEQUEUE(Q) – извлекает элемент из очереди Q; FRONT(Q) – возвращает значение первого элемента очереди Q; ENQUEUE( x, Q) DEQUEUE(Q) x Работа с очередью. Реализация с помощью массива: процедуру увеличения индекса на единицу определим так: i  i mod n  1 rear front 1 ... Первый элемент front rear n Последний элемент 1 ... Последний элемент n Первый элемент а) б) Реализация очереди с помощью «циклического массива». Дек - двусторонняя очередь, позволяет добавлять и удалять элементы с обоих концов. PushBack( x, D) PopBack( D) PushFront( x, D) PopFront( D) Двусторонняя очередь.