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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Форум молодых лидеров Евразии - Семеновский район«Форум молодых лидеров – отличный формат для выстраивания конструктивных доброжелательных отношений между представителями молодежных элит разных стран» - Артем Кавинов Депутат Госдумы от партии Единая Россия,
22.09.2017 Семеновский район
JPG Файл - ГУ МВД Нижегородской областиВ рамках мероприятия к полицейским обратилось 33 жителя Сергачского района с вопросами о порядке получения госуслуг по линии ГИБДД, ИЦ и миграции.
22.09.2017 ГУ МВД Нижегородской области
В сентябре 2017 года председателем Общественного совета при Отделе МВД России по г. Бор Владимиром Веселовым был проведен опрос граждан на предмет удовлетворенности заявителей качеством государственных услуг,
22.09.2017 ГУ МВД Нижегородской области
  На днях читатели «ДВ» рассказали нам очередную историю о предприимчивых продавцах, пытающихся всеми правдами и неправдами навязать одиноким пенсионерам дорогущие фильтры для очистки воды.
22.09.2017 Дзержинское время
fbd68b60-9eb8-11e7-9607-93504d750448 - NewNN.RuНа улице Григорьева в городе Кемерово заработал светофор вызывного типа. Об этом сообщили местные средства массовой информации.
22.09.2017 NewNN.Ru
Почти 85 тысяч показаний электросчетчиков было принято за месяц по телефону единого контактного центра ПАО "ТНС Энерго НН".
22.09.2017 НИА Нижний Новгород
Адвокаты экс-мэра Дзержинска Виктора Портнова обжаловали постановление суда о продлении срока домашнего ареста - НТА-ПриволжьеНижний Новгород. 21 сентября. НТА-Приволжье — Адвокаты экс-мэра Дзержинска Нижегородской области Виктора Портнова обжаловали постановление суда о продлении срока домашнего ареста,
21.09.2017 НТА-Приволжье
Экологический вандализм - Wyksa.Ru21 сентября 2017 г. эта тема стала поводом пресс-тура с участием начальника управления ГО и ЧС администрации округа Игоря Шолохова.
22.09.2017 Wyksa.Ru
Государственная инспекция труда в Нижегородской области расследует тяжелый несчастный случай с 32-летним электросварщиком ООО "Строительная компания "Стройновация".
22.09.2017 ГосИнспекция Труда
Прокурор требует пересмотреть дело о взрыве фейерверка в Дзержинске - АиФ Н.Новгород
Прокурор требует пересмотреть дело о взрыве фейерверка в Дзержинске
Уголовное дело готовится к направлению в Нижегородский областной суд для рассмотрения Степан Корс / https://vk.com/ Угонщик машины, совершивший смертельное ДТП,
АиФ Н.Новгород
За несдержанность сына ответят родители
Подростку, кинувшему в приятеля бутылкой воды, предстоит ответить за свой поступок.
Дзержинское время
Кримпасьянс
С 10 по 17 сентября зарегистрировано 16/5 сообщений о происшествиях и преступлениях.
Газета Саров
Мы – за экологию и творчество! - Репортер и времяВ третий раз в Дзержинске прошел фестиваль «ЭкоДзерФест». По подсчетам организаторов, в этом году в нем приняли участие более двух тысяч дзержинцев.
22.09.2017 Репортер и время
Вы знаете, сегодня Новый год?! - Репортер и время21 и 22 сентября встречают Новый год, а точнее  праздник Рош-а-Шана, люди, исповедующие иудаизм, а их в нашем городе немало.
22.09.2017 Репортер и время
В Нижнем Новгороде пройдут Дни эстонской культуры - АиФ Н.НовгородГлавным событием праздника станет фестиваль эстонской анимации в кинотеатре «Зарница» Виталий Цепляев / АиФ В Нижнем Новгороде прошел День славянской письменности и культуры Дни эстонской культуры пройдут в Нижнем Новгороде,
22.09.2017 АиФ Н.Новгород
Олег РОЙ: «Не врать в книгах проще, чем в жизни» - Нижегородские новости
Олег РОЙ: «Не врать в книгах проще, чем в жизни»
В областную детскую библиотеку на Звездинке пришел Олег Рой. Он привез подарки – книги про маленьких джингликов, Хранителей, Поваряшу и Вкусняшу.
Нижегородские новости
Гуляй, Выкса! Металлурги отмечают двойной юбилей. - Газета Нижегородский рабочий
Гуляй, Выкса! Металлурги отмечают двойной юбилей.
Конец сентября – начало октября для жителей Выксы отмечены целой вереницей ярких культурных событий: город накроет волной концертов и фестивалей.
Газета Нижегородский рабочий
Имена лучших выпускников школы он высек на кладбищенском памятнике - Нижегородские новости
Имена лучших выпускников школы он высек на кладбищенском памятнике
Жителя села Каменки Богородского района Евгения Приятелева односельчане зовут Технарем.
Нижегородские новости
Фото: НИА "Нижний Новгород" Женщина пострадала при столкновении троллейбуса с автобусом в Автозаводском районе Нижнего Новгорода 21 сентября 2017 года.
22.09.2017 НИА Нижний Новгород
«Олимпиец» Нижний Новгород вышел в 1/8 кубка России победив клуб премьер-лиги «Уфа» - Нижегородские новости В 1/16 финала Олимп-Кубка России нижегородский «Олимпиец» победил представителя российской премьер-лиги – «Уфу».
22.09.2017 Нижегородские новости
В День здоровья в БСШ все получили заряд бодрости и положительной энергии - Газета Знамя15 сентября в Большемурашкинской средней школе стал днем особенным, радостным, потому что учеба плавно перетекла в День здоровья.
22.09.2017 Газета Знамя
Вратарь «Прогресса» Дмитрий Коробов — оплот надежности - Газета Знамя
Серебро гарантировано!
17 сентября «Прогресс» принимал ДЮСШ Княгинино и одержал уверенную победу со счетом 2:0.
Газета Знамя
САЛЮТ - Дзержинские ведомости
Андрей Куваев: «Салют» стремительно развивается
В 2017 году исполнилось 20 лет с того дня, когда в Дзержинске решением городского совета народных депутатов был создан клуб физподготовки.
Дзержинские ведомости
«Под флагом Добра»
В Дзержинске в рамках Всероссийской благотворительной акции состоится футбольный матч между командой правительства Нижегородской области и командой звезд российской эстрады.
Репортер и время
В Нижнем Новгороде состоялись пожарно-тактические учения на заводе - МЧС Нижегородской областиВ Нижнем Новгороде прошли пожарно-тактические учения в одном из цехов пивоваренного завода «Волга».
22.09.2017 МЧС Нижегородской области
«Благоустройство набережной Федоровского – отличный пример взаимодействия города и социально ответственного бизнеса», - Елизавета Солонченко - Городская дума Н.НовгородаСбербанк провел работы по благоустройству еще одного места отдыха нижегородцев Сегодня  глава Нижнего Новгорода Елизавета Солонченко провела выездное совещание с управляющим Головным отделением по Нижегородской област
22.09.2017 Городская дума Н.Новгорода
Фото: НИА "Нижний Новгород" Женщина пострадала при столкновении троллейбуса с автобусом в Автозаводском районе Нижнего Новгорода 21 сентября 2017 года.
22.09.2017 НИА Нижний Новгород
Генерал-майор Юрий Кулик возглавил ГУ МВД РФ по Нижегородской области - Время НГУ МВД РФ по Нижегородской области возглавил генерал-майор полиции Юрий Кулик.
22.09.2017 Время Н
Товаропроизводители Нижегородской области представили свою продукцию на ярмарке «Покупайте Нижегородское» в Дзержинске - Администрация г. ДзержинскСегодня, 22 сентября , в Дзержинске проходит ярмарка «Покупайте Нижегородское» .
22.09.2017 Администрация г. Дзержинск