Бесплатно скачать, заказать диплом, курсовую, диссертацию Конструктивизируемость структур и ик степени неразрешимости

У нас уже 21989 рефератов, курсовых и дипломных работ

Сделать закладку на сайт

Заказать диплом, курсовую, диссертацию

Быстрый переход к готовым работам

Мнение посетителей:

Книга жалоб
и предложений

Название	Конструктивизируемость структур и ик степени неразрешимости

Количество страниц	77

ВУЗ	МГИУ

Год сдачи	2010

Бесплатно Скачать	23534.doc

Содержание	Содержание Введение 3 1 Д°-спектры линейных порядков 9 1.1 Д^-спектр... 9 1.2 Линейные порядки, сильно похожие на т/... 15 1.3 Квазидискретные линейные порядки... 21 2 Вычислимые алгебры Бршова 26 2.1 2-низкие алгебры Ершова... 26 2.2 3-низкие алгебры Ершова... 35 3 Класс вычислимых множеств 40 3.1 Теоретико-множественная структура... 40 3.2 Теоретико-множественные сводимости... 51 3.3 SET-1-сводимость на классе вычислимых множеств... 68 Литература 77 Введение Одной из важных задач в теории алгоритмов является изучение алгоритмической сложности различных счетных алгебраических структур на основе построения эффективных представлений этих структур на множестве натуральных чисел. В данной работе мы исследуем такие алгебраические структуры, как линейные порядки и алгебры Ершова. Исследования в этой области были начаты Л. Фейнером в конце 1960-х и продолжены в работах Дж. Реммела, С.С. Гончарова, Дж. Найт, К. Эша и других. В частности, было показано, что существуют вычислимо перечислимые булева алгебра и линейный порядок, не имеющие вычислимые изоморфные копии (см. [1] и [2]), другими словами, являющиеся неконструк-тивизируемыми. В последние года активно изучаются такие вопросы, как описание спектра счетных алгебраических структур. Например, Т. Сламан (см. [3]) и С. Вей-нер (см. [4]) независимо друг от друга построили такую счетную структуру А, что Spec(A) = D — {О}, где D — класс всех тьюринговых степеней. Р. Миллер в [5] доказал, что существует такой линейный порядок L, что Spec(L) П Д° = Д° — {0}. С. Гончаров, В. Харизанов, Дж. Найт, К. МакКой, Р. Миллер и Р. Соломон в [6] построили для любого п € и; такую структуру An, что Spec(An) — D — Ln, где Ln — класс всех п-низких степеней. В этой работе мы докажем, что для любого п 6 и> существует такой линейный порядок Сп, что Spec(?n) П А° = А° — Ln. В [7] Р. Доуни и М. Мозес показали, что любой дискретный линейный порядок низкой степени имеет вычислимую копию. Мы обобщим этот результат, доказав, что каждый 2-низкий квазидискретный (и, следовательно, дискретный) линейный порядок изоморфен вычислимому порядку. Причем, покажем, что для 3-низких квазидискретных порядков этот результат не верен. Также Р. Доуни спросил, какие еще существуют свойства линейных порядков Р, что для любого низкого линейного порядка L из P(L) следует существование вычислимой копии. В этом направлении мы докажем, что каждый низкий линейный порядок, "сильно похожий" на rj, изоморфен вычислимому порядку (причем для 2-низких это не верно). Отечественными и зарубежными учеными активно исследуется также вопрос о та-низких булевых алгебрах и алгебрах Ершова. В [1] Л. Фейнер построил вычислимо перечислимую булеву алгебру, не изоморфную никакой вычислимой алгебре. Построенная им булева алгебра не изоморфна никакой та-низкой алгебре, ни для какого натурального та. Естественно возникает вопрос: каждая ли та-низкая (для любого п ? ш) булева алгебра имеет вычислимую копию? Постановку этого вопроса можно найти, например, в [8]. В общем случае ответ на этот вопрос пока неизвестен, известны частичные ответы. В [9] Р. Доуни и К. Джокуш доказали, что каждая низкая булева алгебра изоморфна вычислимой алгебре. В [8] Дж. Найт и М. Стоб доказали, что любая 4-низкая булева алгебра имеет вычислимую копию. В этой работе мы покажем, что каждая 3-низкая алгебра Ершова изоморфна вычислимой алгебре. В теории вычислимости особое место занимают исследования теоретико-множественных свойств различных структур, особенно теоретико-множественные свойства класса вычислимо перечислимых множеств относительно вычислимых множеств. В третьей главе данной работы изучается теоретико-множественная структура класса вычислимых множеств относительно полиномиально вычислимых и примитивно рекурсивных. В этой главе вводится классификация вычислимых множеств и доказывается, что каждый класс введенной классификации не пуст. В третьей главе вводятся и изучаются две так называемые теоретико-множественные сводимости. Доказаны теоремы о нормальной форме для каждой сводимости, критерии минимальности и плотности. Используя кри- терий плотности, на классе вычислимых множеств доказано, что первая введенная теоретико-множественная сводимость порождает плотный частичный порядок. При доказательстве теорем диссертации использовались методы конечных расширений, приоритета с конечными нарушениями (метод 0'-приоритета), приоритета с бесконечными нарушениями (метод 0"-приоритета). Например, теоремы 3.1.5, 3.3.11 доказывались методом конечных расширений, теорема 2.1.2 — методом приоритета с конечными нарушениями, а теорема 1.2.3 — методом приоритета с бесконечными нарушениями. Содержание диссертации представлено в собственных публикациях автора [11] — [24]. Результаты, изложенные в данной работе, докладывались на международных конференциях "Logic Colloquium'2001" (Вена, Австрия, август 2001 г.), "Logic Colloquium'2002" (Мюнстер, Германия, август 2002 г.), "Колмогоров и современная математика" (Москва, апрель 2003 г.), "Logic Colloquium'2003" (Хельсинки, Финляндия, август 2003 г.), "Мальцевские чтения" (Новосибирск, 2003 г.), "Logic Colloquium'2004" (Турин, Италия, июль 2004 г.), а также на научных семинарах по математической логике в Казанском государственном университете. Автор выражает глубокую признательность своему научному руководителю профессору Арсланову Марату Мирзаевичу за постановку задач, интерес к исследованиям автора и поддержку в работе. В изложении теории вычислимости (теории алгоритмов) мы следуем в основном [10], в изложении теории счетных булевых алгебр, алгебр Ершова и линейных порядков — [25]. Ниже содержатся основные определения и обозначения, необходимые для дальнейшего изложения. Обозначения и терминология. Теория вычислимости. Через ш обозначается множество всех натуральных чисел с 0. Функция (ж, у) = (ж2 + 2ху + у2 + Зж + у)/2 — стандартная вычислимая биекция из и> • ш в и>. Теоретико-множественную разность множеств X С ш и Y С ш будем обозначать через X—У; дополнение множества X С.ш — через X =<уп ш—Х. Мы будем иногда отождествлять множество А С ш с его характеристической функцией Г 1, если х е А, Ха{х) = I ( U, в противном случае, так что запись А(х) — 1 означает, что ж 6 А, а А(х) = 0 эквивалентно х Запись X =* Y означает, что симметрическая разность (X — Y)U(Y — X) конечна. Будем писать А С* В, если А — В конечно. Пишем А Соо В, если А С* В ти В%* А. Тьюринговые степени будем обозначать жирными строчными латинскими буквами а, b, ..., тьюринговую степень множества А обозначаем через deg(A). Если / — некоторая функция, то dom(f) — область ее определения, rang(f) — область ее значений, graph(f) — график функции /: graph(f) = {<,у>\|у = /()}. Если последовательность функций /я : ш —>• и> поточечно сходится к функции /, то будем писать / = lims fa. Функция называется примитивно рекурсивной, если она принадлежит наименьшему классу, содержащему функции О(х) = 0, s(x) =<уп х + 1, I^.(xi,... ,хп) =dfn xm и замкнутому относительно суперпозиции и примитивной рекурсии. Функция называется вычислимой (частично вычислимой), если существует машина Тьюринга, вычисляющая эту функцию. Функция называется полиномиально вычислимой, если она вычислима на машине Тьюринга за количество шагов, ограниченное некоторым наперед заданным полиномом. Множество называется полиномиально вычислимым, примитивно рекурсивным, вычислимым, если его характеристическая функция является полиномиально вычислимой, примитивно рекурсивной или вычислимой, соответственно. Множество называется вычислимо перечислимым, если оно является областью определения некоторой частично вычислимой функции. ф^ — одноместная частично вычислимая функция, вычислимая на машине Тьюринга с оракулом А с гёделевым номером е€ш. Для каждого е полагаем W^ —dfn <1от(ф^). Оператором скачка множества А является А' — {е \| е € И^4}. По индукции можем определить n-ый скачек множества А: А^п+1^ = (А^)'. Для п G ь) множество А <т 0' называется n-низким (или п-высоким), если А^ <т 0^ (или 0(n+1) Булевы алгебры, алгебры Ершова, линейные порядки и их тью-ринговы степени. Алгеброй Ершова называется дистрибутивная решетка с относительными дополнениями, имеющая наименьший элемент. Булевой алгеброй называется дистрибутивная решетка с относительными дополнениями, имеющая наименьший и наибольшие элементы. Идеалом Фреше булевой алгебры Т> называется идеал .F(P) = {а ? Т> \ 3ai,..., ап, где а; — атом или нуль, 1 < г < п}. Под понятием решетки множеств понимается класс множеств Т> С V(w) — {А \| А С и}, замкнутый относительно операций объединения и пересечения (то есть AU В, АГ\ В ?Т> для любых множеств A, Be ?>). Решеткой множеств с наименьшим (с наибольшим) элементом назовем решетку множеств Z>, если 0 € Т> (или ш G Т>, соответственно). Под алгеброй множеств понимается решетка множеств с наименьшим и наибольшим элементами, замкнутая относительно операции теоретико-множественной разности (то есть А — В € Т> для любых А, В € Т>). Автоморфизмом алгебры множеств Л называется такая биекция ср : Л —> Л, что для любых А,В е A tp(A)\J Степень структуры В, обозначается deg(jB), — это тьюринговая степень ее атомной диаграммы, закодированной геделевскои нумерацией как подмножество ш. Если сигнатура структуры В конечна, то тьюринговой степенью В является deg(tf) = deg(\|?\|) V (V?=o deg(/;)) V (V?odeg(P0), где \Е\ — основное множество, {fi}i Мы рассматриваем только счетные структуры, основным множеством которых является ш. Спектром структуры А называется класс Spec(A) = {deg(B) \| В = Л}. Если С — некоторый класс степеней, то С-спектром называется класс Specc(A) = СП Spec(A). Мы будем рассматривать только А° -спектры счетных линейных порядков, то есть С = Дз — класс всех таких степеней а, что а <т О', где О — степень вычислимых множеств. Мы будем говорить, что структура А вычислима (n-низкой степени или п-высокой степени), если его степень deg(,4) вычислима (n-низкая или п-высокая, соответственно). Глава 1 А2-спектры линейных порядков 1.1 А°-спектр Мы будем рассматривать следующие предикаты, определенные на линейном порядке L: S(x,y) := (ж F(x,y) := ([х,у] = {z \| х Р+(х) := (Vy)(x (3z)(x Р~{х) := (Vy)(y <1 х —> (3z)(y dn(x,y) := (Vu,v)(x -^S(u,v)); EP-(x) := (3y)(y EP+(x) := Т. Сламан [З] и С. Вейнер [4] независимо друг от друга построили такую счетную структуру первого порядка Л, что Spec(A) = D — {О}, где D — класс всех тьюринговых степеней. Естественно возникают следующие вопросы: Вопрос 1.1.1 (Р. Доуни, [26]) Существует ли такой линейный порядок L, что Spec(L) = D - {0} ? Вопрос 1.1.2 (Р. Доуни, [26]) Существует ли такой линейный порядок L, что Spec^(L) = Д° - {0} ? Положительный ответ на вопрос 1.1.2 был получен Р. Миллером в [5]. Ответ на вопрос 1.1.1 пока неизвестен. Теорема 1.1.3 (Р. Миллер, [5]) Существует такой линейный порядок L, что SpecA°(L) = Д° - {0}. Р. Доуни поставил более общий вопрос 1.1.4, некоторые частные случаи которого были сформулированы Р. Миллером в [5]. Далее мы дадим положительный ответ на вопрос 1.1.5. Вопрос 1.1.4 (Р. Доуни, [26]) Что можно сказать о Spec(L) для фиксированного линейного порядка L ? Вопрос 1.1.5 (Р. Миллер, [5]) Существует ли такой линейный порядок L, что все высокие степени лежат в Spec(L), а все низкие степени в ш - Spec(L) ? С. Гончаров, В. Харизанова, Дж. Найт, К. МакКой, Р. Миллер и Р. Соломон в [6] построили для любого п ?ш такую структуру Лп, что Spec(An) = D — Ln, где Ln — класс всех п-низких степеней. Естественно возникают следующие вопросы, аналогичные вопросам 1.1.1 и 1.1.2. Вопрос 1.1.6 Верно ли, что для любого п ? со существует такой линейный порядок Ln, что Spec(Ln) = D — Ln ? Вопрос 1.1.7 Верно ли, что для любого n€w существует такой линейный порядок Ln, что Spec^°(Ln) — A-j — Ln ? В теореме 1.1.8 мы ответим на вопрос 1.1.7 и, следовательно, на вопрос 1.1.5. Ответ на вопрос 1.1.6 пока не известен. Теорема 1.1.8 Для любого п ? и) существует такой линейный порядок Ln, что SpecA° {Ln) = A°2 - Ln. Доказательство. По релятивизованной относительно Д°+1 теореме 1.1.3 существует линейный порядок Ао , имеющий копию в каждой А°+2, но не Д°+1 степени. Пусть Ln = (77 + 2 + 77) •... • (77 + 2-f 77) • Ао (п раз), где п — плотный порядок, порядковый тип множества рациональных чисел Q. Зафиксируем произвольную не п-низкую Д2 степень с. Предложение 1.1.9 (Р. Доуни и Дж. Найт, [27]) Линейный порядок А изоморфен Д2 порядку тогда и только тогда, когда (гу + 2 + г/) • А изоморфен вычислимому порядку. Применяя п раз предложение 1.1.9 получаем, что Ln имеет копию в с тогда и только тогда, когда Ао имеет копию в c^n^. Так как с — не п-низкая Aj степень, то с^") является А°+2 не Д°+1 степенью. Тогда Ао имеет копию в с(п) и, следовательно, Ln имеет копию в с. Так как с произвольно выбранная не n-низкая Aj степень, то Д2 — Ln С Spec^2(Ln). Осталось доказать, что Ln не имеет копии в никакой п-низкой степени. Пусть Ln имеет копию в 1, где 1 — любая гс-низкая степень, тогда по предложению 1.1.9 Aq имеет копию в 1(п). Ясно, что 1(п) есть А°+1. Следовательно, Ао имеет А°+1 копию. Это противоречит выбору Ао, что завершает доказательство теоремы. Замечание 1.1.10 Во второй части доказательства доказано более сильное утверждение. А именно, если L = (г/ + 2 + г/) •... • (г/ + 2 + ц) • А (п раз), для некоторого линейного порядка А, является п-низким, то L имеет вычислимую копию. Далее мы построим линейные порядки Ln, удовлетворяющие условиям теоремы, других порядковых типов, которые будут изучаться в разделах 1.2 и 1.3. Теорема 1.1.11 Если т — вычислимый линейный порядок без наименьшего и наибольшего элементов, а А — А2 линейный порядок, то т • А имеет вычислимую копию. Доказательство. Можно считать, что А не пустой, так как иначе теорема очевидна. Будем строить вычислимый линейный порядок L как сумма блоков Ьг, то есть L — YlieA L, где Li — копия г посредством функции изоморфизма /. Так как А есть Д°, то существует такая А% -последовательность конечных множеств {At}teu), что Ао = 0, At С At+\ и А — UtAt, и такая равномерно вычислимая аппроксимация {AttS}t,sew > что At = limaAt Шаг s = 0. Пусть 10 = 0, (0) = 0 и /, = 0. Шаг 5 + 1. Пусть построен конечный порядок L8 = Х^еЛы, L\ и fa : L\ —> т, построим Le+i 2 ?« • Выберем такое наибольшее число t < s, что Л,» = Л..+1, и положим ф + 1) = t + 1. Пусть At,,+i = {а0 <л,,,+1 . • • Подшаг 1. Если для некоторого г G {1,...,п} между блоками I»"'-1 и L"' в Ls имеются другие непустые блоки Laa (множество таких элементов а обозначим через В»), то для а ? Bi положим L"+1 = 0. Если aj_i меньше как натуральное число, чем а,, то положим ^"l^i1 = Ь"'"1 U (иаев,Ь") иначе — Ь"'+1 = (иаев,-^в) U L"1'. В этом случае для новых элементов b0 <ь, • • • <ь. bm € L^ — Ьай1 (случай Ьо Подшаг 2. Пусть At+itS+\ — AtiS+i U {x}. Если х — новый наименьший элемент, то есть ж <а ао, то положим новый блок Х+1 = {у} левее блока ?"!}-!. Аналогично в случае, если х — новый наибольший элемент. Если °i-i <а х <А «г и г € {1,..., п}, то новый блок L^+1 = {у} положим между блоками Ьая'+{ и L^'+1. Во всех случаях у — наименьшее, еще не использованное, натуральное число и /e+i(y) = 0. Подшаг 3. Для любого г € {0,... ,п} если s ? fs+i{L^+1), то переопределим Ь"'+1, расширив Ь"'+1 на один элемент t в соответствии с порядком г, то есть если fs+i(x) Положим La+1 = ?»елф+1),,+1 Ь\+1. Построение завершено. Легко видеть, что L — UaLs — вычислимый линейный порядок. Пусть s = s(t) такой шаг, что для любого s' > s имеем At = At,a>, тогда для любых s' > s и х Е L\, (i E At) имеем /,'(ж) = /„. Следовательно, / = U«/, — Д2. Легко видеть теперь, что L =/ т ¦ А. ? Следствие 1.1.12 Для любого к Е ш линейный порядок А изоморфен Aj-порядку тогда и только тогда, когда {п + к + 1 + ?]) • А изоморфен вычислимому порядку. Доказательство. (=Ф) Следует из теоремы 1.1.11, так как (rj + k + 1 + г)) — вычислимый линейный порядок без наименьшего и наибольшего элементов. (•$=) Очевидно, что предикат S(x,y) вычислимого линейного порядка есть Д". Поэтому множество таких наборов (ai,... ,aj,+i), что для любого г < к выполнено S(a,i,ai+i), является перечислимым относительно Д°. Очевидно, что эти наборы естественным образом линейно упорядочены как порядок А. Поэтому легко по этим наборам построить Д^ линейный порядок, изоморфный А. ? Пусть ki,... ,кп Е о» — {0} — произвольные числа, тогда рассуждениями, аналогичными доказательству теоремы 1.1.8 (используя следствие 1.1.12 вместо предложения 1.1.9), можно показать, что линейный порядок Ln = (v + &i + 1 + п) ¦... • (rj + кп +1 + г)) ¦ Ао удовлетворяет условиям теоремы 1.1.8. Напомним, что линейный порядок Ао имеет копию в каждой Д°+2-, но не Д°+1-степени. Замечание 1.1.13 Аналогично замечанию 1.1.10, если L = (п + к± + 1 + п) • ... • (tj + кп + 1 + tj) • А для некоторого линейного порядка А и некоторых чисел &i,...,/sn E ш — {0} является п-низким, то L имеет вычислимую копию. Далее, для четных п можно найти линейные порядки Ln, удовлетворяющие условиям теоремы 1.1.8, других порядковых типов. Пусть Ln = ?fc • AQ, где п — 2k, (k = (•¦•¦•( (к раз) и ( = w + и? — тип целых чисел Z, тогда Ln удовлетворяет условиям теоремы 1.1.8. На этот раз вместо предложения 1.1.9 нам требуется теорема 1.1.14. Теорема 1.1.14 (Р. Ватник, [28]) Линеный порядок А изоморфен Д^ порядку тогда и только тогда, когда ? • А имеет вычислимую копию. Следствие 1.1.15 Линеный порядок А имеет А^ копию тогда и только тогда, когда ш • А имеет вычислимую копию. Аналогично из следствия 1.1.15 следует, что линейный порядок Ln = шк • Аа удовлетворяет условиям теоремы при п = 2k. Замечание 1.1.16 Аналогично замечаниям 1.1.10 и 1.1.13, каждый 2k-низкий такой линейный порядок L, что L = (к • А или L = шк • А для некоторого линейного порядка А, имеет вычислимую копию. 1.2 Линейные порядки, сильно похожие на г; Определение 1.2.1 Назовем линейный порядок L k-блочным порядком, если для любых х и у из F(x,y) следует \[х,у]\ < k -f 1. Определение 1.2.2 Линейный порядок называется сильно похожим на п (strongly п -like), если он является к -блочным для некоторого к ? ш. Легко видеть, что для любого к ? и>, во-первых, любой к -блочный линейный порядок является Аг+1 -блочным и, во-вторых, существуют к+1 -блочные, но не Аг-блочные порядки. Также очевидно, что 0-блочными порядками являются только линейные порядки следующих порядковых типов: г], 1 + п, 7/+1 И 1+7/ + 1. В конце раздела 1.1 доказано, что для любого к G ш — {0} существует Д° линейный порядок L = (п + к + 1 + п) • А, для некоторого порядка А, удовлетворяющий условиям теоремы 1.1.8. Таким образом, для любого к € ш существует такой Д° А;+1-блочный, но не А:-блочный линейный порядок L, что L имеет копию в каждой не низкой Д 2 -степени и не имеет копии в низкой степени и, следовательно, L не имеет вычислимой копии. Далее мы докажем, что любой сильно похожий на п линейный порядок низкой степени имеет вычислимую копию (теорема 1.2.3). Причем, можно вычислить сложность функции изоморфизма — Дд. Теорема 1.2.3 Любой сильно похожий на п линейный порядок низкой степени Дд -изоморфен вычислимому порядку. Доказательство. Пусть L — fc-блочный линейный порядок низкой степени, где к € и. Предположим, что L не имеет ни наименьшего, ни наибольшего элемента. Иначе порядок L представим в виде a -f- L° + Ь, где а, Ъ < к + 1 и L0 — А;-блочный линейный порядок низкой степени без наименьшего и наибольшего элементов. Очевидно, что если L0 Дд -изоморфен вычислимому порядку, то L также имеет вычислимую копию, посредством Дд-изоморфизма. Так как L низкой степени, то предикат 5(ж,у) есть Д°. А так как L является А;-блочным порядком, то предикат F{x,y) вычислим относительно F(ai, a,j) и для любого х ? L — U либо F(x, aj), либо F(oj, х) для некоторого i ? о;. Так как L — /г-блочный порядок без наименьшего и наибольшего элементов, то легко видеть, что V является плотным линейным порядком и существует такая Ag функция <р, что V =v Q. Далее построим такую функцию / : Q —» {1, ...,&} и такие Sj множества А и В, что L ^ Е{/(У"Ч?)) I 9 € Q} и graph(f) = A-B. Пусть {L.}.e(ll такая Д j-последовательность конечных линейных порядков, что Lo = 0, Ь„ С ?e+i и DaLa = L — V. Зафиксируем оракул Д^. Шаг s=0. Для любого г?ш перечислим в А пару (aj, 1). Шаг s+1. Для любого х G Ь«+1 — i^» найдем такой i € и>, что F(x,ai) или F(a,i,x). Найдем пару (aj,n) ? А — В для некоторого п ? ш. Такая пара обязательно существует и единствена. Перечислим теперь (ai,n) в В, а (a,i,n + 1) в А. Описание конструкции завершено. Очевидно, что множества В С. А вычислимо преречислимы относительно Аз и, следовательно, ?° • Очевидно также, что для любого i 6 ш существует единственная пара (щ^п) 6 А — В. Определим теперь функцию /, как graph(f) = А — В. Так как L является fc-блочным линейным порядком, то область значений rang(f) конечно и ограничено числом А;. Легко видеть теперь, что L * Е{/(у"1( Так как А есть Е", то существует такой четырехместный вычислимый предикат Д(ж,у,?,п), что {t,n) € А тогда и только тогда, когда 3x\/yR(x,y,t,n). Заметим, что по построению множества А, если f(t) — те, то для любого п' < п (t,n'} G А и для любого п" > п (t,n") ? А. Зафиксируем для Д° линейного порядка L' такую вычислимую аппроксимацию конечными линейными порядками {-?t,e}t,eew> что Для любых t,s (E ш Lo,« = 0, Lt,a С Lt+i,,, L't = limsLtiS и L' = UtLJ. Причем, порядок Lt+i,, отличается от Lt Построим теперь вычислимый линейный порядок L = (и/, порядок L обычным способом: если шар х левее шара у, то х В нашей конструкции мы будем использовать раскраску шаров. Мы предполагаем, что имеется счетное число различных цветов. Белый будет особым цветом, обозначающий отсутствие какого-либо цвета и имеющий номер —1. Остальные цвета будут иметь натуральные номера 0,1,... Таким образом, во-первых, каждый шар будет иметь свой натуральный номер, а, во-вторых, каждый шар будет окрашен в свой цвет, который также будет иметь свой номер, возможно отличный от номера шара. Шаг 0. Определим вспомогательную последовательность x(t,n, 0) = —1 для всех t ?w и п < к + 1. Положим также t(0) = 0. Шаг s+1. Предположим, что t(s) уже определено и шары, окрашенные в один (не белый) цвет, стоят непосредственно рядом друг с другом и расположены в соответствии с порядком ?(,),», то есть окрашены в цвета г0,..., гт (здесь цвета перечислены так, как расположены шары, слева направо) и Lt(s),s = Oo )i, • • Подшаг 1. Выберем наибольшее такое t < t(s), что для любого t' < t Lt>,a+i = Lt',8- Положим t(s + 1) = t + 1. Добьемся того, чтобы в нашей конструкции шары, окрашенные в один цвет, стояли рядом и располагались в соответствии с порядком Lt^+i^,+i. Сначала покрасим в белый цвет все шары с цветом у ^ \|Lt(,)i8\| (если такие имеются). Затем пусть \|?t(e+i)ie+i\| = \|?*(«),л\| U {ж}. И пусть х — наименьший в Lt(e+i))i+i (если наибольший, то построения аналогичны). Если самый левый шар на прямой не белый, то положим левее всех шаров новый шар, окрашенный в цвет х. Если левее всех цветных шаров имеются белые, то выберем среди них шар с наименьшим натуральным номером и покрасим его в цвет х. Пусть х не является ни наименьшим, ни наибольшим в ?t(«+i),«+i j тогда выберем такие а,Ь € \|-Ця)1в\|, что а

Список литературы

Цена, в рублях: (при оплате в другой валюте, пересчет по курсу центрального банка на день оплаты)	1425

Скачать бесплатно	23534.doc

Найти готовую работу

ЗАКАЗАТЬ

Обратная связь:

Связаться

Вход для партнеров

Регистрация

Восстановить доступ

Материал для курсовых и дипломных работ

03.11.24 Лексикографический анализ единиц поля

03.11.24 Из истории слова гость и его производных

03.11.24 Семантическое поле гость в русском языке

Архив материала для курсовых и дипломных работ

Ссылки:

Счетчики:

© 2006-2024. Все права защищены.
Выполнение уникальных качественных работ - от эссе и реферата до диссертации. Заказ готовых, сдававшихся ранее работ.