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

---

Совсем немного истории

Головоломка «Instant Insanity» (Мгновенное Безумие), возможно, одна из самых востребованных для иллюстрации применимости теории графов в решении задач подобного ей типа.

Троичные вычисления

Итак, продолжаю цикл статей о разработке троичного вычислителя. В прошлый раз мы познакомились с самым базовым элементом: троичным (де-)мультиплексором, а также на его базе построили полу- и полный сумматор. В этот раз речь пойдёт о ячейках памяти.

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

Итак, вот список опубликованных статей цикла (будет обновляться):

• Считаем до трёх: раз (троичный мультиплексор и сумматоры)
• Считаем до трёх: два (память)
• Считаем до трёх: три (счётчики)
• Считаем до трёх: четыре (однотритный вычислитель и система команд трёхтритного)

Напоминаю, что единственным строительным блоком вычислителя будет троичный мультиплексор. Вот фотография оригинального тримукса дизайна Александра Шабаршина и моего исполнения на поверхностном монтаже. Одна такая плата несёт на себе два троичных (де-)мультиплексора:

Эта история началась с того что я застрял в пробке на хайвее, не особенно большой, но полчаса простоял практически на месте. И, как это часто бывает, пробка рассосалась сама по себе — не было впереди ни аварии, ни ремонта, просто машины в какой-то момент начали двигаться быстрее, еще быстрее, и все — свободная дорога впереди.

Чем обычно занимаются в пробках? Ну кто-чем и когда-как, а я в тот день был в мирном философском настроении — просто сидел и размышлял. Вспомнил в частности пост на Гиктаймс о робомобилях где в комментариях бурно сравнивали манеру вождения людей и роботов и в конце кажется пришли к выводу что будущее на дорогах за AI, при нем и движение станет безопаснее и средняя скорость возрастет. Интересно, а пробки тогда будут? Другими словами, насколько пробки обусловлены внешними (обьективными) обстоятельствами, и насколько эффектом толпы, агрессивной или наоборот тормозной манерой вождения? Заодно вспомнилась прочитанная когда-то книга где утверждалось что моделирование дорожного трафика — одна из самых сложных математических задач, которая до сих пор не решена. Ну это наверное давно уже неправда, читал я это давно и книга уже тогда была не новой, сейчас уже наверняка и теории правильные написали, и на компьютерах своих все посчитали. Хотя… пробки же остались? В общем, полет фантазии было уже не остановить.

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

И еще одно — я убежденный сторонник думанья головой, поэтому в этом посте компьютерного моделирования не будет, вообще совсем не будет, только хардкорный карандаш и бумага.

Компьютеры проникли в большинство сфер жизни человека и продолжают развиваться. Автопилот, банковская сфера, машинный перевод, медицина, финансовые рынки, полеты в космос — все это возможно благодаря одной простой идее.

В этой статье я предлагаю заглянуть за границы возможностей компьютеров и рассмотреть чего же они не могут. И почему. Алан Тьюринг еще в 30-е годы обозначил невозможные для компьютера задачи.

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

В этом блоге мы приведём и прокомментируем некоторые ранее неизвестные производные специальных функций (в первую очередь функций Бесселя и связанных с ними функций), а также коснёмся истории и текущего состояния дифференцирования по параметрам гипергеометрических и других функций. Одной из основных новых формул (более подробно ниже) является замкнутое выражение для первой производной одной из самых популярных специальных функций — функции Бесселя J:

… Молвит он: «Коль жив я буду, чудный остров навещу, у Гвидона погощу».

В царстве Салтана не без изьяна. Принят закон — не лезть за кордон, да тут князь Гвидон.
Опять прислал поклон, да приглашение на угощение,- надо принимать политическое решение.

Дворцовые интриганки, похожие на поганки, встали стеной — «мол, скажи, что больной». Но прослышал Салтан про Гвидонов кальян, про изумрудную белку, да богатырскую стрелку. А главная новинка — молодая жинка. В общем, ехать решено — «Я не был за морем давно».

Было однако одна проблема,- нужен был маршрут или схема. Поскольку никто (кроме Врангеля барона) не знал, как добраться до острова Гвидона. Корабельщики дали карту,- пришлось сесть за парту. Над картой склонился Салтан, — где тут остров Буян? Задача была как будто знакома — проложить путь к острову Гвидона. Но как найти дорогу, когда путей слишком много?

До ночи решал Салтан задачку, в итоге свалился в спячку. Снились ему матрицы и точки, да на болоте кочки. На кочку прыгнул Нео с острова Борнео.
— Если хочешь добраться ко сроку — плыви по максимальному потоку.
— Чего? — Салтан почти проснулся. Но Нео уже в зайца обернулся.

Категорически приглашаем всех желающих на онлайн-курс «Введение в теоретическую информатику» Александра Ханьевича Шеня, подготовленный совместно с Computer Science центром и платформой Stepic. Курс начнётся 24 февраля.



Александр Ханьевич — автор многих популярных книг по математике и программированию. Многие его книги и брошюры можно бесплатно скачать с сайта издательства МЦНМО: например, «Программирование: теоремы и задачи» (Шень, 2004), «Лекции по математической логике и теории алгоритмов» (Верещагин, Шень, 2012), «Классические и квантовые вычисления» (Китаев, Шень, Вялый, 1999). Под его редакцией вышел перевод первого издания классического учебника «Алгоритмы: построение и анализ» (Кормен, Лейзерсон, Ривеста, 1990), а также недавнего учебника «Алгоритмы» (Дасгупта, Пападимитриу, Вазирани, 2006).

В общем, у Александра Ханьевича огромный опыт чтения лекций как школьникам, так и студентам и аспирантам. Рассказывает он очень увлекательно и понятно. В онлайн-курсе он даст обзор различных направлений Theoretical Computer Science: криптография, инварианты циклов, вычислимость, переборные задачи, игры, коды, интерактивные доказательства и многое другое (всего в курсе восемнадцать глав!). В курсе будет много задач — как простых (закрепляющих изученный материал), так и более сложных, над которыми придётся поломать голову и тем, кто уже был знаком с теорией.

Будем рады видеть вас среди слушателей онлайн-курса!
stepic.org/104

В статье описывается реализация известного метода конечных объемов для численного решения уравнений в частных производных.Используется разбиение области на любые стандартные элементы(конечные объемы) — треугольники, четырехугольники и т.д.Метод визуализации результатов расчетов также самописный.

Данную статью можно считать вольным переводом (хотя скорее попыткой разобраться) данной статьи. И да, написанна она скорее для математиков, нежели для широкой аудитории.

Небольшой спойлер: в начале это казалось мне какой-то магией, но потом я понял подвох…

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

Вообще говоря, есть другие модели — Недетерминированная машина Тьюринга, Квантовые машины Тьюринга. Однако они (пока) являются только абстрактными моделями, не реализуемые на практике.

Полгода назад в Science Advances вышла интересная статья с моделью вычислений, которая существенно отличается от МТ и которую вполне возможно реализовать на практике (собственно статья и была о том, как они посчитали задачу SSP на реальном железе).

И да. Самое интересное в этой модели то, что, по заверению авторов, в ней можно решать (некоторые) задачи из класса NP полных задач за полином времени и памяти.

В ноябре мы запускаем онлайн-курс «Алгоритмы: теория и практика. Методы» от Computer Science центра. Курс бесплатный, приглашаются все желающие. В курсе будут подробно разобраны базовые алгоритмические методы: жадные алгоритмы, метод «разделяй и властвуй», динамическое программирование. Для всех алгоритмов будут математически строго доказаны корректность и оценки на время работы. Мы постарались изложить материал так, чтобы были понятны и сами алгоритмы, и то, как можно было бы догадаться до их основных идей. Помимо теоретических основ, будут рассказаны тонкости реализации алгоритмов на языках программирования C++, Java и Python. В частности, будет рассказано, какие есть общие практики написания кода, позволяющие минимизировать вероятность ошибки, как писать и тестировать код, где стоит использовать стандартные методы, а не изобретать колесо.

Мы тщательно подобрали задачи для закрепления материала. Большинство алгоритмов, которые вы узнаете, вам нужно будет запрограммировать. Это лучший способ убедиться, что вы разобрались во всех деталях. Решая такие задачи, вы получите ценный опыт написания и отладки эффективных и надёжных программ. Задачи на программирование помогут вам почувствовать разницу между плохим (медленным) и хорошим (быстрым) алгоритмом. Вас также ждут тесты (где нужно выбрать правильные ответы из предложенных) и теоретические задачи (в них нужно доказать математическое утверждение). Наконец, в курсе есть также задачи повышенной сложности — менее стандартные задачи, которые не являются обязательными для прохождения курса. Получить удовольствие от решения этих задач смогут и те, кто уже знаком с базовыми алгоритмами.

Израильские ученые Шимон Ивэн (Shimon Even) и Ишай Мансур (Yishay Mansour) еще в 1997 году задались вопросом: насколько минимальной конструкцией может обладать стойкий блочный шифр? Под минимальностью они подразумевали число конструктивных элементов в схеме шифра, а под стойкостью — любую (формально верную) оценку снизу сложностей атак на этот шифр. Как говорится, под катом — описание минимального (и по сей день) блочного шифра с доказуемой стойкостью.

Небольшая предыстория. Этот пост я написал для двух целей. Во-первых, обкатать конвертор разметки Markdown + в хабрачитаемый вид. Во-вторых, рассказать об интересной задаче из data streaming. К концу написания, я обнаружил пост про LogLog четырехлетней давности. На мою удачу автор предыдущего поста делал упор на реализацию. Я же, полагаясь на , расскажу больше о математике.

Давайте представим, что у нас есть роутер. Через роутер проходит много пакетов по разным адресам. Нам интересно получить статистику, как много адресов задействовано в коммуникации. Есть пара проблем.

• Пакетов так много, что запомнить их все нельзя. Сказать ушедшему пакету «Вернись! Я все прощу,» — тоже.
• Всех возможных адресов . Столько памяти на роутере нет.

Задача. Есть последовательность целых чисел , все числа принимают значения от до . Требуется в один проход посчитать количество различных чисел, используя памяти.

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



Лектор – Софья Геннадьевна Кисельгоф, младший научный сотрудник Международной научной лаборатории анализа и выбора решений НИУ ВШЭ. Преподаватель департамента математики экономического факультета. На факультете компьютерных наук читает курс Operations Research and Game Theory. Защитила кандидатскую диссертацию на тему «Обобщенные паросочетания при предпочтениях, не являющихся линейными порядками». Софья Геннадьевна проводила исследование механизма зачисления абитуриентов в российские вузы в результате которого была построена модель, описывающая поведения абитуриента при выборе вуза.

Под катом – подробная стенограмма лекции.

Перевод поста Майкла Тротта (Michael Trott) "Making Formulas… for Everything—From Pi to the Pink Panther to Sir Isaac Newton".
Выражаю благодарность за помощь в переводе Сильвии Торосян.
Скачать перевод в виде документа Mathematica, который содержит весь код использованный в статье, можно здесь (архив, ~7 МБ).

В компании Wolfram Research и Wolfram|Alpha мы любим математику и вычисления. Наши любимые темы — алгоритмы, следующие из формул и уравнений. Например, Mathematica может вычислить миллионы интегралов (точнее бесконечное их количество, встречающихся на практике), а также Wolfram|Alpha знает сотни тысяч математических формул (от формулы Эйлера и BBP-формул для Pi до сложных определённых интегралов, содержащих sin (x)) и множество формул физики (например, от закона Пуазейля до классических решений механики для точечной частицы в прямоугольнике или потенциала обратного расстояния в четырехмерном пространстве, в гиперсферических координатах), так же как менее известные формулы, такие как формулы для частоты дрожащей мокрой собаки, максимальной высоты песочного замка, или времени приготовления индейки.

Как вы знаете, Badoo — сервис для поиска новых людей. Кроме всего прочего, мы позволяем искать людей вокруг и в «игре» тоже показываем людей, которые находятся недалеко от вас. Эта часть «вокруг» очень и очень важна. Ведь молодому человеку из Новосибирска гораздо интереснее познакомиться с девушкой, которая живет в пяти минутах ходьбы от него, а не во Владивостоке.
Мы до сих пор не рассказывали публично о том, как мы это делаем. Но новое открытие австрийских ученых настолько нас обрадовало, что мы решились это сделать. Перейдем же к делу.
Badoo работает по всему миру и наш поиск работает абсолютно одинаково, вне зависимости от того, в какой точке земного шара вы находитесь. Как же эффективно искать людей вокруг среди всех 200+ миллионов пользователей?
Решение нетривиально, честно говоря. Нам нужен какой-то индекс, какой-то способ сразу же сузить область поиска. В случае с земным шаром, самым простым разбиением является сетка географических широт и долгот. Однако проблема с этой сеткой в ее неравномерности. Ячейка у северного полюса и ячейка у экватора имеют совсем разные формы. Такое несимметричное разбиение вносит большие проблемы, если мы хотим равномерно распределить нагрузку по поисковому кластеру.

Введение

Ранним воскресным утром я уже третий день сидел за отладкой программы для триангуляции результата лазерного сканирования. Лазерный скан представляет из себя набор трехмерных точек. В результате работы программы нужно объединить точки в непересекающиеся полигоны, таким образом создав модель поверхности. Функцию за функцией я пересчитывал на листочке и, наконец, добрался до функции проверки выполнения условия Делоне. По всей видимости, ошибка затаилась где-то в ней. При детальном разборе оказалось, что формула, указанная в огромном количестве книг про триангуляцию Делоне, не всегда дает верный результат. Подробности под катом.

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

Создавая дополнения к отечественной математической программе SMath Studio, я нашёл в сети ряд библиотек, которые можно было бы использовать в своих программах. Предлагаю небольшой их обзор.

Этот цикл статей описывает волновую модель мозга, серьезно отличающуюся от традиционных моделей. Настоятельно рекомендую тем, кто только присоединился, начинать чтение с первой части.

В предыдущей части мы показали как может выглядеть распределенная память. Основная идея заключается в том, что общий волновой идентификатор может объединить нейроны, которые своей активностью формируют запоминаемую картину. Чтобы воспроизвести конкретное событие достаточно запустить по коре соответствующий идентификатор воспоминания. Его распространение восстановит ту же картину активности, что была на коре на момент фиксации этого воспоминания. Но главный вопрос — это как нам получить требуемый идентификатор? Ассоциативность памяти подразумевает, что по набору признаков мы можем отобрать события, в описании которых присутствовали эти признаки. То есть должен существовать нейронный механизм, который позволит по описанию в определенных признаках, получить идентификатор подходящего под эти признаки воспоминания.

Когда мы говорили о распространении нейронных волн, мы исходили из того, что нейрон хранит на внесинаптической мембране те волновые картины, участником которых он является. Встретив знакомую картину, нейрон своим спайком создает продолжение уникального узора. И тут важно, что нейрон не просто в состоянии узнать волновую картину, а то, что он сам – часть распространяющегося узора. Только будучи сам частью уникальной волны нейрон способен участвовать в ее распространении.

Добрый день! Недавно здесь проскакивал пост про уравнение Кеплера и я был слегка поражен тем, что ничего не написано про то, каким образом оно вообще выводится и откуда, как исторически, так и математически. Как известно, Кеплер вывел его из наблюдения движения планет, а Ландау и Лифшиц вывели движение планет из…