рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Структуры и алгоритмы обработки данных

Структуры и алгоритмы обработки данных - раздел Образование, Министерство Образования И Науки Российской Федерации Государственно...

Министерство образования и науки Российской Федерации

Государственное образовательное учреждение высшего

профессионального образования

«Новгородский государственный университет имени Ярослава Мудрого»

Кафедра информационных технологий и систем

 

Структуры и алгоритмы обработки данных

230100.62 – Информатика и вычислительная техника   Лекции

Стандартная постановка задачи

Стандартная постановка задачи

Включает:

  • наименование задачи (схематическое определение);
  • общее описание (краткое изложение задачи);
  • ввод;
  • вывод;
  • ошибки (явно перечислены необычные варианты ввода и указаны те действия, которые предпримет машина в подобных ситуациях);
  • пример (передает сущность задачи и иллюстрирует различные случаи)

 

Шаги процесса программирования

Шаг1

 

 

Шаг 2

 

Шаг 3

 

 

Шаг 4

 


Шаг 5

 

 

 

Шаг 6

 

 

Пример постановки задачи

Ввести три числа и вывести числа в порядке.

 

Пример постановки задачи в стандартной форме

НАЗВАНИЕ

Сортировка трех целых чисел

ОПИСАНИЕ

Ввод и вывод трех чисел, отсортированных от меньшего к большему.

ВВОД

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

ВЫВОД

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

ОШИБКИ

1) Если введено менее трех чисел, программа ждет дополнительного ввода.

2) Строки ввода, кроме первых трех, игнорируются.

3) Если какая-либо из первых трех строк содержит более одного целого числа, то программа завершает работу и выдает сообщение «ОШИБКА ВВОДА – допускается только одно целое число на строке»

ПРИМЕР

Ввод

-3

+17

Вывод

-3 2 +17

 

Алгоритмы и их сложность

Модель вычислений

• Используется однопроцессорная машина с произвольным доступом (random-access machine,RAM), не предусматривающая параллельного выполнения операций;

• n – размер входных данных задачи;

• Емкостная эффективность алгоритма – объем оперативной памяти, затрачиваемой алгоритмом, как функция размера задачи.

• Временная эффективность алгоритма- время, затрачиваемое алгоритмом, как функция размера задачи.

• Т (n) = 3 *n2+2*n

 

Асимптотическая временная эффективность

Используются обозначения: Θ – обозначение; Ο– обозначение;

Правило сумм

 

• Пусть T1(n) и T2(n) – время выполнения двух программных фрагментов P1 и P2, T1(n) имеет степень роста O(f(n)),

• а T2(n)O(g(n)).

• Тогда время последовательного выполнения фрагментов P1 и P2 имеет степень роста O(max(f(n),g(n)))

 

 

Правило произведений

• Пусть T1(n) имеет степень роста O(f(n)),

• а T2(n)O(g(n)).

• Тогда произведение T1(n) * T2(n) имеет степень роста O( f(n)*g(n))

Правила анализа программ

1. Время выполнения операторов присваивания, чтения и записи обычно имеет порядок О(1)

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

Время вычисления логического выражения обычно имеет порядок О(1)

4. Время выполнения цикла является суммой времени всех исполняемых итераций цикла, в свою очередь состоящих из времени выполнения тела цикла и времени вычисления условия прекращения цикла (обычно последнее имеет порядок О(1). Если в программе несколько циклов, время выполнения каждого должно определяться отдельно.

 

Основы анализа программ

Последовательность действий алгоритма определяется входными данными   Например, алгоритм поиска наибольшего элемента в списке из N элементов

Классы входных данных

Необходимо анализировать работу алгоритма на различных наборах данных

 

Наилучший случай

Наилучшим случаем является тот набор данных на котором алгоритм выполняет меньше всего действий

 

Наихудший случай

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

Средний случай

 

Анализ самый сложный.

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

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

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

 

Среднее время работы вычисляется по формуле

 

 

 

Необходимые математические сведения

Округление числа Х влево называется наибольшее целое число, не превосходящее Х. |_ 2,5_| = 2, |_- 7,3_| = -8  

Метод турниров

 

Рекуррентные соотношения

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

Необходимо привести рекуррентные соотношения к замкнутому виду.

Метод подстановок

  Пример 1. Имеем рекуррентное соотношение

Пример анализа алгоритмов

Задание

Оцените эффективность двух приведенных ниже алгоритмов сортировки

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

INSERTION-SORT (A) стоимость число раз

1 forj ← 2 to length [A] с1

2 do keyA[j] с2

3 // добавить A[j] к отсортированной части A[1..j-1] с3=0

4 ij – 1 с4

5 while i > 0 and A[i] > key с5

6 do A[i + 1] ← A[i ] с6

7 ii – 1 с7

8 A[i + 1] ← key с8

 

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

MERGE-SORT (A, p, r)

1 if p < r

2 then q ← | (p + r) /2 |

3 MERGE-SORT(A, p, q )

4 MERGE-SORT(A, q + 1, r )

5 MERGE(A, p, q, r )

 

Вспомогательная процедура MERGE(A, p, q, r ) соединяет два упорядоченных массива в один. Параметрами этой процедуры являются массив А и числа p, q, r, указывающие границы сливаемых участков. Процедура предполагает, что p ≤ q < r и что участки A[p..q} и A[q+1..r] уже отсортированы, и сливает их в один участок A[p..r]

Время работы процедуры MeRGE есть Θ (n ), где n – общая длина сливаемых участков (n= rp +1)

Выполнение операторов программы

Вычисление выражений

Приоритет операций:

↑ (возведение в степень)

+, - (знак)

*, / (умножение, деление)

+, - (сложение, вычитание)

<, >, =, ≤, ≥, ≠ (операции отношения)

Not (записывается также в виде )

And (записывается также в виде )

Or (записывается также в виде )

(логическая импликация)

Пример. Массив Y описан для значений индекса только от 1 до 10.

Значения переменных n= 11, х= 3

Пусть требуется вычислить значение выражения (n ≤ 10 and Y[n]=x )

11 ≤ 10 and Y[11]=3

ложно and(не определено = 3)

ложно andне определено

ложно

 

 

Выполнение оператора присваивания

 

x:= E(x, y,…)

 

Аксиома

х′- значение переменной x до выполнения оператора присваивания

х′′- значение переменной x после выполнения оператора присваивания

x′′ = E(x, y′,…)

y′′ = y

 

Основы доказательства корректности

Формулируется математическая теорема о результатах выполнения сегмента программы:

Если условие V (предусловие) истинно непосредственно перед выполнением сегмента программы, тогда после выполнения сегмента тоже истнинно будет условие P (постусловие)

 

{V} S {P}

 

V есть предусловие для постусловия P по отношению к оператору S

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

Оператор полностью корректный, если для частично корректного оператора доказано, что его выполнение действительно заканчивается.

Правила вывода

5.2.1 Правило вывода Р1 – усиление предусловия и ослабление постусловия

 

 

 

 

5.2.2 Правило вывода А1 – получение предусловия оператора присваивания

{?} x:=E {P}

V = PxE

Чтобы получить предусловие для заданного постусловия Р по отношению к заданному оператору присваивания x:=E , подставим выражение (Е) вместо переменной с именем х всюду, где это имя встечается в постусловии Р.

Правило вывода А2 – Проверка предусловия оператора присваивания

{V} x:=E {P}

Если

То

{V} x:=E {P}

Правило вывода IF1 - Проверка предусловия условного оператора

 

Если

{V and B} S1 {P} и

{V and not B} S2 {P}

то

{V} ifB then S1 else S2 endif {P}

 

5.2.4 Правило вывода IF2 – Получение предусловия условного оператора

 

Если

{V1} S1 {P} и

{V2} S2 {P}

то

{(V1 and B) or (V2 and not B)} ifB then S1 else S2 endif {P}

 

5.2.5 Правило вывода IF3 –Условный оператор

 

Если

{V1} S1 {P} и

{V2} S2 {P}

то

{V1 andV2 }ifB then S1 else S2 endif {P}

 

 

5.2.6 Правило вывода IF4 – Условный оператор

 

Если

{V1 and B} S1 {P} и

{V2 and not B} S2 {P}

то

{V1 and V2 }ifB then S1 else S2 endif {P}

 

5.2.7 Правило вывода S1 – Последовательность операторов

 

Если

{V} S1 {P1} и

{P1} S2 {P}

то

{V} (S1; S2) {P}

 

5.2.8 Правило вывода W1 – Цикл с условием продолжения без инициализации

 

Если

{I and B} S {I}

 

то

{I} while B do S endwhile {I and notB)

 

Условие I называют инвариантом цикла.

 

5.2.9 Правило вывода W2 – Цикл с условием продолжения с инициализацией

Пусть задано условие I (инвариант цикла)

 

Если

{V} инициализация {I} и

{I and B} S {I} и

{I and not B} P

 

то

{V} (инициализация; while B do S endwhile ){P}

 

Чтобы доказать частичную корректность цикла с условием продолжения с помощью праила вывода W2, необходимо:

1. найти инвариант цикла I,

2. доказать, что {V} инициализация {I},

3.доказать, что {I and B} S {I},

4. доказать, что {I and not B} P

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

 

 

5.2.10Правило вывода DC1 – разделяй и властвуй

Если

{V1} S{P1} и

{V2} S {P2}

то

{V1 andV2 } S { P1 andP2 }

 

 

5.2.11Правило вывода DC2 – разделяй и властвуй

Если

{V1} S{P1} и

{V2} S {P2}

то

{V1 orV2 } S { P1 orP2 }

 

5.2.12Правило вывода DC3 – разделяй и властвуй

Если

{V} S{P1} и

{V} S {P2}

то

{V } S { P1 andP2 }

 

 

5.2.13Правило вывода DC4 – разделяй и властвуй

Если

{V} S{P1} и

{V} S {P2}

то

{V } S { P1 orP2 }

 

 

Инвариант цикла

 

Цикл с условием продолжения без инициализации

Если

{I and B} S {I}

то

{I} while B do S endwhile {I and notB)

 

Условие I называют инвариантом цикла.

Численный алгоритм

a:=x; b:=y; c:=0; while b ≠ 0 do {}

End

{ высказывание: a*b+c=x*y и b = 0 дает с = x*y}

Инвариант цикла

I = a*b+c=x*y

Алгоритм 1 – программа перемножения двух натуральных чисел с использованием метода повторных сложений.

Усовершенствованный алгоритм перемножения натуральных чисел

Программа – алгоритм 2

a:=x; b:=y; c:=0;

while b ≠ 0 do

{высказывание: a*b+c=x*y}

{высказывание: b≠0} c:=c+a* (b MOD 10);

a:= a*10;

b:=b DIV 10

End

{ высказывание: a*b+c=x*y и b = 0 дает с = x*y}

Операция Расчет Инвариант цикла Пароль
a:=7; b:=13; c:=0 a=7; b=13; c=0 7*13+0=7*13 b≠0
c:=c+a* (b MOD 10); a:= a*10; b:=b DIV 10 c=0+7* (13 MOD 10)= a= 7*10= b=13 DIV 10 =   b≠0
       
      b=0

 

Усовершенствованный алгоритм перемножения натуральных чисел

Программа – алгоритм 3

a:=x; b:=y; c:=0;

while b ≠ 0 do

{высказывание: a*b+c=x*y}

{ высказывание: b ≠ 0 } ifOdd (b) then c:=c+a;

a:= a*2;

b:=b DIV 2

End

{ высказывание: a*b+c=x*y и b = 0 дает с = x*y}

 

Операция Расчет Инвариант цикла Пароль
a:=7; b:=13; c:=0 a=7; b=13; c=0 7*13+0=7*13 b≠0
ifOdd (b) then c:=c+a a:= a*2 b:=b DIV 2 c = a= b=   b≠0
       
       
      b=0

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

Алгоритм, основанный на динамическом программировании, решает каждую из подзадач единожды и запоминает ответы в специальной таблице. Это позволяет… В типичном случае динамическое программирование применяется кзадачам… У такой задачи может быть много возможных решений; их «качество» определяется значением какого-то параметра, и…

Перемножение нескольких матриц

A1A2×…×An (1) последовательности п матриц (A1, A2, ….., An). Мы будем пользоваться… Будем говорить, что в произведении матрицполностью расставлены, если это произведение либо состоит из…

Задача об умножении последовательности матриц

Дана последовательность из n матриц áA1, A2, ….., Anñ заданных размеров (матрица Ai имеет размер pi-1 х pi); требуется найти такую (полную) расстановку скобок в произведении A1A2 … An , чтобы вычисление произведения требовало наименьшего числа умножений.

 

Количество расстановок скобок

Разобъем матрицы на группы по три: произведение для каждой группы можно вычислить двумя способами, так что для 3 n матриц есть не менее 2n… Шаг 1: строение оптимальной расстановки скобок Мы должны описать строение оптимальных решений. Для задачи об умножении последовательности матриц это выглядит…

Предполагается

на входе последовательность   length[p] = n+1

Когда применимо динамическое программирование

Для задач, решаемых методом динамического программирования, характерны два признака:

  • оптимальность для подзадач;
  • перекрывающиеся подзадачи.

 

Оптимальность для подзадач

Задача обладает свойством оптимальности для подзадач, если оптимальное решение задачи содержит оптимальные решения ее подзадач.

Перекрывающиеся подзадачи

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

Наибольшая общая подпоследовательность

Последовательность Z =z1,z2,…,zk

называется подпоследовательностью последовательности X = x1,x2,…,xn , если существует строго возрастающая последовательность индексов i1,i2,…,ik , для которой

при всех j = 1, 2, … k.

Пример

Z = B, C, D, B является подпоследовательностью последовательности

X = A, B, C, B, D, A, B ; cоответствующая последовательность индексов есть 2,3,5,7 .

Последовательность Z является общей подпоследовательностьюпоследовательностей X и Y , если Z является подпоследовательностью как X так и Y .

 

Задача о наибольшей подпоследовательности (задача НОП)

Найти общую подпоследовательность наибольшей длины для двух данных последовательностей X и Y.

Решение перебором вариантов

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

Алгоритм будет работать экспоненциальное время, так как последовательность длины m имеет 2m подпоследовательностей.

Строение наибольшей общей подпоследовательности

Теорема 1.

1) если xm = yn, то zk =xm = yn и Zk-1является НОП для Xm-1 и Yn-1; 2)если xm ≠ yn, и zk ≠ xm , то Z является НОП для Xm-1 и Y. 3)если xm ≠ yn и zk ≠ yn , то Z является НОП для Xm и Yn-1.

Рекуррентная формула

Видно, что возникает перекрытие подзадач. Чтобы найти НОП нам может понадобиться найти НОП и НОП ; каждая из этих задач… Обозначение

Then return

3 ifb[i,j] ¬ “ ”

4 thenPRINT-LCS (b,X, i-1, j-1)

5 напечатать xi

6 elsif b[i,j] =“ ↑ ”

7 then PRINT-LCS (b,X, i-1, j)

8 else PRINT-LCS (b,X, i, j-1)

 

Время работы процедуры порядка О (m+n)

 

Жадные алгоритмы

Для многих оптимизационных задач есть более простые и быстрые алгоритмы, чем динамическое программирование. Некоторые задачи можно решать с помощьюжадных алгоритмов.

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

Задача о выборе заявок

Пусть даны пзаявок на проведение занятий в одной и той же аудитории. Два разных занятия не могут перекрываться по времени. В каждой заявке указаны начало и конец занятия ( si, и fi для i-й заявки). Разные заявки могут пересекаться, и тогда можно удовлетворить только одну из них. Мы отождествляем каждую заявку с промежутком [si, fi), так что конец одного занятия может совпадать с началом другого, и это не считается пересечением.

Формально говоря, заявки с номерами i и jсовместны, если интервалы [si, fi), и [sj, fj), не пересекаются

Задача о выборе заявок состоит в том, чтобы набрать максимальное количество совместных друг с другом заявок.

Жадный алгоритм работает следующим образом. Мы предполагаем, что заявки упорядочены в порядке возрастания времени окончания:

f1 £ f2 £ . . . £ fn

Если это не так, то можно отсортировать их за время O(n log n) заявки с одинаковым временем конца располагаем в произвольном порядке. Тогда алгоритм выглядит так (f и s -массивы ):

GREEDY-ACTIVITY-SELECTION (s,f)

1 n ¬ length [s]

2 A ¬ { 1}

3 j ¬ 1

4 for i ¬ 2 to n

5 do if si ³ fj

6 then A ¬ A È {i}

7 j ¬ i

8return A

 

Алгоритм требует всего Q (n) шагов

Правильность алгоритма

Доказательство. Заявки отсортированы по возрастанию времени окончания. Прежде всего докажем, что существует оптимальное решение задачи о выборе заявок, содержащее заявку номер 1 (с самым…

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

 

Абстрактный тип данных (АТД) можно рассматривать как средство расширения языков программирования.

Каждый АТД включает в себя два компонента:

1) тип данных;

2) операции, определенные для этого типа данных.

АТД – спецификация нового, ранее не существующего типа.

 

9.1 АТД «Список»

Список представляет последовательность элементов определенного типа, который в общем случае будем обозначать как elementtype.

a1,a2,…,an, где n ≥0

a1 – первый элемент списка

an – последний элемент списка

n – длина списка

Обозначения

L - список объектов типа elementtype

x – объект этого типа

p – позиция элемента в списке

• Функция END (L) возвращает позицию, следующую за позицией n в n- элементном списке L.

Операции над списками

1. Оператор INSERT ( x,p,L) – вставляет объект x в позицию p в списке L. Если в списке L нет позиции p, то результат этого оператора не определен.

2. Функция LOCATE (x,L) – возвращает позицию первого объекта x в списке L. Если объекта x нет в списке L, то возвращается END(L).

3. Функция RETRIEVE (p,L) – возвращает элемент, который стоит в позиции p в списке L. Результат не определен, если в списке L нет позиции p, или если p= END(L).

4. Оператор DELETE ( p,L) – удаляет элемент в позиции p списка L. Результат не определен, если в списке L нет позиции p, или если p= END(L).

5. Функции NEXT(p, L) и PREVIOUS(p,L) – возвращают соответственно следующую и предыдущую позиции от позиции p в списке L. Функция NEXT не определена, если p= END(L). Функция PREVIOUS не определена, если p= 1. Обе функции не определены, если в списке L нет позиции p.

6. Функция MAKENULL (L) – делает список L пустым и возвращает позицию END(L).

7. Функция FIRST (L) – возвращает первую позицию в списке L. Если список пустой, то возвращается позиция END(L).

8. Оператор PRINTLIST ( L) – печатает элементы списка L в порядке их расположения.

9.2 АТД «Стек»

Стек – специальный тип списка, в котором все вставки и удаления выполняются только на одном конце, называемом вершиной

Добавление элемента, называемое также проталкиванием (push), возможно только в вершину стека (добавленный элемент становится первым сверху). Удаление элемента, называемое также выталкиванием (pop), тоже возможно только из вершины стека, при этом второй сверху элемент становится верхним.

 

Реализация стеков массивами

• stak – массив, используемый для организации стека;

• stksiz – размер массива;

• stktop – указатель вершины стека;

• data - данные;

• pr – признак успешности операции

 

Включить в стек

• begin • {vkl} • if stktop >= stksiz then pr:=false

Массив

Первый способ представляет очередь в виде массива и двух целочисленных переменных start и end.

Обычно start указывает на голову очереди, end — на элемент, который заполнится, когда в очередь войдёт новый элемент. При добавлении элемента в очередь в q[end] записывается новый элемент очереди, а end уменьшается на единицу. Если значение end становится меньше 1, то мы как бы циклически обходим массив и значение переменной становится равным n. Извлечение элемента из очереди производится аналогично: после извлечения элемента q[start] из очереди переменная start уменьшается на 1. С такими алгоритмами одна ячейка из n всегда будет незанятой (так как очередь с n элементами невозможно отличить от пустой), что компенсируется простотой алгоритмов.

Преимущества данного метода: возможна незначительная экономия памяти по сравнению со вторым способом; проще в разработке.

Недостатки: максимальное количество элементов в очереди ограничено размером массива. При его переполнении требуется перевыделение памяти и копирование всех элементов в новый массив.

Связный список

Второй способ основан на работе с динамической памятью. Очередь представляется в качестве линейного списка, в котором добавление/удаление элементов идет строго с соответствующих его концов.

Преимущества данного метода: размер очереди ограничен лишь объёмом памяти.

Недостатки: сложнее в разработке; требуется больше памяти; при работе с такой очередью память сильнее фрагментируется; работа с очередью несколько медленнее.

Реализация с помощью массива

Занести в очередь

• procedure QUEINS(var QUEUE:massiv; QUESIZ:integer; var QUEF, QUER:integer; DATA:integer; var PR:boolean);

• begin

• if (QUEF=QUER+1) or ((QUEF=1) and (QUER=QUESIZ)) then PR:=false

• else

• begin

• PR:=true;

• QUEUE[QUER]:= DATA;

• QUER:=QUER+1;

• if (QUER > QUESIZ)) then QUER:=1

• end;

• end;

 

Исключить из очереди

• procedure QUEDEL(var QUEUE:massiv; QUESIZ:integer; var QUEF, QUER:integer; var DATA:integer; var PR:boolean);

• begin

• if (QUEF=QUER) then PR:=false

• else

• begin

• PR:=true;

• DATA := QUEUE[QUEF]

• QUEF:=QUEF+1;

• if (QUEF > QUESIZ)) then QUEF:=1

• end;

• end;

Инициализация очереди

• procedure QUEINT(var QUEUE:massiv; QUESIZ:integer; var QUEF, QUER:integer; var PR:boolean);

• begin

• var I:integer;

• PR:=true;

• QUEF:=1;

• QUER:=1;

• for I:=1 to QUESIZ do QUEUE[I]:=0;

• end;

 

Множества

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

Хеширование

Хеширование применяется для сравнения данных: если у двух массивов хеш-коды разные, массивы гарантированно различаются; если одинаковые — массивы,… Существует множество алгоритмов хеширования с различными свойствами…

Словари

Абстрактый тип множеств с операторами MAKENULL, INSERT, DELETEиMEMBERназывается DICTIONARY(Словарь)

Реализация словарей

  Оператор Способ реализации словаря INSERT O(N) O(1) O(N) …   Прямая адресацияприменяется, когда количество возможных значений невелико

Словари, основанные на хеш-таблицах

Элемент с ключом k записывается в позицию номер h(k) в хеш-таблице (hash table) T[0..m-1],

где h:U ® {0, 1, …, m-1} – хеш-функция.

 

Коллизия – совпадение хеш-значений двух разных ключей.

Разрешение коллизий:

  • с помощью цепочек (открытое хеширование);
  • открытая адресация (закрытое хеширование).

 

Анализ хеширования с цепочками

Пусть T – хеш-таблица с m позициями, в которую занесено n элементов/ Коэффициент заполнениятаблицы α = n / m Худший случай – θ (n)

Ключи как натуральные числа

Хеш – функции

Деление с остатком

h(k) = k mod m

Умножение

 

Универсальное хеширование

Открытая адресация

Все записи хранятся в самой хэш-таблице. Каждая ячейка таблицы содержит либо элемент динамического множества, либо NIL. h:U × {0, 1, …, m-1} ® {0, 1, …, m-1} Последовательность испробованных мест для данного ключа k имеет вид

Поиск слова в тексте

Нечисленный алгоритм

Поиск слова в тексте

текст: array[0..m-1] of character слово: array[0..n-1] of character i:=0; j:=0;

Сортировка

Дан массив A из n элементов: , Будем считать, что с каждым элементом (помимо другой информации, не влияющей на сортировку) связан ключ . На…

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

InsertionSort (list, N) list - сортируемый список элементов N - число элементов в списке

Корневая сортировка

RadixSort (list, N) List сортируемый список элементов N число элементов в списке

Пирамидальная сортировка

Пирамидальная сортировка (англ. Heapsort, «Сортировка кучей») — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за Θ(n log n) операций при сортировке n элементов. Количество применяемой служебной памяти не зависит от размера массива (то есть, O(1)).

· сконструировать пирамиду

· for i = 1 to N do

· скопировать корень пирамиды в список

· переформировать пирамиду

· end for

Переформирование пирамиды

FixHeap (list, root, key, bound)

List сортируемый список / пирамида

Root номер корня пирамиды

key ключевое значение, вставляемое в пирамиду

bound правая граница (номер) в пирамиде

vacant = root

while 2 * vacant < = bound do

largerChild = 2 * vacant

// поиск наибольшего из двух непосредственных потомков

if ( largerChild < bound ) and ( list [largerChild + 1 ] > list [largerChild ] then

largerChild = largerChild + 1

end if

// находится ли ключ выше текущего потомка?

if key > list [largerChild ] then

// да, цикл завершается

break

else

// нет, большего непосредственного потомка следует поднять

list [ vacant ] = list [largerChild ]

vacant = largerChild

end if

end while

list [ vacant ] = key

 

 


Построение пирамиды

for i = N / 2 down to 1 do

FixHeap {list, i, list [ i ], N )

end for

 

Окончательный алгоритм

for i = N / 2 down to 1 do

FixHeap {list, i, list [ i ], N )

end for

for i = N down to 2 do

max = list [ i ]

FixHeap (list, i, list [ i ], i - 1 )

List [ i ] = max

end for

 

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

Пример сортировки слиянием. Сначала делим список на кусочки (по 1 элементу), затем сравниваем каждый элемент с соседним, сортируем и объединяем. В… Для решения задачи сортировки эти три этапа выглядят так: Сортируемый массив разбивается на две части примерно одинакового размера;

Управление с помощью таблиц

Операция читать_лит – читает очередную литеру анализируемого текста и выдает код, класс литеры. В начале каждого выполнения переменная след_литера имеет своим значением…  

Графы

В математической теории графов и информатике граф — это совокупность непустого множества вершин и множества пар вершин (связей между вершинами).

Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.

Неориентированный граф G= (V, E) состоит из конечного множества вершин V и множества ребер E.

Ориентированный граф G= (V, E) состоит из конечного множества вершин V и множества дуг E.

Дуга – ориентированное ребро, представитма в виде упорядоченной пары вершин ( v, w ), где вершина v называется началом, а вершина w - концом дуги.

Способы представления графа

Матрица смежности

Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) — это квадратная матрица A размера n, в которой значение элемента aij равно числу рёбер из i-й вершины графа в j-ю вершину.

Иногда, особенно в случае неориентированного графа, петля (ребро из i-й вершины в саму себя) считается за два ребра, то есть значение диагонального элемента aii в этом случае равно удвоенному числу петель вокруг i-й вершины.

Матрица смежности простого графа (не содержащего петель и кратных ребер) является бинарной матрицей и содержит нули на главной диагонали.

Матрица инцидентности

Матрица инцидентности — одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина). Столбцы матрицы соответствуют ребрам, строки — вершинам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их инцидентность).

В случае ориентированного графа каждому ребру <x,y> ставится в соответствие "-1" на позиции (x,y) и "1" на позиции (y,x); если связи между вершинами нет, то ставится в соответствие "0".

14.1.3Список рёбер

Список рёбер — это тип представления графа, подразумевающий, что каждое ребро представляется двумя числами — номерами вершин этого ребра.

Алгоритмы обхода графа

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

Обход графа входит как составная часть во многие алгоритмы.

Алгоритмы используют представление графа G=(V,E) или с помощью списка смежных вершин или с помощью матрицы связности (смежности).

Поиск в ширину

Пусть задан граф G=(V,E) и фиксированная начальная вершина s. Алгоритм поиска в ширину перечисляет все достижимые из вершины в порядке… Расстояние – число ребер кратчайшего пути.

Задача о кратчайшем пути

Дан ориентированный взвешенный граф G=(V,E) с вещественной весовой функцией w:ER.

Весом пути p = áv0,v1,…,vkñ называется сумма весов ребер, входящих в этот путь:

 

Вес кратчайшего пути из u в v равен , по определению,

 

Кратчайший путь из u в v – это любой путь p из u в v, для которого w(p)= d (u,v) .

Варианты задачи о кратчайшем пути

Кратчайшие пути из одной вершины: дан взвешенный граф G=(V,E) и начальная вершина s; требуется найти кратчайшие пути из s во все вершины vÎV.

Кратчайшие пути в одну вершину: дана конечная вершина t, требуется найти кратчайшие пути в t из всех вершин vÎV.

Кратчайший путь между данной парой вершин: даны вершины u и v, найти кратчайший путь из u в v.

Кратчайшие пути для всех пар вершин:для каждой пары вершин u и v, найти кратчайший путь из u в v.

 

Ребра отрицательного веса

При наличии ребер отрицательного веса важно, есть ли циклы отрицательного веса.

Если из вершины s можно добраться до цикла отрицательного веса, для вершин этого цикла не существует кратчайших путей (-¥).

Если циклов отрицательного веса нет, то любой цикл можно выбросить, не удлиняя пути.

 

Представление кратчайших путей в алгоритме

По завершении работы алгоритма цепочка предшественников, начинающаяся с произвольной вершины v, будет представлять кратчайший путь из s в v.   Ориентированный подграф предшествования Gp=(Vp,Ep), определенный так:

Свойство оптимальности для подзадач

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

Релаксация

Для каждой вершины vÎ V мы храним некоторое число d[v], являющееся верхней оценкой веса кратчайшего пути из s в v (далее будет использоваться… Начальное значение оценки кратчайшего пути и массива p устанавливается… INITIALIZE-SINGLE-SOURCE (G,s)

Алгоритм Дейкстры

Предполагается, что граф задан с помощью списков смежных вершин. В процессе работы алгоритма поддерживается множество S Í V, состоящее… Алгоритм выбирает вершину uÎ V \ S с наименьшим d[u], добавляет u к множеству S и производит релаксацию всех…

Оценка времени работы алгоритма Дейкстры

Если очередь с приоритетами реализована как массив, стоимость операции EXTRACT-MIN есть O(V).

Алгоритм делает ô V ô таких операций.

Суммарная стоимость всех удалений из очереди есть O(V2).

Оценим стоимость остальных операций.

Каждая вершина vÎ V добавляется к множеству S только один раз, и каждое ребро из Adj[v] обрабатывается тоже один раз. Общее количество элементов во всех списках смежных вершин есть ô E ô; стоимость каждой релаксации есть O(1).

Поэтому стоимость прочих операций есть O(E).

Общая стоимость алгоритма есть O(V2 + E).

 

Пример исполнения алгоритма Дейкстры

Исходный граф

 

 

Шаг 1

 

 

 

Шаг 2

 

 

 

Шаг 3

 

 

Шаг 4

 

 

 

Шаг 5

 

 

 

Алгоритм Беллмана-Форда

Алгоритм возвращает значение TRUE, если в графе нет цикла отрицательного веса, достижимого из исходной вершины, и FALSE, если таковой цикл… В первом случае алгоритм находит кратчайшие пути и их веса; во втором случае… Алгоритм производит релаксацию ребер, пока все значения d[v] не сравняются с d( s,v).

Задача перекресток

Задача

Необходимо создать программу для управления светофорами на сложном перекрестке дорог.

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

Затем с каждой группой сопоставим соответствующий режим работы светофоров на перекрестке.

Желательно минимизировать число разбиений исходного множества поворотов.

 

 

Пример перекрестка

 

 
E
C
B
A
D

Для построения модели этой задачи можно применить математическую структуру – граф.

Вершины графа – повороты, а ребра соединяют вершины повороты, которые нельзя выполнять одновременно.

 

 

 

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

При такой раскраске несовместимым поворотам будут соответствовать вершины, окрашенные в разные цвета.

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

Возможные подходы к решению.

Первый подход

Перебор всех возможных вариантов раскраски (для не слишком больших графов).

Второй подход

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

Третий подход

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

 

Максимальный поток

Максимальный поток

Если (u,v) Ï E мы полагаем c(u,v)=0 В графе выделены две вершину: исток s и сток t . Предполагаем, что в графе нет «бесполезных» вершин (каждая вершина лежит на каком-то пути из истока в сток)

Метод Форда-Фалкерсона

 

Основные понятия: остаточные сети, дополняющие пути и разрезы.

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

FORD-FOLKERSON_METHOD (G,s,t)

1 положить поток f равным 0

2 while (пока) существует дополняющий путь p

3 do дополнить f вдоль p

4 return f

 

Остаточные сети

 

Пусть G=(V,E) - сеть с истоком s и стоком t. Пусть f - поток в этой сети. Для любой пары вершин u и v рассмотрим остаточную пропускную способность из u в v, определяемую как

cf(u,v) = c(u,v) - f(u,v)

Сеть Gf=(V,Ef) , где

Ef = {(u,v) Î V´V : cf(u,v) >0 }

назовем остаточной сетью сети G , порожденной потоком f. Ее ребра, называемые остаточными ребрами, допускают положительный поток.

Остаточное ребро не обязано быть ребром сети

 

 

 

Пример потока

 

 

Остаточная сеть

Дополняющие пути

Пусть f - поток в сети G=(V,E). Назовем дополняющим путем простой путь из истока s в сток t в остаточной сети Gf.

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

cf(p) = min { cf(u,v) : (u,v) Î p}

 

Разрезы в сетях

Разрезом сети G=(V,E) называется разбиение множества V на две части S и T=V\S, для которых s ÎS и t Î T.

Пропускной способностью разреза (S,T) называют сумму пропускных способностей пересекающих разрез ребер.

Минимальным разрезом называется разрез ниаменьшей пропускной способности (среди всех разрезов данной сети)

 

 

 

Пример разреза

Теорема (о максимальном потоке и минимальном разрезе)

 

Пусть f – поток в сети G=(V,E). Тогда следующие утверждения равносильны:

1. Поток максимален в сети G.

2. Остаточная сеть Gf не содержит дополняющих путей.

3. Для некоторого разреза (S,T) сети G выполнено равенство ô f ô = c(S,T)

Общая схема алгоритма Форда-Фалкерсона

 

FORD-FULKERSON (G,s,t)

1 for (для) каждого ребра (u,v) Î E[G]

2 do f[u,v] ¬ 0

3 f[v,u] ¬ 0

4 while в остаточной сети Gf существует путь p из s в t

5 do cf(p) ¬ min{cf(u,v): (u,v) входит в p}

6 for (для) каждого ребра (u,v) пути p

7 do f[u,v] ¬ f[u,v] + cf(p)

8 f[v,u] ¬ -f[u,v]

 

Пример исполнения алгоритма

 

рис а

 

 

рис б

 

 

 

рис в

 

 

 

рис г

 

 

 

рис д

 

Анализ алгоритма Форда-Фалкерсона

 

Время работы зависит от того, как ищется путь.

Если величина потока будет расти все более мелкими шагами, алгоритм может вообще не остановиться.

 

Если выбирать дополняющий путь при помощи поиска в ширину, то алгоритм работает полиномиальное время.

Эта реализация метода Форда-Фалкерсона, называется алгоритмом Эдмондса-Карпа и имеет время работы O(VE2)

 

Минимальные покрывающие деревья

Минимальные покрывающие деревья

Задача

Необходимо соединить n контактов на печатной плате, затратив провод минимальной длины.

Упрощенная математическая модель

Пусть имеется связный неориентированный граф G=(V,E), в котором V – множество контактов, а E – множество их возможных попарных соединений. Для… Задача состоит в нахождении подмножества T Ì E, связывающего все…  

Построение минимального покрывающего дерева

Дан связный неориентированный граф G=(V,E) и весовая функция w:ER.

Общая схема алгоритмов.

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

Ребро (u,v) добавляемое на очередном шаге, выбирается так, чтобы не нарушить этого свойства:

AÈ {(u,v)} тоже должно быть подмножеством минимального остова. Такое ребро называется безопасным ребром для A.

 

GENERIC-MST(G,w)

1 A ¬ Æ

2 while (пока) A не является остовом

3 do найти безопасное ребро (u,v)для A

4 A ¬ AÈ {(u, v)}

5 return A

Определения

Разрезом (S,V\S) неориентированного графа G=(V,E) называется разбиение множества его вершин на два подмножества.

 

 

 

Говорят, что ребро (u,vE пересекает разрез (S,V\S), если один из его концов лежит в S, а другой - в V\S.

Разрез согласован с множеством ребер A, если ни одно ребро из A не пересекает этот разрез.

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

Теорема

Доказательство. Пусть T- минимальный остов, содержащий A. Предположим, что T не содержит ребра… Покажем, что существует другой минимальный остов T¢ , содержащий AÈ {(u,v)}, так что ребро (u,v), является…

Следствие

Пусть G=(V,E) - связнвый неориентированный граф и на множестве E определена весовая функция w. Пусть A - множество ребер графа, являющееся подмножеством некоторого минимального остова. Рассмотрим лес GA=(V,A) . Пусть дерево C - одна из связных компонент леса GA. Рассмотрим все ребра графа, соединяющие вершины из C с вершинами не из C, и возьмем среди них ребро наименьшего веса. Тогда это ребро безопасно для A.

Доказательство

Разрез (C,V\C), согласован с A, а ребро (u,v) - легкое ребро для этого разреза.

Алгоритм Крускала

Пусть (u,v) - такое ребро, соединяющее вершины из компонент C1 и C2. Это ребро является легким ребром для разреза (C1,V\ C1), и можно… Алгоритм Крускала использует структуры данных для непересекающихся множеств.… FIND-SET(u) - возвращает представителя множества, содержащего элемент u.

Оценка времени работы

Инициализация O(V)

Упорядочение ребер (строка 4) – O(E log E)

Далее производится O(E) операций, занимающих в совокупности O(E log E).

Общее время работы алгоритма Крускала O(E log E).

 

Алгоритм Прима

В алгоритме Прима растущая часть остова представляет собой дерево (множество ребер которого есть A). Формирование дерева начинается с произвольной… Алгоритм получает на вход связный граф G и корень r минимального покрывающего… Множество ребер строящегося дерева явно не хранится; его можно восстановить как

Минимальные покрывающие деревья

 

Рис. 24.1 Минимальное покрывающее дерево. На каждом ребре графа указан вес. Выделены ребра минимального покрывающего дерева (суммарный вес 37). Такое дерево не единственно: заменяя ребро (b,c) ребром (a,h), получаем другое дерево такого же веса 37.

 

 

Generic-MST(G,w)

1 A ← Ø

2 while (пока) A не является остовом

3 doнайти безопасное ребро (u,v) для А

4 А ← А U {(u,v)}

5 return A

Теорема 24.1 Пусть G=(V,E) – связный неориентированный граф, на множестве вершин которого определена вещественная функция w. Пусть А – множество ребер, являющееся подмножеством некоторого минимального остова графа G. Пусть (S,V\S)- разрез графа G, согласованный с А, а (u,v)-легкое ребро для этого разреза. Тогда ребро (u,v) является безопасным для А

Алгоритм Крускала

 

MST-Kruskal(G,w)

1 A ← Ø

2 for(для) каждой вершины vЄV[G]

3 doMake-Set(v)

4 упорядочить ребра Е по весам

5 for(для) (u,v) ЄЕ (в порядке возрастания веса)

6 do ifFind-Set(u) ≠ Find-Set(v)

7 thenА ← А U {(u,v)}

8 Union(u,v)

9 return A

 

Алгоритм Прима

 

MST-Prim(G,w,r)

1 Q ← V[G]

2 for(для) каждой вершины u Є Q

3 dokey [u] ←∞

4 key [r] ←0

5 π [r] ←NIL

6 whileQ ≠ Ø

7 dou←Exstract-Min(Q)

8 for(для) каждой вершины v Є Adj[u]

9 do ifv Є Q и w(u,v) < key[v]

10 then π [v] ←u

11 key[v] ← w(u,v)

 

Поиск в глубину

Так делается, пока не обнаружены все вершины, достижимые из исходной. Если после этого остаются необнаруженные вершины, можно выбрать одну из них и… Обнаружив впервые вершину v, смежную с u, мы отмечаем это событие, помещая в поле p [v] значение u.

Классификация ребер

 

Ребра графа делятся на несколько категорий в зависимости от их роли при поиске в глубину.

Пусть мы провели поиск в глубину на графе G и получили лес Gp.

1. Ребра деревьев(tree edges) – это ребра графа .

2. Обратные ребра (Back edges) – это ребра (u,v ), соединяющие вершину u с ее предком v в дереве поиска в глубину. Ребра-циклы, возникающие в ориентированных гоафах, считаются обратными ребрами.

3. Прямые ребра (Forward edges) соединяют вершину с ее потомком, но не входят в дерево поиска в глубину.

4. Перекрестные ребра (Cross edges) – все остальные ребра графа.

Пример исполнения алгоритма DFS

Пример графа

3/6
3/6
3/6
3/6
3/6
3/6
3/6
 
u
v
w
x
y
z
 
 
 
 
 
 

Шаг1

 
3/6
3/6
3/6
3/6
3/6
3/6
3/6
1/
 
 
 
 
 
x
y
z
u
v
w

 

Шаг 2

 
3/6
3/6
3/6
3/6
3/6
3/6
3/6
1/
2/
 
 
 
 
x
y
z
u
v
w

Шаг 3

 

 

 
3/6
3/6
3/6
3/6
3/6
3/6
3/6
1/
2/
 
 
3/
 
x
y
z
u
v
w  

 

Шаг 4

 
3/6
3/6
3/6
3/6
3/6
3/6
3/6
1/
2/
 
4/
3/
 
x
y
z
u
v
w

 

Шаг 5

 
3/6
3/6
3/6
3/6
3/6
3/6
3/6
1/
2/
 
4/
3/
 
x
y
z
u
v
w
B

 

Шаг 6

 
3/6
3/6
3/6
3/6
3/6
3/6
3/6
1/
2/
 
4/5
3/
 
x
y
z
u
v
w
B

Шаг 7

 
3/6
3/6
3/6
3/6
3/6
3/6
3/6
1/
2/
 
4/5
3/6
 
x
y
z
u
v
w
B

Шаг 8

 

 
3/6
3/6
3/6
3/6
3/6
3/6
3/6
1/
2/7
 
4/5
3/6
 
x
y
z
u
v
w
B

 

Шаг 9

 
3/6
3/6
3/6
3/6
3/6
3/6
3/6
1/
2/7
 
4/5
3/6
 
x
y
z
u
v
w
B
F

Шаг 10

 
3/6
3/6
3/6
3/6
3/6
3/6
3/6
1/8
2/7
3/6
4/5
3/6
3/6
x
y
z
u
v
w
B
F

 

 

Шаг 11

 

 

 
3/6
3/6
3/6
3/6
3/6
3/6
3/6
1/8
2/7
9/
4/5
3/6
 
x
y
z
u
v
w
B
F

 

Шаг 12

 

 
3/6
3/6
3/6
3/6
3/6
3/6
3/6
1/8
2/7
9/
4/5
3/6
 
x
y
z
u
v
w
B
F
C

 

Шаг 13

 

 
3/6
3/6
3/6
3/6
3/6
3/6
3/6
1/8
2/7
9/
4/5
3/6
10/
x
y
z
u
v
w
F
B
C

 

Шаг 14

 
3/6
3/6
3/6
3/6
3/6
3/6
3/6
1/8
2/7
9/
4/5
3/6
10/
x
y
z
u
v
w
F
B
C
B

Шаг 15

 

 
3/6
3/6
3/6
3/6
3/6
3/6
3/6
1/8
2/7
9/
4/5
3/6
10/11
x
y
z
u
v
w
F
B
C
B

Шаг 16

 

 
3/6
3/6
3/6
3/6
3/6
3/6
3/6
1/8
2/7
9/12
4/5
3/6
10/11
x
y
z
u
v
w
F
B
C
B

 

 

Топологическая сортировка

Пусть имеется ориентированный граф G=(V,E) без циклов (directed acyclic graf).

Задача о топологической сортировке (topological sort) этого графа состоит в следующем: надо указать такой линейный порядок на его вершинах, что любое ребро ведет от меньшей вершины к большей (в смысле этого порядка)

 

Алгоритм топологической сортировки

 

TOPOLOGICAL-SORT (G)

1. вызвать DFS(G) , при этом

2. завершая обработку вершины

( DFS-VISIT, строка 8),

добавлять ее в начало списка

3. вернуть построенный список вершин

 

Топологическая сортировка выполняется за время Θ (V + E), потому что столько времени занимает поиск в глубину, а добавлять каждую из | V | вершин к списку можно за время O(1).

Деревья

Деревья

Рекурсивные процедуры обхода деревьев

Прямой обход

procedurePREODER (n: узел);

Begin

(1) Занести в список обхода узел n;

(2) for для каждого сына с узла n в порядке слева направо do PREORDER (c )

end; { PREODER}

 

Симметричный обход

procedureINODER (n: узел);

Begin

ifn - лист then

занести в список обхода узел ;

else begin

INORDER (самый левый сын узла n);

занести в список обхода узел n;

for для каждого сына с узла n, исключая

самый левый, порядке слева направо do

INORDER ( c )

end

end; { INODER}

 

Операторы АТД, основанные на деревьях:

 

1.PARENT (n, T)

2. LEFTMOST_CHILD (n, T)

3. RIGHT_SIBLING (n, T)

4. LABEL (n, T)

5. CREATi (v, T1,T2,…Ti)

6. ROOT( T)

7. MAKENULL ( T)

 

АВЛ-деревья

Московские математики Г.М.Адельсон-Вельский и Е.М.Ландис предложили схему самобалансирующегося поискового дерева. Для балансировки дерева требуется… Высота дерева – длина наибольшего пути в этом дереве. Вершина дерева называется сбалансированной, если высота ее левого и правого поддерева отличается не более чем на 1. …

– Конец работы –

Используемые теги: структуры, Алгоритмы, обработки, данных0.071

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Структуры и алгоритмы обработки данных

Что будем делать с полученным материалом:

Если этот материал оказался полезным для Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Еще рефераты, курсовые, дипломные работы на эту тему:

Структуры данных и алгоритмы их обработки
Структуры данных и алгоритмы их обработки... Лабораторный практикум...

Общее понятие о базах данных. Основные понятия систем управления базами данных. Модели данных. 10
Сетевые технологии обработки данных Компоненты вычислительных сетей... Принципы организации и основные топологии вычислительных сетей Принципы... Сетевой сервис и сетевые стандарты Средства использования сетевых сервисов...

Лекция 3. Формулы Шеннона и Хартли. Расчёт количества Информации. Кодирование символьных, графических и звуковых данных. Структуры данных
Информации Кодирование символьных графических и звуковых данных Структуры данных Формула... Log log... Основные свойства логарифмов...

КУРС ЛЕКЦИЙ ПО ИНФОРМАТИКЕ Тема: Базы данных, Банки Данных, Системы Управления Базами Данных — СУБД
ГОУ ВПО ВОЛОГОДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Факультет промышленного менеджмента...

Алгоритм и требования к алгоритму свойства алгоритма
Object Inspector Options goEditing True... StringGrid FexedCols Rows n... Var I J integer Begin...

Информации. Кодирование символьных, графических и звуковых данных. Структуры данных
Информации Кодирование символьных графических и звуковых данных Структуры данных Формула... Log log... Основные свойства логарифмов...

Разработка алгоритмов и программ выполнения операций над последовательными и связанными представлениями структур данных
Дуги орграфов образуют неупорядоченные списки. Орграфы задаются неупорядоченными списками смежных вершин - номеров вершин, в которые ведут ребра из… Особенности представления данных Последовательное представление данных… Таким образом, для каждого графа должно вводится в общей сложности N нолей.

Компьютерные данные: типы данных, обработка и управление
Реляционная модель данных. 5 Заключение: Порядок выполнения практической работы 1. Компьютерные данные: типы данных, обработка и управление… Точность - это способность выполнить задачи без погрешностей или ошибок. Данную характеристику можно трактовать еще и так: - это степень соответствия меры к определенному стандарту.…

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

0.036
Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • По категориям
  • По работам