Small Data Science for Russian Adventurers

#термин
В последнее время мне несколько раз попался термин трансвычислительная задача - задача, которая не могла бы быть решена, если бы решалась компьютером размером с нашу планету на предельной скорости всё время существования планеты. Есть даже константа 10^93 т.н. предел Бремерманна - число бит, которое этот компьютер успеет обработать. Термин, конечно, условный и почти бесполезный, однако, задаёт некоторый "бенчмарк" для сравнения различных задачи. Например, задача коммивояжёра при числе городов n=67 становится трансвычислительной (если решать тупым перебором - что почему-то не всегда оговаривают). Что интуитивно совсем немного (когда на практике возникала такая задача, то чаще n>100).

Wikipedia

Transcomputational problem

problem whose solution requires a computer at least the size of the Earth and a time period at least the estimated age of the Earth to be computed

👍30🔥2😁2

www.tgoop.com/smalldatascience/808

7.03K viewsJul 5, 2022 at 16:07

#термин
В последнее время мне несколько раз попался термин трансвычислительная задача - задача, которая не могла бы быть решена, если бы решалась компьютером размером с нашу планету на предельной скорости всё время существования планеты. Есть даже константа 10^93 т.н. предел Бремерманна - число бит, которое этот компьютер успеет обработать. Термин, конечно, условный и почти бесполезный, однако, задаёт некоторый "бенчмарк" для сравнения различных задачи. Например, задача коммивояжёра при числе городов n=67 становится трансвычислительной (если решать тупым перебором - что почему-то не всегда оговаривают). Что интуитивно совсем немного (когда на практике возникала такая задача, то чаще n>100).

BY Small Data Science for Russian Adventurers