Книжкові видання та компакт-диски Журнали та продовжувані видання Автореферати дисертацій Реферативна база даних Наукова періодика України Тематичний навігатор Авторитетний файл імен осіб
|
Пошуковий запит: (<.>ID=REF-0000272386<.>) |
Загальна кількість знайдених документів : 1
|
Вербіцький О. В. Ігрові та екстремальні задачі комбінаторики із застосуваннями в теорії складності : Автореф. дис... д-ра фіз.-мат. наук: 01.01.08 / О. В. Вербіцький; Київ. нац. ун-т ім. Т.Шевченка. - К., 2007. - 35 c. - укp.Досліджено задачі комбінаторної теорії ігор і екстремальної комбінаторики. Значну увагу приділено питанням конструктивності та застосування у теорії складності обчислень і теорії дескриптивної складності. Розв'язано екстремальні задачі Рамсеївського типу для симетричних підмножин Евклідового простору, у цьому випадку значення екстремальних функцій досягаються ефективними детермінованими або ймовірнісними конструкціями. Для класу сильних ігор щодо уникнення забороненого підграфа введено та вивчено поняття симетричної стратегії. Введено поняття логічної глибини графа й одержано оцінки цього інваріанту на підставі всебічного вивчення гри Еренфойхта на графах. Ці оцінки застосовано для аналізу алгоритму Вайсфайлера - Лемана розпізнання ізоморфних графів. Шляхом ігрової інтерпретації та зведенням до екстремальних задач одержано результати про паралельне повторення інтерактивних доведень. Розроблено доведення без розголошення для теоретико-групових задач про перестановки. З'ясовано обчислювальну важкість форсингового хроматичного числа графа. Проведено оракульне конструювання, що дає змогу розв'язати питання Крайчика та Пудлака про існування оптимальних алгоритмів для coNP-задач. Індекс рубрикатора НБУВ: В126.1,0 + В127.4,0
Рубрики:
Шифр НБУВ: РА349180 Пошук видання у каталогах НБУВ Додаткова інформація про автора(ів) публікації: (cписок формується автоматично, до списку можуть бути включені персоналії з подібними іменами або однофамільці) Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"
|
|
|