Автореферат диссертации на соискание ученой степени




Скачать 121.11 Kb.
PDF просмотр
НазваниеАвтореферат диссертации на соискание ученой степени
страница1/7
Дата конвертации27.05.2013
Размер121.11 Kb.
ТипАвтореферат диссертации
  1   2   3   4   5   6   7
На правах рукописи
Махнычев Владимир Сергеевич
Распараллеливание алгоритмов ретроанализа 
для решения переборных задач 
в вычислительных системах без общей памяти
Специальность 05.13.11 –
математическое и программное обеспечение
вычислительных машин, комплексов и компьютерных сетей
Автореферат
диссертации на соискание ученой степени
кандидата физико-математических наук
Москва – 2012


Работа   выполнена   на   кафедре   автоматизации   систем   вычислительных 
комплексов   факультета   вычислительной   математики   и   кибернетики 
Московского государственного университета имени М.В. Ломоносова.
Научный руководитель:
кандидат физико-математических наук, 
доцент
Гуляев Анатолий Викторович
Официальные оппоненты:
доктор технических наук,
профессор
Рябов Геннадий Георгиевич
доктор технических наук,
профессор
Топорков Виктор Васильевич
Ведущая организация:
Московский физико-технический институт
Защита   диссертации   состоится   19   октября   2012   г.   в   11   часов   на   заседании 
диссертационного   совета   Д   501.001.44   при   факультете   вычислительной 
математики и кибернетики Московского государственного университета имени 
М. В. Ломоносова   по   адресу:   119991,   ГСП-1,   Москва,   Ленинские   горы,   2-й 
учебный корпус, факультет ВМК, аудитория 685. Желающие присутствовать на 
заседании диссертационного совета должны сообщить об этом за два дня по 
тел. (495) 939-30-10 (для оформления заявки на пропуск).
С   диссертацией   можно   ознакомиться   в   Фундаментальной   библиотеке   МГУ 
имени   М.В.Ломоносова.   С   текстом   автореферата   можно   ознакомиться   на 
официальном сайте ВМК МГУ  http://cs.msu.ru  в разделе «Наука» —   «Работа 
диссертационных советов» — «Д 501.001.44».
Автореферат разослан «17» сентября 2012 г.
Заместитель председателя
диссертационного совета,
профессор
В.М. Круглов

Общая характеристика работы
Введение.  Параллельные   вычисления   в   последние   десятилетия 
развиваются бурными темпами. Суперкомпьютерные и кластерные технологии 
позволяют решать задачи, решение которых последовательными алгоритмами 
потребовало   бы   неприемлемо   большого   времени.   При   успешном   создании 
параллельного алгоритма становится возможным получить совершенно новые, 
не достижимые ранее результаты для многих задач.
Одним   из   классов   таких   задач   является   построение  оптимальной 
стратегии  для   игры   двух   противников   методом   ретроанализа.   Оптимальная 
стратегия   —   полный   план   действий,   который   при   безошибочных   действиях 
обоих игроков позволяет либо достичь выигрыша за наименьшее число ходов (в 
случае,   если   выигрыш   достижим),   либо   (в   противном   случае)   максимально 
отдалить проигрыш или добиться ничьей, если это возможно. При построении 
такой   стратегии   требуется   оптимизировать   количество   ходов   как   в   сторону 
минимума (в случае выигрыша), так и в сторону максимума (при проигрыше), 
что обусловливает нетривиальность решения задачи. 
Метод   ретроанализа   применяется   к   играм   с   полной   информацией, 
игровой   процесс   которых   заключается   в   поочередном   выполнении   игроками 
действий («ходов»), каждое из которых изменяет состояние игры; примерами 
таких игр могут служить шахматы, шашки, рэндзю, го (в этих играх состояние 
игры  принято   называть  «положением   на  доске»  или  «позицией»).   В  теории, 
метод   ретроанализа   позволяет   построить   оптимальную   стратегию   для   всей 
игры, но на практике из-за ограниченных вычислительных мощностей удается 
построить   оптимальную   стратегию   лишь   для   некоторого   класса   состояний 
игры.
Актуальность   работы.  Распараллеливание   и   адаптация   алгоритма 
ретроанализа   к суперкомпьютерным   системам   без   общей   памяти   делает 
возможным   построение   оптимальной   стратегии   для   гораздо   более   широкого 
класса   состояний   игры,   чем   это   позволяют   последовательные   алгоритмы. 
Кроме того, алгоритм ретроанализа является частным случаем динамического 
программирования,   и   подходы,   примененные   в   данной   работе   при   его 
распараллеливании,   могут   быть   использованы   при   распараллеливании 
некоторых   других   задач,   решаемых   методами   динамического 
программирования.
Построение оптимальной стратегии для новых классов состояний игры на 
персональных   компьютерах   упирается   в   огромные   объемы   данных   и 
вычислений.   Объем   доступной   оперативной   памяти   компьютера   —   одно   из 
основных   препятствий   на   пути   решения   задач   большой   размерности 
алгоритмом ретроанализа. Например, для задачи игры в шахматы при наличии 
на   доске   не   более   семи   фигур   количество   позиций,   данные   о которых 
необходимо   хранить   одновременно,   даже   после   применения  различных 
3
  1   2   3   4   5   6   7

Похожие:

Автореферат диссертации на соискание ученой степени iconАвтореферат диссертации на соискание ученой степени

Автореферат диссертации на соискание ученой степени iconАвтореферат диссертации на соискание ученой степени

Автореферат диссертации на соискание ученой степени icon  автореферат диссертации на соискание ученой степени 
Защита состоится  15. 08. 2012, в 15. 00 , на заседании Cпециализированного Ученого 
Автореферат диссертации на соискание ученой степени iconАвтореферат диссертации на соискание ученой степени
Институт автоматики и процессов управления Дальневосточного отделения ран по адресу
Автореферат диссертации на соискание ученой степени iconАвтореферат диссертации на соискание ученой степени
Чегис И. А., Яблонский С. В. Логические способы контроля электрических схем // Тр. Миан
Автореферат диссертации на соискание ученой степени iconАвтореферат диссертации на соискание ученой степени
Специальность 05. 13. 11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей
Автореферат диссертации на соискание ученой степени icon  автореферат диссертации на соискание ученой степени 
Математические модели И программные средства  для реконструкции военно-исторических данных 
Автореферат диссертации на соискание ученой степени icon  автореферат диссертации на соискание ученой степени 
Математические модели И программные средства  для реконструкции военно-исторических данных 
Автореферат диссертации на соискание ученой степени iconАвтореферат диссертации на соискание ученой степени
С диссертацией можно ознакомиться в библиотеке Факультета вмк мгу имени М. В. Ломоносова
Автореферат диссертации на соискание ученой степени iconАвтореферат диссертации на соискание ученой степени 
Ю. К.   Калинин,   2007;   П. Б.   Панов   и   соавт.,   2007;   С. В.   Ширинкин,   2008;  
Разместите кнопку на своём сайте:
kak.znate.ru


База данных защищена авторским правом ©kak.znate.ru 2012
обратиться к администрации
KakZnate
Главная страница