Подождите, пожалуйста, выполняется поиск в заданном разделе

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

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

 

Содержание

 
  • 1Примеры трансвычислительных проблем
    • 1 . Об этом говорит сайт https://intellect.icu .1Задача коммивояжёра
    • 1.2Тестирование интегральных схем
    • 1.3Распознавание узоров
    • 1.4Проблема анализа систем
  • 2Следствия
  • 3См. также
  • 4Примечания

 

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

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

Задача коммивояжёра заключается в поиске пути обхода заданного списка городов, имеющего минимальную стоимость. Путь обхода должен посещать все города ровно по одному разу и возвращаться в исходный город. Если в списке n городов, то число возможных путей обхода равно n!. Поскольку 66! примерно равно 5,443449391×1092, а 67! ≈ 3,647111092×1094, задача проверки всех возможных путей становится трансвычислительной для n > 66.

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

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

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

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

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

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

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

k 2 3 4 5 6 7 8 9 10
n 308 194 154 133 119 110 102 97 93

Следствия 

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

См. также 

  • Мозг-матрёшка — теоретическая вычислительная мегаструктура, имеющая размеры, сопоставимые с размером планетной системы.
  • Пределы вычислений
  • Предел Бремерманна
подробнее на сайте https://intellect.icu/transvychislitelnaya-zadacha-5733

Комментарии (0)


avatar

Чтобы оставить комментарий войдите или зарегистрируйтесь



Высоконагруженные проекты.Теория паралельные вычисления. Суперкомпьютеры. Распределенные системы