Элементарные и неэлементарные операции

 

Пример: цикл for – это неэлементарная операции языка.

int a[10];

int s = 0;

for (int i = 0; i < 10 & & a[i] % 10! = 5; i++) s += a[i];

 

Массив – это неэлементарный тип, в данном примере его представитель a.

int – это элементарный тип, в данном примере его представитель s.

Элементарная операция присваивания (инициализации): s = 0.

for – это неэлементарная операция, состоящая из операций присваивания (i = 0), двух операций сравнения, и т. д.

 

Представление типов

 

Целые числа – двоичное представление.

 

Простые элементарные операции: сложение, вычитание, присваивание и т.д.

 

Сложные элементарные операции: целочисленное умножение, деление (не на степень двойки), переход.

 

Приведём пример кода:

if (x > 0) t = 1;

else t = 0;

Этот код выполнится выполняется намного медленнее, чем t = x > 0; (потому что для t = x > 0; есть машинная команда).

 

Инварианты. Индуктивные функции

Индуктивное программирование. Индуктивные функции

 

Пусть имеется множество M. Пусть аргументами функции f будут последовательности элементов множества M, а значениями – элементы множества N.

 

Тогда, если её значение на последовательности x₁, x₂, ..., x_n можно восстановить по её значению на последовательности x₁, x₂, ..., x_n-1 и x_n, то такая функция называется индуктивной.

 

Пример: Если мы хотим найти наибольшее значение среди всех элементов последовательности, то функция maximum индуктивна, т.к. maximum (x₁, x₂, ..., x_n) = max (maximum (x₁, x₂, ..., x_n-1), x_n)

 

Инварианты и предикаты алгоритма

 

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

int m = a[0];

for (int i = 1; i < N; i++)

{

if (a[i] > m) m = a[i];

}

Предикат: ∀ i < N: m_i есть наибольшее значение из элементов a[0]... a[i], т.е. m_i = maximum.

∀ – это квантор общности.

 

Абстракции. Интерфейс абстракции

Понятие абстракции

 

Как только появляются объекты, появляются абстракции – механизм разделения сложных объектов на более простые, без деталировки подробностей разделения.

 

Функциональная абстракция – разделение функций, методов, которые манипулируют с объектами, с их реализацией.

 

Интерфейс абстракции – набор методов, характерных для данной абстракции.

 

Пример: абстракция массива

 

1) create – создать массив (статический или динамический).

int a[100]; // статический

int *b = calloc(100, sizeof(int)); // динамический

int *c = new int[100]; // динамический

2) destroy – удалить массив (статический или динамический).

free(b);

delete c; // можно и delete [] c

3) fetch – обратиться к элементу массива.

int q1 = a[i];

int q2 = b[i];

int q3 = c[i];

 

Для массива основная операция – это доступ к элементу. Она выглядит одинаково для всех представлений.

 

Абстракция “стек”

 

Одна из удобных абстракций – стек.

 

Стек должен предоставлять нам методы:

1) create – создание стека (может быть, потребуется аргумент, определяющий максимальный размер стека);

2) push – занесение элемента в стек (размер стека увеличивается на единицу, занесённый элемент становится вершиной стека);

3) pop – извлечь элемент, являющийся вершиной стека и уменьшить размер стека на единицу (если стек пуст, то значение операции не определено);

4) peek – получить значение элемента, находящегося на вершине стека, не изменяя стека (если стек пуст, значение операции не определено);

5) empty – предикат истинен, когда стек пуст;

6) destroy – уничтожить стек.

 

Абстракция “множество”

 

Множество – это совокупность однотипных элементов, на которых определена операция сравнения.

 

Множество обозначается списком значений внутри фигурных скобок.

 

Пустое множество: s = {}.

 

Множество должно предоставлять нам методы:

 

1) insert – добавление элемента в множество.

{1, 2, 3}.insert(5) -> {1, 2, 3, 5}

{1, 2, 3}.insert{2} -> {1, 2, 3}

2) remove – удалить элемент из множества.

{1, 2, 3}.remove(3) -> {1, 2}

{1, 2, 3}.remove(5) -> не определено.

3) in – определить принадлежность множеству.

{1, 2, 3}.in(2) -> true

{1, 2, 3}.in(5) -> false

4) size – определить количество элементов в множестве.

 

Рекурсия. Принцип разделяй и властвуй

Числа Фибоначчи. Рекуррентная форма

 

{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...}

 

Рекуррентная форма определения:

 

Много алгоритмов первично определяются рекуррентными зависимостями.

 

Рекуррентность и рекурсия

 

Рекуррентная форма -> рекурсивный алгоритм.

int fibo(int n)

{

if (n == 0) return 0;

if (n == 1) return 1;

return fibo(n-1) + fibo(n-2);

}

 

Три вопроса:

1) корректен ли он?

2) как оценить время его работы?

3) как его ускорить?

 

Дерево вызовов функции для n = 5

 

 

Оценка времени вычисления алгоритма

 

Пусть t(n) – количество вызовов функции для аргумента n.

 

t(0) = 1

t(0) > F₀

t(1) = 1

t(1) = F₁

 

Для n > 1:

t(n) = t(n - 1) + t(n - 2) ≥ F_n

 

Оценка требуемой для исполнения памяти

 

Каждый вызов функции создаёт новый контекст функции или фрейм вызова.

 

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

 

Максимально создаётся количество фреймов, равное глубине рекурсии.

 

Сложность алгоритма по занимаемой памяти равна O(N).

 

⇐ Предыдущая1234Следующая ⇒

Поделиться: