Программа для пары однозначно задает




НазваниеПрограмма для пары однозначно задает
Дата конвертации17.07.2013
Размер444 b.
ТипПрограмма


Пример обобщения концепции машины Тьюринга

  • Дипломник: Макаров А.А.

  • Научный руководитель: проф. Граничин О.Н.

  • СПбГУ, математико-механический факультет, 2005 год.


Актуальность темы

  • 1936г. Тьюринг

    • МТ абстрактное вычислительное устройство для мат. модели описания алгоритмов
  • 1936г. Черч

    • Любой процесс, который естественным образом мог бы быть назван процедурой, реализуем МТ. В этом смысле МТ считается эквивалентом любого ВУ
  • 2005г. 40 лет закону Мура

    • Число транзисторов на одной интегральной микросхеме удваивается каждые 18 мес.
    • Через несколько лет размер элементарной ячейки компьютера составит 100-200 ангстрем
    • Новый вид носителей информации требует новых математических оснований


Существующие подходы

  • Создание “СБИС” по все более высокоскоростной технологии

  • Использование квантовых компьютеров для быстрого решения сложных задач с данными большой размерности



Классическая МТ

  • MT =

  • Программа для пары

  • однозначно задает

  • Алгоритм работы: в любой момент времени

  • если машина останавливается, иначе выбираем

  • и полагаем



Нестандартная МТ

  • НМТ =

  • Структура НМТ расширена двумя компонентами:

  • - множество задания программы (где

  • - множество всевозможных наборов )

  • т.е. ,причем и

  • - оператор эволюции состояний и памяти

  • Алгоритм работы: в любой момент времени

    • если , то машина останавливается;
    • если , то происходит “естественная” эволюция
    • если ,то в работу машины вмешивается внешнее воздействие:
  • Здесь – время необходимое для перевода состояния и памяти машины из .



Набор моделей

  • Пусть – это множество НМТ (набор моделей), т.е. каждая ячейка памяти представляет собой отдельное устройство

  • Изменение состояния памяти может происходить непрерывно и параллельно во всех ячейках

  • Такая система позволяет переосмыслить понятие “такт”, момент достижения определенного множества



Алгоритм решения диофантова уравнения

  • 2003г. Тьен Д. Кью предложил квантовый алгоритм решения диофантова уравнения

  • Уравнение

    • неотрицательные целые решения
    • глобальный минимум
  • Набор моделей, для реализации алгоритма, который заключается в следующем:

    • Запускаем физический процесс H, соответствующий заданному диофантову уравнению на время T. Требуется найти основное состояние системы в момент времени T.
    • Повторяем временной процесс для получения статистических данных
    • Если ни одно из измеренных состояний не будет получено с вероятностью более ½, то увеличим T и вернемся к предыдущему шагу
    • В итоге, для некоторого T’, одно из состояний будет получаться с высокой вероятностью. Оно будет основным состоянием системы, в котором получается глобальный минимум
    • Если энергия полученного основного состояния – ноль, то исследуемое диофантово уравнение имеет решение, и не имеет в противном случае.
    • При этом конечность времени T’ следует из квантовой адиабатической теоремы, которая утверждает, что система перейдет в наше искомое основное состояние за конечное время.


Результаты моделирования

  • X-20=0

  • T=86



Заключение

  • Рассмотренная модель вычислений позволяет описывать подавляющее большинство процессов, происходящих в реальном мире

  • Работу различных вычислительных устройств (например, аналоговые компьютеры, биокомпьютеры, нейрокомпьютеры, квантовые компьютеры)

  • Возникает задача создания языков и средств программирования, позволяющих описывать непрерывные процессы с переходами от одной вычислительной модели к другой



Похожие:

Программа для пары однозначно задает iconЛекция №1 Вращательные кинематические пары. Поступательные кинематические пары
Поступательные кинематические пары обеспечивают только поступательное относительное движение
Программа для пары однозначно задает iconПрограмма для детей с ограниченными возможностями здоровья и программа для одаренных детей
Разработаны и применяются такие образовательные программы, как уровневая программа «Природа и творчество», программа дистанционного...
Программа для пары однозначно задает iconПрограмма модернизации серверного парка 20% в год
Внедрение новой прикладной системы сопровождалось закупкой пары идентичных серверных единиц + программа модернизации серверного парка...
Программа для пары однозначно задает iconПрограмма для преподавателей французского языка Программа «Courant du Monde» Программа «Produire au sud»

Программа для пары однозначно задает iconПрограмма Программа
Компания sap предоставляет шаблоны настроек. Программа установки для конкретной страны с начальными настройками
Программа для пары однозначно задает iconПрограмма праздника: Программа праздника: Мини доклад о гендерном воспитании; Тесты для родителей; Развлекательная программа

Программа для пары однозначно задает iconУрок №3 в теме «предельные углеводороды»
Пары хлороформа имеют наркотическое воздействие, он токсичен для обмена веществ и для внутренних органов, особенно печени
Программа для пары однозначно задает iconЖизнь после разработки. Продвижение и продажи мобильных приложений Павел Голуб Давайте познакомимся
Для пользователей App Store цена $1-2 практически даром (free). Для Android пользователя цена в $1 однозначно paid
Программа для пары однозначно задает iconПрограмма для создания рисунков. Графический редактор это программа для создания рисунков
«Когда человек не знает, к какой пристани он держит путь, для него ни один ветер не будет попутным»
Программа для пары однозначно задает iconПрограмма для микроконтроллера Разработана конструкция печатного узла Разработана программа и методика испытаний
Разработка устройства для измерения освещенности и коэффициента пульсации светового потока
Разместите кнопку на своём сайте:
dok.opredelim.com


База данных защищена авторским правом ©dok.opredelim.com 2015
обратиться к администрации
dok.opredelim.com
Главная страница