Составляющие формальной системы. Язык формальной теории. Синтаксис формального языка, отношение между формулой и подформулой, сложные и атомарные формулы (стр. 10 )

Более формально, недетерминированная машина Тьюринга - это шестёрка объектов , где: 1) Q конечное множество состояний; 2) Σ конечное множество символов (алфавит плёнки); 3) - начальное состояние; 4) - пробельный символ (); 5) конечное множество допускающих состояний; 6) - это многозначное отображение из пары состояние - символ называемая функцией перехода, где L левая часть а R правая часть.

40.  Теория сложности. Класс недетерминировано полиномиально разрешимых классов задач (NP). Классы NP-трудных, NP-полных классов задач. Проверка на принадлежность к классу NP-полных.

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

В частности, теория сложности вычислений определяет NP задачи — это задачи, которые недетерминированная машина Тьюринга может вычислить в полиномиальное время, а детерминированная не может. Обычно это сложные проблемы оптимизации, например, задача коммивояжера. Задача коммивояжёра (бродячий торговец) заключается в отыскании самого выгодного маршрута, проходящего через указанные города.

В теории алгоритмов классом NP (от англ. non-deterministic polynomial) называют множество алгоритмов, время работы которых сильно зависит от размера входных данных, но если предоставить алгоритму некоторые дополнительные сведения (так называемых свидетелей решения), то он сможет достаточно быстро (за время, не превосходящее многочлена от размера данных) решить задачу. Язык L называется принадлежащим классу NP, если существуют двуместный предикат из класса P (т. е. вычислимый за полиномиальное время) и многочлен nc такие, что для всякого слова x условие «x принадлежит L» равносильно условию «найдётся y длины меньше nc такой, что верно » (где n — длина слова x). Слово y называется свидетелем принадлежности x языку L.

Проблема является NP-трудной, если и только если есть NP-полная проблема L, которая Тьюринг-сводящаяся к H за полиномиальное время, т. е. . Иными словами, L, могут быть решены за полиномиальное время, абстрактной машиной используются для изучения решения проблем(oracle).

Класс сложности NP-полные (сокращенно NP-C или НКП, Н. П.) является класс проблем, имеющих два свойства:

·  Любое решение проблемы может быть проверено быстро (за полиномиальное время); комплекс проблем, связанных с этим свойством называется NP.

·  Если проблема может быть решена быстро (за полиномиальное время), то аналогично могут быть решены все проблемы в NP.

NP-полнота

Есть язык над конечным алфавитом .

является NP-полной тогда и только тогда, когда выполняются следующие два условия:

· 

·  любой имеет полиномиальное время, сводящихся к (), Где выполнимо, и при следующих условиях:

o  Существует таким образом, чтобы выполнялось .

o  Существует машина Тьюринга с полиномиальным временем, которая работает с лентой со скоростью , при входных данных .

41.  Теория сложности. Класс детерминировано полиномиально разрешимых классов задач (P). Класс экспоненциально разрешимых классов задач, дополнения классов классов задач (P, NP и др.), соотношения между классами. Понятие хорошо характеризованного класса задач.

В информатике, теория сложности вычислений является разделом теории вычислений, изучающим стоимость работы, требуемой для решения вычислительной проблемы. Стоимость обычно измеряется абстрактными понятиями времени и пространства, называемыми вычислительными ресурсами. Время определяется количеством тривиальных шагов, необходимых для решения проблемы, тогда как пространство определяется объёмом памяти или места на носителе данных. Таким образом, в этой области предпринимается попытка ответить на центральный вопрос разработки алгоритмов: "как изменится время исполнения и объём занятой памяти в зависимости от размера входа?".

В частности, теория сложности вычислений определяет NP задачи — это такие задачи, которые недетерминированная машина Тьюринга может вычислить в полиномиальное время, тогда как детерминированная не может. Обычно это сложные проблемы оптимизации, например, задача коммивояжера. Задача коммивояжёра (коммивояжёр — бродячий торговец) заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу.

В теории алгоритмов классом P (от англ. polynomial) называют множество алгоритмов, время работы которых не слишком сильно зависит от размера входных данных (не превосходит многочлена от размера данных). Алгоритмы, принадлежащие классу P, считаются быстрыми. Класс P включён в более широкие классы сложности алгоритмов. Класс P является одним из самых узких классов сложности. Алгоритмы, принадлежащие ему, принадлежат также классу NP, классу BPP (как допускающие полиномиальную реализацию с нулевой ошибкой), классу PSPACE (т. к. зона работы на машине Тьюринга всегда меньше времени), классу P/Poly (для доказательства этого факта используется понятие протокола работы машины, который переделывается в булеву схему полиномиального размера). Уже более 30 лет остаётся нерешённой задача о равенстве классов P и NP. Если они равны, то любую задачу из класса NP можно будет решить быстро (за полиномиальное время). Однако научное сообщество склоняется в сторону отрицательного ответа на этот вопрос. Кроме того, не доказана и строгость включения в более широкие классы, например, в PSPACE, но равенство P и PSPACE выглядит на данный момент очень сомнительно.

Класс сложности EXPTIME (иногда называемый EXP, экспоненциально разрешимых) представляет собой совокупность всех решение проблемы, решаемые на детерминированной машине Тьюринга в O (2 P (N)) времени, где P (N) является полиномиальная функция N.

С точки зрения DTIME,

42.  Модальные логики. Язык, кванторы, семантика и двойственность модальных кванторов.

Модальная логика — логика в которой кроме стандартных логических связок, переменных и/или предикатов есть модальности. Модальности бывают разные; наиболее распространены временны́е («когда-то в будущем», «всегда в прошлом», «всегда» и т. д.) и пространственные («здесь», «где-то», «близко» и т. д.). Например, модальная логика способна оперировать утверждениями типа «Москва всегда была столицей России», которые невозможно или сложно выразить в не модальном языке.

Кроме временных и пространственных модальностей есть и другие, например «известно, что» (логика знания) или «можно доказать, что» (логика доказуемости). Обычно для обозначения модального оператора используется и двойственный к нему : . Модальности: Алетические модальные понятия:

1) Логические: L — необходимо; M — возможно; С — случайно.

2) Фактические: — необходимо; — возможно; — случайно.

Модальная логика исследует логические связи модальных высказываний. Само понятие модальности толкуется как некоторая оценка суждения, или высказывания. Модальное суждение – это характеристика суждения в зависимости от свойства устанавливаемой им достоверности. К обычным логическим операторам, таким, как конъюнкция, дизъюнкция, добавляются операторы строгой импликации →, строгой эквивалентности ↔ и совсем новые операторы: необходимости □ («необходимо что…») и возможности ◊ («возможно что…»). Такие понятия возникают в сферах деятельности, где допускается два вида «истинности». Одна имеет более универсальный характер, чем другая. Формулы модальной логики определяются индуктивно: