Max Home IndustryДональд Кнут, автор классической книги «Искусство компьютерного программирования», отметил свое 80-летие и все еще работает над улучшением своей монументальной работы. Он также все еще надеется, что люди проверят сложные упражнения TAOCP, чтобы убедиться, что они верны.
Рубрика: Теория
Крупнейшее простое число теперь насчитывает более 23 миллионов цифр
Недавно обнаруженное простое число — 277 232 917-1. Простое число такого размера не имеет практического применения, оно просто для развлечения и математики. И я полагаю, что это техническое достижение, заключающееся в наличии вычислительной мощности, позволяющей убедиться, что это простое устройство.
Read more «Крупнейшее простое число теперь насчитывает более 23 миллионов цифр»
Лекция Дональда Кнута о рождественской елке 2017
Ежегодная рождественская лекция Дональда Кнута в этом году посвящена совершенно новой проблеме, у которой нет долгой истории, и в этом суть. Он показывает, что математика — это живой и увлекательный предмет. Видео стоит посмотреть.
Read more «Лекция Дональда Кнута о рождественской елке 2017»
Что такое вычислительная мощность Вселенной?
Вселенную можно рассматривать как огромный физический компьютер, на котором работает 13,7 миллиарда человек. Результат его программы — такой, какой он есть. Обладает ли вселенная необходимой мощностью или ей нужны хитроумные алгоритмы?
Проблема кузнечика
Меня всегда поражает тонкость вероятности. Вы можете процитировать проблему Монти Холла или проблему Фишера Йейтса, но как насчет проблемы с кузнечиком? Легко сформулировать, но очень сложно решить и немного невероятно.
Корпус-Кристи Прайм
Это умная идея, которая кажется очевидной только после того, как вы ее увидели. Есть ли другие приложения, которые ждут, чтобы их придумали?
Тетрис в игре Life — большое достижение
Одно дело знать, что что-то маловероятное является полным по Тьюрингу; совсем другое — использовать его для создания компьютера, а затем реализовать что-то реальное. Именно это и произошло с «Game Of Life» Конвея, когда был сконструирован компьютер для игры в тетрис. Это замечательное достижение, которое должно поставить ваш мозг в штопор.
Новое доказательство того, что P≠NP: окончательное обновление — почти наверняка нет
Доказательств того, что P=NP, и даже для менее интересного и более вероятного P≠NP, очень много. Большинство из них принадлежит энтузиастам, которых, как правило, можно похвалить за энтузиазм, но не за доказательства. Однако последнее доказательство принадлежит уважаемому теоретику сложности и не может быть отвергнуто обычным способом.
Последнее обновление: статья отозвана.
Read more «Новое доказательство того, что P≠NP: окончательное обновление — почти наверняка нет»Завершение N ферзей завершено NP
Проблема размещения восьми ферзей на шахматной доске, чтобы ни один ферзь не атаковал другого, является решенной задачей, как и размещение n ферзей на доске размером nxn. Однако, если вы поместите несколько ферзей на доску и попросите завершить, тогда проблема будет NP завершена.
LZ-сжатие и однобитная катастрофа
Мы широко используем алгоритмы сжатия, чтобы сэкономить как хранилище, так и время. Наиболее популярные алгоритмы основаны на сжатии словаря LZ и используются в форматах GIF, Deflate, Zip, PNG. Его даже назвали вехой IEEE. Но мы мало о них знаем. Один давний вопрос: может ли добавление одного бита в файл кардинально изменить достигнутую степень сжатия? Конечно нет!