Поговорим о сложности. Немного вышедшая из моды тема "P vs NP ". О чем же идет речь? Многие задачи сводятся к перебору на конечном множестве. Скажем, поиск или сортировка. И разные алгоритмы имеют различную сложность, то есть число операций из заданного набора допустимых операций. Например, команд процессора или (в случае сортировки) сравнений. Вот есть сортировка методом пузырька: каждый элемент сравнивается с соседними и меняется с ними местами, если надо. Как бы всплывает. А есть более эффективные алгоритмы, например QuickSort...

В этой лекции рассмотрим операцию, именуемую суммой по модулю 2, а также представим алгоритм построения полинома Жегалкина (алгоритм приведения формулы к алгебраической нормальной форме). Определение. Двоичным сложением (суммой по модулю 2, сложением по модулю 2, кольцевой суммой или операцией «Исключающее или») называется формула логики высказываний (булева функция), таблица истинности которой представлена в виде Таблица истинности для двоичного сложения Таким образом, формула логики высказываний...