Рубрика «комбинаторика» - 2

в 7:10, , рубрики: 2048, комбинаторика, марковский процесс принятия решений, математика, разработка игр, цепи маркова

Часть 1. Расчёт минимального количества ходов для победы с помощью цепей Маркова

Screenshot of 2048

После недавнего обновления экран «You win!» игры 2048 начал показывать количество ходов, потребовавшихся для победы, и я задался вопросом: сколько же нужно ходов, чтобы выиграть?

В первой части статьи мы ответим на этот вопрос, смоделировав игру 2048 в виде цепи Маркова и проанализировав её, чтобы показать, что вне зависимости от мастерства игрока для победы в среднем нужно не менее 938,8 ходов. Это даёт нам неплохое мерило отсчёта — если вы можете выигрывать примерно за такое количество ходов, то неплохо играете.

Количество ходов, необходимых для победы, зависит от случайности, потому что игра добавляет тайлы 2 и 4 случайным образом. Анализ также покажет, что распределение минимального количества ходов до победы имеет стандартное отклонение в 8,3 хода, и что его общая форма хорошо аппроксимируется смесью биномиальных распределений.
Читать полностью »

в 14:46, , рубрики: Блог компании Московский физико-технический институт (МФТИ), комбинаторика, лаборатория мфти, магистратура, МФТИ, образование, онлайн-магистратура, современная комбинаторика, Учебный процесс в IT, метки:

Обучение в онлайн-магистратуре как вариант профессионального и карьерного роста - 1

Так получалось, что мы рассказываем о наших проектах, но мало уделяем внимания содержанию наших нововведений. Сегодня мы постараемся рассказать об онлайн-магистратуре по современной комбинаторике через призму только что запущенного проекта — Лаборатории прикладных исследований МФТИ — Сбербанк.

Читать полностью »

в 11:17, , рубрики: Занимательные задачки, комбинаторика, математика, Спортивное программирование

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

Итак, начну издалека. Я изучал стационарные локализованные структуры в одномерном уравнении Гросса-Питаевского, [пример работы]. Такие структуры, при некоторых достаточных условиях на параметры задачи, можно кодировать бесконечными в обе стороны символическими последовательностями, которые мы называем кодами. То есть, непрерывные решения дифференциального уравнения классифицируются дискретными кодами. Алфавит кодировки, как правило, конечен и состоит из некоторого нечетного числа символов, например из N=2L+1 символов, где L – натуральное число. В алфавите есть нулевой символ Об одной комбинаторной задаче - 3, а все остальные символы делятся на пары, связанные некоторой симметрией. Для простоты мы будем обозначать алфавит кодировки A={i}_{i=-L}^L, где символы i и -i симметричны друг другу. Число N мы будем называть мощностью алфавита A.

Читать полностью »

в 4:14, , рубрики: Алгоритмы, количество, комбинаторика, лемма бернсайда, математика, Программирование, сколько их, судоку, теория групп

Привет! Это вторая часть перевода статьи про подсчет различных судоку.

Судоку: так сколько же их? Часть 2-2 - 1

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

Как обычно, мои комментарии выделены курсивом или спрятаны под спойлеры. Под спойлерами можно найти самое интересное — куски кода, которые верифицируют все числа, полученные в повествовании.
Читать полностью »

в 5:17, , рубрики: Алгоритмы, количество, комбинаторика, математика, Программирование, сколько их, судоку

Привет!

Данная публикация возникла после просматривания этого поста, в котором автор пытается посчитать количество различных судоку. Желая более точно разобраться в вопросе, я за пару минут нагуглил точный ответ, приведенный в данной статье. Текст этой статьи мне показался интересным сам по себе, поэтому я решил сделать перевод (в довольно вольном стиле).

Судоку: так сколько же их? Часть 1-2 - 1

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

в 15:13, , рубрики: java, занимательные задачи, Занимательные задачки, комбинаторика, математика, первый пост на хабре, счастливый билет

image Думаю всем с детства знакома задача о счастливом билете. Однако чаще всего поездка в автобусе занимает гораздо больше времени, чем время, потраченное на суммирование первых и последних трех цифр.

И чтобы развлечь себя до конца поездки, я изобрел концепт «Несчастливого билета». Билета, у которого ни одно число из множества значений, полученного при помощи первых трех цифр, не совпадет ни с одним числом из множества значений, полученного при помощи последних трех цифр. Подробности в условии задачи.
Читать полностью »

в 11:09, , рубрики: Алгоритмы, Блог компании Яндекс, вычислительная математика, гипотезы, комбинаторика, математика, ненормальное программирование, перестановки, последовательности, сложные матзадачи, числа каталана, числа фибоначчи

Некоторое время назад в московский офис Яндекса приезжал Игорь Пак — ученый с множеством научных работ, выпускник мехмата МГУ и аспирантуры Гарварда. Сейчас Игорь работает в Калифорнийском университете. Его лекция в Яндексе была посвящена различным классам последовательностей и перестановкам. В том числе прямо по ходу лекции он представил выкладки, опровергающие гипотезу Нунана и Зайлбергера — одну из ключевых в области перестановок.

Под катом — подробная текстовая расшифровка и большинство слайдов.
Читать полностью »

в 15:28, , рубрики: Алгоритмы, база решений, игры, искусственный интеллект, комбинаторика, логические игры, перебор, поиск в ширь, Программирование, шахматы

Хотите озадачить начинающего шахматиста?
Попросите его поставить мат конём и слоном.

Хотите озадачить начинающего программиста?
Попросите его рассчитать мат конём и слоном.

image

Шахматные задачи будоражат воображение программиста,
именно поэтому для практической демонстрации комбинаторики
я выбрал самую сложную шахматную задачу из цикла «мат одинокому королю».
Читать полностью »

в 11:54, , рубрики: Блог компании Московский физико-технический институт (МФТИ), графы, комбинаторика, магистратура, МФТИ, современная комбинаторика, Учебный процесс в IT

Со следующего года десять студентов смогут обучаться в полноценной магистратуре МФТИ и получить диплом государственного образца, не выходя из дома. Ведущие зарубежные вузы, такие как Гарвард и Стенфорд, уже имеют подобного рода программы, но для России это беспрецедентный образовательный эксперимент. Уверенности в его успехе добавляет уже развитая на Физтехе культура онлайн-обучения, связанная с такими проектами, как курсы на Coursera, НПОО и «Лекторий», запущенных той же командой, которая будет отвечать за онлайн-магистратуру в МФТИ.

image

Обучение в онлайн-магистратуре будет осуществляться по направлению «Современная комбинаторика». Для преподавания разделов прикладной и фундаментальной математики в новом формате нужны передовые преподаватели. Одним из таких специалистов является Андрей Райгородский — ученый с мировым именем и заведующий кафедрой дискретной математики МФТИ.

МФТИ запустил онлайн-магистратуру по современной комбинаторике - 2

Мы расскажем, как будет строиться образовательный процесс!
Читать полностью »

в 8:06, , рубрики: Алгоритмы, комбинаторика, перестановки, Программирование

Сразу оговорюсь, эта статья тематически похожа на опубликованную около года назад автором SemenovVV «Нерекурсивный алгоритм генерации перестановок», но подход тут, на мой взгляд, принципиально иной.

Я столкнулся с необходимостью составления списка всех перестановок из n элементов. Для n = 4 или даже 5, задача решается вручную в считанные минуты, но для 6! = 720 и выше исписывать страницы мне уже было лень – нужна была автоматизация. Я был уверен, что этот «велосипед» уже изобретён многократно и в различных вариациях, но было интересно разобраться самостоятельно – поэтому, намеренно не заглядывая в профильную литературу, я засел за создание алгоритма.
Читать полностью »

123...4
Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js