ISSN 2307-5430
Язык: ru

АКТУАЛЬНЫЕ ПРОБЛЕМЫ ПРЕПОДАВАНИЯ МАТЕМАТИКИ В ТЕХНИЧЕСКОМ ВУЗЕ

ИЗЛОЖЕНИЕ ПОНЯТИЯ ВЫЧИСЛИМОЙ ФУНКЦИИ В ТЕХНИЧЕСКОМ УНИВЕРСИТЕТЕ (2020)

Широко известно сравнение значимости понятия вычислимой функции со значимостью понятия натурального числа (Э. Пост). Однако традиции преподавания в технических вузах не предусматривают знакомства с основами теории вычислимых функций, что затрудняет изучение сложности алгоритмов студентами таких специальностей, как «Информационная безопасноть», САПР, «Прикладная математика» и др. На основе опыта работы со студентами с различной математической подготовкой можно рекомендовать начинать изложение этой темы с формализации понятия алгоритма. В качестве таких конструкций предлагаются машины Тьюринга и нормальные алгорифмы Маркова. Изучение различных формализаций интуитивного понятия алгоритма, сравнение решений, полученных упомянутыми методами, помогает лучшему пониманию теории вычислимых функций и способствует формированию чёткого представления о том, что такое сложность вычислений.

Тип: Статья
Автор (ы): Соболев Сергей Константинович, Тюленев Андрей Всеволодович, Тюленева Марина Валентиновна
Ключевые фразы: МАШИНА ТЬЮРИНГА, НОРМАЛЬНЫЙ АЛГОРИФМ МАРКОВА, ВЫЧИСЛИМАЯ ФУНКЦИЯ

Идентификаторы и классификаторы

УДК
510.57. Вычислимые (рекурсивные) функции
Текстовый фрагмент статьи