БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ ПРИКЛАДНОЙ МАТЕМАТИКИ И ИНФОРМАТИКИ Кафедра дискретной математики и алгоритмики Применение ифнормационных.

Презентация:



Advertisements
Похожие презентации
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ ПРИКЛАДНОЙ МАТЕМАТИКИ и ИНФОРМАТИКИ Кафедра теории вероятностей и математической статистики Робастность.
Advertisements

Методы распознавания зашумленных образов БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ ПРИКЛАДНОЙ МАТЕМАТИКИ и ИНФОРМАТИКИ Кафедра математического.
ЕМЕЛЬЯНЧЕНКО Наталья Сергеевна МОДЕЛИ И АЛГОРИТМЫ ДЛЯ ЗАДАЧ ТЕОРИИ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ ПРИКЛАДНОЙ.
ПОЛЕЩУК МАКСИМ АЛЕКСАНДРОВИЧ АЛГОРИТМЫ И ПРОГРАММЫ ДВУХУРОВНЕВЫХ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Кафедра вычислительной.
«АНАЛИЗ СОЦИАЛЬНЫХ СЕТЕЙ» Малютин Сергей Руководитель Буза Михаил Константинович профессор кафедры МСС Факультет прикладной математики и информатики Кафедра.
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Механико-математический факультет Кафедра высшей алгебры и защиты информации Криптография и теория кодирования.
Выделение средних линий объектов на трехмерных медицинских изображениях Гончаров Д. А. Дипломная работа 2010 БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ Белорусский государственный университет Факультет прикладной математики и информатики Кафедра математической.
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Механико-математический факультет Кафедра геометрии, топологии и методики преподавания математики Сергеева Юлия.
Информационные технологии в прогнозировании финансовых рядов. ФАКУЛЬТЕТ ПРИКЛАДНОЙ МАТЕМАТИКИ и ИНФОРМАТИКИ Бокий Кирилл Константинович Кафедра теории.
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ ПРИКЛАДНОЙ МАТЕМАТИКИ и ИНФОРМАТИКИ Кафедра вычислительной математики Применение информационных технологий.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Факультет прикладной математики и информатики Кафедра вычислительной.
Коллизии в трудовом праве Научный руководитель: Курылёва Ольга Сергеевна, кандидат юридических наук, доцент кафедры гражданского процесса и трудового права.
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ ПРИКЛАДНОЙ МАТЕМАТИКИ И ИНФОРМАТИКИ Кафедра вычислительной математики Лэ Тхи Тхиен Тхуи Руководитель.
Белорусский государственный университет Механико-математический факультет Кафедра функционально анализа Голубовский Олег Николаевич Николаевич Сингулярная.
Белорусский государственный университет Механико-математический факультет Кафедра теории функций Сыричев Вадим Викторович Бесконечные матрицы и пространство.
Белорусский государственный университет Кафедра дифференциальных уравнений и системного анализа Диссертация на соискание ученой степени кандидата физико-математических.
Мелкозернистая параллельная реализация алгоритма Монтгомери Руководитель: доктор физико- математических наук, профессор Соболевский П.И.
Коррекция нелинейности сканера АСМ по изображениям тестовых структур Научный руководитель Малевич А.Э. доцент кафедры ДУ, кандидат физ.-мат. наук Лукьянова.
Численный метод решения нелинейных уравнений Шредингера с использованием алгоритмов цифровой обработки сигналов Руководитель: доктор физико-математических.
Транксрипт:

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ ПРИКЛАДНОЙ МАТЕМАТИКИ И ИНФОРМАТИКИ Кафедра дискретной математики и алгоритмики Применение информационных технологий в исследовании рекурсивно-порождаемых классов, методов декомпозиции и решения дискретных задач Тихон Сергей Александрович Руководитель: канд. физ.-мат. наук Лепин Виктор Васильевич

Применение информационных технологий в исследовании рекурсивно- порождаемых классов, методов декомпозиции и решения дискретных задач Постановка задачи Исследовать графы Халина с древесной основой гусеницей Решить задачу о профиле для графов Халина Решить задачу об оптимальном линейном размещении для графов Халина Изучить графы с особыми блоками Решить задачу разбиения графа с особыми блоками на k-цепи Тихон С.А. Магистерская работа

Применение информационных технологий в исследовании рекурсивно- порождаемых классов, методов декомпозиции и решения дискретных задач Объект и предмет исследования Предмет исследования – алгоритмическая сложность(полиномиальная разрешимость) в графовых задачах. Объект исследования – алгоритмы / подходы по использованию знаний о структуре графов в целях полиномиальной разрешимости NP-полных задач. 3 Тихон С.А. Магистерская работа 2012

Применение информационных технологий в исследовании рекурсивно- порождаемых классов, методов декомпозиции и решения дискретных задач Методология исследования Методы: Теории графов Методы декомпозиции Динамическое программирование Теории NP-полноты 4 Тихон С.А. Магистерская работа 2012

Применение информационных технологий в исследовании рекурсивно- порождаемых классов, методов декомпозиции и решения дискретных задач Результаты 5 Тихон С.А. Магистерская работа 2012

Применение информационных технологий в исследовании рекурсивно- порождаемых классов, методов декомпозиции и решения дискретных задач Положения, выносимые на защиту 6 Тихон С.А. Магистерская работа 2012

Применение информационных технологий в исследовании рекурсивно- порождаемых классов, методов декомпозиции и решения дискретных задач Литература Yung-Ling, Lai On the profile of the corona of two graphs / Yung-Ling Lai, Gerard J.Chang // Information Processing Letters 89 (2004) pp Yung-Ling, Lai A Survey of Solved Problems and Applications on Bandwidth, Edgesum, and Profile of Graphs / Yung-Ling Lai, Kenneth Williams // Journal of Graph Theory 1999 pp Horton, S. B. On some results pertaining to halin graphs / S. B. Horton, R. Gary Parker // Congressus Numerantium 89(1992) pp Kaplan, Haim Physical Maps and Interval Sandwich Problem: Bounded Degrees Help"} / Haim Kaplan, Ron Shamir Diaz, Josep A survey of Graph Layer Problems / Josep Diaz, Jordi Petit, Maria Serna Yung-Ling, Lai On the Profile of the Tensor Product of a Path with a Complete Bipartite Graph 7 Тихон С.А. Магистерская работа 2012

Применение информационных технологий в исследовании рекурсивно- порождаемых классов, методов декомпозиции и решения дискретных задач Литература Horton, S.B. The Linear Arrangement Problem on Recursively Constructed Graphs / S.B. Horton, T. Easton, R. Gary Parker. // NETWORKS, Vol. 42(3) 2003, pp Garey, M.R. Some simplified NP-complete graph problems / M.R. Garey, D.S. Jonson, L. Stockmeyer // Theor Comput Sci 1(1976), pp Adolphson, D. Optimal linear ordering / D. Adolphson, T.C. Hu // SIAM J Appl Math 25 (1973), pp Frederickson, G.N. Planar linear arrangement of outerplanar graphs Diaz, Josep A survey of Graph Layer Problems / Josep Diaz, Jordi Petit, Maria Serna Horton, S.B. The Optimal Linear Arrangement problem: Algorithms and Approximation // Georgia Institute of Technology May 1997 Pan, Jun-Jie Path partition for graph with special blocks / Jun-Jie Pan, Gerard J. Chang // May 2004, NCTS/TPE-Math Technical Report Тихон С.А. Магистерская работа 2012

Применение информационных технологий в исследовании рекурсивно- порождаемых классов, методов декомпозиции и решения дискретных задач Спасибо за внимание! 9 Тихон С.А. Магистерская работа 2012

Применение информационных технологий в исследовании рекурсивно- порождаемых классов, методов декомпозиции и решения дискретных задач Оглавление Постановка задачи Объект и предмет исследования Методология исследования Результаты Положения, выносимые на защиту Литература Тихон С.А. Магистерская работа