23

Алгоритмы и сложность вычислений. 1

Введение 1

49. Определение нормальных алгоритмов Маркова. 3

50. Определение Машины Тьюринга. 6

Q 7

51. Определение частично рекурсивных функций. Основные функции. 9

52. Определение частично рекурсивных функций. Основные операции. 9

53. Определение частично рекурсивных функций. 9

54. Алгебраически неразрешимые проблемы. 9

55. Задачи Р- сложные. Полиномиально сложные задачи. 9

56. NP-проблемы. Экспоненциально сложные задачи. 9

57. Связь NP-проблем с Р-проблемами. 9

МНОГОЗНАЧНЫЕ ФУНКЦИИ 9

ФУНКЦИИ ШЕННОНА И ИХ ОЦЕНКИ 11

1. Матрицы Адамара и их свойства. 18

2. Матрицы Силъвестра-Адамара их свойства. 19

3. Преобразования Уолша-Адамара булевых функций. 20

4. Преобразование Фурье булевой функции. 25

5. Схема Грина быстрых преобразований Уолша и Фурье. 28

6. Критерий нелинейности булевых функций. 29

7. Расстояние до линейных структур. 32

8. Порядок нелинейности. 33

9. Совершенно нелинейные функции. 33

10. Расстояние до аффинных функций и корреляция. 35

11. Булевы функции от нечетного числа аргументов. 37

Алгоритмы и сложность вычислений.

Введение

Слово алгоритм (или алгорифм) происходит от имени арабского математика (из Хорезма Мохаммеда ибн Мусы Альхваризми (IX в.), из трактата которого Европа в XII в. познакомилась с позиционной системой счисления и с арифметическими действиями над числами в таких системах. В связи с этим и само понятие алгоритма ассоциировалось в начале с искусством счета. Постепенно понятие алгоритма деформировалось и к началу XX в. под алгоритмом стали понимать четко определенную процедуру решения некоторого класса задач. Конечно, приведенное пояснение не может служить определением понятия алгоритма. Однако, таким весьма туманным понятием алгоритма математики довольствовались вплоть до XX в., пока не появилась необходимость в доказательстве отсутствия алгоритмов для решения некоторых классов задач. Дело в том, что к началу XX в. в математике накопилось много задач алгоритмического характера не поддававшихся решению, несмотря на многочисленные усилия математиков. Примером может служить известная 10-я проблема Гильберта сформулированная им в докладе “Математические проблемы”, произнесенном в 1900 году на II Международном конгрессе математиков в Париже. Эта проблема заключалась в нахождении способа, позволяющего за конечное число операций установить, разрешимо ли произвольно заданное алгебраическое уравнение с целыми коэффициентами в целых числах или нет. Наличие таких задач зарождало у математиков идею о доказательстве отсутствия алгоритмов их решения. Результаты об отсутствии алгоритмов решения задач теми или иными ограниченными средствами к тому времени уже были. Например, было известно, что задачи трисекции угла, удвоения куба и т. д. неразрешимы с помощью циркуля и линейки. Однако теперь речь шла об отсутствии алгоритма вообще. Для решения такого рода задач необходим был новый качественный скачок в математике. А именно, нужно было дать точное определение понятия алгоритма, поскольку невозможно доказать отсутствие чего-то туманного и расплывчатого.

Задача определения алгоритма была решена в 30-х годах XX в, в ра­ботах математиков и логиков Гильберта, Гёделя, Чёрча, Клини, Поста и Тьюринга. Было дано несколько разных определений понятия алгорит­ма. При этом Гильберт, Гёдель, Чёрч и Клини подошли к понятию алго­ритма через вычислимые арифметические функции, а Пост и Тьюринг - через сведение алгоритма к элементарным преобразованиям слов в ко­нечных алфавитах.

Второй подход к определению алгоритма был использован в 40-х годах и советским математиком А. А. Марковым (1903—1979). Определенные им алгоритмы получили название нормальных алгоритмов Мар­кова.

Прежде чем дать строгое определение алгоритма, математики проанализировали известные примеры алгоритмов и выделили наиболее общие их свойства. Для выявления этих свойств рассмотрим и мы пов­нимательнее, например, хорошо известный из курса алгебры алгоритм Евклида нахождения наибольшего общего делителя двух натуральных чисел. В нем предписывается делить с остатком 1-е число на 2-е, затем 2-е на полученный (первый) остаток, затем 1-Й остаток на 2-й оста­ток и т. д. до тех пор, пока не получится остаток, равный нулю. Послед­ний, не равный нулю, остаток и будет искомым наибольшим общим де­лителем. В итоге любая пара натуральных чисел a, b преобразуется в число d, равное их наибольшему общему делителю:

a, b -> d.

Характерными свойствами алгоритма Евклида являются:

1) массовость—алгоритм может быть применен к любой паре натуральных чисел, причем сама схема работы алгоритма не зависит от ис­ходных данных (в любом случае дели 1-е число на 2-е и т. д.);

2) дискретность-весь алгоритм можно разбить на отдельные элементарные операции (шаги алгоритма), которые могут быть занумеро­ваны натуральными числами в порядке их выполнения;

3) детерминированность - каждый шаг алгоритма однозначно определяется его предыдущими шагами;

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

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

На примере алгоритма Евклида просматриваются не только общие черты алгоритма вообще, но и упомянутые выше два подхода к общему определению алгоритма. А именно, с одной стороны, это вычисление значений некоторой числовой функции двух переменных о. 6.. а с другой—преобразование одной последовательности символов (цифр чисел а и b, разделенных запятой) в другую последовательность (цифр числа d).

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

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

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

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

49. Определение нормальных алгоритмов Маркова.

§ 1. НОРМАЛЬНЫЕ АЛГОРИТМЫ

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

Определение 1. Схемой нормального алгоритма в алфавите

называется упорядоченная последовательность

(1)

слов в алфавите где - слова в алфавите , а есть слово или При этом слово схемы (1) называется ее -й формулой с левой частью и правой частью .

Формула называется простой, если есть и заключительной, если есть

Действие НА на слово в алфавите описывается следующим определением.

Определение 2. Пусть - слово в алфавите и хотя бы одно из слов является его подсловом. Элементарным преобразованием слова по нормальному алгоритму со схемой (1) называется замена в первого вхождения слова с наименьшим номером словом Если результатом указанного элементарного преобразования является слово то пишут т. е. или .