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

При сравнении скорости роста двух неотрицательных функций 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 клетках каждой строки.

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

Дата добавления: 2015-07-11