Модели вычислений



Скачать 14.85 Kb.
Дата15.01.2013
Размер14.85 Kb.
ТипДокументы

Модели вычислений


Под эффективными алгоритмами всюду ниже, согласно тезису Эдмондса, мы будем понимать полиномиальные алгоритмы. Последние, в соответствии с подходом, принятым в теоретической криптографии, можно определить в двух моделях вычислений.

В однородной (uniform) модели вычислений полиномиальный алгоритм -- это вероятностная машина Тьюринга, время работы которой ограничено полиномом от длины входного слова.

В неоднородной (nonuniform) модели под алгоритмом понимается семейство булевых схем . Схема имеет входов и построена, скажем для определенности, из функциональных элементов И, ИЛИ и НЕ. Без ограничения общности можно считать, что все элементы И и ИЛИ двухвходовые. Алгоритм называется полиномиальным, если существует полином, ограничивающий сверху количество элементов в схеме для всех достаточно больших .

Альтернативно, алгоритм в неоднородной модели можно определить как семейство машин Тьюринга , где работает на входных словах длины . Алгоритм называется полиномиальным, если существует полином, ограничивающий сверху время работы машины для всех достаточно больших . Это определение эквивалентно предыдущему.

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

Похожие:

Модели вычислений iconТеория сложности вычислений
Разрешимые и перечислимые множества. Нумерации вычислимых функций. Модели вычислений. Примеры неразрешимых проблем. Сводимость одних...
Модели вычислений iconМетоды распределённых вычислений на основе модели потока данных. Прототип системы. М. О. Бахтерев, П. А. Васёв
Методы распределённых вычислений на основе модели потока данных. Прототип системы
Модели вычислений iconСемантическая масштабируемость для специализации вычислений при разработке деловых игр: аппликативные модели
Рассмотрено два класса систем, обеспечивающих семантическое масштабирование. В первом из них реализуется компиляция в промежуточный...
Модели вычислений iconМодели вычислений
Представление о категориальной абстрактной машине (кам). Вычисление значения в д з к
Модели вычислений iconЛекция 26. Проверка адекватности и работоспособности регрессионной модели. Планы второго порядка. Регрессионный анализ результатов вычислительного эксперимента на детерминированной теоретической модели
Следовательно, поверхность отклика проходит через все точки, и полученная модель адекватна. Значения в этом случае используют для...
Модели вычислений iconОрдена ленина
О языке программирования для модели вычислений, основанной на принципе потока данных
Модели вычислений iconБилет 10. Теория сложности вычислений
Теория сложности вычислений является разделом теории вычислений, изучающим стоимость работы, требуемой для решения вычислительной...
Модели вычислений iconВопросы к дифференцированному зачету по курсу Программирование 2
Повелительное и изъявительное наклонения в языках программирования. На какой базе можно строить модели вычислений с повелительным...
Модели вычислений iconРеферат по Информационным технологиям «Современные принципы и методы обработки информации»
Целью данного реферата я вижу ознакомится с некоторыми из выше перечисленных принципов. Именно: квантовые вычисления, нейросетевые...
Модели вычислений iconМодели вычислений. Кафедра общей экономики
Показываются связи между возможными формами представления объектов, комбинаторная редукция, экспансия и конверсии. Подробно рассматривается...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org