Прекрасни фигурки
Легендарният тетрис е създаден през 80-те години на миналия век от Алексей Пажитнов. Математик
Пажитнов пусна една от първите версии на играта на съветския микрокомпютър "Електроника-60"
Целта на Tetris е да се движи и върти падайкигеометрични фигури, за да образувате пълни редове в долната част на игралното поле, отбелязвайки точки. От практическа гледна точка това е игра на скорост на реакция и концентрация, но математиците гледат на това от различен ъгъл. Учените анализираха изчислителната сложност на алгоритъма Tetris и установиха, че той принадлежи към класа на NP-пълен - недетерминиран полином; няма ефективни алгоритми за решаване на такива неща.
Основният проблем е, че количеството наза намиране на решение на изчислението нараства експоненциално с увеличаване на броя на променливите (размер на проблема). Например, ако има четири параметъра, тогава са необходими 16 итерации, а ако 100, тогава 2 ^ 100, което е повече от атомите във Вселената (!). Един типичен компютър, когато е правилно настроен, може да направи няколко милиарда от тези итерации в секунда. Съответно, той може лесно да решава малки NP-задачи чрез изброяване и когато променливите станат забележимо повече от 15, той ще спре да решава.
Колкото до тетрис.Размерът на задачата на класическата игра е малък: на отделна стъпка има текущ пейзаж в стъклото (игрално поле) - това е параметър, не влияе значително на количеството изчисления. Има информация за текущата и следващата фигура - това са две групи променливи: за всяка фигура има максимум четири (въпреки че за квадрат - само една) ориентации в пространството и максимум 10 координати на "кацането" на фигурите. Всеки ход има 40 състояния, два имат 1600, няма повече информация, това е малък проблем с NP. Въпреки че Tetris може да бъде сложен: увеличете броя на клетките до 100 и се уверете, че играчът знае не само коя ще бъде следващата фигура, но и сто от следващите, тогава ще има проблеми.
Вие също не знаете други NP-пълни игриот слухове: миночистач, судоку, етикет и дори некомерсиална версия на Super Mario. Въпреки простотата на техните правила, при определени условия размерът им нараства, компютърът не може да предложи идеално решение. Защо ги е грижа на математиците? Тъй като изборът на най-добрия маршрут, оптимизирането на процес или график също са проблеми от клас NP.
Класическият "Марио" изглеждаше така
Логическите игри са изключително удобна тестова площадка заалгоритми за тестване и тяхната софтуерна реализация. Пъзелите най-често са „чисти“, без различни видове изключения от правилата, които са присъщи на практическите проблеми. Пространството на състоянието на такива проблеми има регулируемо измерение и свойствата не се променят при мащабиране (например тагове 2x2, 4x4, 3x6). Всички състояния са описани по един и същи начин. Математическото описание на пъзелите по правило също не е толкова сложно, колкото тези на житейските проблеми.
Времето на "квантовите" играчки
Същият проблем с раницата (как да побера повече нещав ограничено пространство) доста напомня на игра на тетрис, а ефективният резултат ще бъде полезен за логистичните компании, тъй като ще им позволи да не пилеят ресурси. Ако се намери „полиномиално бърз“ алгоритъм за някой от тези проблеми или игри, тогава всеки друг проблем от класа NP може да бъде решен също толкова „бързо“. На теория квантовите компютри ще помогнат за това, но засега има само прототипи на тези компютри на бъдещето. През 2018 г. дори беше изобретена нова концепция, която да опише текущото състояние на производство на квантови процесори - ерата на NISQ (шумна квантова ера с междинен мащаб) или времето на субквантовите технологии.
Докато учените работят за подобряване на квантпроцеси, ръководителите на компании търсят съвременни аналози, които спомагат за оптимизиране на работата на производството. Такъв „заместител“ станаха квантово вдъхновени алгоритми, които намират 95-99% оптимално решение на конвенционалните компютри. В Русия QuSolve прави това - задачите, върху които работи компанията, принадлежат към класа NP, а математиците разработват и подобряват алгоритми за решаване на бизнес проблеми. В QuSolve, за да тестват собствения си решаващ (решаващ), те използваха тагове, които помогнаха да намерят няколко грешки в алгоритъма и да направят допълнения към интерфейса на софтуерния пакет.
Наистина ли съвременните учени не правят нищо друго освенМислите ли как да подобрите и оптимизирате всичко? Разбира се че не. В свободното си време продължават да измислят игри. Разработчиците вече са успели да превърнат повечето игри в NP, добавяйки малко магия на квантово-физичните явления.
Така се появиха квантовите технологии през последните 10 години.пулове, квантова морска битка и квантова тик-так-палец. Особена популярност придоби квантовият шах, в който дори се провеждат турнири, а шампионът получава титлата гросмайстор. Повечето от новите „квантови игри“ са изградени върху фундаменталния принцип на квантовата механика – суперпозицията.
Например, фигурите за шах могат да бъдат включениняколко места на дъската едновременно, което означава, че е по-трудно да се защитава и атакува - това прави играта непредсказуема и зрелищна. През 2016 г. те дори заснеха кратък филм, който показваше игра на квантов шах между Стивън Хокинг и Пол Ръд, актьор, известен с ролята си на Ant-Man в Marvel Cinematic Universe.
Екранна снимка на играта. Ето как изглеждаше онлайн дъската в играта между Хокинг и Ръд. Тогава актьорът победи легендарния физик
Не знаем дали тези игри ще бъдат такива в бъдещетолкова обичайни, колкото обикновените тик-так, тетрис и таг, но определено ще вдъхновят математиците да създадат уникални алгоритми за решаване на практически бизнес проблеми и разработване на технологии. Няма съмнение за това.
Прочетете още:
Формата на Млечния път изобщо не е такава, каквато си мислехме през цялото време, установиха учени
Две суперземи, открити на ръба на обитаемата зона: едната от тях има комфортна температура
Откриха черна дупка, която унищожава звезден рекорд близо до Земята