Главная – Журналы – Профессиональное образование в современном мире 2019 номер 2

Статья посвящена выявлению роли и значения теории алгоритмов в фундаментализа- ции математического образования специалистов в области компьютерных наук и информационных технологий, обучающихся в образовательных учреждениях СПО и ВО. При этом теория алгоритмов предстает в двух своих ипостасях: как теория конкретных алгоритмов (или интуитивно-содержательная теория алгоритмов) и как формально-логическая (абстрактная) теория алгоритмов. В первом случае теория алгоритмов занимается созданием и изучением алгоритмов решения конкретных задач, и главной проблемой здесь является проблема разработки такого конкретного алгоритма, который может быть реализован современным компьютером в реальное время, а также проблема сравнения различных конкретных алгоритмов решения одной и той же задачи по степени их сложности, в основном по времени, требуемом для решения задачи. В связи с этим возникают классы сложности алгоритмов P и NP, а вместе с ними и проблема взаимоотношений между этими классами, не решенная до конца до настоящего времени. Во втором случае теория алгоритмов создает строго математические (абстрактные) понятия алгоритма и изучает свойства таких понятий. В 1930-е годы и первые послевоенные годы было разработано несколько абстрактных понятий алгоритма или, как говорят, формализаций интуитивного понимания алгоритма. Это машины Тьюринга и вычислимые с их помощью функции, рекурсивные функции как функции вычислимые с помощью некоторого алгоритма, нормальные алгоритмы А. А. Маркова и вычислимые с их помощью функции. Абстрактная теория алгоритмов устанавливает эквивалентность этих абстрактных понятий. Важнейшей проблемой здесь является также проблема существования таких алгоритмов для решения той или иной массовой проблемы. В частности, абстрактная теория алгоритмов устанавливает отсутствие алгоритмов для решения ряда массовых проблем. В нашей работе характеризуется методическая система обучения теории алгоритмов, учитывающая эти две ее ипостаси: интуитивно-содержательную и абстрактную.