1.Введение

1.1.Предмет и цель курса лекций.

Предмет курса – элементарная теория сложности алгоритмов.

Данное учебное пособие представляет собой семестровый курс лекций. В этом курсе проведено изложение и сравнение основных базовых формальных схем алгоритмов: алгорифм Маркова, детерминированная и недетерминированная машина Тьюринга, оракульная машина Тьюринга и др. На основе этих формализмов и понятий сводимости проанализированы соотношения сложностей и построена иерархия сложности наиболее известных классов задач.

Учебная программы семестра – 32 часа лекций и 16 часов семинарских занятий.

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

Данный курс не является полностью автономным. Требуется знакомство с элементами математической логики, знание основных понятий и определений теории графов и математического программирования.

Особенность курса – простота изложения. Студент инженерной специальности не обладает глубокой математической подготовкой, поэтому автор стремился довести до него интересные и важные в прикладном смысле результаты с использованием аналогий, разъяснений и примеров.

1.2.Некоторые необходимые определения и понятия.

При сравнении скорости роста двух неотрицательных функций f(n) и g(n) удобно использовать следующие обозначения.

Говорят, что функция g(n) f(n)-ограничена, если g(n)f(n). Если f(n) - полином, то функция g(n) называется полиномиально ограниченной, а если экспонента – экспоненциально ограниченной.

Будем говорить, что f(n)= O(g(n)), если существуют такие положительные константы c и N, что f(n)≤c g(n)для всех n>N.

В этой же ситуации можно использовать и обозначение g(n)=Ω(f(n)). Например, справедливы соотношения log₂ n = O(n), n = Ω(log₂ n), n = O(2ⁿ).

Будем говорить, что f(n)= o(g(n)), если .

Если f(n)= O(g(n) и O(f(n))= g(n) , то это будем обозначать через f(n)=Θg(n).

Для числа x целые числа [x] и ]x[ - это целые части числа с недостатком и с избытком.

Опр. Алфавит A – это конечный или бесконечный набор символов: A={a₁,a₂,…,a_n,…}.

Опр. Слово – это конечный упорядоченный набор символов алфавита.

Выделяется специальное пустое слово (слово, не содержащее символов).

Пусть – множество всех слов в алфавите .

Опр. Язык L – это подмножество . ( ).

Опр. Конкатенация слов и .

.

Число сочетаний (без повторений) из n элементов по k элементов обозначим через . Число сочетаний с повторениями из n элементов по k элементов обозначим через .

Если не оговорено обратное, вместо log₂n будем писать log n.

Простой граф с множеством вершин V, |V|=n, и множеством ребер E, |E|=m, будем обозначать через G=(V,E). Ориентированность графа будет оговариваться отдельно.

Булевы переменные - это переменные, принимающие значения из множества B={0,1}. Множество n-мерных векторов из нулей и единиц называется булевым кубом и обозначается Bⁿ. Очевидно, что число вершин этого куба равно 2ⁿ.

Отображение f: BⁿB называется булевой функцией. Число булевых функций от n переменных равно

Примеры известных булевых функций: конъюнкция (&), дизъюнкция (), отрицание (), импликация (), сложение по модулю «два» (), эквивалентность ( ) и пр.

Табличный способ задания функции представляет собой таблицу размером 2ⁿx(n+1). В последнем столбце таблице записаны значения функции на каждом из 2ⁿ возможных наборах значений переменных. Сами эти наборы записаны в первых n клетках каждой строки.

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