Аннотированный отчет о научно-исследовательской работе за 2005 год Тема нир: Сложностные свойства детерминированных и вероятностных математических моделей. Численные методы построения алгоритмов



Скачать 75.84 Kb.
Дата30.12.2012
Размер75.84 Kb.
ТипОтчет
Регистрационный номер НИР: 1. 14.01

АННОТИРОВАННЫЙ ОТЧЕТ

о научно-исследовательской работе за 2005 год

1. Тема НИР: Сложностные свойства детерминированных и вероятностных математических моделей. Численные методы построения алгоритмов.

2. Номер государственной регистрации НИР: 01.200.202510

3. Характер НИР: фундаментальное научное исследование
4. Исполнитель (руководитель) НИР: Аблаев Ф.М., проф., д.ф.-м.н.

5. Вуз (организация), в котором проводится НИР: Казанский государственный университет
6. Наименование структурного подразделения вуза (организации), в котором проводится НИР: кафедра теоретической кибернетики

7. Телефон исполнителя: 2927444

8. E-mail исполнителя: Farid.Ablayev@ksu.ru

9. WWW адрес (для ссылки на информацию о результатах НИР):

10. Сроки проведения: начало - 01.01.2001 , окончание - 31.12.2005

11. Наименование годового отчетного/ завершающего этапа НИР: Приложение разработанных методов построения алгоритмов для различных моделей вычислений.

12. Плановый объем средств на проведение годового отчетного / завершающего этапа НИР:

Плановый объем средств на проведение НИР с начала ее проведения, включая отчетный этап НИР:

13. Фактический объем средств, выделенных на проведение годового отчетного / завершающего этапа НИР:

Фактический объем средств на проведение НИР с начала ее проведения, включая отчетный этап НИР:

14. Коды темы по ГРНТИ : 28.15.15,27.35.23

15. Полученные научные и (или) научно-технические результаты: I. Основным результатом нашего проекта является доказательство факта, что квантовые вычисления, реализованные на одном кубите, являются такими же мощными, как и схемы из функциональных элементов

логарифмической глубины. Точнее: нами определены модели вероятностной (классической) и квантовой синтаксической ветвящейся программы. Доказано, что класс функций, представимых в синтаксических квантовых ветвящихся программах ширины два (программы постренные на однокубите) совпадает с известным классом NC^1. Доказано, что класс функций, представимых в синтаксических вероятностных ветвящихся программах ширины два является собственным подклассом функций представимых в квантовых бинарных программах ширины два.

II. Разработанн метод "линейнейного" моделирования квантового вычислительного процесса классическим вычислительным процессом. На основе этого метода установлены 1) оценка сложности классического

моделирования квантовой ветвящейся программы (неоднородной вычислительной модели) и 2) оценка сложности классического моделирования квантовой машины Тьюринга (однородной вычислительной модели) и

сложности классического моделирования квантовой ветвящейся программы (неоднородной вычислительной модели).
В качестве следствия из полученных оценок установлены новые соотношения между классическими и

квантовыми классами сложности, получены ранее известные соотношения.

III. Исследовались квантовые коммуникационные модели вычислений. Доказана нижняя оценка сложности для одностроннего квантового коммуникационного вычисления булевых функций. Полученная оценка является обобщением нижней оценки, представленной Хартмутом Клауком на конференции STOC в 2000 году.

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

IV. Определен новый класс много раз измеряемых квантовых конечных автоматов. Доказано, что в отличии от ранее известных моделей много раз измеряемых квантовых автоматов, наша модель может распознавать

произвольный регулярный язык.

V. Предложен (на основе техники конечных полей) подход построения классической автоматной модели квантового бита. Рассмотрены сложностные характеристики этой модели.

16. Полученная научная и (или) научно-техническая продукция:

17. Ключевые слова и словосочетания, характеризующие результаты (продукцию): Сложность вычислений, ветвящиеся программы, машины Тьюринга, вероятностные, квантовые алгоритмы
18. Наличие аналога для сопоставления результатов (продукции) или отсутствие аналогов: аналог отсутствует

19. Преимущества полученных результатов (продукции) по сравнению с результатами аналогичных отечественных или зарубежных НИР:

а) по новизне: результаты являются новыми

б) по широте применения: в масштабах отрасли

в) в области получения новых знаний Определен новый класс много раз измеряемых квантовых конечных автоматов. Доказано, что в отличии от ранее известных моделей много раз измеряемых квантовых автоматов, наша модель может распознавать произвольный регулярный язык.

20. Степень готовности полученных результатов к практическому использованию: выполнен эксперимент. образец (установки,методики,системы, программы и т.д.)

21. Предполагаемое использование результатов и продукции: Предполагается использование полученных результатов в дальнейших исследованиях, а также в учебном процессе.

22. Форма представления результатов НИР:

статьи в российских изданиях - 9

статьи в зарубежных изданиях - 8

доклады - 18

диссертации - 2
23. Библиографический список публикаций, отражающих результаты работы:

статьи в российских изданиях:

1. Аблаев,Ф.М. О сложности классических и квантовых моделей вычислений [Текст]/ Ф.М. Аблаев // Мат. вопросы кибернетики. - М., 2005. - Вып 13.

2. Аблаев,Ф.М. О сложности классических и квантовых бинарных программ и автоматов[Текст] /Ф.М. Аблаев// Сбор. трудов XIII Международной конф-ции ``Проблемы теор. кибер-ки''. - Казань:изд-во Казан. гос. ун-та, 2005. - С.5-15.

3. Аблаев,Ф.М. О квантовой коммуникационной сложности булевых функций [Текст]/Ф.М. Аблаев // Материалы VIII Международного сем-ра ''Дискр. мат-ка и ее прилож.''. - М.: Изд-во мехмата МГУ, 2004. - С. 50-52.

4. Аблаев,Ф.М. Модель квантового автомата, способного распознавать любой рег. язык [Текст]/Ф. М. Аблаев, А.Ф. Гайнутдинова // Труды Математического центра имени Н. И. Лобачевского. Т. 25 -- Казань: Изд. Казан. математическогообщества, 2005. -- С. 6-7

5. Мубаракзянов,Р.Г. О сложности функций для вероятностных один раз читающих бинарных программ [Текст]/Р.Г.Мубаракзянов //Тезисы VIII международного семинара "Дискретная математика и ее приложения".- М.: МГУ, февраль, 2004.

6. Мубаракзянов,Р.Г. Для вероятностных упорядоченных бинарных программ многократное чтение переменных не дает преимущества [Текст]/Р.Г.Мубаракзянов//Труды Мат. центра им. Н. И. Лобачевского,).- Казань:Изд.-во Каз. мат. об-ва, 2004.- С. 193-194.

7. Мубаракзянов,Р.Г. О соотношении сложности упорядоченных вероятностных и неупорядоченных детерминированных бинарных программ [Текст]/Р.Г. Мубаракзянов// Труды VI Межд. конф.``Дискр. модели в теории управляющих систем''.- М.:МГУ,2004. - С.61-64.

8. Ablayev, F. Comparative Power of Quantum and Classical Computation Models [Text]/F. Ablaуev // Intern. Symposium "Quantum informatics -- 2004". Book of Abstracts. October 5th- 8th, 2004, Moscow, Russia. -- Institute of Physics and Technology. - P.2.

9. Ablayev, F. On Classical Simulation of Quantum Machines [Text]/F. Ablayev, A. Gainutdinova // International Symposium "Quantum informatics -- 2004". Book of Abstracts.Moscow, Russia. -- Institute of Physics and Technology 2004. -- P. 10-3.

статьи в зарубежных изданиях:

1. Ablayev, F. Complexity of quantum uniform and nonuniform automata [Text] / F. Ablayev, A. Gainutdinova // Developments of language theory - DLT2005, Palermo; proceeding, Lecture Notes in Computer Science., 3572.- Palermo,2005. - P.78-87.

2. Ablayev, F. On the computational power of probabilistic and quantum branching program [Text] / F. Ablayev, A. Gainutdinova, M. Karpinski, C. Moore, C. Pollette // Information and Computation Vol. 203, Issue 2. - 15 December 2005. - P. 145-162.

3. Ablayev, F. Comparative power of quantum and classical computation models [Text] / F. Ablayev // Quantum Informatics 2004.- Proceedings of The International Society for Optical Engineering(SPIE). - Vol. 5833. - 2005. - P.100-108.

4. Ablayev, F. On classical stimulation of quantum machines [Text] / F. Ablayev, A. Gainutdinova // Quantum Informatics 2004.- Proceedings of The International Society for Optical Engineering (SPIE). - Vol. 5833. - 2005. - P.109-115.

5. Ablayev, F. A lower bound for integer multiplication on randomuzed ordered read-once branching rograms [Text] / F. Ablayev, M. Karpinski //Informaton and Computation, 186(1), - 2003. - P. 78-89.

6. Ablayev, F. Classical Simulation Complexity of Quantum Machines [Text] / F. Ablayev, A. Gainutdinova //14th FCT 2003, Sweden, Proceedings Lecture Notes in Computer Science Springer-Verlag, 2751. - 2003. - P.296-302.

7. Ablayev, F. On Computational Power of Quantum Branching Programs [Text] / F. Ablayev, A. Gainutdinova, M. Karpinski //Preprint 2002-028 of Mathematical Sciences Research Institute, Berkeley. - California, 2003. - P. 20.

8. Ablayev, F. Quantum and Stochastic Branching Programs of Bounded Width [Text] / F. Ablayev, C. Moore, C. Pollett // Proc. of the ICALP'2002, Lecture Notes in Computer Science, Springer-Verlag, TR02-013. - 2002.-- P.343-354.

доклады:

1. Международная конференция ``Проблемы теоретической кибернетики'' Пенза 2005.

2. 9th International Conference ``Developments of language theory'' DLT2005, 2005, Italy.

3. Third International Symposium "Stochastic Algorithms:Foundations and Applications" SAGA 2005, Moscow, Russia, October 20-22, 2005

4. International Conference "Quantum Informatics 2005" QI 2005, Moscow Zvenigorod, Russia, October 3-7 2005.

5. VIII Международный семинар "Дискретная математика и ее приложения", МГУ, Москва, февраль, 2004.

6. V Всероссийский семинар "Сеточные методы для краевых задач и приложения", Казань, 17-21 сентября 2004 г.

7. Международная научная конференции "Актуальные проблемы математики и механики", Казань, 27 сентября - 1 октября 2004 г.

8. International Symposium "Quantum informatics -- 2004" Moscow, October, 2004, organized by Institute of Physics and Technology (FTIAN) of Russia Academy of Science.

9. International Dagstuhl seminar ``Algebraic methods in complexity theory'' October 2004, Dagstuhl castle, Germany.

10. На семинарах по теории сложности в Боннском и Гамбургском университетах в октябре 2004.

11. VI Международная конференция Дискретные модели в теории управляющих систем, МГУ, Москва, декабрь, 2004.

12. Международной конференции Fundamentals of Computation Theory: 14th International Symposium / FCT 2003, Malmo, Sweden, August 12-15, 2003;

13. V Международной конференции "Дискретные модели в теории управляющих систем" (Ратмино, 26-29 мая 2003г.);

14. Международной летней школе-семинаре по теоретической и математической физике, (июнь 2003 г., Казань);

15. Конференции по глобальным системам связи, проводимой Минсвязи РТ (сентябрь 2003, г. Казань)

16. New Geometry of Nature Mathematics, Mechanics, Geophysics, Astronomy & Biology. Joint International Scientific Conference August 25 -September 5, 2003 Kazan State University Russia

17. Первая Всерос. научная конф. <Методы и средства обработки информации>. (Москва, МГУ 01 - 03 октября 2003г).

18. На семинарах мехмата МГУ, физико-технического института АН (г. Москва), Латвийского государственного университета (г. Рига).

диссертации:

1. Нурутдинов, Ш.Р. Полиномиальные модели автоматных преобразований над полем GF(2^n) [Текст]: дис. ...док. физ.-мат. наук: 05.13.18 : защищена 22.12.05 / Нурутдинов Шамиль Рамилович. -- Казань, 2005. -- 222 с. -- Библиогр.: с. 199-213.

2. Гайнутдинова, А.Ф. Сравнительная сложность квантовых и классических моделей вычислений [Текст]: дис. ... канд. физ.-мат. наук: 01.01.09 : защищена 08.04.04 : утв. 11.06.04 / Гайнутдинова Аида Фаритовна.-- Казань,2004.-- 101 с.-- Библоиогр.: С. 94-101.
24. Использование результатов в учебном процессе: создание новых дисциплин, использование в преподавании существующих дисциплин

25. Количество сотрудников профессорско-преподавательского состава, принимавших участие в выполнении НИР и указанных в научно-технических отчетах в качестве соисполнителей: 7

26. Количество студентов, принимавших участие в выполнении НИР: 30 , в том числе:

- являющихся авторами публикаций по результатам НИР - 0

- указанных в научно-технических отчетах в качестве соисполнителей - 0

- с оплатой за счет выделенных на данную НИР средств - 0

27. Предполагаемое развитие исследований Построение помехоустойчивых квантовых алгоритмов. Построение эффективных квантовых алгоритмов, ветвящихся программ для широкого класса булевых функций.

Исполнитель НИР _____________________( Аблаев Ф.М. )

Похожие:

Аннотированный отчет о научно-исследовательской работе за 2005 год Тема нир: Сложностные свойства детерминированных и вероятностных математических моделей. Численные методы построения алгоритмов iconАннотированный отчет о научно-исследовательской работе за 2005 год Тема нир: Исследование магнитных наноструктур для спинтроники Номер государственной регистрации нир

Аннотированный отчет о научно-исследовательской работе за 2005 год Тема нир: Сложностные свойства детерминированных и вероятностных математических моделей. Численные методы построения алгоритмов iconАннотированный отчет о научно-исследовательской работе за 2004 год Тема нир: Синтез и стереохимия семичленных гетероциклов с атомами O,S,N,P. Номер государственной регистрации нир

Аннотированный отчет о научно-исследовательской работе за 2005 год Тема нир: Сложностные свойства детерминированных и вероятностных математических моделей. Численные методы построения алгоритмов iconАннотированный отчет о научно-исследовательской работе за 2005 год Тема нир: Структурно-динамические свойства сложных молекулярных систем, включая биологические
Тема нир: Структурно-динамические свойства сложных молекулярных систем, включая биологические
Аннотированный отчет о научно-исследовательской работе за 2005 год Тема нир: Сложностные свойства детерминированных и вероятностных математических моделей. Численные методы построения алгоритмов iconАннотированный отчет о научно-исследовательской работе за 2005 год Тема нир: Математическое моделирование и методы расчета деформирования изотропных и анизотропных тел
Тема нир: Математическое моделирование и методы расчета деформирования изотропных и анизотропных тел
Аннотированный отчет о научно-исследовательской работе за 2005 год Тема нир: Сложностные свойства детерминированных и вероятностных математических моделей. Численные методы построения алгоритмов iconАннотированный отчет о научно-исследовательской работе за 2004 год Тема нир: Анализ физического состояния вещества в атмосферах звезд разных типов. Номер государственной регистрации нир

Аннотированный отчет о научно-исследовательской работе за 2005 год Тема нир: Сложностные свойства детерминированных и вероятностных математических моделей. Численные методы построения алгоритмов iconАннотированный отчет о научно-исследовательской работе за 2005 год Тема нир: Методы оптимизации, теоретические аспекты информационно-телекоммуникационных комплексов и математического моделирования
...
Аннотированный отчет о научно-исследовательской работе за 2005 год Тема нир: Сложностные свойства детерминированных и вероятностных математических моделей. Численные методы построения алгоритмов iconАннотированный отчет о научно-исследовательской работе за 2005 год Тема нир: Создание археологических геоинформационных систем (агис) Республики Татарстан Номер государственной регистрации нир
Тема нир: Создание археологических геоинформационных систем (агис) Республики Татарстан
Аннотированный отчет о научно-исследовательской работе за 2005 год Тема нир: Сложностные свойства детерминированных и вероятностных математических моделей. Численные методы построения алгоритмов iconОтчет о научно-исследовательской работе за 2005 год
Тема нир: Координационные соединения 3d-переходных, платиновых и редкоземельных металлов: термодинамика и кинетика образования, синтез,...
Аннотированный отчет о научно-исследовательской работе за 2005 год Тема нир: Сложностные свойства детерминированных и вероятностных математических моделей. Численные методы построения алгоритмов iconАннотированный отчет о научно-исследовательской работе за 2004 год Тема нир: Методы оптимизации, теоретические аспекты информационно-телекоммуникационных комплексов и математического моделирования
...
Аннотированный отчет о научно-исследовательской работе за 2005 год Тема нир: Сложностные свойства детерминированных и вероятностных математических моделей. Численные методы построения алгоритмов iconАннотированный отчет о научно-исследовательской работе за 2005 год Тема нир: Численное исследование задач со свободными границами и вариационных неравенств
Тема нир: Численное исследование задач со свободными границами и вариационных неравенств
Разместите кнопку на своём сайте:
ru.convdocs.org


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