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

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

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

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

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

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

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

7 Применение информационных технологий в исследовании рекурсивно- порождаемых классов, методов декомпозиции и решения дискретных задач Литература 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

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

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