БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТВыпускная работа по«Основам информационных технологий» Магистранткафедры УМФ Петрович Роман Александрович Руководители: профессор, доктор физико-математических наук Тышкевич Регина Иосифовна, доцент Кожич Павел ПавловичМинск – 2009 г. Оглавление Оглавление 3Список обозначений ко всей выпускной работе 4Реферат на тему «Применение информационный технологий в теории графов». 5 Введение 5 Глава 1. Некоторые сведения из теории алгоритмов 6^ Глава 2. Элементы теории сложности 10 Глава 3. Теория сложности в магистерской диссертации 10 Глава 4. Обзор применения ИТ в теории графов 11 Глава 5. Обзор библиотеки JGraphT. 12^ Глава 6. Обзор библиотеки JGraph. 15 Заключение 19 Список литературы к реферату 21Предметный указатель к реферату 22Интернет ресурсы в предметной области исследования 23Действующий личный сайт в WWW 24Граф научных интересов. 25Презентация магистерской диссертации. 31 Список литературы к выпускной работе. 34Приложения 35Приложение1. Список вопросов для теста по ИТ. 35 ^ Список обозначений ко всей выпускной работе ИТ – информационные технологии.ЭВМ – электронно-вычислительная машина. Реферат на тему «Применение информационный технологий в теории графов». Введение Рассматриваемый реферат посвящен применению информационных технологий в теории графов. В наше время теория графов приобретает все возрастающий интерес у специалистов самых различных областей науки и техники. Эта привлекательность объясняется не только очень широким разнообразием возможностей ее применения, но и красотой результатов, достигаемых простыми средствами. Известно, что само появление теории графов восходит к началу XVIII века к задаче «О Кёнигсбергских мостах». Эта задача была решена великим математиком того времени Леонардом Эйлером. В современной математике его результат известен как «Лемма о рукопожатиях». Следующий раз про теорию графов «вспомнили» лишь в начале XX века, найдя ее применение в химии (описание строений соединений углеродов), физике (электрические цепи) и конечно же в самой математике. Действительно, в рамках теории графов имеется множество различных направлений; результаты ее формулируются с привлечением понятий теории множеств, топологии, алгебры, но в тоже время методы теории графов нельзя рассматривать как простую совокупность методов этих разделов математики.Теория графов и гиперграфов является эффективным аппаратом формализации современных инженерных и научных задач, как уже сказано, в различных областях знаний. Язык теории графов удобен при проведении системных исследований, описании организации генетических систем. В последнее время большое применение нашла теория графов в современной вычислительной технике и кибернетике: в теоретическом программировании, при проектировании на ЭВМ и сетей ЭВМ, баз данных, систем логического управления [1].^ Глава 1. Некоторые сведения из теории алгоритмов Особый интерес для практики и приложений представляют алгоритмические аспекты задач на графах. На практике важно уметь с помощью ЭВМ находить в графе наибольшее паросочетание и наибольшее независимое множество, строить гамильтонов цикл или гамильтонову цепь, выделять связные или двусвязные компоненты и т. п. Иначе говоря, надо иметь соответствующие алгоритмы, а в конечном счете и программы для ЭВМ. К примеру, связные и двусвязные компоненты применяются при проектировании компьютерных сетей, обеспечивающих высокую степень надежности. Графы в таких задачах – это огромная (сотни и тысячи вершин) структура, поэтому очень важно использовать оптимальные способы хранения данных и оптимальные алгоритмы их обработки.Нетрудно для каждой из упомянутых выше задач разработать алгоритм, реализующий перебор всех возможных вариантов. Такой подход, однако, неприемлем из-за чрезвычайно большого числа этих вариантов. Поэтому нужен не просто алгоритм, а алгоритм, эффективный, причем эффективность алгоритма очень важно уметь оценивать apriori.Для этой цели служит анализ алгоритма. При анализе алгоритма решения какой-либо задачи нас в первую очередь будет интересовать его трудоемкость, под которой мы понимаем время выполнения соответствующей программы па ЭВМ. Ясно, что этот показатель существенно зависит от типа используемой ЭВМ. Для того, чтобы сделать рассуждения о трудоемкости алгоритмов в достаточной мере универсальными, считается, что все вычисления производятся на некой абстрактной вычислительной машине. Такая машина в состоянии выполнять арифметические операции, сравнения, пересылки и операции условной и безусловной передач управления. Эти операции считаются элементарными. Каждая из элементарных операции выполняется за единицу времени и, следовательно, время работы алгоритма равно числу выполненных им элементарных операций. Память абстрактной вычислительной машины состоит из неограниченного числа ячеек, имеющих адреса 1, 2, 3, ..., n. Причем, ко всем ячейкам памяти этой машины есть прямой доступ.При анализе алгоритмов наибольший интерес представляет зависимость времени работы алгоритма от числа вершин и (или) ребер графа. Cчитается, что любое число, независимо от его величины, можно разместить в одной ячейке памяти и каждая ячейка может содержать только одно число. Рассмотрим теперь представление информации в памяти машины. Всякая конечная последовательность элементов произвольной природы называется списком, а число элементов списка — его длиной. Элементами этого списка могут быть числа, буквы алфавита, векторы, матрицы и т. п. В той ситуации, когда, каждый элемент списка помещается в одной ячейке, этот список будем размещать в n последовательных ячейках памяти, где n — длина списка. Такое представление списка обычно называется последовательным, и далее используется только это представление.Пусть А =||Ai,j|| — матрица порядка n.A*=(A11, A12, …, A1n, A21, A22,…, A2n, …, An1, An2,…, Ann) — список ее элементов по строкам. Принцип «одно число — одна ячейка» означает, что матрица порядка n занимает n2 ячеек памяти.Рассмотрим теперь представление графа G в памяти машины. Пусть VG={v1,v2,…,vn}. Будем пользоваться тремя способами представления.Первый — задание графа матрицей смежности. Если граф взвешенный и w(x, у) обозначает вес ребра xу, то вместо матрицы смежности используется матрица весов W(G)=W. У этой матрицы Wij=w(vi, vj), если vi,vjEG. Если же vivj не является ребром графа G, то полагаем Wij=0 или Wij=∞ — в зависимости от задачи, которую предстоит решить. Из сказанного выше о представлении матрицы в машине следует, что такой способ задания графа требует |G|2 ячеек памяти. Стоит отметить, что в рассматриваемом примере весами ребер могут быть любые вещественные числа.Второй способ — задание графа списком ребер VE={e1,e2,…,em}, где m=|EG|, eiEG. Поскольку ребро графа можно хранить, используя две ячейки (по одной на каждую концевую вершину), то для хранения всего списка Е достаточно 2т ячеек. Если граф взвешенный, то под каждый элемент списка Е можно отвести три ячейки — две для ребра и одну для его веса, т. е. всего потребуется Зm ячеек.И, наконец, последний способ, который будет использоваться, — представление графа списками смежности. При таком способе каждой вершине vi, ставится в соответствие список Nvi вершин, смежных с vi. Под этот список достаточно отвести deg(vi)+1 ячеек — по одной на каждый элемент и одну ячейку для обозначения конца списка. Кроме того, формируется список N={N1,N2,…,Nm}, где Ni, — номер ячейки, в которой хранится первый элемент списка Nvi. Следовательно, такой способпредставления графа требует ячеек памяти. Если граф ^ G взвешенный, то дли каждой вершины vj, списка Nvi отводится дополнительно одна ячейка, содержащая число w(vi, vj).Хотя представление графа списком ребер является наиболее экономным «по памяти», оно имеет существенный недостаток. Чтобы определить, содержит ли граф данное ребро, надо просматривать поочередно элементы этого списка, а это может потребовать около 2т элементарных операций. Если же граф задан списками смежности, вычислительные затраты составят не более n+1 таких операций. Представление графа матрицей смежности, требующее наибольших затрат памяти, обеспечивает «прямой доступ» к ребрам графа. Узнать, содержит ли граф ребро vivj можно, вычислив адрес k = in + j и сравнив М(k) c нулем, где М — массив, в котором построчно размещена матрица смежности графа.Выбор того или иного задания графа зависит от конкретной задачи, которую предстоит решать.Стандартным подходом является то, что во всех рассматриваемых задачах главной частью исходной информации служит граф. Кроме этого, исходные данные могут включить номера одной или нескольких выделенных вершин. Если, например, задача состоит в отыскании цепи, соединяющей две заданные вершины графа, то помимо графа необходимо задать номера этих двух вершин.После того как ко всем исходным данным задачи присвоены конкретные значения, они размещены в памяти ЭВМ, они называются входом задачи. Размером (или длиною) входа считается число ячеек, занятых входом.При анализе алгоритма решения любой задачи математика в первую очередь интересует зависимость времени его работы от размера задачи, т. е. от размера входа. Однако, это время зависит не только от размера входа, но и от других параметров задачи, т. е. время работы алгоритма на входах одинаковой длины может быть не одинаковым. Поясним сказанное на простейшем примере. Пусть элементами списка S={S1,S2,…,Sm} являются натуральные числа и требуется определить, содержит ли список S число, кратное трем. Очевидный алгоритм решения этой простой задачи состоит в следующем: проверяем поочередно делимость элементов списка S на 3 до тех пор, пока не встретится число кратное трем, или же не будут проверены все элементы S. Время выполнения р таких проверок равно t = 2р (р делений и р изменений адреса). Следовательно, при неизменной длине входа т время работы алгоритма будет изменяться в пределах 2t 2т в зависимости от расположения подходящего элемента s в списке S. Наихудшим будет случай, когда S не содержит чисел, кратных трем, либо когда Sm — единственное такое число. Один из основных подходов к определению понятия «трудоемкость алгоритма» ориентируется именно на такого рода наихудший случай [1].^ Глава 2. Элементы теории сложности Трудоемкость (или сложность) алгоритма решения данной задачи определяетcя как функция f, ставящая в соответствие каждому натуральному числу п время работы f(n) алгоритма в худшем случае на входах длины n. Иначе говоря, f(n) —максимальное время работы алгоритма по всем входам данной задачи длины п. Анализ эффективности алгоритмов заключается в выяснении вопроса: как быстро растет функция f(n) с ростом n? При ответе на этот вопрос обычно используют O-символику.Говорят, что неотрицательная функция f(n) не превосходит по порядку функцию g(n), если существует такая константа с, что f(n) 0; при этом пишут f(n) = O(g(n)). Выражению «трудоемкость (сложность) алгоритма есть O(g(n)) придается именно этот смысл. В частности, трудоемкость O(i) означает, что время работы соответствующего алгоритма не зависит от длины входа. Алгоритм с трудоемкостью О(п), где n — длина входа, называют линейным. Линейный алгоритм ограниченное константой чиcло раз просматривает входную информацию и для подавляющего большинства «естественных» задач является неулучшаемым в смысле трудоемкости. Поэтому отыскание линейного алгоритма для некоторой задачи часто является своего рода «последней точкой» в ее алгоритмическом решении.Алгоритм, сложность которого равна О(пс), где с — константа, называется полиномиальным. В большинстве случаев эта степень не превосходит трех и оценка сложности алгоритма, как правило, имеет один из следующих видов: O(n3), O(n2), O(n), O(n log n). [1]^ Глава 3. Теория сложности в магистерской диссертации Одним из подходов к анализу NP-трудных задач, т.е. таких, про которые известно, что для их точного решения не существует полиномиальных алгоритмов, является наложение ограничений на вход исходной задачи и переход к рассмотрению возникающих при этом подзадач. В этом случае часто возникает пограничная область, отделяющая NP-полные подзадачи от полиномиально разрешимых и включающая те подзадачи, сложность которых неизвестна. Естественной целью является максимально возможное сужение этой области. Особых интерес представляют такие ограничения, при которых пограничная область отсутствует. Например, известно, что задача «k-раскраска» решается за полиномиальное время при k2 и NP-полна при k3. Еще более интересны ограничения, отражающие внутреннюю структуру подаваемых на вход объектов. Так, для задачи 3-раскраска, известно, что она полиномиально разрешима в классе графов G с максимальной степенью вершин (G)3 и является NP-полной при (G)4. В действительности, в приведеных примерах утверждения о полиномиальной распознаваемости тривиальны. В магистерской диссертации исследуется нетривиальный пример такого рода. Исследуется NP-полная задача распознавания принадлежности графа G классу Ll3графов пересечений ребер линейных 3-униформных гиперграфов. Для нее существует порог полиномиальной разрешимости, связанный с минимальной степенью вершин (G) тестируемого графа G. А именно, существует такое натуральное число *, что задача GLl3 (1) полиномиально разрешима в классе графов G с (G) * и NP-полна при (G)*. В настоящее время существует довольно узкая оценка для числа *: 6*10. А также существует линейный алгоритм, решающий задачу проверки графа на алгоритм, который решает данную задачу в классе графов с (G) 10 [2].Задачей, поставленной в магистерской диссертации, является по возможности уменьшение оценки (G) за счет сужения рассматриваемых классов графов. ^ Глава 4. Обзор применения ИТ в теории графов Применение информационных технологий в теории графов можно разделить по следующим группам.Программы, служащие для набора научных статей по теории графов (например, Microsoft Word, TeX).Программы для изображения графов в удобном виде (например, использование автофигур в Microsoft PowerPoint, либо стандартного набора специальных изображений в Microsoft Visio).Программы для подготовки иллюстраций научных статей (например, Adobe Photoshop, Corel Draw).Специальные библиотеки в языках программирования. Начиная от единиц, предоставляющий графический интерфейс пользователю, до сложных библиотек используемых в при реализации алгоритмов в коммерческих приложениях (например, JGraph и JGraphT в Java). Такого рода библиотеки содержат минимально необходимые сущности, например «граф», «ребро», «бинарное дерево», а также стандартный набор алгоритмов: «поиск в ширину», «поиск в глубину», проверка связности графа, бинарный поиск и многое другое, что позволяет прикладному алгоритмисту абстрагироваться от несущественной детализации и перейти непосредственно к реализации алгоритма.Поиск информации в сети Internet.Отметим, что одним из наиболее важных моментов применения ИТ в теории графов является поиск информации. Зачастую бывает очень трудно найти печатный вариант необходимой книги. С помощью глобальной сети Internet эта проблема решается, появляется возможность искать книги и научные статьи по необходимой тематике.А сейчас остановимся более подробно на использовании библиотек JGraphT и JGraph.^ Глава 5. Обзор библиотеки JGraphT. Сайт производителя этой библиотеки: http://www.jgraph.com/jgraph.html. JGraphT – это open source Java библиотека, которая содержит огромное количество объектов из теории графов и не меньшее количество стандартных алгоритмов. JGraph поддерживает работу со следующими типами графов.Ориентированные и неориентированные графы.Графы с помеченными и непомеченными ребрами.Простые графы, мультиграфы, псевдографы.Несмотря на всю мощь этой библиотеки, она довольно проста в использовании. С помощью JGraphT можно хранить в памяти компьютера объекты многих сложных типов. Для создания графа программист может использовать большой набор функций. Также предусмотрена возможность экспорта созданных объектов в XML-документ и наоборот, создания объектов из специальных XML-документов. Эта библиотека содержит в себе следующий набор пакетов. org.jgrapht «Стартовая точка» пользовательского приложения. Пакет содержит в себе такой наборы сущностей, как Graph, DirectedGraph, Multigraph, Pseudograph, UndirectedGraph. org.jgrapht.alg Содержит стандартный набор алгоритмов JGraphT. org.jgrapht.alg.util Набор утилит для использования в алгоритмах. org.jgrapht.demo Демонстрационные программы для быстрого ознакомления с «мощью» архива JGraphT. org.jgrapht.event Обработчики событий. org.jgrapht.ext Средства расширения и совместимости с другими продуктами. org.jgrapht.generate Конструкторы графов с различной структурой, например, можно создать полный случайный граф, полный двудольный, «колесо», и т.д. org.jgrapht.graph Имплементация различных графов. org.jgrapht.traverse Средства обхода графов. org.jgrapht.util Набор структур данных, алгоритмов и утилит, не специфичных для теории графов, но используемых в библиотеке JGraphT. Основными достоинствами библиотеки JGraphT являются то, что она:оптимизирована для моделей данных и алгоритмов;разработана для использования в высокопроизводительных приложениях;может работать с графами содержащими миллионы вершин и ребер;может обеспечивать графическую визуализацию данных с помощью библиотеки JGraph.Рассмотрим, к примеру, пакет org.jgrapht.alg. Этот пакет интересен тем, что в нем содержится реализация многих стандартных алгоритмов из теории графов. Пакет содержит в себе следующий набор классов: BellmanFordShortestPath Класс, реализующий алгоритм Беллмана-Форда. BiconnectivityInspector Класс, предназначенный для проверки графа на двусвязность. BlockCutpointGraph Класс, являющийся двумя сущностями: «блок» и «точка сочленения»ю BronKerboschCliqueFinder Класс, содержащий реализацию алгоритма Брона-Кербоша поиска клик в графе. ChromaticNumber Класс для приближенного поиска хроматического числа графа. ConnectivityInspector Класс, работающий с сущностью «связный граф».Обеспечивается проверка на связность, поиск вершин и ребер по определенным условиям и многое другое. CycleDetector Класс, реализующий поиск циклов в графе. DijkstraShortestPath Класс, содержащий реализацию алгоритма Дейкстры для поиска кратчайшего пути между вершинами. DirectedNeighborIndex Класс, предназначенный для поиска окружения произвольной вершины в графе. EdmondsKarpMaximumFlow Класс, реализующий сущность «поток в сети». EulerianCircuit Класс, содержащий алгоритм поиска эйлерова пути. FloydWarshallShortestPaths Класс, реализующий алгоритм Флойда для поиска кратчайших путей между всеми вершинами графа. HamiltonianCycle Класс, содержащий реализацию алгоритма поиска гамильтонова пути в графе. VertexCovers Класс, содержащий реализацию алгоритма поиска вершинного покрытия в графе. Из рассмотренного примера видно, насколько большой функционал у библиотеки JGraphT и насколько сильно он облегчает работу алгоритмиста.Документация по JGraphT содержится по адресу: http://www.jgrapht.org/javadoc.^ Глава 6. Обзор библиотеки JGraph. Что же касается библиотеки JGraph, то она в свою очередь:является swing-компонентом для построения графического интерфейса пользователя;содержит более сложное API, чем JGraphT, и поэтому для ее правильного и эффективного использования необходимо изучить предоставляемую документацию;производительность кода, написанного с использованием JGraph, является менее быстрой, чем JGraphT, и поэтому эта библиотека более требовательна к ресурсам.Следующий адрес http://jgrapht.sourceforge.net/visualizations.html содержит пример работы библиотеки JGraph.Рисунок 1.На рисунке 1 мы видим граф на четырех вершинах v1, v2, v3, v4, содержащий ребра v1v2, v2v3, v3v1, v4v3. Этот написанный на языке Java апплет поддерживает пользовательский интерфейс типа drag and drop, благодаря чему пользователь может упорядочить вершины графа по своему усмотрению:Рисунок 2Ниже приведен исходный код рассмотренной выше программы на языке Java. package org.jgrapht.demo;import java.awt.Color; import java.awt.Dimension; import java.awt.Rectangle;import java.util.HashMap; import java.util.Map;import javax.swing.JApplet; import javax.swing.JFrame;import org.jgraph.JGraph; import org.jgraph.graph.DefaultGraphCell; import org.jgraph.graph.GraphConstants;import org.jgrapht.ListenableGraph; import org.jgrapht.ext.JGraphModelAdapter; import org.jgrapht.graph.ListenableDirectedGraph; import org.jgrapht.graph.DefaultEdge;public class JGraphAdapterDemo extends JApplet {private static final Color DEFAULT_BG_COLOR = Color.decode( "#FAFBFF" ); private static final Dimension DEFAULT_SIZE = new Dimension( 530, 320 );// private JGraphModelAdapter m_jgAdapter;/*** @see java.applet.Applet#init().*/ public void init( ) {// create a JGraphT graph ListenableGraph g = new ListenableDirectedGraph( DefaultEdge.class );// create a visualization using JGraph, via an adapter m_jgAdapter = new JGraphModelAdapter( g );JGraph jgraph = new JGraph( m_jgAdapter );adjustDisplaySettings( jgraph ); getContentPane( ).add( jgraph ); resize( DEFAULT_SIZE );// add some sample data (graph manipulated via JGraphT) g.addVertex( "v1" ); g.addVertex( "v2" ); g.addVertex( "v3" ); g.addVertex( "v4" );g.addEdge( "v1", "v2" ); g.addEdge( "v2", "v3" ); g.addEdge( "v3", "v1" ); g.addEdge( "v4", "v3" );// position vertices nicely within JGraph component positionVertexAt( "v1", 130, 40 ); positionVertexAt( "v2", 60, 200 ); positionVertexAt( "v3", 310, 230 ); positionVertexAt( "v4", 380, 70 );// that's all there is to it!... }private void adjustDisplaySettings( JGraph jg ) { jg.setPreferredSize( DEFAULT_SIZE );Color c = DEFAULT_BG_COLOR; String colorStr = null;try { colorStr = getParameter( "bgcolor" ); } catch( Exception e ) {}if( colorStr != null ) { c = Color.decode( colorStr ); }jg.setBackground( c ); }private void positionVertexAt( Object vertex, int x, int y ) { DefaultGraphCell cell = m_jgAdapter.getVertexCell( vertex ); Map attr = cell.getAttributes( ); Rectangle b = GraphConstants.getBounds( attr );GraphConstants.setBounds( attr, new Rectangle( x, y, b.width, b.height ) );Map cellAttr = new HashMap( ); cellAttr.put( cell, attr ); m_jgAdapter.edit( cellAttr ); } } Заключение Из всего выше сказанного следует, что «информационный бум» оставил свой след во многих сферах человеческой жизни. С появлением компьютерных технологий стало возможно решать такие математические задачи, за которые раньше учёные не могли даже взяться именно из-за большой вычислительной сложности таких задач. Да что и говорить, само бурное развитие теории графов во многом обязано именно появлению вычислительных машин. И наоборот, во многом благодаря теории графов стал возможен такой большой скачок в их производительности.Как известно, немаловажным понятием теории графов является понятие алгоритма. Практическое применение алгоритмов связано именно с использованием ЭВМ.Основной целью этой работы являлось применение информационных технологий в теории графов. И это применение, поистине, безгранично. Начиная с текстовых редакторов, редакторов изображений и заканчивая огромным количеством всевозможных библиотек в языках программирования.^ Список литературы к реферату Лекции по теории графов / В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич. – М.; Наука, 1990. 384 c.Перез-Чернов А.Х., Тышкевич Р.И. К проблеме распознавания реберных графов линейных 3-униформных гиперграфов: предбольшие клики // Труды института математики. 2007. Т.15. № 2. С 78-89.Скумс П.В, Суздаль С.В., Тышкевич Р.И. О пороге полиномиальной разрешимости для задачи распознавания графов пересечений ребер линейных 3-униформных гиперграфов // Докл. НАН Беларуси. 2004. Т.48. № 4. С.29-34.^ Предметный указатель к реферату Adobe Photoshop 12Corel Draw 12Internet 12, 24JGraph 12, 13, 14, 15, 16, 17, 18JGraphT 12, 13, 14, 15, 18Microsoft PowerPoint 12Microsoft Visio 12Microsoft Word 12NP-полная задача 11NP-трудная задача 10O-символика 10TeX 12абстрактная вычислительная машина 7вход задачи 9граф взвешенный 7, 8длина списка 7задача \«k-раскраска\» 11задача \«О Кёнигсбергских мостах\» 5задача 3-раскраска 11Лемма 5линейный алгоритм 10матрица весов 7матрица смежности 7, 8полиномиальный алгоритм 10последовательное представление списка 7сложность 10, 11список 7список ребер 8список смежности 8трудоемкость 10ЭВМ 5, 6, 9элементарная операция 6^ Интернет ресурсы в предметной области исследования http://www.jgraph.com – официальный сайт проекта JGraph.http://arxiv.org – сервис для поиска статей по математике, компьютерным наукам, физике, биологии, статистике. http://poiskknig.ru - поисковая машина электронных книг, свободно распространяемых в интернете. Главным приоритетом является образовательная литература, являющаяся базисом научного и технического знания. http://lib.org.by – библиотека научной литературы по математике, компьютерным наукам, физике, инженерным наукам.http://exponenta.ru – образовательный сайт по математике.http://www.vak.org.by/ – сайт Высшей аттестационной комиссии Республики Беларусь. ^ Действующий личный сайт в WWW Ссылка на мой личный сайт в сети Internet: http://raman-piatrovich.narod.ru. Граф научных интересов. магистранта Петровича Р.А.Механико-математический факультет.Специальность: 01.01.09 – дискретная математика и математическая кибернетика Смежные специальности 01.01.01 – математический анализ Теория функций действительного и комплексного переменного, обобщенные функции. Специальные функции и интегральные преобразования. Выпуклый, негладкий и многозначный анализ. Теория приближений и методы численного анализа. Вариационное исчисление и общая теория экстремальных задач. Гармонический анализ. Абстрактные и функциональные пространства, наделенные алгебраическими, топологическими, метрическими, порядковыми и др. структурами. Измеримые пространства. Линейные и нелинейные операторы и специальные классы (дифференциальные, интегральные, интегро-дифференциальные, разностные и др.) таких операторов. Методы исследования абстрактных операторных уравнений, а также методы исследования дифференциальных, интегральных, интегро-дифференциальных, разностных и др. конкретных операторных уравнений. Анализ на многообразиях, p-адический анализ, нестандартный анализ, различные направления конструктивного анализа, интервальный анализ, анализ в упорядоченных пространствах. 01.01.02 – дифференциальные уравнения Развитие теории обыкновенных дифференциальных уравнений и уравнений в частных производных, интегральных, интегро-дифференциальных, функционально-дифференциальных, дифференциально-операторных уравнений и дифференциальных уравнений со случайными параметрами. Обоснование численных методов решения дифференциальных, интегральных, интегро-дифференциальных, функционально-дифференциальных и дифференциально-операторных уравнений. Разработка методов дифференциальных уравнений для решения задач механики, математической физики и других прикладных наук. 01.01.05 – теория вероятностей и математическая статистика Вероятностные пространства и случайные элементы. Предельные теоремы. Случайные процессы и поля. Стохастический анализ и стохастические дифференциальные уравнения. Случайные процессы специального вида, включая процессы массового обслуживания. Статистические выводы и анализ данных. Последовательный анализ. Непараметрическая и робастная статистика. Статистика случайных процессов, полей и временных рядов. Вероятностно-статистическое моделирование. 01.01.07 – вычислительная математика Теория приближенных методов и численных алгоритмов решения задач алгебры, дифференциальных и интегральных уравнений, задач дискретной математики, экстремальных задач, задач управления, некорректных задач других задач линейного, нелинейного и стохастического анализа. Теория и методы параллельных вычислений. Численные методы и алгоритмы решения прикладных задач, возникающих при математическом моделировании естественнонаучных, научно-технических, социальных и других проблем. Основная специальность 01.01.09 – дискретная математика и математическая кибернетика Теория функциональных систем, теория графов и комбинаторный анализ, теория сложности вычислений, теория кодирования и криптология, теория расписаний, теория очередей и массового обслуживания, комбинаторная вычислительная геометрия. Теория и методы минимизации функций; общая теория экстремальных задач; теория многокритериальной и векторной оптимизации; теория и методы решения задач математического программирования, включая задачи стохастического программирования и задачи в условиях неопределенности; дискретная оптимизация; теория устойчивости и чувствительности задач оптимизации; негладкий и многозначный анализ; негладкие задачи оптимизации; методы и алгоритмы решения экстремальных задач. Вариационное исчисление, идентификация, наблюдение, управление и стабилизация динамических систем; методы оптимального управления, наблюдения и идентификации; оптимизация динамических систем в условиях неопределенности, р