Ульянов М.В.

Среда, 14:35,
ауд. 613

Спецкурс для магистров. Начало 26 сентября.

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

Содержательно в спецкурсе рассматриваются следующие вопросы:

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

Страница курса: http://vmk.somee.com/Details/6088