멋진 인형
전설적인 테트리스는 지난 세기의 80년대에 알렉세이 파지트노프에 의해 만들어졌습니다.수학자
Pajitnov는 소비에트 마이크로 컴퓨터 "Electronics-60"에서 게임의 첫 번째 버전 중 하나를 출시했습니다.
테트리스의 목표는 이동하고 회전하여 떨어지는 것입니다.경기장 바닥에 완전한 행을 형성하는 기하학적 모양으로 점수를 얻습니다. 실용적인 관점에서 볼 때 이는 반응 속도와 집중력의 게임이지만 수학자들은 이를 다른 각도에서 봅니다. 과학자들은 테트리스 알고리즘의 계산 복잡성을 분석하고 이것이 NP-완전(비결정론적 다항식) 클래스에 속한다고 판단했습니다. 그러한 문제에 대한 효과적인 솔루션 알고리즘은 없습니다.
핵심 문제는 그 양이다.계산에 대한 솔루션을 찾기 위한 변수(문제 크기)의 수가 증가함에 따라 기하급수적으로 증가합니다. 예를 들어 매개변수가 4개라면 16번의 반복이 필요하고, 100이면 2^100으로 우주의 원자(!)보다 많다. 일반적인 컴퓨터는 적절하게 조정되면 초당 이러한 반복을 수십억 회 수행할 수 있습니다. 따라서 그는 열거를 통해 작은 NP 문제를 쉽게 해결할 수 있으며 변수가 눈에 띄게 15보다 커지면 해결을 중단합니다.
테트리스의 경우.클래식 게임의 작업 크기는 작습니다. 별도의 단계에서 유리 (경기장)에 현재 풍경이 있습니다. 이것은 매개 변수이며 계산량에 큰 영향을 미치지 않습니다. 현재 및 다음 그림에 대한 정보가 있습니다. 이들은 변수의 두 그룹입니다. 각 그림에 대해 공간에서 최대 4개의 방향(정사각형의 경우 - 단 하나)과 최대 10개의 "착륙" 좌표가 있습니다. 수치. 각 이동에는 40개의 상태가 있고 두 개는 1,600개이며 더 이상 정보가 없습니다. 이것은 작은 NP 문제입니다. Tetris는 복잡할 수 있지만 셀 수를 100개로 늘리고 플레이어가 다음 그림이 무엇인지 뿐만 아니라 다음 그림이 100개인지 알고 있는지 확인하면 문제가 발생할 수 있습니다.
다른 NP완전 게임도 모르시죠?소문에 따르면 지뢰 찾기, 스도쿠, 태그, 심지어 비상업적 버전의 슈퍼 마리오까지 있습니다. 규칙이 단순함에도 불구하고 특정 조건에서는 차원이 증가하므로 컴퓨터는 이상적인 솔루션을 제공할 수 없습니다. 수학자들은 왜 관심을 갖는가? 최적의 경로를 선택하고 프로세스나 일정을 최적화하는 것도 NP 수업 문제이기 때문입니다.
클래식 "마리오"는 이렇게 생겼습니다.
논리 게임은 매우 편리한 테스트 장소입니다.테스트 알고리즘 및 소프트웨어 구현. 퍼즐은 실제 문제에 내재된 규칙에 대한 다양한 예외가 없는 경우가 대부분 "순수"합니다. 이러한 문제의 상태 공간에는 조정 가능한 크기가 있으며 크기 조정 시 속성이 변경되지 않습니다(예: 태그 2x2, 4x4, 3x6). 모든 상태는 동일한 방식으로 설명됩니다. 일반적으로 퍼즐에 대한 수학적 설명은 삶의 문제만큼 복잡하지 않습니다.
"양자" 장난감의 시대
배낭에 대한 동일한 문제(더 많은 물건을 넣는 방법제한된 공간에서)은 테트리스 게임을 연상케 하며 효과적인 결과는 자원 낭비를 방지하기 때문에 물류 회사에 유용할 것입니다. 이러한 문제나 게임에 대해 "다항식으로 빠른" 알고리즘이 발견되면 NP 클래스의 다른 문제도 "빠르게" 해결될 수 있습니다. 이론적으로는 양자 컴퓨터가 이에 도움이 될 것이지만, 지금까지는 이러한 미래 컴퓨터의 프로토타입만 있을 뿐입니다. 2018년에는 양자 프로세서 생산의 현재 상태, 즉 NISQ 시대(시끄러운 중간 규모 양자 시대) 또는 하위 양자 기술 시대를 설명하기 위해 새로운 개념도 발명되었습니다.
과학자들이 양자를 개선하기 위해 노력하는 동안프로세스, 회사 경영진은 생산 작업을 최적화하는 데 도움이 되는 최신 아날로그를 찾고 있습니다. 이러한 "대체"는 기존 컴퓨터에서 95-99%의 최적 솔루션을 찾는 양자 기반 알고리즘이 되었습니다. 러시아에서는 QuSolve가 이를 수행하고 있습니다. 회사에서 수행 중인 작업은 NP 클래스에 속하며 수학자들은 비즈니스 문제를 해결하기 위한 알고리즘을 개발 및 개선합니다. QuSolve에서는 자체 솔버(솔버)를 테스트하기 위해 알고리즘에서 몇 가지 오류를 찾고 소프트웨어 패키지의 인터페이스에 추가하는 데 도움이 되는 태그를 사용했습니다.
현대 과학자들은 정말로 아무것도 하지 않고 있는가?모든 것을 개선하고 최적화하는 방법을 생각하고 계십니까? 당연히 아니지. 여가 시간에는 계속해서 게임을 만듭니다. 개발자들은 이미 대부분의 게임을 NP로 전환하여 양자 물리 현상에 약간의 마법을 추가할 수 있었습니다.
지난 10년간 양자기술은 이렇게 등장했다.체커, 양자 해전, 양자 틱택토. 양자 체스는 토너먼트가 개최되는 등 특별한 인기를 얻었으며 챔피언에게는 그랜드 마스터라는 칭호가 부여됩니다. 대부분의 새로운 "양자 게임"은 양자 역학의 기본 원리인 중첩을 기반으로 구축되었습니다.
예를 들어, 체스 말은동시에 보드의 여러 위치는 방어와 공격이 더 어렵다는 것을 의미합니다. 이로 인해 게임이 예측할 수 없고 장관이 됩니다. 2016년에는 스티븐 호킹과 마블 시네마틱 유니버스에서 앤트맨으로 유명한 배우 폴 러드의 양자 체스 게임을 보여주는 단편 영화도 촬영했습니다.
게임 스크린샷. 이것은 호킹과 러드 사이의 게임에서 온라인 보드가 어떻게 생겼는지입니다. 그런 다음 배우는 전설적인 물리학자를 이겼습니다.
이 게임들이 미래에도 이렇게 될지는 알 수 없습니다일반적인 틱택토, 테트리스, 태그처럼 평범하지만 수학자들이 실질적인 비즈니스 문제를 해결하고 기술을 개발하기 위한 고유한 알고리즘을 만들도록 영감을 줄 것입니다. 의심의 여지가 없습니다.
더 읽어보기 :
은하수의 모양은 우리가 생각했던 것과 전혀 다르다는 사실을 과학자들이 발견했습니다.
거주 가능 구역 가장자리에서 발견된 두 개의 슈퍼 지구: 그 중 하나는 편안한 온도를 가지고 있습니다.
지구와 가까운 별 기록을 파괴하는 블랙홀 발견