Думаю, независимость стратегий стоит обосновать получше: когда на рынке два продавца, каждый на свою аудиторию, иногда им будет выгодно кредитовать друг друга коровами.
Я еще раз обдумал Ваше предложение и должен признать, что приближенное решение можно свести к задаче сильно напоминающей поиск максимального по мощности циклического потока в графе, однако на этот поток, в случае чистой стратегии (детерминированной), накладываются ограничения неделимости в узлах, поэтому, как Вы понимаете, вся простота алгоритмов теряется. Если применять смешанные стратегии (зависящие от случая), решение приближенной задачи действительно можно найти указанным способом, однако есть две проблемы:
а) нужно доказать, что максимум достигается на чистой стратегии (почти очевидно)
б) вычислительная сложность растет по экспоненте от величины обратной к величине шага дискретизации.
Многие из ваших замечаний разумны, например, как вы правильно заметили, нужно учитывать, какие коровы уже заказаны и что они придут в будущем. Если же ваши ожидания насчет потока клиентов не оправдываются, действительно не стоит заказывать лишних коров, и поэтому правдоподобно, что заказ, если происходит, то только в момент продажи. Однако процесс требует постоянного управления и не сводится к определению размера буфера, поскольку оптимальность зависит не только от количества коров в вашем распоряжении сейчас но и от именно функции «уже заказанное пополнение»(«время»). С выбраковкой классов тоже не стоит спешить: если все шло как по часам, а затем случайно целый период T не было продаж, то возможно от лишних коров стоит избавится при первой возможности.
Как мне представляется, задача достаточно сложная, ее решение с обоснованием, если оно где-то опубликовано,- небольшая глава в книге по алгоритмам. Не стоит торопится с ответом)
Боюсь, оба решения вкладывают в вероятность совсем не тот смысл, который принят для этого понятия в математике. Вы никогда не знаете, сколько придет покупателей в ближайший час и каких: у вас есть лишь вероятности каждого их набора, которые оправдываются в среднем и то лишь по вероятности. Пусть, например, класс покупателей только один, их количество за час имеет распределение Пуассона с математическим ожиданием 1. Если вы собираетесь закупать раз в час корову, то учтите, что более чем в четверти случаев по истечению часа не сможете продать купленную в прошлый раз, и с довольно большой вероятностью, если на начало очередного часа у вас будет только одна корова, то по крайней мере один клиент будет потерян.
1) Да есть некоторая неточность языка. Считается, что Мужик всегда способен продать, если захочет.
2)Вы правы, забыл уточнить: независимые пуассоновские процессы с непрерывным временем(определение можно посмотреть почти в любой книге по теории вероятностей или математической энциклопедии)
3)Ввиду 2) появление когда либо сразу двух покупателей — событие нулевой вероятности
Спасибо за совет. В статье я предполагал, что задача в стиле книг бородатых 50-х годов и интересно прежде всего концептуальное, а не вычислительное решение, с исследованием асимптотик.
Может быть, стоит определиться сначала с тем, что подразумевается под количеством информации? Если Шарик знает, что никаких других сообщений он получить не может, то количество информации 0, если его могут еще поздравить верблюдом, то 1. Информация в классическом понимании — мера разнообразия вероятных исходов. В постановке задачи этот математический термин используется спекулятивно, хотя нельзя не признать и присутствия разумного зерна в поднятом вопросе.
Я очень рад, что вам удалось решить этот парадокс, и мне хотелось бы по этому поводу указать на некоторые его следствия и добавить пару комментариев к решению.
На сегодняшний день в математике не используются языки, объектами высказываний которых были бы значения предложений самих этих языков, поэтому, как вы правильно заметили, доказательство всюду определенности G(n) не может быть проведено внутри никакой из современных теорий, если та использовалась для построения участвующего в парадоксе списка. Однако, математики никогда не ограничивали себя одной какой-либо теорией и не гнушаются на ходу придумать одну-другую, лишь бы с их помощью решалась стоящая перед ними на тот момент задача. Скорее, у каждого из них имеется некоторый запас доказательных методов и неформальных «истин», в которые они верят. В таком свете, приведенный парадокс показывает, что если вы имеете некоторый набор самоочевидных для вас доказательных методов, то все равно этот набор не включает достаточно самоочевидного относительно этого набора диагонального метода, участвующего в парадоксе.
Второе замечание — а собственно чем так плохи языки, способные высказываться о значении своих предложений и как решается парадокс в этом случае? Вы можете шаг за шагом попытаться представить в этом случае алгоритм действий, описанный в парадоксе. Скажем, вы уже нашли первые сто программ с доказательствами их всюду определенности и вот теперь смотрите на предложение, которое описывает диагональную конструкцию. Задает ли оно функцию и является ли тогда доказательством ее всюду определенности? Если предположить, что «да», то поставив его на сто первое место в списке, вы тут же придете к противоречию, если же вы решите «нет» и не поместите его в список, то с этого самого момента оно начнет задавать всюду определенную функцию и быть доказательством ее всюду определенности.
Все это было бы простой забавой и ненужным софизмом, если бы человечество остро не нуждалось в языках, способных высказываться о собственном значении в связи с задачами восприятия и мышления (описывая что-то, вы всегда можете описать и ваш язык описания, а размышляя над чем-то, размышлять над ходом мыслей). Но пока революция в основаниях математики только зреет.
Хорошо, попытаюсь объяснить.
Вся математика с начала прошлого века попыталась стать формальной. С этого времени доказательства проводятся в формальных аксиоматических системах, которые суть
1. некоторый способ составлять слова и предложения из печатных символов, этот способ задает язык теории, причем проверка, является ли некоторая цепочка символов словом или предложением, должна быть выполнима всегда завершающимся алгоритмом, одним для всех цепочек.
2. формальных правил вывода, позволяющим из всякого семейства предложений, взятых в качестве первоначальных, выводить (продуцировать) другие предложения. На процесс продуцирования налагается то же требование алгоритмичности, что и в пункте 1.
3. Некоторого начального семейства формул, называемых аксиомами. Это семейство не обязательно должно быть конечным, однако должен быть предъявлен алгоритм, позволяющий для всякого предложения языка эффективно выяснить, является оно аксиомой или нет.
Формула языка называется доказанной, если она аксиома либо получена из аксиом и уже доказанных формул.
Основной прием предыдущего парадокса состоит в том, что все программы МТ, для которых существует доказательство конечности времени выполнения на каждом натуральном числе, можно выписать на листке бумаги в ряд (алгоритмически перечислить). Для этого будем перебирать все цепочки из букв и пробелов и алгоритмически проверять не является ли каждая из них доказательством конечности выполнения некоторой программы МТ на всех натуральных числах. Как только вы обнаружили очередное доказательство, проверьте нет ли указанной в нем программы в вашем списке, если нет — добавьте в него программу и найденное доказательство. Утверждается, что если программа имеет доказательство конечности своего выполнения на каждом натуральном числе, то рано или поздно вы на него наткнетесь и она таким образом попадет в список.
Конечно «существуют» программы, которые завершаются на любом натуральном числе, но этот факт никак нельзя доказать, однако для приведенного парадокса этот факт не имеет значения.
А вот вам еще одна головоломка про машину Тьюринга:
Не для всех программ, реализующих функции из натуральных в множество {0,1}, есть способ выяснить, останавливаются ли они на каждом аргументе или нет. Однако для некоторых таких программ существуют доказательства того, что они останавливаются. Процесс же поиска всех таких доказательств, как, наверное, известно читателям, всегда можно переложить на некоторую МТ, а значит множество программ, реализующих упомянутые функции и имеющих доказательство своей всюду определенности, алгоритмически перечислимо. Давайте построим МТ, перечисляющую для них пары (текст алгоритма, доказательство), и определим новую функцию G(n): она равна на n-том аргументе 1, если n-тая функция равна на нем 0 и наоборот. Читатель должен видеть, что задающий эту функцию алгоритм, не только всюду определен, но и имеет доказательство своей всюду определенности и конечно же не может совпадать ни с одним из имеющихся в списке!
Есть ли решение у этого парадокса?
Очень интересует способ реализации схемы смыслового поиска, даже в предположении, что яндекс располагает идеальным алгоритмом анализа смысла. С обратным индексом поиска по словам все было просто: по каждому слову собираете адреса документов, в которых оно упоминалось, затем пытаетесь найти документы, в которых больше всего значимых слов из запроса.
Внимание! Как составить идекс смыслов? Я хочу указать на одну принципиальную трудность: конечная конструктивная вещь может иметь бесконечно много нетривиальных свойств, например, сколько интересных свойств двойки вам известно? Представим нелепую упрощенную ситуацию: каждый документы в мире — запись некоторого натурального числа, мой запрос — некоторое хорошее в том смысле свойство натуральных чисел, что по любому конкретному числу можно понять, удовлетворяет оно этому свойству или нет. Каким образом будет обрабатываться мой запрос?
Я хочу сказать, что один и тот же текст при смысловом анализе может отвечать на множество вопросов, предвидеть же заранее все из них может оказаться бесконечно сложной задачей, чуть более сложной, чем анализировать каждый документ на соответствие каждому запросу.
Часто говорят, а давайте сделаем ракету и полетим на Луну, в этом случае стоит спросить: «Предположим, вы сделали ракету и долетели до Луны, что дальше?»
Честно говоря, не так просто сказать чему равна энтропия черепков или статуи, но если перевести спор в область интуитивной физики, то легко можно представить, как, падая, статуя разбивается на много мелких черепков, и довольно трудно, как черепки, брошенные на пол, собираются в образ прекрасной женщины. Говорят, что в природе энтропия замкнутой системы не может уменьшаться.
Еще одна тонкость, которая никак не делает лучше мой пример, но в действительности уничтожает ваши контраргументы, — это то, что состояния, переводимые друг в друга каким либо процессом вычисления, могут иметь различную энтропию (Больцмана): вычислительная машина, как и холодильник, не могут работать без притока энергии извне. Иными словами, чтобы собрать статую, вам придется съесть бутербродов эдак пять, а куда пойдут эти джоули: на порождение или на уничтожение информации, из поверхностного анализа не ясно.
Цель моего полудетского примера со статуей была обратить внимание на то, что большинство естественных сообщений хорошо структурированы и крайне не случайны. Например, текст, который Вы читаете, мало похож на совсем уж случайную последовательность букв и может быть сжат по объему в несколько раз любым адекватным архиватором.
а) нужно доказать, что максимум достигается на чистой стратегии (почти очевидно)
б) вычислительная сложность растет по экспоненте от величины обратной к величине шага дискретизации.
2)Вы правы, забыл уточнить: независимые пуассоновские процессы с непрерывным временем(определение можно посмотреть почти в любой книге по теории вероятностей или математической энциклопедии)
3)Ввиду 2) появление когда либо сразу двух покупателей — событие нулевой вероятности
На сегодняшний день в математике не используются языки, объектами высказываний которых были бы значения предложений самих этих языков, поэтому, как вы правильно заметили, доказательство всюду определенности G(n) не может быть проведено внутри никакой из современных теорий, если та использовалась для построения участвующего в парадоксе списка. Однако, математики никогда не ограничивали себя одной какой-либо теорией и не гнушаются на ходу придумать одну-другую, лишь бы с их помощью решалась стоящая перед ними на тот момент задача. Скорее, у каждого из них имеется некоторый запас доказательных методов и неформальных «истин», в которые они верят. В таком свете, приведенный парадокс показывает, что если вы имеете некоторый набор самоочевидных для вас доказательных методов, то все равно этот набор не включает достаточно самоочевидного относительно этого набора диагонального метода, участвующего в парадоксе.
Второе замечание — а собственно чем так плохи языки, способные высказываться о значении своих предложений и как решается парадокс в этом случае? Вы можете шаг за шагом попытаться представить в этом случае алгоритм действий, описанный в парадоксе. Скажем, вы уже нашли первые сто программ с доказательствами их всюду определенности и вот теперь смотрите на предложение, которое описывает диагональную конструкцию. Задает ли оно функцию и является ли тогда доказательством ее всюду определенности? Если предположить, что «да», то поставив его на сто первое место в списке, вы тут же придете к противоречию, если же вы решите «нет» и не поместите его в список, то с этого самого момента оно начнет задавать всюду определенную функцию и быть доказательством ее всюду определенности.
Все это было бы простой забавой и ненужным софизмом, если бы человечество остро не нуждалось в языках, способных высказываться о собственном значении в связи с задачами восприятия и мышления (описывая что-то, вы всегда можете описать и ваш язык описания, а размышляя над чем-то, размышлять над ходом мыслей). Но пока революция в основаниях математики только зреет.
Вся математика с начала прошлого века попыталась стать формальной. С этого времени доказательства проводятся в формальных аксиоматических системах, которые суть
1. некоторый способ составлять слова и предложения из печатных символов, этот способ задает язык теории, причем проверка, является ли некоторая цепочка символов словом или предложением, должна быть выполнима всегда завершающимся алгоритмом, одним для всех цепочек.
2. формальных правил вывода, позволяющим из всякого семейства предложений, взятых в качестве первоначальных, выводить (продуцировать) другие предложения. На процесс продуцирования налагается то же требование алгоритмичности, что и в пункте 1.
3. Некоторого начального семейства формул, называемых аксиомами. Это семейство не обязательно должно быть конечным, однако должен быть предъявлен алгоритм, позволяющий для всякого предложения языка эффективно выяснить, является оно аксиомой или нет.
Формула языка называется доказанной, если она аксиома либо получена из аксиом и уже доказанных формул.
Основной прием предыдущего парадокса состоит в том, что все программы МТ, для которых существует доказательство конечности времени выполнения на каждом натуральном числе, можно выписать на листке бумаги в ряд (алгоритмически перечислить). Для этого будем перебирать все цепочки из букв и пробелов и алгоритмически проверять не является ли каждая из них доказательством конечности выполнения некоторой программы МТ на всех натуральных числах. Как только вы обнаружили очередное доказательство, проверьте нет ли указанной в нем программы в вашем списке, если нет — добавьте в него программу и найденное доказательство. Утверждается, что если программа имеет доказательство конечности своего выполнения на каждом натуральном числе, то рано или поздно вы на него наткнетесь и она таким образом попадет в список.
Конечно «существуют» программы, которые завершаются на любом натуральном числе, но этот факт никак нельзя доказать, однако для приведенного парадокса этот факт не имеет значения.
Не для всех программ, реализующих функции из натуральных в множество {0,1}, есть способ выяснить, останавливаются ли они на каждом аргументе или нет. Однако для некоторых таких программ существуют доказательства того, что они останавливаются. Процесс же поиска всех таких доказательств, как, наверное, известно читателям, всегда можно переложить на некоторую МТ, а значит множество программ, реализующих упомянутые функции и имеющих доказательство своей всюду определенности, алгоритмически перечислимо. Давайте построим МТ, перечисляющую для них пары (текст алгоритма, доказательство), и определим новую функцию G(n): она равна на n-том аргументе 1, если n-тая функция равна на нем 0 и наоборот. Читатель должен видеть, что задающий эту функцию алгоритм, не только всюду определен, но и имеет доказательство своей всюду определенности и конечно же не может совпадать ни с одним из имеющихся в списке!
Есть ли решение у этого парадокса?
Внимание! Как составить идекс смыслов? Я хочу указать на одну принципиальную трудность: конечная конструктивная вещь может иметь бесконечно много нетривиальных свойств, например, сколько интересных свойств двойки вам известно? Представим нелепую упрощенную ситуацию: каждый документы в мире — запись некоторого натурального числа, мой запрос — некоторое хорошее в том смысле свойство натуральных чисел, что по любому конкретному числу можно понять, удовлетворяет оно этому свойству или нет. Каким образом будет обрабатываться мой запрос?
Я хочу сказать, что один и тот же текст при смысловом анализе может отвечать на множество вопросов, предвидеть же заранее все из них может оказаться бесконечно сложной задачей, чуть более сложной, чем анализировать каждый документ на соответствие каждому запросу.
Часто говорят, а давайте сделаем ракету и полетим на Луну, в этом случае стоит спросить: «Предположим, вы сделали ракету и долетели до Луны, что дальше?»
Еще одна тонкость, которая никак не делает лучше мой пример, но в действительности уничтожает ваши контраргументы, — это то, что состояния, переводимые друг в друга каким либо процессом вычисления, могут иметь различную энтропию (Больцмана): вычислительная машина, как и холодильник, не могут работать без притока энергии извне. Иными словами, чтобы собрать статую, вам придется съесть бутербродов эдак пять, а куда пойдут эти джоули: на порождение или на уничтожение информации, из поверхностного анализа не ясно.
Цель моего полудетского примера со статуей была обратить внимание на то, что большинство естественных сообщений хорошо структурированы и крайне не случайны. Например, текст, который Вы читаете, мало похож на совсем уж случайную последовательность букв и может быть сжат по объему в несколько раз любым адекватным архиватором.