Новости города БезФормата.Ru
Нижний Новгород
Главные новости
 
Задать вопрос?

Ученые ННГУ занимаются поиском быстрых алгоритмов дискретной оптимизации

Исследования поддержаны грантом РНФ

Учеными Университета Лобачевского под руководством ведущего научного сотрудника ИИТММ ННГУ, профессора Института математики Уорикского университета (Великобритания) Лозина Вадима Владиславовича реализуется научный проект «Алгоритмические, сложностные и структурные вопросы теории графов и дискретной оптимизации».

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

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

К задачам дискретной оптимизации относятся, например, задачи на графах. Графом в математике называют объект, состоящий из точек (называемых узлами или вершинами графа) и соединяющих некоторые из этих точек линий (называемых дугами или ребрами). Например, с помощью графа можно изобразить сеть дорог между городами. Тогда города будут представляться узлами графа, а дороги между ними ‒ дугами.

Графом можно изобразить компьютерную локальную сеть или даже всю всемирную сеть Интернет. Здесь узлами будут компьютеры, а соединены дугой будут только те узлы, для которых соединены соответствующие им компьютеры. Чтобы доставить сообщение от одного компьютера другому, требуется определить наикратчайший путь между ними.

С помощью графов можно изобразить социальные сети. Каждый узел будет соответствовать конкретному пользователю социальной сети, при этом два узла будут соединены дугой только в тех случаях, когда два человека дружат между собой. 

Удобным и достаточно универсальным языком, на котором удается описать задачи дискретной оптимизации (включая задачи на графах) является целочисленное линейное программирование.

За более чем полвека исследований для части задач дискретной оптимизации были найдены быстрые алгоритмы (т.е. алгоритмы, время работы которых ограничено полиномом от длины входной информации). К полиномиально разрешимым задачам относятся, например, задачи о кратчайшем пути в графе, о максимальном потоке, о наибольшем паросочетании и многие др.

Для другой большой части задач быстрых алгоритмов найдено не было. Все усовершенствования алгоритмов для таких трудноразрешимых, «неподдающихся» задач мало чем отличаются от прямого перебора, несмотря на усилия тысяч специалистов. К неподдающимся относятся, например, задачи о клике, о минимальном покрытии, о максимальном независимом множестве и многие др.

Тем не менее, остается открытым вопрос: «а существуют ли в принципе быстрые алгоритмы для «неподдающихся» задач или такие эффективные алгоритмы пока еще не найдены?» Большинство специалистов склоняется к мнению, что таковых алгоритмов для большинства неподдающихся задач не существует, поэтому их никто никогда не сможет найти. Если будет доказана известнейшая гипотеза «P ≠ NP», то это будет означать, что это действительно так.

Проблема «P = NP?» была сформулирована в 1971 г. С.Куком, но до сих пор никто не доказал P = NP или P ≠ NP. Это одна из самых главных открытых проблем в теоретической информатике. Математический институт Клэя в 2000 г. назвал ее первой среди семи нерешенных важнейших «Задач тысячелетия». 

Проблема построения полиномиальных алгоритмов и проблема изучения границы эффективной разрешимости порождают ряд сложных математических задач, над которыми трудится коллектив исследователей ННГУ. 

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

Rian 2901775.hr .ru - NewsNN.RuВ ближайшее время все вертолеты линейки Ми-8 будут оборудованы новым вертолетным навигационным комплексом БФНИ-1.
24.11.2017 NewsNN.Ru
Увеличить - ТПП Нижегородской области23 ноября 2017 года в рамках Школы высоких технологий «INDICUM» на базе ТПП НО прошло первое занятие образовательного курса для менеджеров «Блокчейн: новая парадигма экономики и управления».
24.11.2017 ТПП Нижегородской области
0d8e95022e81115586dc41ed7be77261 - NewsNN.RuФото: udmurt.media В Липецке более 20 школьников попали в больницу из-за мобильного приложения с ультразвуком.
24.11.2017 NewsNN.Ru
8139b13000fe432f2962a18a36c8649e - NewNN.RuДвадцать четвертого ноября текущего года на заседании Пермской ассоциации радио и телевидения выбрали нового руководителя данной организации.
24.11.2017 NewNN.Ru
Итоги дня: Никитин на открытии суда, штаб Собчак и жители аварийного дома - NewsNN.RuNewsNN подводит информационные итоги дня, напоминая о наиболее значимых и резонансных событиях, которые освещались в новостях издания.
24.11.2017 NewsNN.Ru
Фото: АПЗ Депутат Заксобрания Нижегородской области, генеральный директор АО "АПЗ" Олег Лавричев оказал помощь Арзамасскому родильному дому в обновлении пожарной сигнализации.
24.11.2017 НИА Нижний Новгород
Поножовщина 2 - NewNN.RuВ Лукояновском районе Нижегородской области 41-летний пьяный мужчина во время ссоры ранил свою сожительницу ножом.
24.11.2017 NewNN.Ru
Ребра - NewNN.RuВ Ульяновске суд приговорил 37-летнего мужчину к трем годам тюрьмы за то, что он переломал ребра знакомому, приревновав его к своей сожительнице.
24.11.2017 NewNN.Ru
Кража денег из дома - NewNN.RuВ Нижнем Новгороде сотрудники полиции задержали 30-летнего рецидивиста, который похитил из чужого дома 20 тысяч рублей.
24.11.2017 NewNN.Ru
Уроки для садовника - Нижегородские новости
Уроки для садовника
Помните эту детскую игру-считалочку: «Я садовником родился, не на шутку рассердился, все цветы мне надоели…»?
Нижегородские новости
В Нижнем Новгороде задержана искусавшая полицейского нетрезвая женщина. - АиФ Н.Новгород
В Нижнем Новгороде задержана искусавшая полицейского нетрезвая женщина
Хулиганке грозит до пяти лет тюрьмы В Нижнем Новгороде задержана искусавшая полицейского нетрезвая женщина.
АиФ Н.Новгород
Грабителя ищут
На днях средь бела дня неизвестный вырвал сумку у пенсионерки. Об этом сообщается в сообществе «Криминальные вести Дзержинска» в социальной сети «ВКонтакте».
Дзержинское время
Куда сходить в выходные? - Саров24Самые интересные и зрелищные события, которые пройдут в Сарове в выходные, 25 и 26 ноября, в нашей традиционной подборке.
25.11.2017 Саров24
30 ноября в 16.00 в концертном зале Детской школы искусств (г. Выкса, ул.
24.11.2017 Красные зори
3 декабря в 14.00 в библиотеке «Отчий край» (г. Выкса, мкр. Гоголя, д. 50) ЛИТО «Слово» проводит открытое заседание «Слово - ключи, что открывают душу».
24.11.2017 Красные зори
Поэт с душой ребенка - Репортер и время
Поэт с душой ребенка
Детская поэтесса Анна Бочковская приезжала в Дзержинск на встречу с библиотекарями и школьниками.
Репортер и время
Там, где жил, творил и любил Алексей Максимович - Нижегородские новости
Там, где жил, творил и любил Алексей Максимович
Горьковских мест в Нижнем Новгороде и Нижегородской области невероятно много - притом что Горький провел здесь, за вычетом поездок и странствий, менее тридцати лет.
Нижегородские новости
Никита МИХАЛКОВ: «Воспитание актеров - это штучная, тактильная работа» - Нижегородские новости
Никита МИХАЛКОВ: «Воспитание актеров - это штучная, тактильная работа»
Большинству киноманов Никита Михалков известен как ярчайший актер и режиссер-«монументалист».
Нижегородские новости
DSC02072 - МЧС Нижегородской областиВ г.Саров завершились двухнедельные соревнования по волейболу, посвященные памяти начальника инспекции пожарной части №4 Степанова Олега Гурьевича.
25.11.2017 МЧС Нижегородской области
Денис Котков – в расширенном списке сборной России - ХК СтартТренерский штаб национальной сборной России назвал состав команды для участия в международном «Турнире четырех наций», который с 8 по 10 декабря состоится в шведском Сёдерхамне.
24.11.2017 ХК Старт
В Дзержинске завершается молодежная спартакиада - Дзержинск.рфГородская спартакиада молодежи завершается в Дзержинске. 25 ноября состоится 5 этап соревнований – турнир по настольному теннису.
25.11.2017 Дзержинск.рф
Первые награды юных футболистов «Виктории» - Дзержинское время
Успехи юных
  Весьма продуктивным оказалось начало сезона для молодых дзержинских мини-футболистов.
Дзержинское время
Борис МАРТЫНОВ: «Я старался оградить ребят от дурных привычек» - Нижегородские новости
Борис МАРТЫНОВ: «Я старался оградить ребят от дурных привычек»
«Когда мне исполнилось восемь лет, в городской магазин завезли настоящие лыжи, всего две пары, и обе эти пары купила моя мама - мне и брату.
Нижегородские новости
Кубок у казанцев
В дзержинском плавательном бассейне СДЮСШОР «Заря» прошло открытое первенство Нижегородской области по водному поло с розыгрышем Кубка памяти Анатолия Голованова.
Дзержинское время
Самый первый дом - Администрация города АрзамасСамый первый дом Депутат Законодательного собрания Нижегородской области, генеральный директор АО «АПЗ» Олег Лавричев оказал помощь Арзамасскому родильному дому,
24.11.2017 Администрация города Арзамас
Администрация Нижнего Новгорода готовит документацию для строительства дороги за "Теплообменником" в обход кольца на "Пролетарской" - НТА-ПриволжьеНижний Новгород. 21 ноября. НТА-Приволжье — Администрация Нижнего Новгорода начала подготовку документации для строительства дороги за ПАО "Теплообменник" в обход кольцевого движения на "Пролетарской".
21.11.2017 НТА-Приволжье
%d0%b4%d0%be%d1%80%d0%be%d0%b3%d0%b0 - NewsNN.RuФото: i.artfile.me Нижегородское ГУ МЧС для обмена информацией с водителями-дальнобойщиками наладило канал радиосвязи.
23.11.2017 NewsNN.Ru
Открытие центра развития медицинского приборостроения в регионе — это событие на карте инновационного развития страны в целом — Никитин - Время НГлеб Никитин Врио губернатора Нижегородской области Торжественное открытие Центра инновационного развития медицинского приборостроения состоялось в Нижегородской области в пятницу, 24 ноября.
24.11.2017 Время Н
Отреставрированное здание суда Автозаводского района откроется 24 ноября - Время НГлеб Никитин Врио губернатора Нижегородской области Здание суда Автозаводского района Нижнего Новгорода откроется после реконструкции 24 ноября.
24.11.2017 Время Н