Параметризованные алгоритмы

2020/2021

Лучший по критерию «Полезность курса для Вашей будущей карьеры»

Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»

Лучший по критерию «Новизна полученных знаний»

Статус: Дисциплина общефакультетского пула

Кто читает: Департамент информатики

Где читается: Школа информатики, физики и технологий

Когда читается: 3 модуль

Охват аудитории: для своего кампуса

Язык: русский

Кредиты: 3

Контактные часы: 40

Дополнительные материалы в LMS Задать вопрос

Аннотация

Решение любой вычислительной задачи как правило начинается с предобработки данных, удаления несущественных деталей и упрощения поставленной задачи. Для NP-трудной задачи подобное упрощения невозможно в общем случае, в предположении гипотезы о неравенстве классов P и NP. В связи с этим для формализации процесса используют язык параметризованной сложности. В предобработке параметризованной задачи требуется уменьшить размер задачи до размера, не превосходящего значения некоторой функции от значения параметра. Если изначально размер задачи был мал относительно параметра, то дальнейшее уменьшение не предполагается. Подобная формализация позволяет развить очень плодотворную теорию с интересными практическими приложениями.

Цель освоения дисциплины

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

Планируемые результаты обучения

Знает классические алгоритмы построения ядра
Знает основные техники, позволяющие предобработать данные
Умеет доказывать эквивалентность существования параметризованного алгоритма и ядра
Умеет использовать техники, основанные на представляющих множествах, матроидах, лемме о подсолнухе и других
Владеет основными методами доказательства отсутствия ядра для данной задачи