Трансвычислительная задача

Привет, Вы узнаете о том , что такое трансвычислительная задача, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое трансвычислительная задача , настоятельно рекомендую прочитать все из категории Высоконагруженные проекты.Паралельные вычисления. Суперкомпьютеры. Распределенные системы.

Трансвычисли́тельная зада́ча (англ. Transcomputational problem) — в теории сложности вычислений задача, для решения которой требуется обработка более чем 10⁹³ бит информации^[1]. Число 10⁹³, называемое «пределом Бремерманна», согласно Гансу-Иоахиму Бремерманну, представляет собой общее число бит, обрабатываемых гипотетическим компьютером размером с Землю за период времени, равный общему времени существования Земли^[1][2]. Термин «трансвычислительность» был предложен Бремерманном^[3].

Примеры трансвычислительных проблем 

Задача коммивояжера 

Задача коммивояжера  заключается в поиске пути обхода заданного списка городов, имеющего минимальную стоимость. Об этом говорит сайт https://intellect.icu . Путь обхода должен посещать все города ровно по одному разу и возвращаться в исходный город. Если в списке n городов, то число возможных путей обхода равно n!. Поскольку 66! примерно равно 5,443449391×10⁹², а 67! ≈ 3,647111092×10⁹⁴, задача проверки всех возможных путей становится трансвычислительной для n > 66.

Тестирование интегральных схем 

Полное тестирование всех комбинаций интегральной схемы с 308 входами и 1 выходом требует проверки 2³⁰⁸ комбинаций входных данных. Поскольку число 2³⁰⁸ является трансвычислительным, задача тестирования такой системы интегральных схем является трансвычислительной проблемой. Это означает, что отсутствует способ проверки схемы для всех входных данных методом грубой силы^[1][4].

Распознавание узоров 

Рассмотрим массив размером q×q, представляющий узор, похожий на шахматную доску, в которой каждый квадрат может быть одного из k цветов. Общее число возможных узоров равно kⁿ, где n = q². Задача определения наилучшей классификации узоров по какому-либо выбранному критерию может быть решена перебором всех возможных цветовых узоров. Для 2 цветов такой поиск становится трансвычислительным при размере массива 18×18 и более. Для массива 10×10 задача становится трансвычислительной при числе цветов 9 и более^[1] .

Данная задача имеет отношение к изучению физиологии сетчатки. Сетчатка состоит примерно из миллиона светочувствительных клеток. Даже если у клетки имеется всего 2 возможных состояния, обработка состояния сетчатки в целом требует обработки более чем 10^{300 000} бит информации. Это намного превосходит предел Бремерманна^[1].

Проблема анализа систем  

Система из n переменных, каждая из которых может принимать k возможных состояний, может иметь kⁿ возможных состояний. Анализ такой системы требует обработки как минимум kⁿ  бит информации. Задача становится трансвычислительной, если kⁿ > 10⁹³. Это происходит при следующих значениях kи n^[1]:

Следствия  

Существование реальных трансвычислительных задач имеет своим следствием ограниченность компьютеров, как средств обработки данных . Простым наращиванием вычислительных мощностей не удастся решить проблемы, требующие обработки огромного числа возможных ситуаций^[2].

Вау!! 😲 Ты еще не читал? Это зря! 

• Мозг-матрешка — теоретическая вычислительная мегаструктура, имеющая размеры, сопоставимые с размером планетной системы.
• Пределы вычислений
• Предел Бремерманна

В заключение, эта статья об трансвычислительная задача подчеркивает важность того что вы тут, расширяете ваше сознание, знания, навыки и умения. Надеюсь, что теперь ты понял что такое трансвычислительная задача и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Высоконагруженные проекты.Паралельные вычисления. Суперкомпьютеры. Распределенные системы