Метка «Алгоритмы» - 2

Идея

  1. Игровое пространство — клетчатое поле ограниченное рамкой
  2. Существующие типы клеток:
    • Пустая клетка — белый
    • Стена — чёрный
    • Зверь — красный
    • След — коричневый
    • Дом — зелёный
  3. Перемещение зверя оставляет неисчезающий след
  4. При запуске генерируется лабиринт
  5. Зверь знает состояние соседних клеток и на основании этого строит карту при перемещении
  6. При перемещении зверь расходует силы, которые восстанавливаются в доме(+5) или на любой клетке(+1)
  7. При столкновении звери объединяются в стаи(дома переносятся в соседние точки), если несколько зверей одновременно отдыхают в доме их карты объединяются
  8. (Не реализовано)Разные «кланы» случайным образом объединяются или воюют
  9. (Не реализовано)Генетический алгоритм для различных поведений зверей, случайно перемешивающиеся при размножении(+мутации), более перспективный вид выживет в войнах

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

Простой алгоритм псевдослучайного выбора альтернатив
В данном посте я хочу рассказать о простом алгоритме предложения на основании сделанных ранее выборов. Для этого, прежде всего, поставим две задачи:

  1. Выбрать случайное значение из массива
  2. Выбрать случайное значение из массива на основании веса значений

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

Для решения я буду использовать псевдокод, чем-то похожий на Javascript. Потому, мой метод random() будет возвращать значение от 0 до 1.
Читать полностью »

Уважаемые участники конкурса!

Полуфинальная выборка доступна для скачивания.

Обращаем ваше внимание, что пароль к выборке будет объявлен на сайте www.m2ies.com в день старта полуфинала 1.04.2014 в 14-00 по московскому времени.

Результаты работы вашей системы можно будет присылать до 14-00 2.04.2014.

Подробности — в конкурсной документации.

Удачи!

image

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

Первую статью на хабр хотел написать совершенно о другом, но в один прекрасный день коллега по работе решил заморочиться и сделать защиту от «Атаки по времени» (Timing attack). Не долго разбираясь в различных материалах на эту тему, Я загорелся и решил написать свой велосипед и покататься на нем по лаборатории поэкспериментировать.

Атаки по времени — сказка или реальная угроза?

Результат этого небольшого эксперимента под катом.
Читать полностью »

Использование случайных битов — один из способов усиления возможностей компьютеров. Вероятностные алгоритмы позволяют решать некоторые задачи теоретической информатики, для которых не работают детерминированные алгоритмы. Самый интересный вопрос — это насколько использование случайностей сокращает время работы алгоритма? Частично на этот вопрос уже можно ответить: при некоторых предположениях истинную случайность можно подменить фальшивой и детерминированно смоделировать любой вероятностный алгоритм с незначительной потерей во времени работы. Проверка этих предположений будет, по всей видимости, одной из центральных тем теоретической информатики XXI века.

Лекцию читает старший научный сотрудник Вычислительного центра им. А.А. Дородницына РАН, доцент кафедры математических основ управления МФТИ, кандидат физико-математических наук Михаил Вялый.

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

Помогает ли в вычислениях подбрасывание монетки? Лекция в Яндексе

Такая постановка, конечно, слишком общая. Постараемся уточнить ее с точки зрения теоретической информатики. Для этого сначала введем понятие алгоритма. Алгоритм — настолько точно определенная инструкция, что она может быть исполнена механически. Основное свойство детерминированных алгоритмов заключается в том, что каждое следующее состояние однозначно определяется текущим состоянием. Вероятностные алгоритмы отличаются тем, что в любой момент они могут определить значение случайного бита (подбросить монету), который с равной вероятностью будет равен 0 или 1. В процессе исполнения вероятностного алгоритма это может происходить неоднократно, и разные подбрасывания будут независимы.
Читать полностью »

И сила и слабость современных компьютеров в том, насколько они точны. Сегодня в нашей серии лекций от Яндекса рассказ о том, как использование случайностей может помочь сделать вычисления более эффективными.

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

Лекцию читает старший научный сотрудник Вычислительного центра им. А.А. Дородницына РАН, доцент кафедры математических основ управления МФТИ, кандидат физико-математических наук Михаил Вялый.

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

На прекрасной Coursera скоро снова начинается курс по Алгоритмам от Тима из Стэнфорда. И я не могу про него не написать. А в свете вот этого поста про дистанционное образование так тем более.

Начну с того, что это самый интересный курс, который мне вообще когда-либо приходилось брать. А я провела во всяких не самых худших университетах немало лет. Курс называется Algorithms: Design and Analysis. Рассказывается в курсе про разные алгоритмы для графов, обсуждаются подходящие структуры данных для каждого алгоритма, присутствует теория и краткие доказательства этих алгоритмов. Во второй части рассказывается в том числе про P=NP проблему и алгоритмы с неполиномиальным временем.

Почему этот курс мне так понравился. Потому что лектор невероятно классный! Он настолько вовлечен, он так все это рассказывает. И потом каждую неделю надо запрограммировать новый алгоритм (на языке по собственному выбору) и найти с помощью своей имплементации ответ на вопрос. Ответ на вопрос засабмитить на сайте, и еще раз, пока не получится правильный ответ. Каждую неделю, как я сказала, новый алгоритм. И соответственно дедлайны. Мотивировало меня это просто сумасшедше: я бежала домой с работы и я не расставалась с алгоритмами по выходным, я ездила в отпуск, сидела на вершине самой высокой точки страны и программировала merge sort.

Я ждала полгода, чтобы снова объявили о его начале, чтобы посоветовать его другим людям, потому что для меня это было как найденный клад.

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

Если помните, Рей Курцвейл обещал приход сингулярности уже в 30 годах этого века. Похоже, что первые предвестники уже появляются: два бывших наших соотечественника, Алексей Лисица и Борис Конев, работающие в Ливерпульском университете, запустили на расчет задачу несоответствия Эрдеша. Задача считается неразрешенной, и программа, запущенная исследователями с задачей справилась. Но! Проблема в том, что доказательства решения сами по себе занимают 13 Гб (еще раз, текстовый лог-файл, по сути и являющийся доказательством, занимает 13 Гб) и с трудом поддается верификации. Отсюда напрашивается простой вопрос – можем ли мы доверять решению компьютера, если не в состоянии проверить его выкладки?

Можем ли мы доверять решению компьютера, если не можем его проверить?
Читать полностью »

Сегодня мы поговорим о моделировании реальности как о способе мышления, восприятия информации и анализа данных. Будем вместе заново изобретать и улучшать модели, которые сегодня используются в поисковых системах: в метриках качества поиска, при создании факторов ранжирования и даже при построении новых интернет-сервисов. Именно этому посвящена лекция Федора Романенко.

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

Алгоритм Улучшенной Самоорганизующейся Растущей Нейронной Сети (ESOINN)

Введение

В моей предыдущей статье о методах машинного обучения без учителя был рассмотрен базовый алгоритм SOINN — алгоритм построения самоорганизующихся растущих нейронных сетей. Как было отмечено, базовая модель сети SOINN имеет ряд недостатков, не позволяющих использовать её для обучения в режиме lifetime (т.е. для обучения в процессе всего срока эксплуатации сети). К таким недостаткам относилась двухслойная структура сети, требующая при незначительных изменениях в первом слое сети переобучать второй слой полностью. Также алгоритм имел много настраиваемых параметров, что затрудняло его применение при работе с реальными данными.

В этой статье будет рассмотрен алгоритм An Enhanced Self-Organizing Incremental Neural Network, являющийся расширением базовой модели SOINN и частично решающий озвученные проблемы.
Читать полностью »