СЛОЖНОСТЬ АЛГОРИТМОВ ПЕРВОГО РОДА

Автор(ы): Цветков Виктор Яковлевич

Рубрика: Информационные технологии

DOI: 10.21777/2500-2112-2020-4-73-80

Выпуск: 2020-4 (33)

Страницы: 73-80

Ключевые слова: алгоритмы, классы сложности, виды сложности, алгоритм первого рода, алгоритм второго рода, вычислительная модель, машина Тьюринга

Аннотация: Статья проводит анализ сложности алгоритмов первого рода. Анализируются признаки, по которым алгоритм можно отнести к алгоритму первого рода. Вводится новое понятие «результативность алгоритма» в теорию сложности вычислений. Показано различие между алгоритмами первого и второго рода на примере детерминированной и недетерминированной машины Тьюринга. Вычислительная модель раскрывается на примере машины Тьюринга. Дана обобщенная модель алгоритмов первого рода. Раскрывается содержание и обосновывается необходимость понятия асимптотическая сложность. Основной анализ выполняется с классами и видами временной сложности. Приведены примеры и дан анализ алгоритмов постоянного времени и линейного времени. Отмечена условность некоторых видов сложности. Она состоит в том, что алгоритмы, которые относятся к одному классу или виду сложности физически используют разное время вычислений. Отмечена ситуация, при которой более простой вид сложности затрачивает больше времени на вычисления, чем более сложный. Отмечен недостаток существующей теории алгоритмической сложности – исключение из анализа сложности когнитивного фактора и когнитивной сложности. Это обусловлено исключением понятия результативности алгоритма при анализе или оценки сложности. Существующая теория сложности акцентирует внимание на вычислениях и времени вычислений. Но главным в вычислениях является результат. Если результат вычислений не качественный или нечеткий, то время вычислений теряет свою важность. Соответственно
оценка классов сложности должна привязываться не только ко времени, но и к качеству результата. Намечены результаты дальнейших исследований.

Библиографическая ссылка: Цветков В.Я. СЛОЖНОСТЬ АЛГОРИТМОВ ПЕРВОГО РОДА // Образовательные ресурсы и технологии. – 2020. – № 4 (33). – С. 73-80. doi: 10.21777/2500-2112-2020-4-73-80