"Русский переплет" зарегистрирован как СМИ.
Свидетельство о регистрации в Министерстве печати РФ: Эл. #77-4362 от
5 февраля 2001 года. При полном или частичном использовании
материалов ссылка на www.pereplet.ru обязательна.
|
04.02.2012 23:44 |
Школы США переводят на цифровые учебники
По заявлению Associated Press, администрация Обамы призывает все учебные заведения страны перейти на цифровые учебники в течение 5 лет. Сообщение было получено от . . . |
04.02.2012 12:49 |
NASA разработало мобильный аксессуар, способный обнаруживать раковые клетки
После нескольких лет упорного труда инженеры NASA разработали уникальное устройство, способное распознавать раковые клетки. Прибор представляет собой . . . |
03.02.2012 22:24 |
Сети для домашней медицины
Беспроводные датчики, смартфоны, планшетные и настольные компьютеры помогут лечить хронические болезни Один из наиболее перспективных способов сокращения . . . |
03.02.2012 21:16 |
Cisco TelePresence для молодежи Москвы
Мэр Москвы Сергей Собянин одобрил проект оснащения инновационного центра для молодежи системами видеосвязи Cisco TelePresence Концепция телекоммуникационной . . . |
03.02.2012 18:40 |
IBM разработали 9 нм транзисторы
Исследователи из компании IBM разработали самый маленький транзистор, построенный из углеродных нанотрубок, размеры которого составляют 9 нанометров. Для . . . |
03.02.2012 18:36 |
Глобальное потепление помогло кораллам расти
Австралийские ученые установили, что рост кислотности уровня океанов, который считался главной угрозой кораллам по всему миру, некоторым из них (кораллов) . . . |
03.02.2012 14:19 |
На охрану "Домодедово" поставят "киборгов"
Сотрудников службы безопасности московского аэропорта "Домодедово" оснастят носимыми камерами. Проект получил кодовое названием "Киборг", рассказал директор по . . . |
03.02.2012 14:17 |
NASA выразило доверие российским ракетостроителям
Несмотря на ряд инцидентов, произошедших с российскими космическими аппаратами в 2011 году, NASA по-прежнему уверена в способности российских коллег отправлять к МКС . . . |
03.02.2012 14:15 |
Астрономы нашли еще одну похожую на Землю экзопланету
Астрономы обнаружили еще одну экзопланету, похожую на Землю. Статья ученых принята к публикации в Astrophysical Journal Letters, а ее препринт доступен на сайте arXiv.org. Объектом . . . |
03.02.2012 14:14 |
Ученые заглянули внутрь работающего мозга мыши
Международная группа физиков, химиков и биологов впервые пронаблюдали за работой живых нейронов в голове мыши с рекордным на настоящий момент разрешением - 70 . . . |
03.02.2012 14:08 |
Переживет ли Интернет космическую бурю?
Блог Стивена Лю (Stephen Liu), директора компании Cisco по маркетингу продуктов и технологий для операторов связи В середине января мы стали свидетелями самой сильной . . . |
02.02.2012 23:14 |
Обнаружена связь ожирения с уменьшением мозга
Шведские неврологи из Университета Уппсалы опубликовали в The International Journal of Obesity результаты исследования, в котором было выявлено сокращение участка головного . . . |
02.02.2012 22:16 |
Нейтрино предложили использовать для поиска полезных ископаемых
Ученые из Перу и США предложили использовать нейтрино для обнаружения полостей в Земле, в том числе, возможно, с полезными ископаемыми. Слабым местом их работы . . . |
02.02.2012 22:14 |
Роскосмос утвердил дату отправки экспедиции на МКС
Роскосмос назначил пилотируемый старт к МКС, отложенный из-за повреждения ракеты-носителя "Союз ТМА-04М", на 15 мая, сообщает "Интерфакс". Корабль, на котором новые . . . |
02.02.2012 20:35 |
Телевизоры стремительно вымирают
Исследователи отмечают падение интереса к телевизорам потребителей по всему миру, включая Россию. Привычные <ящики> все чаще заменяют мобильные электронные . . . |
02.02.2012 20:27 |
Итальянские физики: Темной энергии нет. Есть антигравитация
Итальянский физик Массимо Виллата из Национального института астрофизики разработал теорию, согласно которой никакой темной энергии не существует, а . . . |
02.02.2012 20:13 |
Россияне смогут заработать на Facebook миллиарды долларов
Российские акционеры Facebook - Mail.ru Group, Алишер Усманов, Юрий Мильнер, Михаил Фролкин и другие - в результате IPO компании станут владельцами пакетов акций стоимостью до . . . |
02.02.2012 18:43 |
Версию о воздействии радара на "Фобос-Грунт" опровергли опытным путем
Роскосмос признал несостоятельной версию о воздействии на "Фобос-Грунт" американского радара после опытной проверки. Об этом в эфире "Эхо Москвы" заявил глава . . . |
02.02.2012 18:42 |
NASA опубликовало съемку обратной стороны Луны
NASA опубликовало видео обратной стороны Луны, сделанное зондами-близнецами GRAIL. Об этом сообщается на официальном сайте агентства. На видео видна панорама . . . |
02.02.2012 18:34 |
Математики вычислили сложность игры "Скрэббл" Ученые вычислили сложность игры Scrabble ("Скрэббл"), известной в русском варианте как "Эрудит". Статья исследователей пока не принята к публикации в рецензируемом журнале, однако ее препринт доступен на сайте arXiv.org.
Игра "Эрудит" состоит из поля-доски в 15 на 15 клеток и набора из 104 букв. Перед игрой каждый участник (которых может быть от 2 до 4) получает по 7 случайных букв из набора, а на середину игрового поля выкладывается начальное слово, составленное из оставшихся от раздачи букв. Затем игроки по очереди начинают выкладывать на доске собственные слова, например, слева направо и сверху вниз. Главное требование - каждое новое слово должно иметь общую букву или буквы с уже выложенными (все правила можно прочитать здесь).
В рамках работы ученые интересовались следующим вопросом. Пусть на доске задана некоторая позиция - какова сложность алгоритма определения лучшей игровой стратегии? Традиционно ответы на подобные вопросы даются в виде утверждения о принадлежности задачи к некоторому классу сложности.
Эти классы определяются при помощи машины Тьюринга - универсальной модели вычислительного устройства. Мерой сложности алгоритма является либо количество действий, которые должна совершить машина в зависимости от длины строки входных данных, либо количество памяти, которое в зависимости от этой же строки надо задействовать.
В результате ученым удалось установить, что задача относится к классу PSPACE. Это означает, что для обработки входной строки длины n потребуется не более чем p(n) ячеек памяти, где p - некоторый многочлен. Более того, ученые установили, что задача PSPACE-полная, то есть любая другая задача из этого класса за полиномиальное время сводится к данной. В некотором смысле это PSPACE-полные - это самые сложные задачи класса PSPACE.
Некоторое время назад на arXiv.org появился препринт итальянца Джованни Вильетты из Пизанского университета, который подсчитал вычислительную сложность известных компьютерных игр. Среди попавших в исследование игр были Doom, Starcraft, Pac-Man и другие.
|