ISSN 2307-5430
Язык: ru

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

Читать онлайн

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

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

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

УДК
510.57. Вычислимые (рекурсивные) функции
Для цитирования:
СОБОЛЕВ С. К., ТЮЛЕНЕВ А. В., ТЮЛЕНЕВА М. В. ИЗЛОЖЕНИЕ ПОНЯТИЯ ВЫЧИСЛИМОЙ ФУНКЦИИ В ТЕХНИЧЕСКОМ УНИВЕРСИТЕТЕ // АКТУАЛЬНЫЕ ПРОБЛЕМЫ ПРЕПОДАВАНИЯ МАТЕМАТИКИ В ТЕХНИЧЕСКОМ ВУЗЕ. 2020. № 8
Текстовый фрагмент статьи