Учебные материалы (Практические занятия, контрольные задания, конспект лекций) / Практические занятия / Практическое занятие 6

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ №4.

“Сложность вычислительных процедур”

Введение. Рассмотрим задачу сортировки (упорядочения) чисел:

Пусть дан список чисел: [1,6,8,3,4,2]. Требуется расположить эти числа в порядке неубывания (возрастания). Собственно, сам алгоритм вовсе не обязан быть оптимальным и служит лишь целям иллюстрации. Наш алгоритм будет таким.

1. Найти минимальное число в списке и поставить его на первое место.

2. Все полученные к данному моменту минимальные числа далее в процессе сортировки не участвуют.

3. Повторять шаги 1,2, пока не останется не отсортированных чисел.

Чтобы оценить сложность этой процедуры, заметим, что при поиске очередного минимального числа из n чисел мы производим (n-1) сравнение. Пусть в исходном списке N чисел. Тогда мы последовательно произведем число сравнений, равное (N-1)+(N-2)+(N-3)+…+ 2=N*(N-1)-(1+2+3+…+N-1)=N*(N-1)-(N-1)*(N-2)/2= (N-1)*(N-(N-2)/2) =O(N²).

Обозначение O(N²) указывает, что мы имеем дело с функцией одного порядка что и N² .

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

Разумеется, можно использовать различные системы кодировки. Этот вопрос нас пока не будет интересовать.

В рассмотренной задаче о сортировке списка размер задачи равен числу элементов списка – N.

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

Определение. Алгоритм называется эффективным с вычислительной точки зрения, если и только если его вычислительная сложность есть некоторый полином от размера задачи.

Мы видим, что приведенный выше алгоритм сортировки является эффективным с вычислительной точки зрения.

Дадим пример неэффективного алгоритма. Пусть даны символы

+, 6, -, =, 5,8,7

Спрашивается, можно ли разместить эти символы последовательно так, чтобы получилось верное арифметическое равенство?

Очевидно, простейший алгоритм будет просто перебирать все варианты, пока не найдет что-нибудь типа такого:

6-5+7=8.

Здесь N=7. Но сколько же варbантов переберет алгоритм? Очевидно, в среднем 0.5*N!

Здесь N! читается как N- факториал и вычисляется по формуле

N!= N*(N-1)*(N-2)*(N-3)*…*2*1.

Теорема. N! имеет порядок, не сравнимый ни с одним полиномом от N.

Доказательство. Пусть это не так и пусть k –порядок некоторого полинома сравнимого с N!. Тогда, согласно математическому представлению сравнимости имеем

Lim_N N!/N^k не существует. В самом деле, возьмем логарифм от N!/N^k : Ln(N!/N^k)=

N+(N-1)+(N-2)+…+1- N*k=O(N²)-N*k. Поскольку N стремится к бесконечности, то никакое целое k не может обеспечить сравнимости O(N²)-N*k и, следовательно, предела нет.

Полученный результат в математике известен как проклятие размерности, а алгоритмы подобного типа называются экспоненциальными (что является эквивалентном неэффективности). Для некоторых задач до настоящего времени так и не нашли эффективных алгоритмов. К числу таких задач относится задача ВЫПОЛНИМОСТЬ.

Задания.

1. Разработайте алгоритм для определения того, является ли число N простым или составным.

(Идея – последовательно делить N на 2,3,4,5,6,7…, N^0.5 ). Какова сложность такого алгоритма?

1+2+3+…+ N^0.5= N^0.5*(N^0.5-1)*0.5.

Из этого следует, что число делений растет приблизительно как функция порядка N. Однако хитрость в том, что для представления N нужна запись размера m порядка logN, т.е. m= logN. Вычислительная сложность определяется как функция от размера записи задачи. В нашем случае получаем оценку вычислительной сложности в виде

N^0.5*(N^0.5-1)*0.5= (10^m) ^0.5*((10^m)^0.5-1)*0.5 . Эта функция имеет порядок 10^m и заведомо превосходит любой полином от m.

2. Доказать, что 10^m имеет порядок, не сравнимый ни с каким полиномом от m при m  бесконечность.

3. Разработайте алгоритм для определения того, содержится ли данная подстрока в строке. Например, строка есть aaabbbcccabcaccbaccb а подстрока – cba. В данном случае вхождение имеет место. Вопрос: каков размер задачи в этом случае, как он определяется? (ответ – как сумма размеров строки и подстроки). Придумайте алгоритм и укажите его сложность.

4. Пусть дана схема соединения городов дорогами. Нарисуйте какую-нибудь собственную схему, причем город будет отображаться кружком, а дорога – отрезком, соединяющим два города. Пусть у вас будет 6-8 городов и 10-12 дорог (порядок проводки которых определите самостоятельно). Разработайте алгоритм и оцените его сложность, с помощью которого можно найти путь из одного города в другой.

5. Пусть имеются замены для букв

1. b

2. c

3. d

4. a

С помощью этих замен можно из слова aabd получить слово сссс. Для этого мы используем следующую схему

aabd -> bbbd -> ccca -> cccb -> cccc

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

a -b

a -e

b-c

b-a

c-d

d-a

e-b

Например, теперь из aaa можно вывести dba.

Разработайте алгоритм, который на входе получает два слова и правила замены букв. Вопрос: можно ли из первого слова получить второе с помощью данной системы подстановок. Какова сложность такого алгоритма?