Лекція 3. Побудова алгоритмів

3.1 Оценка (подсчет) итераций.

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

При подсчете итераций сумма называется арифметической прогрессией и равна .

Основным способом вычисления сумм рядов является метод математической индукции (от простого – к сложному). Это метод математического доказательства истинности некоторого утверждения (выражения) от натурального аргумента. Например, если утверждение истинно, то истинным должно быть и выражение для случая итераций. Т.е.

.

 

3.2 Элементы комбинаторики и работа со строками.

Чтобы ответить на вопрос "сколько?", не выполняя подсчета, пользуются комбинаторикой.

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

Например, если в некоторой строке фигурируют все 33 буквы украинского алфавита, то количество всех возможных подстрок из символов можно вычислить так: . Если имеем дело с бинарной строкой, получим выражение .

Перестановка. При перестановке элементов строки предполагается, что каждый из символов должен встречаться только 1 раз. Тогда для строки из различных символов имеем перестановок.

При перестановке -подстрок справедливо выражение . Например, для строки имеем 6 2-перестановок. Когда порядок следования элементов подстрок не важен, пользуются формулой вычисления сочетаний . Так для строки имеем 3 сочетания 2-элементных подстрок.

Например, при работе с текстом часто приходится находить фрагменты, совпадающие с образцом (для осуществления автозамены). Соответствующие алгоритмы работы со строками принято называть алгоритмами сопоставления строк или StringMatching-алгоритмами.

Постановка задачи поиска подстроки по образцу формализуется следующим образом:

– проверяемый текст представим массивом , где – длина массива;

– образец (шаблон) – массивом , где ;

– элементами массивов являются символы конечного алфавита . Например, или ;

Массивы и называют строками. также называют подстрокой.

При решении такой задачи говорят, что образец встречается в тексте со сдвигом или с позиции , если

 

и . (3.1)

 

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

Существуют различные алгоритмы решения такой задачи: алгоритм Рабина-Карпа, Кнута-Морриса-Пратта и др. Наиболее простой – наивный алгоритм поиска подстрок:

Вычислительная асимптотическая сложность такого алгоритма составляет .

 

3.3 Построение алгоритмов.

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

Пусть имеем две квадратные матрицы размером – и , где . Тогда элементы искомой матрицы вычисляют по следующей формуле: .

Псевдокод алгоритма перемножения матриц представляют следующим образом:

По причине того, что каждый из циклов в тройной вложенности циклов for выполняется ровно раз, а выполнение строки 6 занимает константное время, асимптотическую вычислительную сложность такой реализации можно представить выражением .