ИСЧИСЛЕНИЯМИ.
Есть еще один подход к аксиоматике, когда основной упор делается именно на правила вывода. Такие системы (почему-то) называются системами естественного вывода, намекая на то, что в них собраны базовые естественные правила логических рассуждений.
Логики резвились меж собой до тех пор, пока не был сформулирован подход к созданию аксиоматических систем под названием ПРИНЦИП (МЕТОД) РЕЗОЛЮЦИ. Он очень способствовал продвижению логики в широкие народные массы.
С одной стороны, активизировались работы по использованию компьютеров для реализации логического вывода и работы по искусственному интеллекту в частности. А с другой стороны, на этой основе был создан язык ПРОЛОГ.
Это совсем другое программирование, нежели традиционное процедурное. Это даже не программирование в обычном смысле слова, коль скоро здесь программист не пишет алгоритм решения задачи. Он описывает логические зависимости «мира», в котором существует задача. На основе описанной логики «мира» система (машина) сама создает алгоритм в процессе поиска решения!
Это только кажется, что аксиоматические системы – это сложно. Любой может напридумывать их сколько угодно. Более простым делом вам вряд ли приходилось заниматься.
Например, в качестве языка можно об'явить любые «слова» из последовательности буквы Я.
Букву Я об'явим аксиомой.
Правило вывода будет удваивать букву Я.
То есть сходу придумана теория, в которой выводимы любые последовательности (слова), состоящие из буквы Я.
Я ЯЯ ЯЯЯ… ЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯ…
И все бы хорошо, только такая строго заданная теория мало что дает создателю, кроме радости созидания. Поэтому встает вопрос целесообразности, смысла. Той самой семантики… Здесь логики заняли очень( !) интересную позицию.
Коль скоро логика не интересуется смыслом высказываний, а лишь их истинностью, то ее (истинность) и об'явили смыслом высказываний. Вдумайтесь, смысл высказывания, например, «Газ при нагревании расширяется» не в том, что это отражение физического закона, а в том что оно истинно. Следовательно, точно такой же смысл( !) имеет высказывание «Никита Михалков – кинорежиссер». То есть его смысл в том, что оно тоже истинное.
Дальше – больше. Язык предикатов – это существенное расширение языка высказываний и обычным образом перебрать все случаи даже в простейшей ситуации, вроде «Икс любит кашу», не всегда возможно. Тем более, что речь может идти и о бесконечностях. Для решения проблем семантики в этом случае прибегают к теории моделей. Но это теория также, в конечном итоге, упирается в «смысл» типа истинно-ложно.
Возвращаясь к аксиоматическим теориям следует сказать, что в математике «практический смысл» имеют лишь такие теории, в которых можно выводить только истинные формулы. И нельзя ложные.
Одна ложная формула «уничтожает без остатка» любую аксиоматическую теорию.
Наша теория, созданная из буквы Я, не привязана к понятию истинности. Поэтому она бессмысленна, как бессистемная перестановка детских кубиков.
С кубиками все ясно. Но проблемы аксиоматических теорий на этом не исчерпываются. Пожалуй самым фундаментальным открытием в этой сфере следует считать доказанную Геделем ТЕОРЕМУ О НЕПОЛНОТЕ. Оказывается, в сколько-нибудь сложной аксиоматической системе (посложнее, чем кубики, но достаточно даже арифметики) существуют формулы, которые нельзя ни доказать, ни опровергнуть. Может в этом причина, что не все школьные задачки имеют решения?!
Так что, создавая свои аксиоматические теории помните, что они должны обладать какими-то полезными свойствами. А такие теории создавать уже не так-то просто. Хотя создать свою собственную математику может каждый!
Известно высказывание одного крупного математика: «Преимущество аксиоматизации – это преимущество воровства перед честным трудом».
Лекция 11. ТЕОРИЯ АЛГОРИТМОВ
Лекция 12. ФОРМАЛЬНЫЕ ГРАММАТИКИ
Лекция 13. СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ
ПОСЛЕСЛОВИЕ
Есть еще один подход к аксиоматике, когда основной упор делается именно на правила вывода. Такие системы (почему-то) называются системами естественного вывода, намекая на то, что в них собраны базовые естественные правила логических рассуждений.
Логики резвились меж собой до тех пор, пока не был сформулирован подход к созданию аксиоматических систем под названием ПРИНЦИП (МЕТОД) РЕЗОЛЮЦИ. Он очень способствовал продвижению логики в широкие народные массы.
С одной стороны, активизировались работы по использованию компьютеров для реализации логического вывода и работы по искусственному интеллекту в частности. А с другой стороны, на этой основе был создан язык ПРОЛОГ.
Это совсем другое программирование, нежели традиционное процедурное. Это даже не программирование в обычном смысле слова, коль скоро здесь программист не пишет алгоритм решения задачи. Он описывает логические зависимости «мира», в котором существует задача. На основе описанной логики «мира» система (машина) сама создает алгоритм в процессе поиска решения!
Это только кажется, что аксиоматические системы – это сложно. Любой может напридумывать их сколько угодно. Более простым делом вам вряд ли приходилось заниматься.
Например, в качестве языка можно об'явить любые «слова» из последовательности буквы Я.
Букву Я об'явим аксиомой.
Правило вывода будет удваивать букву Я.
То есть сходу придумана теория, в которой выводимы любые последовательности (слова), состоящие из буквы Я.
Я ЯЯ ЯЯЯ… ЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯЯ…
И все бы хорошо, только такая строго заданная теория мало что дает создателю, кроме радости созидания. Поэтому встает вопрос целесообразности, смысла. Той самой семантики… Здесь логики заняли очень( !) интересную позицию.
Коль скоро логика не интересуется смыслом высказываний, а лишь их истинностью, то ее (истинность) и об'явили смыслом высказываний. Вдумайтесь, смысл высказывания, например, «Газ при нагревании расширяется» не в том, что это отражение физического закона, а в том что оно истинно. Следовательно, точно такой же смысл( !) имеет высказывание «Никита Михалков – кинорежиссер». То есть его смысл в том, что оно тоже истинное.
Дальше – больше. Язык предикатов – это существенное расширение языка высказываний и обычным образом перебрать все случаи даже в простейшей ситуации, вроде «Икс любит кашу», не всегда возможно. Тем более, что речь может идти и о бесконечностях. Для решения проблем семантики в этом случае прибегают к теории моделей. Но это теория также, в конечном итоге, упирается в «смысл» типа истинно-ложно.
Возвращаясь к аксиоматическим теориям следует сказать, что в математике «практический смысл» имеют лишь такие теории, в которых можно выводить только истинные формулы. И нельзя ложные.
Одна ложная формула «уничтожает без остатка» любую аксиоматическую теорию.
Наша теория, созданная из буквы Я, не привязана к понятию истинности. Поэтому она бессмысленна, как бессистемная перестановка детских кубиков.
С кубиками все ясно. Но проблемы аксиоматических теорий на этом не исчерпываются. Пожалуй самым фундаментальным открытием в этой сфере следует считать доказанную Геделем ТЕОРЕМУ О НЕПОЛНОТЕ. Оказывается, в сколько-нибудь сложной аксиоматической системе (посложнее, чем кубики, но достаточно даже арифметики) существуют формулы, которые нельзя ни доказать, ни опровергнуть. Может в этом причина, что не все школьные задачки имеют решения?!
Так что, создавая свои аксиоматические теории помните, что они должны обладать какими-то полезными свойствами. А такие теории создавать уже не так-то просто. Хотя создать свою собственную математику может каждый!
Известно высказывание одного крупного математика: «Преимущество аксиоматизации – это преимущество воровства перед честным трудом».
Лекция 11. ТЕОРИЯ АЛГОРИТМОВ
Теория алгоритмов не учит «составлять» алгоритмы. Она занимается более важным вопросом. Основная задача классической теории алгоритмов – это ответ на вопрос: «Можно ли (вообще) для задач данного типа построить алгоритм?». Говоря более наукообразно: «Являются ли задачи данного типа алгоритмически разрешимыми»?
Это связано с тем, что, во-первых, не для всех задач возможно создать алгоритмы их решения. А, во-вторых, чтобы сделать математически строгий вывод о невозможности построить алгоритм, надо иметь строгое (формальное) определение самого алгоритма. Но понятие АЛГОРИТМАотносится к фундаментальным неопределяемым понятиям. В вопросе об алгоритме у нас собачья позиция. Понимать понимаем, а сказать не можем. Если где-то встречаете «определение» алгоритма, то там, что ни слово – то аллегория…
Из этого тупика был найден нетривиальный выход. Понятие алгоритма заменили строго формализованными математическими моделями. Среди самых известных рекурсивные функции, машины Тьюринга и нормальные алгорифмы Маркова.
Эти математические модели выступают в роли «конкретизаций понятия алгоритма». То есть длительная практика подтверждает так называемый тезис Черча, который можно пересказать так:
Для любой алгоритмически разрешимой задачи можно построить рекурсивную функцию (машину Тьюринга, нормальный алгорифм Маркова). И наоборот, для задач, для которых нельзя построить перечисленные конкретизации, не существует алгоритма решения.
РЕКУРСИВНЫЕ ФУНКЦИИоснованы на той идее, что исходные данные и возможные результаты решения любой задачи можно пронумеровать. Для чего, естественно, достаточно множества натуральных чисел (целых положительных чисел, начиная с нуля). А далее базовыми об'являются функции, возможность выполнить (вычислить) которые не вызывает сомнений.
НУЛЬ– ФУНКЦИЯ– это функция, которая дает значение ноль для любого значения аргумента. Реализовать эту функцию может не только ребенок. Можно посадить попугая и подучить его на любой вопрос о значении функции кричать «Ноль!».
ФУНКЦИЯ СЛЕДОВАНИЯдает следующее, по сравнению с аргументом, значение. Для пяти это шесть, для миллиона – миллион один. Можно бы было сказать, что здесь надо просто прибавлять 1.
Но операции сложения у нас пока нет!
ФУНКЦИЯ ВЫБОРА АРГУМЕНТА. Это вообще забавная даже для первоклассника функция, содержащая в своем имени номер аргумента. Если у вас есть несколько аргументов, то эта функция в качестве значения возьмет значение указанного в ней аргумента. Например, функция выбора третьего из Иванова, Петрова и Сидорова, которых мы ранее пронумеровали, например, как 22, 13 и 49, даст значение 49.
Эти три базовых функции могут использоваться далее в качестве исходного материала для создания более сложных функций с помощью трех операторов: суперпозиции, примитивной рекурсии и наименьшего корня.
Известный хорошо еще со школы ОПЕРАТОР СУПЕРПОЗИЦИИпозволяет вместо аргумента подставлять функцию… «Игла в яйце, а яйцо в ларце»…
Дольше словами описывать ОПЕРАТОР ПРИМИТИВНОЙ РЕКУРСИИ. Но если поднатужиться, то можно понять. Этот оператор позволяет построить новую функцию из двух функций, одна из которых имеет на один аргумент меньше, а другая на один аргумент больше.
Значение создаваемой функции для нулевого значения выбранного аргумента приравнивается к функции, не имеющей как раз этого аргумента. Значение же создаваемой функции для всех прочих
(ненулевых) значений выбранного аргумента приравнивается другой функции, зависящей (напрягитесь!) от тех же аргументов, кроме выбранного; от ПРЕДЫДУЩЕГОзначения выбранного аргумента и от создаваемой функции от предыдущего значения выбранного аргумента.
Ну как тут не пожалеть о формулах.
Хотя, на самом-то деле мы со школы сталкиваемся с такого рода функциями, но, как тот герой, только на старости лет узнаем, что говорим прозой. Приведем построение с помощью рекурсии всем известной двухместной функции умножения икс на игрек (считая выбранной переменной игрек).
Функцию умножения икс на ноль можно выразить через нуль-функцию от икс, которая обеспечит нам желанное значение – ноль.
Функцию умножения икс на игрек (отличный от нуля) можно выразить через функцию сложения икса со значением функции умножения икса на предыдущее значение игрека… То есть мы выразили умножение через сложение.
Здесь следует сделать два замечания. Считаем, что к этому моменту доказана рекурсивность используемой здесь функция сложения. И второе, при умножении икс на игрек в нашем распоряжении функция от трех аргументов. Но, применив проектирующую функцию мы избавимся от среднего аргумента, коль скоро он нам здесь не нужен. Нам ведь дозволено заниматься подбором из возможного!
Последний оператор – ОПЕРАТОР НАИМЕНЬШЕГО КОРНЯ. Его необходимость просто об'яснить хотя бы тем, что рекурсивные функции, призванные решать любые алгоритмически разрешимые задачи, сами используют лишь целые положительные числа. А это не позволяет решить даже детскую задачку: 5 – 8 =? (Нет для рекурсивных функций отрицательных чисел). На самом-то деле эти детские задачки можно решить по-детски. Договориться, что 1000 это (сдвинутый) ноль, а вычитание – есть сложение с «отрицательным» числом! Тогда
1005 + 992 = 1997 (приведение к шкале: 1997 – 1000 = 997)
Поскольку мы при этом сдвиг нуля учли дважды, то окончательный результат (в системе с один раз сдвинутым на 1000 нулем) будет 997. Но это детское решение лишь говорит о том, что без отрицательных чисел и в школе можно обойтись. Как и в древнем Риме обходились. Правда там и без нуля обходились, а здесь он нам нужен позарез.
Именно оператор наименьшего корня и следит, при каком значении выбранного аргумента наблюдаемая им функция впервые опустится до нуля. Это значение выбранного аргумента и будет значением оператора наименьшего корня. Например, для функции икс минус игрек при иксе равном 5, значение оператора наименьшего корня также будет равно 5, поскольку двигаясь в значениях игрека от нуля получим нулевое значение функции именно при игрек равном 5.
Базовые функции и функции, которые могут быть построены из них с помощью операторов суперпозиции, примитивной рекурсии и наименьшего корня, образуют множество ЧАСТИЧНО-РЕКУРСИВНЫХ ФУНКЦИЙ. А множество частично-рекурсивных функций совпадает с множеством всех алгоритмически разрешимых задач (множеством всех вычислимых функций). Кстати, за слово «частичные» надо благодарить оператор наименьшего корня, из-за которого в множество построенных функций входят и не всюду определенные (частичные) функции.
Тьюринг не был автостроителем. Машина Тьюринга не предполагает двигателя внутреннего сгорания, поскольку все там перемещается исключительно силой мысли. Это математическая модель. Она чем-то может и напоминающая автомашину, но не более чем машину напоминает магнитофон, в котором лента (разделенная на ячейки) неподвижна, а считывающе-записывающая головка вдоль нее ездит. Хуже того, ездит головка рывками, от ячейки к ячейке. А в ячейках записаны символы. (Чтобы не было пустых ячеек, в пустые ячейки записывают специальный пустой символ).
В машине Тьюринга есть устройство управления, имеющее память «состояний» и работающее по задаваемой программе (алгоритму). Программа состоит из команд. Каждая «команда» состоит в следующем: Машина читает символ из ячейки, против которой стоит головка (находясь в каком-то состоянии [вначале – в начальном]), записывает в эту ячейку символ (может и тот же самый), меняет свое состояние (может сохранить прежнее) и делает шаг влево или вправо (может остаться на месте).
Так Машина ходит вдоль ленты до тех пор, пока не перейдет в специальное состояние, называемое заключительным. Это говорит об окончании работы Машины (алгоритма). А на ленте остается результат (решения).
Пример. Построим Машину, которая в сплошной последовательности единичек стирает последнюю.
Поскольку количество единичек в сплошной последовательности произвольное и неизвестное, последнюю определим как ту, которая стоит ПЕРЕДпустым символом. Это главная идея данного решения. Остальное – дело техники. Напишем программу – четыре команды.
Машина читает пустой символ, находясь в начальном состоянии пишет пустой символ и делает шаг вправо. (Значит машина находится ДОначала последовательности единичек)
Машина читает единичку, находясь в начальном состоянии, пишет единичку и делает шаг вправо, оставаясь в этом состоянии. (Значит машина «идет» по последовательности единичек)
Машина читает пустой символ, находясь в начальном состоянии, пишет пустой символ, делает шаг влево и переходит во второе состояние. (Значит найдена последняя единичка)
Машина читает единичку, находясь во втором состоянии, пишет пустой символ (стирает единичку), стоит на месте и переходит в заключительное состояние. (Задача решена)
Несмотря на внешнюю примитивность такой конструкции, для любой алгоритмически разрешимой задачи можно построить Машину Тьюринга! А поскольку машина строится в собственной голове, вопросы «технической эффективности» такой машины никакой роли не играют. Единственный вопрос. Доберется ли машина до заключительного состояния? Пусть и через (воображаемый) миллион лет. Тогда задача разрешима!
Не будет преувеличением сказать, что нормальные алгорифмы Маркова создал А.А.Марков, член-корреспондент Академии Наук СССР из Москвы. Для восстановления единообразия, по праву автора, он назвал алгориТмы алгориФмами, поскольку слово это арабо-греческое, как и слово ариФметика…
Смысл нормальных алгорифмов – принудительный обмен, порядок которого жестко задан.
Собственно алгоритм в нормальных алгорифмах задается НОРМАЛЬНОЙ СХЕМОЙ ПОДСТАНОВОК– очередностью правил «что на что менять». Лучше всего это показать на примере замены слов, тем более, что и сам Марков любую последовательность букв, какую ни в одном словаре не сыщешь, называл «словами». Так при наличии двух подстановок: меняющей «ха» на «ссон» и «мусс» на «сл» из «муха» можно сделать «слон».
Механизм нормальных алгоритмов настолько прост, что напоминает скорее детскую игру, чем математику. Но на самом деле это очень мощный механизм, поскольку через него можно выразить решение любой алгоритмически разрешимой задачи. И опять напомним, что это не следует воспринимать, как предложение решать любую задачу через подстановки (хотя на этих принципах работает замечательный язык программирования РЕФАЛ). Это лишь означает, что любую алгоритмически разрешимую задачу МОЖНОпредставить в виде такой системы подстановок. А если нельзя (и вы это смогли доказать), то такая задача вообще не имеет алгоритма решения.
Это связано с тем, что, во-первых, не для всех задач возможно создать алгоритмы их решения. А, во-вторых, чтобы сделать математически строгий вывод о невозможности построить алгоритм, надо иметь строгое (формальное) определение самого алгоритма. Но понятие АЛГОРИТМАотносится к фундаментальным неопределяемым понятиям. В вопросе об алгоритме у нас собачья позиция. Понимать понимаем, а сказать не можем. Если где-то встречаете «определение» алгоритма, то там, что ни слово – то аллегория…
Из этого тупика был найден нетривиальный выход. Понятие алгоритма заменили строго формализованными математическими моделями. Среди самых известных рекурсивные функции, машины Тьюринга и нормальные алгорифмы Маркова.
Эти математические модели выступают в роли «конкретизаций понятия алгоритма». То есть длительная практика подтверждает так называемый тезис Черча, который можно пересказать так:
Для любой алгоритмически разрешимой задачи можно построить рекурсивную функцию (машину Тьюринга, нормальный алгорифм Маркова). И наоборот, для задач, для которых нельзя построить перечисленные конкретизации, не существует алгоритма решения.
РЕКУРСИВНЫЕ ФУНКЦИИоснованы на той идее, что исходные данные и возможные результаты решения любой задачи можно пронумеровать. Для чего, естественно, достаточно множества натуральных чисел (целых положительных чисел, начиная с нуля). А далее базовыми об'являются функции, возможность выполнить (вычислить) которые не вызывает сомнений.
НУЛЬ– ФУНКЦИЯ– это функция, которая дает значение ноль для любого значения аргумента. Реализовать эту функцию может не только ребенок. Можно посадить попугая и подучить его на любой вопрос о значении функции кричать «Ноль!».
ФУНКЦИЯ СЛЕДОВАНИЯдает следующее, по сравнению с аргументом, значение. Для пяти это шесть, для миллиона – миллион один. Можно бы было сказать, что здесь надо просто прибавлять 1.
Но операции сложения у нас пока нет!
ФУНКЦИЯ ВЫБОРА АРГУМЕНТА. Это вообще забавная даже для первоклассника функция, содержащая в своем имени номер аргумента. Если у вас есть несколько аргументов, то эта функция в качестве значения возьмет значение указанного в ней аргумента. Например, функция выбора третьего из Иванова, Петрова и Сидорова, которых мы ранее пронумеровали, например, как 22, 13 и 49, даст значение 49.
Эти три базовых функции могут использоваться далее в качестве исходного материала для создания более сложных функций с помощью трех операторов: суперпозиции, примитивной рекурсии и наименьшего корня.
Известный хорошо еще со школы ОПЕРАТОР СУПЕРПОЗИЦИИпозволяет вместо аргумента подставлять функцию… «Игла в яйце, а яйцо в ларце»…
Дольше словами описывать ОПЕРАТОР ПРИМИТИВНОЙ РЕКУРСИИ. Но если поднатужиться, то можно понять. Этот оператор позволяет построить новую функцию из двух функций, одна из которых имеет на один аргумент меньше, а другая на один аргумент больше.
Значение создаваемой функции для нулевого значения выбранного аргумента приравнивается к функции, не имеющей как раз этого аргумента. Значение же создаваемой функции для всех прочих
(ненулевых) значений выбранного аргумента приравнивается другой функции, зависящей (напрягитесь!) от тех же аргументов, кроме выбранного; от ПРЕДЫДУЩЕГОзначения выбранного аргумента и от создаваемой функции от предыдущего значения выбранного аргумента.
Ну как тут не пожалеть о формулах.
Хотя, на самом-то деле мы со школы сталкиваемся с такого рода функциями, но, как тот герой, только на старости лет узнаем, что говорим прозой. Приведем построение с помощью рекурсии всем известной двухместной функции умножения икс на игрек (считая выбранной переменной игрек).
Функцию умножения икс на ноль можно выразить через нуль-функцию от икс, которая обеспечит нам желанное значение – ноль.
Функцию умножения икс на игрек (отличный от нуля) можно выразить через функцию сложения икса со значением функции умножения икса на предыдущее значение игрека… То есть мы выразили умножение через сложение.
Здесь следует сделать два замечания. Считаем, что к этому моменту доказана рекурсивность используемой здесь функция сложения. И второе, при умножении икс на игрек в нашем распоряжении функция от трех аргументов. Но, применив проектирующую функцию мы избавимся от среднего аргумента, коль скоро он нам здесь не нужен. Нам ведь дозволено заниматься подбором из возможного!
Последний оператор – ОПЕРАТОР НАИМЕНЬШЕГО КОРНЯ. Его необходимость просто об'яснить хотя бы тем, что рекурсивные функции, призванные решать любые алгоритмически разрешимые задачи, сами используют лишь целые положительные числа. А это не позволяет решить даже детскую задачку: 5 – 8 =? (Нет для рекурсивных функций отрицательных чисел). На самом-то деле эти детские задачки можно решить по-детски. Договориться, что 1000 это (сдвинутый) ноль, а вычитание – есть сложение с «отрицательным» числом! Тогда
1005 + 992 = 1997 (приведение к шкале: 1997 – 1000 = 997)
Поскольку мы при этом сдвиг нуля учли дважды, то окончательный результат (в системе с один раз сдвинутым на 1000 нулем) будет 997. Но это детское решение лишь говорит о том, что без отрицательных чисел и в школе можно обойтись. Как и в древнем Риме обходились. Правда там и без нуля обходились, а здесь он нам нужен позарез.
Именно оператор наименьшего корня и следит, при каком значении выбранного аргумента наблюдаемая им функция впервые опустится до нуля. Это значение выбранного аргумента и будет значением оператора наименьшего корня. Например, для функции икс минус игрек при иксе равном 5, значение оператора наименьшего корня также будет равно 5, поскольку двигаясь в значениях игрека от нуля получим нулевое значение функции именно при игрек равном 5.
Базовые функции и функции, которые могут быть построены из них с помощью операторов суперпозиции, примитивной рекурсии и наименьшего корня, образуют множество ЧАСТИЧНО-РЕКУРСИВНЫХ ФУНКЦИЙ. А множество частично-рекурсивных функций совпадает с множеством всех алгоритмически разрешимых задач (множеством всех вычислимых функций). Кстати, за слово «частичные» надо благодарить оператор наименьшего корня, из-за которого в множество построенных функций входят и не всюду определенные (частичные) функции.
Тьюринг не был автостроителем. Машина Тьюринга не предполагает двигателя внутреннего сгорания, поскольку все там перемещается исключительно силой мысли. Это математическая модель. Она чем-то может и напоминающая автомашину, но не более чем машину напоминает магнитофон, в котором лента (разделенная на ячейки) неподвижна, а считывающе-записывающая головка вдоль нее ездит. Хуже того, ездит головка рывками, от ячейки к ячейке. А в ячейках записаны символы. (Чтобы не было пустых ячеек, в пустые ячейки записывают специальный пустой символ).
В машине Тьюринга есть устройство управления, имеющее память «состояний» и работающее по задаваемой программе (алгоритму). Программа состоит из команд. Каждая «команда» состоит в следующем: Машина читает символ из ячейки, против которой стоит головка (находясь в каком-то состоянии [вначале – в начальном]), записывает в эту ячейку символ (может и тот же самый), меняет свое состояние (может сохранить прежнее) и делает шаг влево или вправо (может остаться на месте).
Так Машина ходит вдоль ленты до тех пор, пока не перейдет в специальное состояние, называемое заключительным. Это говорит об окончании работы Машины (алгоритма). А на ленте остается результат (решения).
Пример. Построим Машину, которая в сплошной последовательности единичек стирает последнюю.
Поскольку количество единичек в сплошной последовательности произвольное и неизвестное, последнюю определим как ту, которая стоит ПЕРЕДпустым символом. Это главная идея данного решения. Остальное – дело техники. Напишем программу – четыре команды.
Машина читает пустой символ, находясь в начальном состоянии пишет пустой символ и делает шаг вправо. (Значит машина находится ДОначала последовательности единичек)
Машина читает единичку, находясь в начальном состоянии, пишет единичку и делает шаг вправо, оставаясь в этом состоянии. (Значит машина «идет» по последовательности единичек)
Машина читает пустой символ, находясь в начальном состоянии, пишет пустой символ, делает шаг влево и переходит во второе состояние. (Значит найдена последняя единичка)
Машина читает единичку, находясь во втором состоянии, пишет пустой символ (стирает единичку), стоит на месте и переходит в заключительное состояние. (Задача решена)
Несмотря на внешнюю примитивность такой конструкции, для любой алгоритмически разрешимой задачи можно построить Машину Тьюринга! А поскольку машина строится в собственной голове, вопросы «технической эффективности» такой машины никакой роли не играют. Единственный вопрос. Доберется ли машина до заключительного состояния? Пусть и через (воображаемый) миллион лет. Тогда задача разрешима!
Не будет преувеличением сказать, что нормальные алгорифмы Маркова создал А.А.Марков, член-корреспондент Академии Наук СССР из Москвы. Для восстановления единообразия, по праву автора, он назвал алгориТмы алгориФмами, поскольку слово это арабо-греческое, как и слово ариФметика…
Смысл нормальных алгорифмов – принудительный обмен, порядок которого жестко задан.
Собственно алгоритм в нормальных алгорифмах задается НОРМАЛЬНОЙ СХЕМОЙ ПОДСТАНОВОК– очередностью правил «что на что менять». Лучше всего это показать на примере замены слов, тем более, что и сам Марков любую последовательность букв, какую ни в одном словаре не сыщешь, называл «словами». Так при наличии двух подстановок: меняющей «ха» на «ссон» и «мусс» на «сл» из «муха» можно сделать «слон».
Механизм нормальных алгоритмов настолько прост, что напоминает скорее детскую игру, чем математику. Но на самом деле это очень мощный механизм, поскольку через него можно выразить решение любой алгоритмически разрешимой задачи. И опять напомним, что это не следует воспринимать, как предложение решать любую задачу через подстановки (хотя на этих принципах работает замечательный язык программирования РЕФАЛ). Это лишь означает, что любую алгоритмически разрешимую задачу МОЖНОпредставить в виде такой системы подстановок. А если нельзя (и вы это смогли доказать), то такая задача вообще не имеет алгоритма решения.
Лекция 12. ФОРМАЛЬНЫЕ ГРАММАТИКИ
Формальные грамматики – это хорошо развитый математический аппарат, позволяющий, кроме изучения «высоких материй», (математически) грамотно создавать языки программирования и писать компиляторы для этих языков.
Между естественными и формальными языками непреодолимая пропасть. Поэтому совпадение терминологии лучше считать случайным… Тем более, в рамках многогранного и разветвленного ЯЗЫКА МАТЕМАТИКИраздел формальных грамматик и языков ориентирован прежде всего на проблемы построения компиляторов.
Формальный язык можно задать как некое множество слов. Слово, это последовательность символов. Любая компьютерная программа в этом случае тоже воспринимается как слово. Пробелы в ней – специальные символы, для которых на клавиатуре выделена самая длинная клавиша.
Словами данного языка может быть далеко не любая абракадабра, доступная клавиатуре. А только лексически и синтаксически (безупречно!) правильные программы. Безупречная с точки зрения грамматики программа может быть бесполезной, бессмысленной или даже вредной. Но за правильную работу программы формальная грамматика и компилятор не отвечают. (Повторим, математика обычно смыслом не занимается).
Поскольку и здесь, в формальных грамматиках и языках, математика за смысл не отвечает. Есть специальное направление в теоретическом программировании, когда на формальном языке (обычно на языке предикатов и его диалектах) описывается, что должна делать программа. На основании этого описания специальная система синтезирует программу. Однако, это тема совсем другого разговора. Тем более, что ошибок в описании того, что должна делать программа, человек допускает больше, чем при написании программы непосредственно.
Для того, чтобы задать грамматику, надо задать множества ТЕРМИНАЛЬНЫХи НЕТЕРМИНАЛЬНЫХсимволов. Терминальные символы это символы используемые в языке. Нетерминальные (промежуточные) символы – это символы, используемые в создании (порождении) слов языка. А создаются слова по грамматическим правилам. И каждое слово, напомним, это с точки зрения программиста – программа, записанная исключительно терминальными символами. Далее задаются ГРАММАТИЧЕСКИЕ ПРАВИЛА. Они очень напоминают подстановки в алгорифмах Маркова. Но в отличие от последних порядок применения грамматических правил произвольный. Применение правила заключается в замене в преобразуемой строке какой-то последовательности символов, совпадающей с левой частью какого-то правила, правой частью (последовательностью символов) этого правила.
Введем в оборот из чисто эстетических соображений еще один красивый термин – СЕНТЕНЦИАЛЬНАЯ ФОРМА. Дело в том, что при построении программ в формальных грамматиках всегда танцуют от одного начального нетерминального символа. Обозначим этот символ «программа». Вместо этого символа по одному из грамматических правил происходит подстановка соответствующей правой части, которая может содержать последовательность из каких-то нетерминальных и терминальных символов. Кстати, такой процесс называется НЕПОСРЕДСТВЕННЫМ ПОРОЖДЕНИЕМ. Любой их появившихся нетерминальных символов может быть заменен по подходящему грамматическому правилу какой-то цепочкой символов. То есть начальный нетерминальный символ «программа» последовательно превращается во все более длинную цепочку символов. И так вплоть до того момента, когда в последовательности символов останутся только терминальные символы. То есть будет получено слово данного языка (по иронии судьбы называемое ПРЕДЛОЖЕНИЕМ). Все последовательности символов, которые в процессе непосредственных порождений находятся между начальным нетерминальным символом и конечным предложением и называются сентенциальными формами. А нам остается радоваться, что английский язык нам неродной.
Компилятор, получив программу, выполняет обратную работу. Пред'явленное предложение он свертывает по грамматическим правилам (теперь двигаясь от правой части правила к левой) начального символа «программа».
Обычно существует огромное количество вариантов как порождения, так и свертывания. Если свертывание потерпело неудачу, то должны исследоваться другие варианты. Слово будет признано НЕпринадлежащим данному языку (грамматике), если ни один из вариантов свертывания не приведет к удаче. Поскольку такой перебор вариантов на практике как правило неприемлем, то и грамматики пытаются придумывать не случайные, а с полезными свойствами. А способы свертывания (распознавания) используют эти хорошие свойства, чтобы минимизировать или вообще исключить блуждания.
Есть достаточно грубая, но, все равно, полезная в первом приближении классификация грамматик, принадлежащая Хомскому. Он их делит на три типа, если не считать нулевого. К нулевому он относит грамматики с грамматическими правилами произвольного вида. А раз нет никаких ограничений, то там может быть все, что угодно и, следовательно, анализировать их невозможно. Точнее, считайте, что проанализировали и сделали заключение: Там может быть все, что угодно и неугодно. Так что иметь с ними дело бессмысленно. Даже сумасшедшим.
Грамматики первого типа называют КОНТЕКСТНО-ЗАВИСИМЫМИ(или просто КЗ). В большинстве случаев разумно принять общее ограничение, что правило заменяет строго один нетерминальный символ. Отличительная особенность КЗ–правил в том, что замена нетерминального символа на строку допускается, когда этот символ находится в некотором окружении других символов (в контексте). Например, нетерминальный символ «оператор» может быть заменен на нетерминальный символ «пустой оператор», если в преобразуемой строке перед символом «оператор» был другой символ, за которым непосредственно следовал «оператор». А иначе такую замену делать нельзя.
Представьте например, правило официанта. Осуществлять замену грязной тарелки на выписанный счет можно при наличии опустошенного бокала. В другом контексте (при полном бокале [граненом стакане] рядом) вместо грязной тарелки клиенту предлагается новая закуска.
Для того, чтобы грамматика относилась к типу КЗдостаточно, чтобы хотя бы одно правило было именно первого типа. (Остальные могут быть других типов, кроме нулевого).
Грамматики второго типа называют КОНТЕКСТНО-СВОБОДНЫМИ(или просто КС). Каждое правило может применяться без оглядки на контекст. Вместо грязной тарелки – новая закуска (без всяких дополнительных условий)… Грамматики разных типов могут порождать один и тот же язык. Компиляторы диктуют требование приводить грамматику к типу КС. Обычно в рамках уже этого типа накладываются дополнительные ограничения, что позволяет существенно упростить грамматический разбор в компиляторе.
Грамматики последнего третьего типа называются АВТОМАТНЫМИили РЕГУЛЯРНЫМИ. Это связано с тем, что они порождаются и распознаются автоматами (эту математическую модель ассоциируют не с Калашниковым, а с фамилиями математиков-логиков Мили Мура Трахтенбротта и т. п.) и регулярными выражениями (это, как и в регулярной армии – выражения строятся по простым правилам и просто распознаются – это тоже математическая модель).
Обычно автоматные грамматики используются на уровне лексики. Лексема, в обычном понимании – это словарная единица. Тем ни менее, с точки зрения компилятора это «символ», коль скоро «словом» будет вся программа. В данном случае, например, 345.08 может быть распознан как один символ – действительное число.
Лексический анализ в компиляторе предшествует синтаксическому анализу… Существуют знаменитые команды UNIX lexи yacc, который позволяют автоматизировать процесс написания лексического и синтаксического анализаторов компилятора.
Что– то мы очень уклонились в сторону программирования. Программирование -это тоже математика. Тоже дискретная. Но уже другая. И это другая история.
А из программирования уже, обычно, так просто не возвращаются…
Между естественными и формальными языками непреодолимая пропасть. Поэтому совпадение терминологии лучше считать случайным… Тем более, в рамках многогранного и разветвленного ЯЗЫКА МАТЕМАТИКИраздел формальных грамматик и языков ориентирован прежде всего на проблемы построения компиляторов.
Формальный язык можно задать как некое множество слов. Слово, это последовательность символов. Любая компьютерная программа в этом случае тоже воспринимается как слово. Пробелы в ней – специальные символы, для которых на клавиатуре выделена самая длинная клавиша.
Словами данного языка может быть далеко не любая абракадабра, доступная клавиатуре. А только лексически и синтаксически (безупречно!) правильные программы. Безупречная с точки зрения грамматики программа может быть бесполезной, бессмысленной или даже вредной. Но за правильную работу программы формальная грамматика и компилятор не отвечают. (Повторим, математика обычно смыслом не занимается).
Поскольку и здесь, в формальных грамматиках и языках, математика за смысл не отвечает. Есть специальное направление в теоретическом программировании, когда на формальном языке (обычно на языке предикатов и его диалектах) описывается, что должна делать программа. На основании этого описания специальная система синтезирует программу. Однако, это тема совсем другого разговора. Тем более, что ошибок в описании того, что должна делать программа, человек допускает больше, чем при написании программы непосредственно.
Для того, чтобы задать грамматику, надо задать множества ТЕРМИНАЛЬНЫХи НЕТЕРМИНАЛЬНЫХсимволов. Терминальные символы это символы используемые в языке. Нетерминальные (промежуточные) символы – это символы, используемые в создании (порождении) слов языка. А создаются слова по грамматическим правилам. И каждое слово, напомним, это с точки зрения программиста – программа, записанная исключительно терминальными символами. Далее задаются ГРАММАТИЧЕСКИЕ ПРАВИЛА. Они очень напоминают подстановки в алгорифмах Маркова. Но в отличие от последних порядок применения грамматических правил произвольный. Применение правила заключается в замене в преобразуемой строке какой-то последовательности символов, совпадающей с левой частью какого-то правила, правой частью (последовательностью символов) этого правила.
Введем в оборот из чисто эстетических соображений еще один красивый термин – СЕНТЕНЦИАЛЬНАЯ ФОРМА. Дело в том, что при построении программ в формальных грамматиках всегда танцуют от одного начального нетерминального символа. Обозначим этот символ «программа». Вместо этого символа по одному из грамматических правил происходит подстановка соответствующей правой части, которая может содержать последовательность из каких-то нетерминальных и терминальных символов. Кстати, такой процесс называется НЕПОСРЕДСТВЕННЫМ ПОРОЖДЕНИЕМ. Любой их появившихся нетерминальных символов может быть заменен по подходящему грамматическому правилу какой-то цепочкой символов. То есть начальный нетерминальный символ «программа» последовательно превращается во все более длинную цепочку символов. И так вплоть до того момента, когда в последовательности символов останутся только терминальные символы. То есть будет получено слово данного языка (по иронии судьбы называемое ПРЕДЛОЖЕНИЕМ). Все последовательности символов, которые в процессе непосредственных порождений находятся между начальным нетерминальным символом и конечным предложением и называются сентенциальными формами. А нам остается радоваться, что английский язык нам неродной.
Компилятор, получив программу, выполняет обратную работу. Пред'явленное предложение он свертывает по грамматическим правилам (теперь двигаясь от правой части правила к левой) начального символа «программа».
Обычно существует огромное количество вариантов как порождения, так и свертывания. Если свертывание потерпело неудачу, то должны исследоваться другие варианты. Слово будет признано НЕпринадлежащим данному языку (грамматике), если ни один из вариантов свертывания не приведет к удаче. Поскольку такой перебор вариантов на практике как правило неприемлем, то и грамматики пытаются придумывать не случайные, а с полезными свойствами. А способы свертывания (распознавания) используют эти хорошие свойства, чтобы минимизировать или вообще исключить блуждания.
Есть достаточно грубая, но, все равно, полезная в первом приближении классификация грамматик, принадлежащая Хомскому. Он их делит на три типа, если не считать нулевого. К нулевому он относит грамматики с грамматическими правилами произвольного вида. А раз нет никаких ограничений, то там может быть все, что угодно и, следовательно, анализировать их невозможно. Точнее, считайте, что проанализировали и сделали заключение: Там может быть все, что угодно и неугодно. Так что иметь с ними дело бессмысленно. Даже сумасшедшим.
Грамматики первого типа называют КОНТЕКСТНО-ЗАВИСИМЫМИ(или просто КЗ). В большинстве случаев разумно принять общее ограничение, что правило заменяет строго один нетерминальный символ. Отличительная особенность КЗ–правил в том, что замена нетерминального символа на строку допускается, когда этот символ находится в некотором окружении других символов (в контексте). Например, нетерминальный символ «оператор» может быть заменен на нетерминальный символ «пустой оператор», если в преобразуемой строке перед символом «оператор» был другой символ, за которым непосредственно следовал «оператор». А иначе такую замену делать нельзя.
Представьте например, правило официанта. Осуществлять замену грязной тарелки на выписанный счет можно при наличии опустошенного бокала. В другом контексте (при полном бокале [граненом стакане] рядом) вместо грязной тарелки клиенту предлагается новая закуска.
Для того, чтобы грамматика относилась к типу КЗдостаточно, чтобы хотя бы одно правило было именно первого типа. (Остальные могут быть других типов, кроме нулевого).
Грамматики второго типа называют КОНТЕКСТНО-СВОБОДНЫМИ(или просто КС). Каждое правило может применяться без оглядки на контекст. Вместо грязной тарелки – новая закуска (без всяких дополнительных условий)… Грамматики разных типов могут порождать один и тот же язык. Компиляторы диктуют требование приводить грамматику к типу КС. Обычно в рамках уже этого типа накладываются дополнительные ограничения, что позволяет существенно упростить грамматический разбор в компиляторе.
Грамматики последнего третьего типа называются АВТОМАТНЫМИили РЕГУЛЯРНЫМИ. Это связано с тем, что они порождаются и распознаются автоматами (эту математическую модель ассоциируют не с Калашниковым, а с фамилиями математиков-логиков Мили Мура Трахтенбротта и т. п.) и регулярными выражениями (это, как и в регулярной армии – выражения строятся по простым правилам и просто распознаются – это тоже математическая модель).
Обычно автоматные грамматики используются на уровне лексики. Лексема, в обычном понимании – это словарная единица. Тем ни менее, с точки зрения компилятора это «символ», коль скоро «словом» будет вся программа. В данном случае, например, 345.08 может быть распознан как один символ – действительное число.
Лексический анализ в компиляторе предшествует синтаксическому анализу… Существуют знаменитые команды UNIX lexи yacc, который позволяют автоматизировать процесс написания лексического и синтаксического анализаторов компилятора.
Что– то мы очень уклонились в сторону программирования. Программирование -это тоже математика. Тоже дискретная. Но уже другая. И это другая история.
А из программирования уже, обычно, так просто не возвращаются…
Лекция 13. СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ
Мало того, что есть алгоритмически неразрешимые задачи и их бесконечно больше, чем задач алгоритмически разрешимых. С практической точки зрения нам не легче, если решение разрешимой задачи мы сможем получим через миллион лет. Раньше не закончить расчеты… Это трудно-решаемые задачи. Для нас (простых смертных) такие задачи не отличаются от задач алгоритмически неразрешимых.
А ситуация с такими задачами еще более туманная, чем с алгоритмической разрешимостью. Пока единственный, фактически, «железный» аргумент нашей беспомощности, что задача относится к трудно-решаемым, что никто пока не нашел для нее легкого решения! Даже американские политики.
Ненормальность такой ситуации усугубится, если учесть, что теоретики рассматривают только конечные дискретные задачи (задачи либо на поиск оптимума, либо распознавания [да-нет]), любая из которых (теоретически) может быть решена хотя бы (за неимением лучшего) простым перебором. Но от этого не легче, если вспомнить легенду об изобретателе шахмат, который попросил в награду за первую клеточку шахматной доски одно зернышко, за вторую два… за 64-ю клеточку – 2 в 64-ой степени зернышек. Что превышает зерновые ресурсы Земного шара.
Одна из книг по сложности вычислений начиналась с цитаты из украинского философа Георгия Сковороды:" Спасибо тебе Господи, что ты создал все нужное нетрудным, а все трудное – ненужным." Но кажется, что здесь более точной будет другая мысль из Сковороды, а именно, эпитафия на его могиле: «Мир ловил меня, но не поймал»… И еще одна мысль более конкретная мысль уже от современных математиков: «Сложность становится проблемой века».
Из-за огромного количества несущественных особенностей различных способов (методов, парадигм) вычисления признаки, которые следовало бы учитывать при определении сложности вычислений слишком многочисленны и противоречивы. Но в конечном счете большинство сходится к тому, что все можно свести к времени (числу элементарных шагов) вычисления и объему памяти. Более того, многие так и видят при этом в качестве наилучших моделей – машины Тьюринга.
Проблему быстро свели к двум словам и их сочетанию.
Эти слова Polinomial – полиномиальныйи Nondeterministic – недетерминированный.
Возьмем большой мешок камней и решим задачу поиска самого большого камня. Будем вынимать поочередно камни, сравнивая с самым большим на данный момент. Исчерпав мешок мы оставим в руках самый большой камень. Если число камней мы увеличим в 2 раза, то сложность решения задачи тоже увеличится (примерно) в два раза. Если возьмем мешок с "n" то и трудность решения будет пропорциональна "n". Говорят, что такую задачу можно решить за полиномиальное время. Если вы решаете задачу нахождения самого большого ребра в полном нагруженном графе, то это тоже задача полиномиальной сложности, исходя из формулы для полного графа, увеличивающая сложность с ростом числа вершин по закону роста числа ребер, пропорциональному «n квадрат».
Однако, есть задачки (для тех же графов), для которых не найдено простых (полиномиальных) решений. Вторым из классических примеров таких задач (первый оставим для финала) служит задача о коммивояжере: Каков минимальный цикл в нагруженном графе, что при обходе его в каждую вершину заходим однажды. Для этой задачи есть только «трудные решения», сложность которых растет по экспоненте (как число зернышек на шахматной доске).
Но проверить решение такой задачи можно за полиномиальное время. Вся сложность в том, чтобы знать «траекторию решения». А вот снять проблему выбора правильной траектории позволяет недетерминированная машина Тьюринга, которую можно представить как сколь угодно большое число (обычных детерминированных) машин, каждая из которых делает попытку добраться до решения задачи по одной из возможных траекторий. У кого из читателей фантазия при этом отказывает, могут просто представить себе бога (говорят – «оракула»), который подсказывает правильный путь, чтобы не гонять кучу машин неведомыми тропами. Конечный эффект тот же.
Таким образом, множество труднорешаемых задач ( NPзадач) относится к задачам, решаемым недетерминированной машиной за полиномиальное время. А проблему сложности вычислений математики выразили в виде формулы, которую все-таки приведу из-за ее краткости и «нетрудности» печати:
P = NP?
Интересно, говорят этой формулой математики, совпадают ли множество задач, решаемых за полиномиальное время и множество NPзадач? Может просто толку пока не хватает найти простые решения…
Как бы там ни было, а задачи, для которых простые (полиномиальные) решения пока не найдены, существуют. И чем дальше, тем больше математики упорствуют в этой (недоказанной) уверенности. Более того, они коллекционируют типовые труднорешаемые задачи, которых уже набралось не менее тысячи. Более того, утверждают, что одни труднорешаемые задачи сводятся к другим труднорешаемым задачам. Поэтому даже используется для таких задач термин " NP–полные" задачи. И делается радикальное заявление: если хоть для одной NP–полной задачи будет найдено простое (полиномиальное) решение, тогда простое решение будет найдено и для всех остальных NP–полных задач. Тогда будет доказано P=NPи проблема сложности вычислений в этом ее виде будет закрыта!
А ситуация с такими задачами еще более туманная, чем с алгоритмической разрешимостью. Пока единственный, фактически, «железный» аргумент нашей беспомощности, что задача относится к трудно-решаемым, что никто пока не нашел для нее легкого решения! Даже американские политики.
Ненормальность такой ситуации усугубится, если учесть, что теоретики рассматривают только конечные дискретные задачи (задачи либо на поиск оптимума, либо распознавания [да-нет]), любая из которых (теоретически) может быть решена хотя бы (за неимением лучшего) простым перебором. Но от этого не легче, если вспомнить легенду об изобретателе шахмат, который попросил в награду за первую клеточку шахматной доски одно зернышко, за вторую два… за 64-ю клеточку – 2 в 64-ой степени зернышек. Что превышает зерновые ресурсы Земного шара.
Одна из книг по сложности вычислений начиналась с цитаты из украинского философа Георгия Сковороды:" Спасибо тебе Господи, что ты создал все нужное нетрудным, а все трудное – ненужным." Но кажется, что здесь более точной будет другая мысль из Сковороды, а именно, эпитафия на его могиле: «Мир ловил меня, но не поймал»… И еще одна мысль более конкретная мысль уже от современных математиков: «Сложность становится проблемой века».
Из-за огромного количества несущественных особенностей различных способов (методов, парадигм) вычисления признаки, которые следовало бы учитывать при определении сложности вычислений слишком многочисленны и противоречивы. Но в конечном счете большинство сходится к тому, что все можно свести к времени (числу элементарных шагов) вычисления и объему памяти. Более того, многие так и видят при этом в качестве наилучших моделей – машины Тьюринга.
Проблему быстро свели к двум словам и их сочетанию.
Эти слова Polinomial – полиномиальныйи Nondeterministic – недетерминированный.
Возьмем большой мешок камней и решим задачу поиска самого большого камня. Будем вынимать поочередно камни, сравнивая с самым большим на данный момент. Исчерпав мешок мы оставим в руках самый большой камень. Если число камней мы увеличим в 2 раза, то сложность решения задачи тоже увеличится (примерно) в два раза. Если возьмем мешок с "n" то и трудность решения будет пропорциональна "n". Говорят, что такую задачу можно решить за полиномиальное время. Если вы решаете задачу нахождения самого большого ребра в полном нагруженном графе, то это тоже задача полиномиальной сложности, исходя из формулы для полного графа, увеличивающая сложность с ростом числа вершин по закону роста числа ребер, пропорциональному «n квадрат».
Однако, есть задачки (для тех же графов), для которых не найдено простых (полиномиальных) решений. Вторым из классических примеров таких задач (первый оставим для финала) служит задача о коммивояжере: Каков минимальный цикл в нагруженном графе, что при обходе его в каждую вершину заходим однажды. Для этой задачи есть только «трудные решения», сложность которых растет по экспоненте (как число зернышек на шахматной доске).
Но проверить решение такой задачи можно за полиномиальное время. Вся сложность в том, чтобы знать «траекторию решения». А вот снять проблему выбора правильной траектории позволяет недетерминированная машина Тьюринга, которую можно представить как сколь угодно большое число (обычных детерминированных) машин, каждая из которых делает попытку добраться до решения задачи по одной из возможных траекторий. У кого из читателей фантазия при этом отказывает, могут просто представить себе бога (говорят – «оракула»), который подсказывает правильный путь, чтобы не гонять кучу машин неведомыми тропами. Конечный эффект тот же.
Таким образом, множество труднорешаемых задач ( NPзадач) относится к задачам, решаемым недетерминированной машиной за полиномиальное время. А проблему сложности вычислений математики выразили в виде формулы, которую все-таки приведу из-за ее краткости и «нетрудности» печати:
P = NP?
Интересно, говорят этой формулой математики, совпадают ли множество задач, решаемых за полиномиальное время и множество NPзадач? Может просто толку пока не хватает найти простые решения…
Как бы там ни было, а задачи, для которых простые (полиномиальные) решения пока не найдены, существуют. И чем дальше, тем больше математики упорствуют в этой (недоказанной) уверенности. Более того, они коллекционируют типовые труднорешаемые задачи, которых уже набралось не менее тысячи. Более того, утверждают, что одни труднорешаемые задачи сводятся к другим труднорешаемым задачам. Поэтому даже используется для таких задач термин " NP–полные" задачи. И делается радикальное заявление: если хоть для одной NP–полной задачи будет найдено простое (полиномиальное) решение, тогда простое решение будет найдено и для всех остальных NP–полных задач. Тогда будет доказано P=NPи проблема сложности вычислений в этом ее виде будет закрыта!
ПОСЛЕСЛОВИЕ
Самой первой
NP–полной задачей стала задача нахождения клик графа, то есть полных подграфов данного графа с конкретным числом вершин…
Но в середине семидесятых годов были опубликованы так называемые " алгоритмы Магу", которые исключили из числа переборных не только задачи типа «восьми ферзей» (прежде стандартный полигон для эвристических алгоритмов «искусственного интеллекта»), но там и клики графа также находятся с помощью несложных манипуляций на уровне алгебры высказываний (преобразования выражения к ДНФ), что ни как не выше полиномиальной сложности.
Мало радости признаваться в собственной бестолковости и некомпетентности, но проблема трудно решаемых задач для меня существует в несколько извращенном виде.
Но в середине семидесятых годов были опубликованы так называемые " алгоритмы Магу", которые исключили из числа переборных не только задачи типа «восьми ферзей» (прежде стандартный полигон для эвристических алгоритмов «искусственного интеллекта»), но там и клики графа также находятся с помощью несложных манипуляций на уровне алгебры высказываний (преобразования выражения к ДНФ), что ни как не выше полиномиальной сложности.
Мало радости признаваться в собственной бестолковости и некомпетентности, но проблема трудно решаемых задач для меня существует в несколько извращенном виде.