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

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

В понятие "Задачи" входят в первую очередь такие классы проблемных ситуаций, когда необходимо осуществить: 1) сбор информации, 2) оценку ситуации, 3) принятие решений, 4) осуществление действий. К группе наиболее важных классов "задач" относятся: 1) формулировка целей, 2) постановка задач, 3) построение моделей, 4) выдвижение гипотез, 5) оценка достоверности решений, 6) верификация моделей, 7) декомпозиция задач,

упрощение, 8) планирование, 9) классификация\категоризация, 10) выбор из многих альтернатив, 11) распознавание образов, и проч.

Классы сложност.

Схема кодирования (кодировка): необходимо ввести алфавит Σ — множество, состоящее из конечного числа символов , Σ* — множество слов для алфавита, слово — конечный набор букв, слово будем обозначать &sigma = {σi, σj, σk, …}. Кодировка — e: П → Σ*, ∀I ⇒ e(I) = σ ∈ Σ* — отображение массовой задачи в множество слов, индивидуальная задача отображается в слово. Можно сказать, что отображение параметров задачи. Отображение должно удовлетворять следующим свойствам: Возможность декодирования однозначного: ∀I1 ≠ I2, e(I1) ≠ e(I2)

Само кодирование и процесс декодирования должны быть полиминальной сложностиЮ e, e-1 — полиномиальные вычисления. Неизбыточность кодировки: для любой другой кодировки, удовлетворяющей свойствам 1 и 2 найдётся такой полином от n, что для любого натурального n найдётся такая задача I, что длина входа задачи I: — не существует кодировки, которая на порядок лучше. Обычно встречаемся с кодировкой чисел. Какие бывают кодировки: двоичная. Например, есть число N, в двоичной кодировке получаем число N2 = (1, 0, …, 1), |N2| = log2 N, можно взять другую систему: |N10| = log10 N, и в данном случае порядок соответствует.

Другая кодировка: кодирование палочками, длина слова |N1| = N = 2log2 N, и эта кодировка избыточная, так как в этом случае получаем не полином а экспоненту.

Классы сложности задач

Класс полиномиально разрешимых задач = {L(Π, e) | ∃ A решающий Π с кодировкой e, ∃p(.) — полином:

Задача принадлежит классу полиномиальных задач: П ∈ P — ежели для неё существует алгоритм с полиномиальной сложностью.

Труднорешаемые задачи — задачи, для которых нет полиномиального алгоритма.

Слово о полиномиальных и экспоненциальных алгоритмах: если есть алгоритм, который имеет полиномиальную сложность, но степено например порядка 7. Это ничем не лучше экспоненты. Но опыт показывает, что через некоторое время появляется алгоритм, который решает задачу с приемлемыми степенями полинома.

Ежели задача не принадлежит классу полиномиальных (П ∉ P), то есть три возможности:

·  П неразрешима алгоритмически, то есть, нет алгоритма, который не решает любую индивидауальную задачу. Пример: 10-я проблема Гильберта по многочлену с целыми коэфициентами g необходимо найти, имеет ли уравнение g = 0 целочисленные решения. Было доказано (), что эта проблема алгоритмически неразрешима.

·  Запись решения имеет экспоненциальную сложность

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

34.  Теория алгоритмов. Детерминированная машина Тьюринга. Программа машины Тьюринга.

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

Машина Тьюринга (МТ) —абстрактная вычислительная машина. Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления.

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

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

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

35.  Теория алгоритмов. Понятие алгоритма, свойства. Разрешимость задач, функций, предикатов и теорий. Тезис Чёрча-Тьюринга.

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

Алгоритм — описание последовательности действий (план), строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов. Алгоритмизация — процесс разработки алгоритма (плана действий) для решения задачи. Свойства: 1) Дискретность (от лат. discretus — разделенный, прерывистый) – это разбиение алгоритма на ряд отдельных законченных действий (шагов). 2) Детерминированность (от лат. determinate — определенность, точность) - любое действие алгоритма должно быть строго и недвусмысленно определено в каждом случае. 3) Конечность - каждое действие в отдельности и алгоритм в целом должны иметь возможность завершения. 4) Массовость - один и тот же алгоритм можно использовать с разными исходными данными. 5) Результативность - в алгоритме не было ошибок.

Те́зис Чёрча — Тью́ринга — фундаментальное утверждение для многих областей науки, таких, как теория вычислимости, информатика, теоретическая кибернетика и др. Это утверждение было высказано Алонзо Чёрчем и Аланом Тьюрингом в середине 1930-х годов.

В самой общей форме оно гласит, что любая интуитивно вычислимая функция является частично вычислимой, или, что тоже самое, может быть вычислена некоторой машиной Тьюринга. Тезис Чёрча — Тьюринга невозможно строго доказать или опровергнуть, поскольку он устанавливает «равенство» между строго формализованным понятием частично вычислимой функции и неформальным понятием «интуитивно вычислимой функции». Физический тезис Чёрча — Тьюринга гласит: Любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга.

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

36.  Теория алгоритмов. Существование невычислимых функций. Неразрешимость проблема остановки (предиката ).

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