Текст удивляет даже больше, чем программы. Очень круто!
Есть такая летняя компьютерная школа. Всех детей они делят на группы по уровню развития. Основной упор делается на алгоритмы и решение математически-алгоритмических задач. Преподаватели там из МГУ, МФТИ, СПбГУ, ИТМО, УрФУ. Я узнал о ней поздно, но даже одна единственная поездка в качестве школьника запомнилась надолго и сильно изменила жизнь (в лучшую сторону :). Очень рекомендую.
P.S. Да, там что-то пишут про 6-10 класс, но написать в любом случае стоит. Школьники из младшей школы там тоже бывают.
Я скорее про игрушки типа реверси, шашки, клоподавки и т.п. На самом деле может составить. У голых MCTS есть проблема с оценкой действий. Это дорого. Я пытался прикрутить их к войнам вирусов, и скажем так, они с большим трудом чуть-чуть отличались от рандома, при этом жрали секунды процессорного времени.
Я слышал, что в 2006 кто-то играл с ними в го и даже до какого-то дана дошел и все в режиме unsupervised learning. Но вот интересно, было ли у них обучение и какое? В голом MCTS его нет, значит, весь процесс принятия решений остается на момент обработки запроса. Т.е. интересно в первую очередь, что же там за эвристики сверху пилят.
RTS — другой пласт игр. Конечно, реакция у компьютера будет на порядки лучше. Вопрос скорее, насколько будет легко человеку найти стиль игры, с которым компьютер не будет справляться.
По моим наблюдениям возраст такого молодого поколения колеблется от 15 до 60. Что на форумах, что в реальной жизни получить внятный ответ вместо мутных рассуждений получается далеко не всегда.
На самом деле, если тебе говорят, что ты мудак — это не страшно. Ты просто поймешь, что здесь ловить нечего, и пойдешь в другое место. Благо, есть еще англоязычный интернет. На тостере я временами наблюдаю более печальную картину. Отвечающие не различают или не хотят различать понятия "я не знаю, как это сделать" и "это невозможно". Вреда от таких ответов гораздо больше.
Я правильно понимаю, что идея — использовать подсчет числа различных элементов, чтобы проверить лежит ли элемент в множестве. Если это так, нам потребуется константная абсолютная погрешность. По информационным оценкам на такое потребуется как минимум линейная память, а по оценкам HyperLogLog-а она будет квадратичной от числа различных элементов.
По поводу 1-разреженных векторов и проверок. Да, мы хотим уместить память алгоритма в . Если не дать алгоритму ошибаться, нижняя оценка по памяти взлетит до . Это на самом деле несложно показать.
Представьте, что у вас есть алгоритм, который умеет детерминированно определять, осталась в векторе ровно одна ненулевая позиция или нет. Возьмем множество размера и кинем обновления для всех . После обработки всех обновлений алгоритм сформирует слепок памяти. Вот я утверждаю, что из этого слепка можно восстановить все множество . Поскольку всего таких множеств , то размер слепка будет порядка .
Восстанавливать просто: перебираем все подмножества размером и кидаем обновления . Если угадали подмножество , то результат будет 1-разреженным вектором и алгоритм вернет True, иначе – False. Берем объединение по всем хорошим и получаем .
Интересно, что Канн-Гринвальд детерминированный и всегда дает ответ с нужной погрешностью. Но он мне в свое время показался очень сложным, особенно в смысле понимания, почему работает.
У задачи поиска медианы и произвольного -квантиля есть очень простое вероятностное решение через сэмплирование. Берем из всего набора случайно элементов, сортируем. Теперь, если хотим посчитать -квантиль, нужно просто вернуть -ый элемент. С константной вероятностью ответ будет на расстоянии не более от правильного. Если нужна вероятность ошибки , берем соответсвенно элементов.
Гарантия доказывается довольно просто через неравенство Чернова.
P.S. Предлагаю на подобные вещи ставить тэг data streaming.
Есть такая летняя компьютерная школа. Всех детей они делят на группы по уровню развития. Основной упор делается на алгоритмы и решение математически-алгоритмических задач. Преподаватели там из МГУ, МФТИ, СПбГУ, ИТМО, УрФУ. Я узнал о ней поздно, но даже одна единственная поездка в качестве школьника запомнилась надолго и сильно изменила жизнь (в лучшую сторону :). Очень рекомендую.
P.S. Да, там что-то пишут про 6-10 класс, но написать в любом случае стоит. Школьники из младшей школы там тоже бывают.
Я слышал, что в 2006 кто-то играл с ними в го и даже до какого-то дана дошел и все в режиме unsupervised learning. Но вот интересно, было ли у них обучение и какое? В голом MCTS его нет, значит, весь процесс принятия решений остается на момент обработки запроса. Т.е. интересно в первую очередь, что же там за эвристики сверху пилят.
На самом деле, если тебе говорят, что ты мудак — это не страшно. Ты просто поймешь, что здесь ловить нечего, и пойдешь в другое место. Благо, есть еще англоязычный интернет. На тостере я временами наблюдаю более печальную картину. Отвечающие не различают или не хотят различать понятия "я не знаю, как это сделать" и "это невозможно". Вреда от таких ответов гораздо больше.
Если хочется максимально ужать множество, посмотрите коды Голомба: http://giovanni.bajo.it/post/47119962313/golomb-coded-sets-smaller-than-bloom-filters
По поводу 1-разреженных векторов и проверок. Да, мы хотим уместить память алгоритма в
Представьте, что у вас есть алгоритм, который умеет детерминированно определять, осталась в векторе ровно одна ненулевая позиция или нет. Возьмем множество
Восстанавливать просто: перебираем все подмножества
Зависит от начального уровня. Здесь нужно за спиной иметь базовые алгоритмы, графы и теорию вероятностей.
У задачи поиска медианы и произвольного
Гарантия доказывается довольно просто через неравенство Чернова.
P.S. Предлагаю на подобные вещи ставить тэг data streaming.
Да, спасибо за ответ.