- •§ 8. Диафантовы множества.
- •Теорема Лагранжа.
- •8.1. Разрешимость в натуральных числах.
- •Определение.
- •Определение.
- •Теорема 8.1.
- •Теорема 8.2.
- •Необходимость.
- •Достаточность.
- •8.2. Нумерация кортежей.
- •Канторова нумерация.
- •Геделево кодирование.
- •Определение.
- •Теорема 8.3.
- •Теорема 8.4.
- •Определение.
- •0.2. Машина с неограниченными регистрами (мнр) [Ктл, c.16]
- •0.3. Равнодоступные адресные машины (рам) [Ахо, с.22]
- •Типы операндов.
- •Команды.
- •0.4. Интерпретация программы как функции.
- •0.6. Вычислительная сложность рам-программ.
- •Определение.
- •Определение.
- •Определение.
- •Логарифмический критерий.
- •0.7. Модификации рам.
- •0.8. Неветвящиеся программы и равномерный весовой критерий.
- •Определение.
- •0.9. Неветвящиеся программы и логарифмический весовой критерий.
- •0.10. Ветвления.
- •0.11. Операции с двоичными векторами фиксированной длины. Определение.
- •Определение.
- •0.12. Машина Тьюринга (k-ленточная).
- •Определение.
- •Определение.
- •0.13. Связь мт и рам.
- •Теорема 0.1.
- •Утверждение 1.
- •Утверждение 2.
- •§ 1. Структуры данных. Определение.
- •1) Вставка.
- •2) Удаление.
- •1.1. Очередь и стек. Определение.
- •Определение.
- •1.2. Множества. Представление множеств.
- •1) Применение списков.
- •3) Представление в виде массивов.
- •4) Представление в виде графа.
- •Определение.
- •Определение.
- •§ 2. “Разделяй и властвуй”.
- •Теорема 2.1
- •§ 3. Динамическое программирование
- •Алгоритм 3.1.
- •§ 4. Редактирующее расстояние
- •Алгоритм 4.1.
- •Алгоритм 4.2.
- •§ 5. Порядковые статистики Определение.
- •Алгоритм 5.1
- •Теорема 5.2.
- •§ 6. Вхождение образца
- •Определение.
- •Алгоритм 6.1a.
- •Алгоритм 6.1б. Вычисление функции отказов.
- •Теорема 6.2.
- •Алгоритм 6.1.Б вычисляет f за o(n) шагов.
- •Конец пока
- •Алгоритм lz
- •Дельта – алгоритм
- •Арифметическое кодирование
§ 8. Диафантовы множества.
Рассмотрим уравнение
D(x1, x2,…. xn) = 0, где D полином с целочисленными коэффициентами.
Нас будет интересовать проблема разрешимости в целых числах.
Попытаемся обобщить задачу. Рассмотрим систему диафантовых уравнений:
Задача (2) не сложнее задачи (1), множества их решений совпадают. Значит, эти задачи эквивалентны.
Теперь займемся понижением степени уравнения. Диафантовы уравнения первой степени разрешимы. Оказывается, любое диафантово уравнение может быть сведено к диафантову уравнению 4-ой степени.
Степень полинома D максимум из сумм степеней сомножителей по всем слагаемым D.
Теорема Лагранжа.
Для любого a существует его представление в виде суммы четырех квадратов.
a = x12 + x22 + x32 + x42.
8.1. Разрешимость в натуральных числах.
По любому диафантову уравнению можно построить диафантово уравнение в целых числах.
Сведение задачи в целых числах к задаче в натуральных это всегда сведение вида :
и наоборот.
Верно ли, что уравнение D(Xn) = 0 разрешимо в целых числах?
Уравнение D( a1 b1, a2 – b2, ... , an – bn ) = 0 разрешимо в целых числах.
Если одну задачу можно свести к другой , то они эквивалентны.
Задачи распознавания – это задачи, в которых надо решить, существует ответ или нет.
Для решения задачи вводится некий язык L *
П L * .
Определение.
Будем говорить, что язык L1 *1 сводится( ) к языку L2 *2 тогда и только тогда, когда существует вычислимая функция
f : 1* 2* такая, что
для любого x 1* выполняется: x L1 тогда и только тогда, когда f(x) L2.
Аналогично можно говорить о сводимости задачи, следовательно, можно говорить и о сводимости языков, которые они определяют. Если функция f существует, но не вычислима, то данное определение не имеет смысла.
Мы считали, что задачи эквивалентны в вычислительном смысле, если П1 П2 и П2 П1, т.е. разрешимы и неразрешимы одновременно.
У диафантовых уравнений у нас присутствует не только одновременное существование решений, но и построение одного решения по другому. Поэтому будем считать, что все переменные в диафантовом уравнении . Любое диафантово уравнение можно представить в виде :
D(a1, …, an, x1, …, xm) =0, где {ai }i = 1...n – параметры, {xj }j = 1…m переменные.
Тогда существует множество кортежей из натуральных чисел < a1, … , an > n , при которых (как параметрах) диафантово уравнение разрешимо.
Определение.
Множество n n называется диафантовым, если существует полином с целыми коэффициентами D(An,Xm) такой, что <a1, …, an > n Xm такой, что D(An,Xm) = 0, т.е. параметрическое диафантово уравнение разрешимо.
Множество n это множество кортежей. Если n = 1, то это множество чисел.
Теорема 8.1.
Пусть M1n и M2n диафантовы множества. Тогда M1n M2n и M1n M2n тоже являются диафантовыми.
1) M1n M2n
Так как множества M1 и M2 диафантовы, то существует их диафантовы уравнения, и либо одно, либо другое разрешимо. Тогда представим M1 и M2 полиномами D1(A, Xm1) и D2(A, Xm2). Объединение будет описываться следующим образом: Xm такой , что D1(A, Xm1)* D2(A, Xm2) = 0 , где M = Max{ M1, M2 }. Если хоть одно из уравнений Di(A, Xmi) = 0, i = 1,2 разрешимо, то и это уравнение будет разрешимо.
2) M1n M2n
Здесь общее уравнение и переменные другие: D1(A, Xm1) + D2(A, Ym2) = 0