Пусть A перечислимое множество натуральных чисел. Докажите, что множество всех натуральных корней единичной кратности многочленов с коэффициентами из A перечислимо.

задан 2 Май '20 2:02

10|600 символов нужно символов осталось
1

Всякое перечислимое множество (исключая пустое) есть множество значений некоторой (тотальной) вычислимой функции f. Это одно из эквивалентных определений перечислимости. Смысл в том, что f(i) печатается на i-м шаге процесса.

Известна конструкция эффективного перечисления всех конечных последовательностей (например, при помощи гёделевых номеров, хотя можно и по-другому). Теперь перечисляем все номера, по ним восстанавливаем последовательность i(0), ... , i(s), и применяем к этим номерам функцию f. Получится конечная последовательность номеров из A. По ним строим многочлен f(i(0))+f(i(1))x+ ... + f(i(s))x^s. Его натуральные корни (если они есть) -- это делители свободного члена. Их конечное число. Начинаем их подставлять в схему Горнера. Если получился корень, то проверяем его на кратность. Если он оказался не кратный, то выдаём его на печать. Это даёт искомое перечисление.

ссылка

отвечен 2 Май '20 4:06

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,153
×716

задан
2 Май '20 2:02

показан
327 раз

обновлен
2 Май '20 4:06

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru