Методы программирования и прикладные алгоритмы: Учебное пособие
– СПб.: Санкт-Петербургский государственный университет аэрокосмического приборостроения, 2007. – 166 с.Учебное пособие представляет собой курс лекций, многие годы читающийся студентам, обучающимся по направлениям «Информационная безопасность», «Информационные системы», «Информатика и вычислительная техника» в Санкт-Петербургском государственном университете аэрокосмического приборостроения и в Санкт-Петербургском государственном политехническом университете.Предназначено для студентов специальн.
– СПб.: Санкт-Петербургский государственный университет аэрокосмического приборостроения, 2007. – 166 с.Учебное пособие представляет собой курс лекций, многие годы читающийся студентам, обучающимся по направлениям «Информационная безопасность», «Информационные системы», «Информатика и вычислительная техника» в Санкт-Петербургском государственном университете аэрокосмического приборостроения и в Санкт-Петербургском государственном политехническом университете.Предназначено для студентов специальности 090104, а также может быть использовано для самостоятельной работы при выполнении заданий по НИР.Содержание:Введение в разработку и анализ алгоритмов.Вычисление веса двоичного вектора. Коды, сохраняющие разность. Методы построения алгоритмов. Этапы построения алгоритмов. Методы частных целей, подъема вверх и отрабатывания назад. Рекурсия. Методы декомпозиции и композиции. Эвристические алгоритмы. Методы анализа алгоритмов Классы алгоритмов. Решение рекуррентных уравнений. Контрольные задачи. Методы исчерпывающего поиска Исчерпывающий поиск. Динамическое программирование. Метод ветвей и границ. Методы решета. Приближение исчерпывающего поиска. Книга «Методы программирования и прикладные алгоритмы: Учебное пособие» авторов Овчинникова А., Крук Е.А. оценена посетителями КнигоГид, и её читательский рейтинг составил 0.00 из 10.
Для бесплатного просмотра предоставляются: аннотация, публикация, отзывы, а также файлы для скачивания.
Крук Е.А., Овчинников А.А. Методы программирования и прикладные алгоритмы: Учебное пособие
– СПб.: Санкт-Петербургский государственный университет аэрокосмического приборостроения, 2007. – 166 с.
Учебное пособие представляет собой курс лекций, многие годы читающийся студентам, обучающимся по направлениям «Информационная безопасность», «Информационные системы», «Информатика и вычислительная техника» в Санкт-Петербургском государственном университете аэрокосмического приборостроения и в Санкт-Петербургском государственном политехническом университете.
Предназначено для студентов специальности 090104, а также может быть использовано для самостоятельной работы при выполнении заданий по НИР.
Содержание:
Введение в разработку и анализ алгоритмов.
Вычисление веса двоичного вектора.
Коды, сохраняющие разность.
Методы построения алгоритмов.
Этапы построения алгоритмов.
Методы частных целей, подъема вверх и отрабатывания назад.
Рекурсия.
Методы декомпозиции и композиции.
Эвристические алгоритмы.
Методы анализа алгоритмов
Классы алгоритмов.
Решение рекуррентных уравнений.
Контрольные задачи.
Методы исчерпывающего поиска
Исчерпывающий поиск.
Динамическое программирование.
Метод ветвей и границ.
Методы решета.
Приближение исчерпывающего поиска.
Методы программирования и прикладные алгоритмы. Учебное пособие СанктПетербург 2007
Единственный в мире Музей Смайликов
Самая яркая достопримечательность Крыма
Скачать 2.32 Mb.
x
g
x
1
x
2
x
3
x
g
k
k
k
k
m
m
m
x
x
g —1
k
а)
)
kg m
/
Рис. 1.2. Представления вектора x в ячейках памяти
13
Выбор способа представления данных, однако, может осуществ- ляться не только в зависимости от того, что нам важнее в данной реализации: минимально используемая память или максимально короткое время выполнения. Этот выбор может зависеть и от то- го, какие именно операции нам необходимо совершать. Возможно эти операции можно эффективно выполнять и с данными, пред- ставленными в компактной форме, без извлечения их из общего массива m-ячеек. В качестве примера такой оптимизации опера- ций рассмотрим следующую задачу.
Задача 1.2 . Пусть даны два вектора: x = (x
1
, . . . , x g
), y =
(y
1
, . . . , y g
), где x i
, y i
∈ . Необходимо определить,
выполняется ли неравенство g
i=1
|x i
− y i
| ≤ t,
(1.5)
где t — некоторое неотрицательное целое число.
Выражение (1.5) может быть использовано, например для оцен- ки похожести наборов x и y. Вычисление суммы в (1.5) с уче- том размещения элементов x i
и y i
в отдельных ячейках состоит из g m-битных вычитаний, и временная сложность может быть оценена как O(mg) (битовых операций). В случае компактного представления векторов временная сложность будет выше за счет необходимости дополнительных битовых операций. Каким обра- зом можно уменьшить временную сложность вычисления (1.5)
при компактном представлении? Для этого введем в рассмотрение понятие кодов, сохраняющих разности.
Определение 1.3
Расстоянием Хэмминга d(x, y) между двумя векторами x =
(x
1
, . . ., x n
) и y = (y
1
, . . . , y n
) назовем число позиций, в которых эти векторы не совпадают.
Определение 1.4
Весом Хэмминга W (x) назовем число ненулевых позиций век- тора x.
14
Из определений 1.3 и 1.4 очевидно, что d(x, y) = W (x − y).
(1.6)
Определение 1.5
Назовем (N, n, t)-кодом, сохраняющим разности, такое отоб- ражение множества целых чисел i ∈ в двоичные векторы > длины n, для которого
1. d(a i
, a j
) = |i − j|, если |i − j| ≤ t,
2. d(a i
, a j
) > t, если |i − j| > t.
Пример (8,4,1)-кода, сохраняющего разности, приведен в сле- дующей таблице:
i
10
i
2
a i
0 000 0000 1
001 0001 2
010 0011 3
011 0111 4
100 0110 5
101 1110 6
110 1100 7
111 1101
Как можно использовать код, сохраняющий разности, для реше- ния нашей задачи? Будем хранить в памяти (компактно) не дво- ичные представления i
2
десятичных чисел i
10
, а соответствующее кодовое слово a i
. Тогда для хранения потребуется O(ng/m) ячеек памяти. В этом случае оценка неравенства (1.5) может быть эф- фективно получена следующим образом. Вычислим W (x ⊕ y), где x и y представлены описанным способом с помощью кода, сохра- няющего разности, ⊕ — означает операцию побитового исключа- ющего ИЛИ (операция XOR), W (·) — хэммингов вес полученной суммы. Обозначим десятичное значение элементов > вектора x через (10)
i
>, а их представление в коде, сохраняющем разности
15
— через (a)
i
>. Тогда с учетом (1.6)
W (x ⊕ y) =
g i=1
W (x
(a)
i
⊕ y
(a)
i
) =
g i=1
d(x
(a)
i
, y
(a)
i
).
Расстояние d(x
(a)
i
, y
(a)
i
) в точности равно |x
(10)
i
− y
(10)
i
|, если аб- солютное значение этой разности не превышает t и больше t в противном случае. Отсюда следует, что неравенство (1.5) выпол- няется тогда и только тогда, когда выполняется неравенство
W (x ⊕ y) ≤ t.
(1.7)
Приведем пример. Пусть x = (1, 2, 3, 4), y = (1, 2, 3, 5), t = 1.
Очевидно, неравенство (1.5) выполняется. Представление векто- ров x, y с помощью кодов, сохраняющих разности x = (0001|0011|0111|0110),
y = (0001|0011|0111|1110).
Тогда x ⊕ y = (0000|0000|0000|1000),
W (x ⊕ y) = 1 ≤ t,
и неравенство (1.5) также выполняется с учетом (1.7).
Теперь, пусть y = (1, 2, 5, 3). Тогда неравенство (1.5) не выпол- няется, а вычисление (1.7) дает x ⊕ y = (0000|0000|1001|0001),
W (x ⊕ y) = 3 > t,
и неравенство (1.7) также не выполнено.
Таким образом, заменили представление элементов векторов x и y, и нашли способ вычислять неравенство (1.5) в этом но- вом представлении. Заметим, что при вычислении (1.7) не нужно выделять отдельные элементы векторов, сложение (XOR) может
16
быть осуществлено сложением m-битных ячеек памяти. Для вы- числения веса Хэмминга может быть использован алгоритм с ло- гарифмической сложностью, описанный в подразд. 1.1. Тогда, вы- числение неравенства (1.5) требует O(ng/m) ячеек памяти, O(ng)
битовых операций для вычисления x ⊕ y, и O(log ng) операций для вычисления веса, т.е. общая временная сложность составит
O(ng+log ng) ∼ O(ng). Выигрыш во времени по сравнению с базо- вой схемой вычисления (которая давала сложность O(mg)) будет достигаться в случае, если n 2 3 4 5 6 7 8 9