Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 54
То ли я чего-то не понял, то ли операция «нажать на барабан» коммутативна, и всего вариантов 3^5 (да и их перебирать не надо).
Ну, конкретно для этой задачи можно составить систему линейных уравнений, которая примитивно решается за N^3 ( можно и быстрей ), в то время как ваш способ имеет экспоненциальную сложность.
А вообще не понял, о чем статья. О том, что интуиция рулит? Ну, так вы написали программу которая делает тупые действия, а не ищет решение данной проблемы, поэтому неудивительно, что она действовала так тупо.
Разумеется, что программа написанная за 5 минут на коленке не может сравниться в изощренности с человеческим мозгом.
А вообще не понял, о чем статья. О том, что интуиция рулит? Ну, так вы написали программу которая делает тупые действия, а не ищет решение данной проблемы, поэтому неудивительно, что она действовала так тупо.
Разумеется, что программа написанная за 5 минут на коленке не может сравниться в изощренности с человеческим мозгом.
Согласен, линейные уравнения — первое что приходит в голову.
from sympy import *
A = Matrix([[1, -1, 1, 0, 0],
[1, 1, 0, 0, -1],
[0, -1, 1, -1, 0],
[-1, 0, 0, 1, 1],
[0, 0, -1, 1, 1]]).T
b = Matrix([0,0,0,-3,-1])
sol = A.LUsolve(b)
print map(lambda a: a % 4, sol)
[2, 1, 3, 3, 1]
Причем здесь линейные уравнения? Это поисковая задача.
Решение:
1 1 1 2 3 3 3 4 4 4
Я немного ошибся с статье (давно дело было, детали забыл). Кратчайшее решение имеет длину не 14, а 10, но это сути не меняет.
Решение:
1 1 1 2 3 3 3 4 4 4
Я немного ошибся с статье (давно дело было, детали забыл). Кратчайшее решение имеет длину не 14, а 10, но это сути не меняет.
При том, что решение может быть представлено как решение системы линейных уравнений.
Как верно заметили выше — операции поворота барабанов коммутативны, то есть не имеет значения, в каком порядке крутить выбирать барабаны — важно только то, сколько раз каждый будет повернут. Если количество поворотов каждого из барабанов обозначить переменными xi — как раз СЛАУ из пяти уравнений и получится.
Как верно заметили выше — операции поворота барабанов коммутативны, то есть не имеет значения, в каком порядке крутить выбирать барабаны — важно только то, сколько раз каждый будет повернут. Если количество поворотов каждого из барабанов обозначить переменными xi — как раз СЛАУ из пяти уравнений и получится.
Ну вы же сами изобразили повороты как +1 и -1, и получилась матрица. К тому же, через уравнения сразу находится кратчайшее решение.
PS накосячил с данными, там не [0,0,0,-3,-1] а [0, -2, 2, -3, -1]. И получается как раз [0, 3, 1, 3, 3]
PS накосячил с данными, там не [0,0,0,-3,-1] а [0, -2, 2, -3, -1]. И получается как раз [0, 3, 1, 3, 3]
ОК, я понял ваше решение (без объяснения оно выглядит странно). Еще я вспомнил, один наш бизнес-аналитик решил задачу в Excel-е. Он скорее всего использовал ваш метод.
В общем, да, задачу можно решить оптимально несколькими способами, но суть не в том можно или нельзя ее решить, а в том как ее решает обычный, случайный человек без математического образования, а именно в методе тыка и его эффективности у разных людей.
Решая задачу методом тыка, человек (в данном случае я) перебирает комбинации, не задумываясь о коммутативности и тем более не решая систем уравнений. Я помню, что перебирал варианты, возвращаясь к предыдущим, и я точно не перебирал сотни комбинаций (это заняло бы больше времени). Барабанов в этой задаче не просто так пять, именно это число образов человек может одновременно держать в памяти, поэтому предсказать ходы более чем на один шаг здесь очень сложно. Парадокс заключается в том, что я делал ходы без всяких рассчетов, на основании внутреннего ощущения, и это дало результат. Объяснить это удачей сложно, потому что уж слишком малая здесь вероятность попасть пальцем в небо.
В конце концов, ваше решение тоже как-то пришло к вам в голову или вы его вспомнили, но тогда оно как-то пришло в голову кому-то другому. Не известно формального способа решить любую задачу, но задачи как-то решаются, и в этом заключается загадка.
В общем, да, задачу можно решить оптимально несколькими способами, но суть не в том можно или нельзя ее решить, а в том как ее решает обычный, случайный человек без математического образования, а именно в методе тыка и его эффективности у разных людей.
Решая задачу методом тыка, человек (в данном случае я) перебирает комбинации, не задумываясь о коммутативности и тем более не решая систем уравнений. Я помню, что перебирал варианты, возвращаясь к предыдущим, и я точно не перебирал сотни комбинаций (это заняло бы больше времени). Барабанов в этой задаче не просто так пять, именно это число образов человек может одновременно держать в памяти, поэтому предсказать ходы более чем на один шаг здесь очень сложно. Парадокс заключается в том, что я делал ходы без всяких рассчетов, на основании внутреннего ощущения, и это дало результат. Объяснить это удачей сложно, потому что уж слишком малая здесь вероятность попасть пальцем в небо.
В конце концов, ваше решение тоже как-то пришло к вам в голову или вы его вспомнили, но тогда оно как-то пришло в голову кому-то другому. Не известно формального способа решить любую задачу, но задачи как-то решаются, и в этом заключается загадка.
Ваше «поисковое» решение нашло неоптимальный вариант. Кратчайшее решение имеет длину 10 (см. товарища hellman ниже) и находится как решение СЛУ [0;2;2;1;3]=K*M, где M — Ваша транспонированная матрица паттернов. Проблема не в отсутствии алгоритмов, а в Вашем неумении их использовать.
Любая задача математики может быть сформулирована как поисковая. «найти верное решение». Можно даже пространство поиска соорудить, а потом обвинять компьютер, что он дурак и ничего не может решить.
Любая задача математики может быть сформулирована как поисковая. «найти верное решение». Можно даже пространство поиска соорудить, а потом обвинять компьютер, что он дурак и ничего не может решить.
А в чем парадокс то?
У машины нет фантазии для гипотезы
зачем брут-форс? почитайте ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%B2_%D1%88%D0%B8%D1%80%D0%B8%D0%BD%D1%83
Поиск в ширину без априорной оценки и есть brute force. Подбор числа можно реализовать оптимальней и распаралелить.
Это не будет брутфорсом, если не заходить повторно в уже посещенные состояния — это уже будет динамическое программирование, с асимптотическим временем работы O(M^N) = O(1024).
Прямой последовательный перебор тоже не заходит в пройденные состояния.
в общих чертах да, но динамическое программирование в данной ситуации неприменимо — граф состояниий цикличен
Как несложно заметить, у нас всего 4^5 = 1024 вершины. Любой разумный алгоритм поиска решит задачу мгновенно.
Так что пример неудачный. Если Вы не смогли придумать эффективный алгоритм — это не значит, что его нет.
Общая же мысль довольно очевидна. Существование алгоритмически неразрешимых задач — один из краеугольных камней фундаментальной математики (с его помощью например доказываются теоремы Геделя о неполноте).
На практике, если «не очень длинная» машина Тьюринга — это машина Тьюринга длиной <= 100500 бит, то вполне есть алгоритм, который по каждой такой МТ скажет, останавливается она или нет)
Так что пример неудачный. Если Вы не смогли придумать эффективный алгоритм — это не значит, что его нет.
Общая же мысль довольно очевидна. Существование алгоритмически неразрешимых задач — один из краеугольных камней фундаментальной математики (с его помощью например доказываются теоремы Геделя о неполноте).
На практике, если «не очень длинная» машина Тьюринга — это машина Тьюринга длиной <= 100500 бит, то вполне есть алгоритм, который по каждой такой МТ скажет, останавливается она или нет)
Тоже не понял, в чем собственно парадокс. Приведенная задача с машиной Тьюринга не решается алгоритмически в общем случае, для частных случаев решение находится. С человеком так же, некоторые задачи веками ждут решения и не доказана их неразрешимость. Приведите хоть одну задачу, которая неразрешима алгоритмически, но решена человеком в общем виде.
Касательно математики — да, многие задачи изначально решались с привлечением интуиции, но любое доказательство принимается только тогда, когда имеет строго формальную форму. А за пределами математики полной достоверности нет вообще.
Касательно математики — да, многие задачи изначально решались с привлечением интуиции, но любое доказательство принимается только тогда, когда имеет строго формальную форму. А за пределами математики полной достоверности нет вообще.
> Приведите хоть одну задачу, которая неразрешима алгоритмически, но решена человеком в общем виде.
Тест Тьюринга.
Тест Тьюринга.
Все алгоритмы придуманы людьми, но не придумано алгоритма, построения других алгоритмов, потому что невозможно создать алгоритм строящий сам себя.
Простите, что Вы понимаете под «построить алгоритм»? Только формально, пожалуйста.
бездоказательное утверждение.
а алгоритмы, строящие другие алгоритмы, существуют. пример — генетическое программирование
а алгоритмы, строящие другие алгоритмы, существуют. пример — генетическое программирование
Моделирование эволюции — это совсем другая материя. Эволюционные процессы фундаментально недетерминированы, поэтому не могут считаться классическими вычислительными процессами.
Что за бред, простите? С каких пор вероятностные алгоритмы перестали быть алгоритмами, и уж тем более вычислительными процессами (которые, кстати, и есть «другая материя»)? Вы не хотите ли перечитать определение алгоритма и вычислительного процесса, прежде чем писать такую чушь?
«Алгоритм — это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность». (Д. Э. Кнут)
«Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи». (А. Колмогоров)
«Алгоритм — это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату». (А. Марков)
«Алгоритм — точное предписание о выполнении в определённом порядке некоторой системы операций, ведущих к решению всех задач данного типа». (Философский словарь / Под ред. М. М. Розенталя)
«Алгоритм — строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд». (Николай Дмитриевич Угринович, учебник «Информатика и информ. технологии»)
«Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи». (А. Колмогоров)
«Алгоритм — это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату». (А. Марков)
«Алгоритм — точное предписание о выполнении в определённом порядке некоторой системы операций, ведущих к решению всех задач данного типа». (Философский словарь / Под ред. М. М. Розенталя)
«Алгоритм — строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд». (Николай Дмитриевич Угринович, учебник «Информатика и информ. технологии»)
Детерминированный порядок выполнения и детерминированность алгоритма — не одно и то же. Если Вы помните, у Кнута второй том посвящен вероятностным алгоритмам. Ни в одном из приведенных определений нет ни слова об эквивалентности алгоритма вычислительным процессам и отрицания возможности использования случайных величин.
Хорошо, тогда как получить криптографическое случайное число, не имея источника энтропии?
Начнем с того, что Вы понимаете под источником энтропии. Про генераторы псевдослучайных чисел слышали?
С псевдослучайными числами есть одна проблема — рано или поздно они начинают повторяться и в долгосрочной перспективе процесс все равно становится детерминорованным.
Источники энтропии, в контексте криптографии, — это то, что генерирует действительно случайные величины, паттерн которых гарантированно никогда не повторяется. К примеру, перепады напряжения в сети, потеря IP пакетов, движения мышкой и т.д. Из этих данных в операционных системах генерируются криптографические ключи.
Если нам нужны случайные данные для вычисления со сколь угодно большим количеством обращений к генератору случайных чисел, нам нужен генератор действительно случайных чисел, то есть криптографический генератор.
Источники энтропии, в контексте криптографии, — это то, что генерирует действительно случайные величины, паттерн которых гарантированно никогда не повторяется. К примеру, перепады напряжения в сети, потеря IP пакетов, движения мышкой и т.д. Из этих данных в операционных системах генерируются криптографические ключи.
Если нам нужны случайные данные для вычисления со сколь угодно большим количеством обращений к генератору случайных чисел, нам нужен генератор действительно случайных чисел, то есть криптографический генератор.
Последовательность случайных чисел, взятых извне, может считаться исходными данными алгоритма. Это никак не противоречит определению алгоритма. При этом сам алгоритм не изменится. Это и есть «детерминированный порядок выполнения» — структура алгоритма не изменяется в зависимости от входных данных. Это могут быть даже не случайные числа. Представьте машину Тьюринга, которая читает ленту нулей и единиц и останавливается тогда, когда встретит первую единицу на ленте. Длина и содержание ленты при этом никак не влияет на структуру самой машины Тьюринга. Любые взятые извне данные в принципе могут считаться случайными
выделяемое Вами слово определённость говорит только о конечности множества операций, составляющих носитель алгоритма
Не совсем
"Детерминированность (определённость). В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных», вероятностный алгоритм становится подвидом обычного".
"Детерминированность (определённость). В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных», вероятностный алгоритм становится подвидом обычного".
И в чем противоречие? если считать начальное значение генератора псевдослучайных чисел или само случайное число входными данными, вероятностный алгоритм выродится в обычный детерминированный
Кстати, от куда это определение? Оно не совсем верно в части В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. Это не так, если нет оговорки, что различные реализации используют одно мультимножество операций и на множестве операций определено транзитивное отношение.
А давайте теперь вспомним строгое, принятое в математике определение алгоритма (точнее вычислимой функции) (там их несколько, но все они в смысле вычислимости эквивалентны).
Итак. Функция называется вычислимой, если существует вычисляющая ее машина Тьюринга. В понятии МТ случайности нет, да она там и не нужна.
Хотя есть и вариант со случайностью. Как правило, он реализуется путем дополнительного входа, содержащего «результаты бросания монетки».
Обычное требование к вероятностному алгоритму — он дает правильный ответ чаще, чем неправильный. В этом случае наличие случайности на вычислимость никак не влияет. Ибо никто не мешает нам перебрать все возможные варианты выпадения монетки.
Итак. Функция называется вычислимой, если существует вычисляющая ее машина Тьюринга. В понятии МТ случайности нет, да она там и не нужна.
Хотя есть и вариант со случайностью. Как правило, он реализуется путем дополнительного входа, содержащего «результаты бросания монетки».
Обычное требование к вероятностному алгоритму — он дает правильный ответ чаще, чем неправильный. В этом случае наличие случайности на вычислимость никак не влияет. Ибо никто не мешает нам перебрать все возможные варианты выпадения монетки.
Ксати, приведенный «универсальный алгоритм, которым любой обычный человек решает любую головоломку» по-сути есть эвристический поиск в пространстве состояний. Вы просто не определили эвристики «хорошая комбинация» и «оценка состояния».
Складывая числа от 1 до 100 большинство людей тупо сделают цикл 1+2+3+...+100, хотя маленький Гаусс доказательно советовал решение в две операции (1+100)*50. Ничего не напоминает? Тупой перебор vs СЛАУ+метод все того же Гаусса.
P.S. Теги к заметке — это такая тонкая ирония?
P.S. Теги к заметке — это такая тонкая ирония?
Описанную ситуацию можно назвать парадоксом, если считать компьютер волшебной палочкой, а не высокотехнологичным молотком. :)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Интуиция, головоломки и вычислимость