Max Home IndustryЕсли вам сложно собрать кубик Рубика, вам будет приятно узнать, что это действительно так. Теперь доказано, что определение разрешимости случайного куба ровно за n ходов является NP полным.
Read more «Кубик Рубика сложен — NP Hard»Рубрика: Теория
HerbGrind: инструмент для поиска ошибок с плавающей запятой
Числовой формат с плавающей запятой используется для большинства вычислений, и мы склонны доверять ему, но это доверие неуместно. Вычисления с плавающей запятой могут быть настолько ошибочными, что напоминают шум. Теперь есть способ автоматически определять, когда что-то идет не так.
Read more «HerbGrind: инструмент для поиска ошибок с плавающей запятой»
Лучшие планы львов и людей
Сможет ли человек пережить нападение льва двух львов? Да, если речь идет о математике, а не о настоящих львах. Это почти классическая математическая головоломка.
День Пи 2017 — Почему Пи?
Снова наступил День Пи, и пришло время глубоко задуматься о Пи и о том, почему он такой особенный. Конечно, вы можете просто использовать это как предлог для употребления большого количества пирога.
// Без комментариев — Турмиты универсальны по Тьюрингу, алгоритм и правила китового роя, управляющие рыбой
• Нетривиальные турмиты универсальны по Тьюрингу
Никаких супер-машин Тьюринга
Время от времени вы будете читать о прорыве, в котором утверждается, что какой-то странный компьютер может решить NP-задачи на P. Иными словами, нам представлена супер-машина Тьюринга, способная вычислять что-то, что не является вычислимым. Обычно это оказывается сложнее, чем предполагают заголовки.
// Без комментариев — приблизительное расстояние редактирования, иррациональная гвардия и DCT в 14 дополнениях
• О практической точности алгоритмов аппроксимации расстояния редактирования
// Без комментариев — параллельное программирование сложно; Выбор подмножества столбцов является NP-полным и сбалансированная атака на блокчейны Proof-of-Work
Сложно ли параллельное программирование, и если да, что с этим делать?
Прорыв десятилетия в области компьютерных наук восстановлен!
Это почти беспрецедентно. Во-первых, у нас есть важный результат в области информатики. Через пару месяцев он внезапно отозвался, что вызвало волну разочарования в сообществе. Но, к нашему большому облегчению, его восстановили всего через несколько дней.
Read more «Прорыв десятилетия в области компьютерных наук восстановлен!»
// Без комментариев — Unums, головоломки 1 × n сложны & P? = NP
• Формат числа Unum: математические основы, реализация и сравнение с числами с плавающей запятой IEEE 754
Read more «// Без комментариев — Unums, головоломки 1 × n сложны & P? = NP»