РЕФЕРАТИВНА БАЗА ДАНИХ "УКРАЇНІКА НАУКОВА"
Abstract database «Ukrainica Scientific»


Бази даних


Реферативна база даних - результати пошуку


Вид пошуку
Пошуковий запит: (<.>ID=REF-0000272386<.>)
Загальна кількість знайдених документів : 1

Вербіцький О. В. 
Ігрові та екстремальні задачі комбінаторики із застосуваннями в теорії складності : Автореф. дис... д-ра фіз.-мат. наук: 01.01.08 / О. В. Вербіцький; Київ. нац. ун-т ім. Т.Шевченка. - К., 2007. - 35 c. - укp.

Досліджено задачі комбінаторної теорії ігор і екстремальної комбінаторики. Значну увагу приділено питанням конструктивності та застосування у теорії складності обчислень і теорії дескриптивної складності. Розв'язано екстремальні задачі Рамсеївського типу для симетричних підмножин Евклідового простору, у цьому випадку значення екстремальних функцій досягаються ефективними детермінованими або ймовірнісними конструкціями. Для класу сильних ігор щодо уникнення забороненого підграфа введено та вивчено поняття симетричної стратегії. Введено поняття логічної глибини графа й одержано оцінки цього інваріанту на підставі всебічного вивчення гри Еренфойхта на графах. Ці оцінки застосовано для аналізу алгоритму Вайсфайлера - Лемана розпізнання ізоморфних графів. Шляхом ігрової інтерпретації та зведенням до екстремальних задач одержано результати про паралельне повторення інтерактивних доведень. Розроблено доведення без розголошення для теоретико-групових задач про перестановки. З'ясовано обчислювальну важкість форсингового хроматичного числа графа. Проведено оракульне конструювання, що дає змогу розв'язати питання Крайчика та Пудлака про існування оптимальних алгоритмів для coNP-задач.


Індекс рубрикатора НБУВ: В126.1,0 + В127.4,0

Рубрики:

Шифр НБУВ: РА349180 Пошук видання у каталогах НБУВ 
Додаткова інформація про автора(ів) публікації:
(cписок формується автоматично, до списку можуть бути включені персоналії з подібними іменами або однофамільці)
  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"
 
Національна бібліотека України імені В. І. Вернадського
Відділ наукового формування національних реферативних ресурсів
Інститут проблем реєстрації інформації НАН України

Всі права захищені © Національна бібліотека України імені В. І. Вернадського