Нормальный алгоритм Маркова. Тезис Маркова и машина Тьюринга. Гипотеза теории алгоритмов. Алгоритмически неразрешимые проблемы. Задача эквивалентности двух слов в ассоциативном исчислении. Задача распознавания выводимости. Линейная оценка сложности.
Аннотация к работе
Кафедра: Автоматика и информационные технологии ТЕОРИЯ АЛГОРИТМОВ Екатеринбург 2006 Приводится формализация понятия «алгоритм». Обсуждаются два способа формального описания алгоритма -с помощью нормальных алгоритмов Маркова и через машины Тьюринга. Приводятся меры сложности алгоритмов, определяются легко и трудноразрешимые задачи, классы задач P и NP, алгоритмически неразрешимые проблемы. Содержание ФОPМАЛИЗАЦИЯ ПОНЯТИЯ АЛГОPИТМА Определение Нормальный алгоритм Маркова Тезис Маркова Машина Тьюринга Основная гипотеза теории алгоритмов (тезис Чёрча) Универсальная машина Тьюринга МЕPЫ СЛОЖНОСТИ АЛГОPИТМОВ Оценка алгоритма Практические и NP-полные алгоритмы Алгоритмически неразрешимые проблемы «Формализация понятия алгоритма; Машина Тьюринга.