Представление логических функций от большого числа переменных

В результате получаем следующую СДНФ:

f(x, y, z) = (Ø xyz) È (x Ø yz) È (xy Ø z) È (xyz)

Выводы по первым двум темам.

Логическая переменная может принимать два значения, тогда из n-переменных можно составить N= 2n комбинаций из “0” и “1”, которые принято называть наборами переменных, и говорят, что функция f опреде

лена на множестве наборов. Поскольку функция принимает два значения, то на N наборов можно построить M= mN различных функций. Становится очевидно, что чем больше переменных содержит функция, тем более громоздкой становится таблица истинности. Поэтому чаще используют аналитическую форму записи. Но машинам (тем же ЭВМ) непонятна такая форма записи и всё равно необходимо строить таблицы истинности, что порою может отнимать значительно времени. Об этом речь пойдет чуть ниже.

Так же бывает проблематично, а порою даже и невозможно построить СДНФ не использую таблицы истинности.

Так же существует СКНФ – Совершенная Конъюнктивная Нормальная Формула. Я не стал останавливаться на ней более подробно, так как она очень похожа на СДНФ, с той лишь разницей, что состоит из конъюнктивных элементов дизъюнкции. Соответствующие изменения будут и при получении СКНФ из таблицы истинности.

Таким образом получаем следующую СКНФ:

f(x,y,z)=(хÈyÈz)^(xÈyÈ Øz)^(xÈ ØyÈz)^(Ø xÈ yÈ z)

Разрешимoсть задач в классической теории алгоритмов

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

Среди различных возможных характеристик алгоритмов наиболее важными с прикладной точки зрения являются две: время и память, расходуемые при вычислении. Физическое время вычисления алгоритма характеризуется произведением tt, где t - число действий (шагов) вычисления, а t - среднее физическое время реализации одного шага. Число шагов t определяется описанием алгоритма в данной алгоритмической модели, это - величина математическая, не зависящая от особенностей физической реализации модели. Напротив, t зависит от реализации и определяется скоростью обработки сигналов в элементах, записи и считывания информации и т. д. Поэтому число действий t можно считать математическим временем вычисления алгоритма, определяющим физическое время вычисления с точностью до константы t, зависящей от реализации.

Память как количественная характеристика алгоритма

Память как количественная характеристика алгоритма определяется количеством S единиц памяти (ячеек ленты машины Тьюринга или машинных слов в современных ЭВМ), используемых в процессе вычисления алгоритма. Ясно, что эта величина по порядку не может превосходить числа шагов вычисления: mt ³ s, где m - максимальное число единиц памяти, используемых в данной машине на одном шаге. Напротив, t может существенно превосходить s, например, возможно соотношение t ³ s^c. С этой точки зрения время более тонко отражает сложность алгоритма, чем память; и это - одна из причин, по которой исследованию временных характеристик алгоритма уделяется большее внимание. Существуют и другие, прикладные причины (в частности, то, что, грубо говоря, память дешевле времени), которые здесь обсуждаться не будут. Так или иначе, здесь будет идти речь о трудоемкости алгоритмов и задач, решаемых алгоритмами.

Итак, трудоемкость алгоритма - это число элементарных действий, выполненных при его вычислении.

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

И в математике, и на практике в конечном счете нас интересуют не алгоритмы сами по себе, а задачи, которые они решают. Одна и та же задача может решаться различными алгоритмами и на разных машинах. Если машина М зафиксирована, то трудоемкостью данной задачи относительно машины М называется минимальная из трудоемкостей алгоритмов, решающих задачу на машине М. Задач, трудоемкость которых была бы определена точно, довольно мало; хорошим результатом считается определение ее по порядку, т. е. с точностью до множителя, ограниченного некоторой константой. Чаще удается оценить ее сверху или снизу. Оценку сверху получают, указав конкретный алгоритм решения задачи: по определению, трудоемкость задачи не превосходит трудоемкости любого из решающих ее алгоритмов. Оценки трудоемкости снизу - гораздо более трудное дело; их получают обычно из некоторых общих соображений (например, мощностных или информационных). О них здесь говорить не будем.

 Скачать реферат