Общероссийский семинар «Информатика, управление и системный анализ»

ОБЩЕРОССИЙСКИЙ СЕМИНАР «ИНФОРМАТИКА, УПРАВЛЕНИЕ И СИСТЕМНЫЙ АНАЛИЗ»
под общим руководством
Академика РАН Юрия Ивановича Журавлева,
Академика РАН Евгения Ивановича Моисеева,
Академика РАН Станислава Николаевича Васильева,
Члена-корреспондента РАН Юрия Соломоновича Попкова
организатор и ученый секретарь семинара
профессор Михаил Васильевич Ульянов

Сайт семинара: www.commonmind.ru

ЗАСЕДАНИЕ № 7

Вторник 16 сентября 2014 г., 17-30, ауд. 685 ВМК МГУ

ПОВЕСТКА ДНЯ
Информационный доклад:
«УГЛОВАЯ МЕРА АСИМПТОТИЧЕСКОГО РОСТА ФУНКЦИЙ И КЛАССИФИКАЦИЯ АЛГОРИТМОВ ПО ТРУДОЁМКОСТИ»

Докладчики: д.т.н., профессор, профессор кафедры высшей математики МИРЭА
ГОЛОВЕШКИН ВАСИЛИЙ АДАМОВИЧ; д.т.н., профессор, в.н.с. ИПУ РАН,
профессор ВМК МГУ и ФКН НИУ ВШЭ УЛЬЯНОВ МИХАИЛ ВАСИЛЬЕВИЧ

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