WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

На правах рукописи

ПАВЛОВСКИЙ Евгений Николаевич

Оценка алгоритмической сложности

классов вычислимых моделей

01.01.06 математическая логика, алгебра и теория чисел

Автореферат

диссертации на соискание учной степени

е

кандидата физико-математических наук

Новосибирск 2008

Работа выполнена в Новосибирском государственном университете.

Научный руководитель: доктор физико-математических наук профессор, член-корреспондент РАН Гончаров Сергей Савостьянович

Официальные оппоненты: доктор физико-математических наук, профессор Хисамиев Назиф Гарифуллинович доктор физико-математических наук, профессор Добрица Вячеслав Порфирьевич

Ведущая организация: Казанский государственный университет

Защита состоится “ 27 ” июня 2008 г. в 15 ч. 00 мин. на заседании Диссертационного Совета Д 003.015.02 при Институте математики им. С.Л. Соболева СО РАН, пр-т Ак.Коптюга, 4, г.Новосибирск, 630090.

С диссертацией можно ознакомиться в библиотеке Института математики им.

С.Л. Соболева СО РАН.

Автореферат разослан “26”мая 2008 г.

Учный секретарь диссертационного совета е кандидат физико-математических наук Ряскин А.Н.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Академик А.И.Мальцев предложил использовать нумерации как базовую концепцию для изучения алгоритмических свойств алгебраических систем и их подмножеств, в частности таких классических систем, как группы, кольца и поля.

В рамках теории конструктивных моделей на сегодня разработаны различные подходы к исследованию алгоритмической и структурной сложности вычислимых моделей и отношений. Задача изучения структурных свойств вычислимых моделей и классов вычислимых моделей рассматривается как в рамках изучения сложности их ранга и формул Скотта, так и через индексные множества в универсальной нумерации вычислимых структур. Исследования в этом направлении были начаты в работах А.И.Мальцева, А.В.Кузнецова, Д.Макинси, К.Эша и А.Нероуда. Одним из продуктивных методов здесь является метод определимости в рекурсивном фрагменте языка бесконечных формул и задача изучения выразительных возможностей этого фрагмента языка в отношении описания свойств моделей. В этой связи актуальной является проблема нахождения формул и рангов Скотта для конкретных алгебраических структур и устойчивых относительно автоморфизмов отношений на них, исследование влияния на ранг Скотта константных и других естественных обогащений для алгебр, различных операторов над моделями, а также соотношений рангов и сложности структур для образов и прообразов. Этими проблемами занимались как зарубежные, так и российские математики, такие как Ершов, Гончаров, Каллибеков, Селиванов, Арсланов, Перетятькин, Добрица, Хисамиев и другие. Одно из направлений исследований связано с решением проблемы определимости и ее степени сложности в языке бесконечных формул.

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

К настоящему времени известно достаточно много результатов об индексных множествах моделей, классов моделей, теорий [1], [2], [3], [4], [5], [6], [7], [8], [9]. Большую роль индексные множества сыграли в общей теории вычислимости и вычислимых нумераций (кн. Ю.Л.Ершов. Теория нумераций [10]). Открытые проблемы этого направления привлекли специалистов и обсуждались на нескольких логических конференциях, в частности, приведены в работе Гончарова и Хусаинова [11], Гончарова и Найт [12].

Гончаров и Найт предложили [12] общие подходы для изучения структурных и алгоритмических свойств классов вычислимых моделей на основе исследования индексных множеств. Для многих классов индексное множество лежит на низком уровне гиперарифметической иерархии: множество I(K) является 0 -множеством для следующих классов: линейные порядки, булевы алгебры, абелевы p-группы, модели эквивалентности, векторные пространства над Q, модели фиксированного вычислимого языка.

В работе [6] даны точные оценки для индексных множеств конструктивных моделей с заданными условиями автоэквивалентности рассматриваемых конструктивизаций. В работе [13] дана точная оценка индексного множества для локальных конусов. Ряд работ В.П. Добрицы посвящено изучению различных индексных множеств конструктивных моделей [6], [14], [15], [13], [16].

Для некоторых классов индексное множество гиперарифметично:

(Клини, Спектор) множество I(K) является 1 -полным для следующих классов: полные порядки, суператомные булевы алгебры, редуцированные p-группы.

Для решения вопроса о существовании вычислимой классификации классов в [12] предложен подход оценки проблемы изоморфизма в терминах индексных множеств и приводятся доказательства оценок проблемы изоморфизма для некоторых важных классов. Так, например, множество E(K) проблемы изоморфизма является 1 -полным для следующих классов K: абелевы p-группы, деревья, булевы алгебры, линейные порядки, произвольные модели языка, содержащего по крайней мере один предикатный символ местности большей или равной 2. Проблемы изоморфизма также исследуются в работах [1], [2] для векторных пространств, алгебраических полей фиксированной характеристики, [17] для классов конструктивных Iалгебр, [18] для классов автоматных моделей. Подход через индексные множества также позволяет оценить сложность семантических классов предложений, целая глава в монографии [19] посвящена оценкам алгоритмической сложности классов предложений, используемых в теории моделей и логике.

Настоящая работа посвящена исследованию вопроса о характеризации известных классов моделей через оценку сложности индексных множеств классов вычислимых моделей. С этой точки зрения можно рассмотреть классы специальных моделей (простые, однородные, насыщенные, универсальные), классы моделей с заданными свойствами теорий (теория допускает простую модель, счётная-категоричность теории, несчётная категоричность, Эренфойхтовость, разрешимость теории), классы моделей с фиксированными алгоритмическими свойствами (разрешимые модели, автоустойчивые, модели конечной(бесконечной) алгоритмической размерности, модели с вычислимым рангом Скотта, с невычислимым рангом Скотта, d-разрешимые счётно-категоричные модели, d-разрешимые простые модели). Решение вопроса об оценке сложности этих множеств находится в русле проблем, обсуждаемых в докладе Гончарова и Хусаинова [11], а именно с проблемами существования конструктивных моделей для определённых классов теорий, а также о максимальной сложности некоторых теорий, имеющих конструктивные модели [11, Problems 3, 5, 11, Question 6].

Из перечисленных классов уже построены точные оценки для класса d-разрешимых моделей (0,d ), d-разрешимых счётно-категоричных модеd лей (3 ) [9]. Для класса универсальных вычислимых моделей получена нижняя оценка 1 [18]. Е.Б. Фокиной также была получена точная оценка индексного множества моделей, имеющих разрешимые теории 2 [20].

В последнее время в совместной работе российских и зарубежных специалистов был получен важный результат об индексных множествах структур высокого ранга Скотта.

В данной работе применён подход понижения вычислительной сложности в теоретико-модельных конструкциях (подход Гончарова-Хусаинова на основе конструкции Маркера) [22] для получения нижних оценок алгоритмической сложности вычислимых представителей естественных классов моделей. В работе использованы синтаксические характеризации классов моделей, обладающих -категоричными теориями (РылльНардзевский [23]), обладающих 1 -категоричными теориями (ЛахланБалдвин [24], Еримбетов [25]), современные результаты о синтаксической характеризации Эренфойхтовых теорий (Судоплатов, [26]). Для тех классов, для которых получены точные оценки, фактически подтверждается тезис выдвинутый в работе [3] о том, что точная оценка индексного множества даётся некоторым оптимальным описанием модели. В настоящей работе доказано, что упомянутые синтаксические характеризации обладают наименьшей возможной вычислительной сложностью, т.е. являются наилучшими синтаксической характеризациями с точки зрения вычислимости.

Цель работы. Анализ взаимосвязи между структурными и алгоритмическими свойствами классов вычислимых моделей.

Общая методика исследований. В работе анализируется взаимосвязь определимости классов моделей с алгоритмической их сложностью посредством построения точных оценок индексных множеств классов вычислимых моделей в соответствующих иерархиях алгоритмической сложности множеств, а также с помощью явного построения алгоритмов, или доказательства отсутствия таковых для определённых классов задач.

Используется аппарат теории моделей, широко используются теоретикомодельные функторы, предложенные Гончаровым [31], [22], синтаксические характеризации теоретико-модельных свойств [23],[26], [25], методы теории вычислимости, теории квазимногообразий.

Научная новизна. В работе получены следующие результаты:

- для классов моделей, определимых квазитождествами в сигнатуре унаров показано существование алгоритма определяющего наличие свойства конечности в свободной структуре класса, для более сложных сигнатур показано, что общего алгоритма не существует;

- на основе введенного понятия маркеровского свойства получена универсальная нижняя оценка сложности (0 ) для различных классов вычислимых моделей;

- построены точные оценки следующих классов вычислимых моделей:

простые модели, d-разрешимые простые модели (относительно арифметической Тьюринговой степени d), модели с Эренфойхтовой теорией, модели, теории которых допускают бесконечное число счетных моделей;

- построены верхние и нижние оценки следующих классов: модели с -категоричной теорией, модели с 1 -категоричной теорией.

Все основные результаты работы являются новыми, опубликованы.

Теоретическая и практическая ценность. Все результаты работы теоретические. Результаты работы могут быть использованы для построения классификации вычислимых моделей.

Апробация работы. Результаты работы были доложены на Девятой Азиатской логической конференции (Новосибирск, 2005), на Международной научно-практической студенческой конференции "Студент и научно-технический прогресс"(Новосибирск, 2003, 2004, 2006), на Логическом Коллоквиуме (Вроцлав, Польша, 2007), на Летней международной школе по вычислимым моделям и нумерациям (Новосибирск, 2007), С результатами работы автор неоднократно выступал на семинаре "Конструктивные модели"(Новосибирск, НГУ, 2003 – 2008), семинаре "Алгебра и логика"(Новосибирск, НГУ, 2003, 2005).

Публикации. Основные результаты опубликованы в работах [35]источники входят в перечень ВАК ведущих рецензируемых научных журналов и изданий, в которых должны быть опубликованы основные научные результаты диссертации.

Объём и структура диссертации. Диссертация содержит 95 страниц и состоит из введения, четырёх глав, заключения, библиографии. Основные утверждения диссертации названы теоремами. Нумерация теорем сделана двумя индексами: первый означает номер главы, второй - номер теоремы внутри главы. Все остальные утверждения и определения занумерованы тройками индексов, из которых первый индекс указывает на номер главы, второй номер соответствующего параграфа, а третий порядковый номер утверждения в этом параграфе. Нумерация замечаний сквозная.

СОДЕРЖАНИЕ РАБОТЫ

Во введении описана актуальность проблемы, рассмотрены известные результаты по тематике индексных множеств. Даны основные определения используемые в работе.

В работе [27] было показано, что для любой конечной сигнатуры без функциональных символов существует универсальная вычислимая нумерация вычислимых моделей этой сигнатуры. Для случая же бесконечной сигнатуры существует универсальная вычислимая нумерация всех вычислимых моделей сигнатуры вместе со всеми конечными вычислимыми моделями конечных частей этой сигнатуры [28, §1.4], [34, §1.3].

Существование таких универсальных нумераций моделей позволяет получить характеризацию классов вычислимых моделей соотнесением индексных множеств конкретных классов моделей с уровнем подходящей алгоритмической иерархии. Характеризация классов алгебраических систем в сигнатуре с функциональными символами может быть построена на основе этого подхода представлением функций своими графиками – предикатами.

Пусть = {M0, M1,..., Mn,...} упомянутая универсальная вычислимая нумерация моделей для соответствующей сигнатуры. Пусть K некоторый класс моделей сигнатуры без функциональных символов.

Определение 1.4. Индексным множеством I(K) абстрактного класса моделей K (класса, замкнутого относительно изоморфизмов), называется множество I(K) := {i | Mi K}.

Индексным множеством I(K) класса вычислимых моделей K называется множество I(K) := {i | существует M K, что Mi вычислимо изоморфно M}.

Определение 1.5. Пусть – некоторый уровень сложности (например, 1, 0 ). Тогда:

1. I(K) является -множеством, если I(K) ;

2. I(K) является m-полным -множеством, если I(K) и для любого S существует равномерно вычислимая последовательность вычислимых моделей (Cn )n такая, что В определении гиперарифметической иерархии будем следовать обозначениям Роджерса [29, §14], например 0, 0. Верхний индекс 1 в 1 означает разность 0 -множеств (0 \ 0 ).

В главе 1 работы рассматривается вопрос об алгоритмической сложности определения теоретико-модельных свойств класса алгебраических систем, заданного некоторым набором формул. С этой позиции исследуется свойство конечности алгебраических систем. Исследование построено на анализе проблемы существования алгоритма, определяющего конечность свободной системы квазимногообразия, заданного с помощью конечного множества квазитождеств. В главе приводится алгоритм распознающий конечность свободной системы, заданной системой квазитождеств в сигнатуре с одной унарной операцией и, может быть, некоторым вычислимым множеством констант. Доказано отсутствие общего алгоритма определения конечности по системе квазитождеств в сигнатуре с, по крайней мере, двумя унарными операциями. Доказательство основано на алгоритмической нераспознаваемости свойства конечности конечно-определённых групп. Используется результат Адяна и Рабина [30]. Построено сведение рассматриваемой проблемы для сигнатур с одной бинарной операцией и одной константой к результату предыдущего параграфа, а значит и к несуществованию алгоритма. Построена точная оценка индексного множества класса конечных моделей 0. Результаты первой главы изложены в работах [38], [35].

В главе 2 работы развиты подходы Гончарова для построения нижних оценок индексных множеств. Доказано, что функтор построенный в [31] сохраняет важные свойства вычислимых моделей:

Теорема 2.1. Пусть - вычислимая сигнатура без функциональных символов с конечным числом предикатных символов. Тогда для любой модели M сигнатуры существует модель M сигнатуры графов, для которой:

1. M вычислима M вычислима;

2. M d-разрешима M d-разрешима;

3. количество счётных моделей теорий T h(M) и T h(M ) совпадает;

4. M проста M проста.

Данный результат используется в работе для построения нижних оценок для соответствующих сигнатур.

В параграфе 2.2 развит универсальный подход построения нижних оценок сложности для определённого класса теоретико-модельных свойств.

Этот класс определяется через понятие маркеровского расширения модели [22].

Определение 2.3.3. Теоретико-модельное свойство R называется маркеровским, если для любой модели M любой конечной предикатной сигнатуры : M обладает свойством R тогда и только тогда, когда маркеровские расширения M и M обладают свойством R.

Назовём свойство маркеровским*, если оно маркеровское и дополнительно для сигнатур, содержащих предикатный символ P местности n 1, существуют модели A и B этой сигнатуры, такие что:

(1*) A обладает свойством R, B – не обладает свойством R, (2*) модели A, B вычислимы, (3*) предикаты P A, P B являются бесконечными кобесконечными множествами.

Для классов вычислимых моделей, которые определены с помощью маркеровских* свойств получена нижняя оценка 0. Об этом свидетельствует Теорема 2.4. Для любого маркеровского* свойства R существует вычислимая функция fR (m, n) такая, что Mf (m,n) обладает свойством R, если m (n), и не обладает им, в противном случае.

Результаты второй главы опубликованы в [39], [40], [36], [41], [37].

Глава 3 посвящена оценке индексных множеств специальных классов вычислимых моделей. Найдена и доказана точная оценка для класса простых d-разрешимых моделей, для арифметической Тьюринговой степени d.

Назовём сигнатуру нетривиальной, если она содержит предикатный или функциональный символ местности 2. Пусть вычислимая нетривиальная сигнатура. Первый результат формулируется как Теорема 3.1. Для любой арифметической Тьюринговой степени d индексное множество P rimed всех d-разрешимых простых моделей вычислимой сигнатуры является m-полным 1,d множеством в универсальной вычислимой нумерации всех вычислимых моделей сигнатуры.

Установлена точная оценка для класса простых моделей, но уже для бесконечных сигнатур. Пусть теперь вычислимая сигнатура, содержащая бесконечное число предикатных символов местности 2.

Теорема 3.2. Индексное множество P rime всех простых вычислимых моделей сигнатуры является m-полным 0 множеством в универсальной вычислимой нумерации всех вычислимых моделей сигнатуры.

Результаты третьей главы опубликованы в статьях [36], [41].

В главе 4 рассмотрены классы моделей, определённые естественными свойствами своих теорий. Установлены нижняя и верхняя оценка для вычислимых моделей, имеющих -категоричные теории.

Теорема 4.1. Для сигнатуры, содержащей бесконечное число преCat является 0 -сложным 0 дикатных символов местности + множеством.

Верхняя оценка верна для произвольных сигнатур. Для построения верхней оценки использовалась синтаксическая характеризация счётнокатегоричных теорий, впервые полученная Рылль-Нардзевским [23]. Найдены нижняя и верхняя оценки для вычислимых моделей, имеющих 1 категоричные теории. Для построения верхней оценки используется синтаксическая характеризация 1 -категоричных теорий, впервые полученная Лахланом и Балдвином [24], и законченная в работах Еримбетова [25],[32].

Эта характеризация с точки зрения вычислимости, как показывает теорема, почти идеальна.

Теорема 4.2. Для вычислимой сигнатуры, содержащей для каждого натурального числа n предикатный символ местности n, множество U Cat является 0 -сложным 0 -множеством.

Доказана 1 -полнота класса вычислимых моделей, имеющих Эренфойхтову теорию:

Теорема 4.5. Индексное множество Ehr сигнатуры, содержащей бесконечное число предикатных символов местности 2, является 1 -полным множеством в универсальной вычислимой нумерации всех вычислимых моделей сигнатуры.

Доказательство верхней оценки построено на синтаксической характеризации Эренфойхтовых теорий, полученной сравнительно недавно Судоплатовым [26]. Оказывается, что эта характеризация неулучшаема с точки зрения теории вычислимости. Нижняя оценка базируется на результатах, полученных Лемппом и Сламаном [33], о сложности разрешимых Эренфойхтовых теорий.

Как следствие этой теоремы и синтаксической характеризации Судоплатова получается оценка для индексного множества моделей, теории которых допускают бесконечное число моделей.

Следствие 4.3.1. Индексное множество вычислимых моделей сигнатуры, содержащей бесконечное число предикатных символов местности 2, теории которых допускают бесконечное число счтных моделей является m-полным 1 множеством.

Результаты главы опубликованы в [37], [36].

Изложение работы заканчивается заключением и списком литературы.

Автор выражает глубокую признательность своему научному руководителю Сергею Севостьяновичу Гончарову за внимание к работе, терпение и поддержку, а также за постановку задач и приобщению к проблемам математической логики. Автор также благодарит Сибирской фонд алгебры и логики за моральную и материальную поддержку в проведении исследований.

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

[1] Calvert W. The isomorphism problem for classes of computable elds // Archive for Mathematical Logic. 2004. Vol. 34, no. 3. Pp. 327–336.

[2] Calvert W. The isomorphism problem for computable abelian p-groups of [3] Калверт У., Каммингс Д., Найт Дж. Ф., Миллер С. Сравнение классов конечных структур // Алгебра и логика. 2004. Т. 43, № 6.

С. 666–701.

[4] Калверт У., Харизанова В., Найт Дж. Ф., Миллер С. Индексные [5] Csima B. F., Montalbn A., Shore R. A. Boolean algebras, tarski invariants, and index sets // Notre Dame Journal of Formal Logic.

[6] Добрица В. П. Сложность индексного множества конструктивной модели // Алгебра и логика. 1983. Т. 22, № 4. С. 372–381.

[7] White W. On the complexity of categoricity in computable structures // Mathematical Logic Quarterly. 2003. Vol. 49. Pp. 603–614.

[8] White W. Characterizations for Computable Structures: Ph.D. thesis / PhD dissertation. Cornell University, 2000.

[9] Фокина Е. Б. Индексные множества разрешимых моделей // [10] Ершов Ю. Л. Теория нумераций. М.: Наука, 1977.

[11] Goncharov S., Khoussainov B. Open problems in the theory of constructive algebraic systems // Computability Theory and Its Applications: Current Society: 2000. Pp. 145–169.

[12] Гончаров С. С., Найт Д. Вычислимые структурные и антиструктурные теоремы // Алгебра и логика. 2002. Т. 41, № 6. С. 639–681.

[13] Добрица В. П. Вычислимость некоторых подклассов вычислимого [14] Добрица В. П. Сложность индексных множеств вычислимых классов с конечным числом конструктивных систем // Сиб. мат. журн.

[15] Добрица В. П. Структурные свойства вычислимых классов конструктивных моделей // Алгебра и логика. 1987. Т. 26, № 1. С. 36–62.

[16] Добрица В. П. Индексные множества в обобщённых вычислимых нумерациях // Мат.журн.2. 2002. Т. 3, № 1. С. 38–42.

[17] Когабаев Н. Т. Сложность некоторых естественных проблем на классе С. 352–360.

[18] Винокуров Н. С. Индексные множества классов автоматных структур // Сиб. мат. журн. 2006. Т. 47, № 5. С. 1019–1030.

[19] Перетятькин М. Г. Конечно аксиоматизируемые классы. Новосибирск: Научная книга, 1997.

[20] Fokina E. B. Index sets of computable structures with decidable theories // Computation and Logic in the Real World – Third Conference of Computability in Europe (CiE) 2007. Vol. 4497 of Lecture Notes in Computer Science. Siena, Italy: June 2007. Pp. 290–296.

[21] Calvert W., Fokina E., Goncharov S. S. et al. Index sets for classes of Pp. 1418–1432.

[22] Гончаров С. С., Хусаинов Б. Х. Сложность теорий вычислимых категоричных моделей // Алгебра и логика. 2004. Т. 43, № 6. С. 650– [23] Ryll-Nardzewski C. On the categoricity in power [24] Baldwin J. T., Lachlan A. H. On strongly minimal sets // J. Symbolic [25] Еримбетов М. М. О полных теориях с 1-кардинальными формулами // Алгебра и логика. 1975. Т. 14, № 3. С. 245–257.

[26] Судоплатов С. В. Полные теории с конечным числом счетных моделей. I // Алгебра и логика. 2004. Т. 43, № 1. С. 110–124.

[27] Нуртазин А. Т. Вычислимые классы и алгебраические критерии автоустойчивости: Дисс....канд.физ.-мат. наук. / АН Казахской ССР. Ин-т математики и механики. Лаб. алгебры и логики. Алма-Ата, 1974.

[28] Гончаров С. С., Ершов Ю. Л. Конструктивные модели. Новосибирск: Научная книга, 1999.

[29] Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. М.: Мир, 1972.

[30] Адян С. И., Дурнев В. Г. Алгоритмические проблемы для групп и [31] Гончаров С. С. Проблема числа неавтоэквивалентных конструктивизаций // Алгебра и логика. 1980. Т. 19, № 6. С. 621–639.

[32] Еримбетов М. М. Категоричность в мощности и недвукардинальность С. 493–500.

[33] Lempp S., Slaman T. A. The complexity of the index sets of 0 -categorical theories and of ehrenfeucht theories // Proc. of the North Texas Logic Conference, October 8-10, 2004. 2004.

[34] Goncharov S. S. Computability and computable models // Mathematical problems from applied logic. II / Ed. by S. S. G. Dov M. Gabbay, century.

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

[35] Павловский Е. Н. Алгоритмическая распознаваемость свойства конечности конечно-определённых систем // Вестник НГУ. Серия: математика, механика, информатика. 2006. Т. 6, № 4. С. 83–92.

[36] Павловский Е. Н. Оценка алгоритмической сложности классов вычислимых моделей // Сиб. мат. журн. 2008. Т. 49, № 3. С. 635–649.

[37] Павловский Е. Н. Сложность индексных множеств некоторых классов моделей // Вестник НГУ. Серия: математика, механика, информатика. 2008. Т. 8, № 1. С. 71–76.

[38] Павловский Е. Н. Алгоритмическая распознаваемость свойства конечности конечно-определённых систем // Материалы XLII международной научной студенческой конференции Студент и научнотехнический прогресс. Математика. Новосибирск: 2004. С. 14– [39] Павловский Е. Н. Оценка алгоритмической сложности классов вычислимых моделей // Материалы XLIV международной научной студенческой конференции Студент и научно-технический прогресс. Математика. Новосибирск: 2006. С. 76–77.

[40] Pavlovsky E. N. Estimation of algorithmic complexity of computable models classes // Book of abstracts, Logic Colloquium’07. Wroclaw, [41] Павловский Е. Н. Индексные множества простых моделей // Сибирские электронные математические известия. 2008. Т. 5.

С. 200–210.



Похожие работы:

«Горюнова Ольга Борисовна РАЗРАБОТКА БИОЛОГИЧЕСКОГО ПРЕПАРАТА ДЛЯ БОРЬБЫ С ЛИЧИНКАМИ КОМАРОВ 03.00.23 – биотехнология АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Москва – 2009 Работа выполнена на кафедре биотехнологии Российского ХимикоТехнологического Университета имени Д.И. Менделеева Научный руководитель : кандидат технических наук, доцент Марквичев Николай Семенович Официальные оппоненты : доктор технических наук, профессор Бирюков...»

«Петраков Олег Викторович ИССЛЕДОВАНИЕ И РАЗРАБОТКА ТЕХНОЛОГИИ ПОЛУЧЕНИЯ БИМЕТАЛЛИЧЕСКИХ ОТЛИВОК ПРОКАТНЫХ ВАЛКОВ С ВЫСОКОЙ ЭКСПЛУАТАЦИОННОЙ СТОЙКОСТЬЮ РАБОЧЕГО СЛОЯ Специальность: 05.02.01 Материаловедение в машиностроении АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Москва – 2007 Работа выполнена в Брянском государственном техническом университете. Научный руководитель доктор технических наук, профессор Кульбовский Иван Кузьмич Официальные...»

«Мальчикова Александра Германовна ОРГАНИЗАЦИЯ ЛОГИСТИЧЕСКИХ ПОТОКОВ В СИСТЕМЕ ГОРОДСКИХ ПАССАЖИРСКИХ ПЕРЕВОЗОК Специальность 08.00.06 - Логистика Автореферат диссертации на соискание ученой степени кандидата экономических наук Санкт-Петербург 2000 2 Работа выполнена в Санкт-Петербургском государственном университете экономики и финансов Научный руководитель - доктор экономических наук, профессор Щербаков В.В....»

«УДК: 616-005.1:575.113+ 575.174.015.3+577.21 МОКАН ЕЛЕНА ЭФФЕКТИВНОСТЬ МОЛЕКУЛЯРНЫХ МАРКЕРОВ В ОПРЕДЕЛЕНИИ ГЕНЕТИЧЕСКОГО РИСКА ИШЕМИЧЕСКОГО ИНСУЛЬТА 03.00.15 – ГЕНЕТИКА Автореферат диссертации на соискание ученой степени доктора биологии КИШИНЕВ, 2012 Работа выполнена в лаборатории Молекулярной Генетики Института Генетики и Физиологии растений Академии наук Республики Молдова Научный руководитель : БАРБАКАР Николае...»

«УДК 581.14: 633.5.511: 577.34: 58.035 МАВЛАНОВА САДБАРХОН АБДУКАРИМОВНА ФИЗИОЛОГО-БИОХИМИЧЕСКИЕ ОСОБЕННОСТИ ИНДУЦИРОВАННОЙ УСТОЙЧИВОСТИ ХЛОПЧАТНИКА К СОСУЩИМ НАСЕКОМЫМ-ВРЕДИТЕЛЯМ И ВОЗБУДИТЕЛЮ ВЕРТИЦИЛЛЕЗНОГО ВИЛТА 03.00.12 – Физиология и биохимия растений АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата биологических наук Ташкент - Работа выполнена в Институте физиологии...»

«Секиринский Денис Сергеевич...»

«ЛАВРИК Сергей Николаевич ХОЛОДНИКАНСКИЙ ЗЕЛЕНОКАМЕННЫЙ ПОЯС (АЛДАНСКИЙ ЩИТ): ПРИРОДА ПРОТОЛИТОВ МЕТАМОРФИЧЕСКИХ ПОРОД И ИХ ПЕТРОГЕНЕЗИС Специальность 25.00.04 – петрология, вулканология АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата геолого-минералогических наук ВЛАДИВОСТОК 2006 Работа выполнена в Дальневосточном геологическом институте Дальневосточного отделения Российской Академии Наук Научные руководители: доктор геолого – минералогических наук Олег...»

«Митрофанова Алла Владиславовна РОЛЬ СЕРДЕЧНО-СОСУДИСТЫХ РЕАКЦИЙ В КИСЛОРОДОСБЕРЕГАЮЩЕМ ЭФФЕКТЕ ПРИ ИМИТАЦИИ НЫРЯНИЯ У ЧЕЛОВЕКА 03.03.01 – Физиология АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата биологических наук Санкт-Петербург 2011 Работа выполнена на кафедре Общей физиологии Санкт-Петербургского государственного университета. Научный руководитель : доктор биологических наук, доцент Татьяна Ивановна Баранова...»

«Галактионов Владимир Александрович Программные технологии синтеза реалистичных изображений Специальность 05.13.11 – математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей. Автореферат диссертации на соискание ученой степени доктора физико-математических наук Москва - 2006 Работа выполнена в Институте прикладной математики им. М.В. Келдыша РАН (г. Москва) Научный...»

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

«Петросян Лилит Грантовна ОЦЕНКА НЕЙРОПРОТЕКТИВНЫХ СВОЙСТВ КСЕНОНА ПРИ ОПЕРАЦИЯХ У БОЛЬНЫХ С ОБЪЕМНЫМИ ОБРАЗОВАНИЯМИ ГОЛОВНОГО МОЗГА 14.01.20 - анестезиология и реаниматология АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата медицинских наук Москва- 2014 г. 1 Работа выполнена в Федеральном государственном бюджетном учреждении Российский научный центр хирургии имени академика Б.В. Петровского Российской академии медицинских наук, отделении анестезиологииреанимации...»

«ХОБРАКОВА ВАЛЕНТИНА БИМБАЕВНА ЭКСПЕРИМЕНТАЛЬНЫЕ ВТОРИЧНЫЕ ИММУНОДЕФИЦИТНЫЕ СОСТОЯНИЯ И ИХ ФАРМАКОТЕРАПИЯ РАСТИТЕЛЬНЫМИ СРЕДСТВАМИ 06.02.01 – диагностика болезней и терапия животных, патология, онкология и морфология животных Автореферат диссертации на соискание ученой степени доктора биологических наук Благовещенск – 2012 Работа выполнена в Федеральном государственном бюджетном учреждении науки Институт общей и экспериментальной биологии Сибирского отделения Российской...»

«Кульков Сергей Сергеевич Разработка комплексной автоматизированной информационной системы для создания, хранения и предоставления информации в области химии и химической технологии 05.13.01 Системный анализ, управление и обработка информации (химическая технология, нефтехимия и нефтепереработка, биотехнология) 05.13.18 – Математическое моделирование, численные методы и комплексы программ (технические наук и) АВТОРЕФЕРАТ Диссертации на соискание ученой степени Кандидата...»

«Байдин Василий Григорьевич Математические и вычислительные подходы к повышению качества сейсмических изображений на основе моделирования упругих волновых полей Специальность 05.13.18 – Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Москва – 2013 Работа выполнена на кафедре вычислительной математики Московского физико-технического института (государственного...»

«ДЖАДЖАНИДЗЕ ИГОРЬ МАМИЕВИЧ МОТОРНО-ЭВАКУАТОРНАЯ ДИСФУНКЦИЯ ЖЕЛУДОЧНОКИШЕЧНОГО ТРАКТА ПРИ ОСТРОМ ДЕСТРУКТИВНОМ ПАНКРЕАТИТЕ 14.01.17. – хирургия АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата медицинских наук Красноярск – 2013 Работа выполнена на кафедре хирургии ГБОУ ДПО Иркутская государственная медицинская академия последипломного образования Министерства здравоохранения Российской Федерации, на базе НУЗ Дорожная клиническая больница на ст....»

«Конченков Владимир Игоревич КИНЕТИЧЕСКИЕ СВОЙСТВА ГРАФЕНА И СВЕРХРЕШЕТОК НА ЕГО ОСНОВЕ В УСЛОВИЯХ ВОЗДЕЙСТВИЯ ВЫСОКОЧАСТОТНЫХ ЭЛЕКТРИЧЕСКИХ ПОЛЕЙ И ПОСТОЯННОГО МАГНИТНОГО ПОЛЯ 01.04.04 – Физическая электроника АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Волгоград – 2012 Работа выполнена на кафедре Общая физика в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования Волгоградский...»

«Ветров Андрей Алексеевич РАСЧЕТ ЭЛЕКТРОДИНАМИЧЕСКИХ ХАРАКТЕРИСТИК И ОПТИЧЕСКИХ СВОЙСТВ УСКОРЯЮЩИХ СТРУКТУР В ШИРОКОМ ДИАПАЗОНЕ ДЛИН ВОЛН Специальность 01.04.20 Физика пучков заряженных частиц и ускорительная техника Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Москва - 2005 Работа выполнена в отделе...»

«Кучина Елена Викторовна СУДЕБНО-МЕДИЦИНСКАЯ ДИАГНОСТИКА ОТРАВЛЕНИЙ НЕКОТОРЫМИ СУРРОГАТАМИ АЛКОГОЛЯ 14.00.24. – судебная медицина Автореферат диссертации на соискание ученой степени кандидата медицинских наук Москва 2008 2 Работа выполнена в танатологическом отделе Федерального государственного учреждения Российский центр судебно-медицинской экспертизы Федерального агентства по здравоохранению и социальному развитию. Научный руководитель : доктор медицинских наук, профессор...»

«Маркина Татьяна Николаевна ПРОЛИФЕРАТИВНАЯ АКТИВНОСТЬ И ЗАДЕРЖКА КЛЕТОЧНОГО ЦИКЛА ЛИМФОЦИТОВ КРОВИ ЧЕЛОВЕКА В ОТДАЛЕННЫЕ СРОКИ ХРОНИЧЕСКОГО ОБЛУЧЕНИЯ 03.01.01 - радиобиология Автореферат диссертации на соискание ученой степени кандидата биологических наук Москва, 2011 2 Работа выполнена на базе ФГУН – Уральского научно-практического центра радиационной медицины, г. Челябинск Научный руководитель : доктор медицинских наук, профессор заслуженный деятель науки РФ, Аклеев...»

«ВАТУТИН АЛЕКСЕЙ НИКОЛАЕВИЧ ПОЛИТИКО-ТЕХНОЛОГИЧЕСКИЕ АСПЕКТЫ ФОРМИРОВАНИЯ ОБЩЕСТВЕННОГО МНЕНИЯ В УСЛОВИЯХ ВОЕННО-ПОЛИТИЧЕСКОГО КРИЗИСА Специальность 23.00.02 - Политические институты, процессы и технологии (политические наук и) Автореферат диссертации на соискание ученой степени кандидата политических наук Пятигорск – 2013 Работа выполнена на кафедре государственной политики и государственного управления ФГБОУ ВПО Кубанский государственный университет Научный руководитель :...»








 
2014 www.av.disus.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.