Российской федерации

Скачать 0.91 Mb.

Название	Российской федерации
страница	10/11
Дата публикации	15.03.2015
Размер	0.91 Mb.
Тип	Основная образовательная программа

100-bal.ru > Право > Основная образовательная программа

1 2 3 4 5 6 7 8 9 10 11

Раздел 1. Общие сведения о языках логического программирования. Унификации. Логическая программа. Исчисление предикатов. Хорновские дизъюнкты. Унификации, Алгоритм унификации, Теорема об унификации.

Раздел 2. Резолюции. Резольвента, метод резолюций. SLD-вывод, опровержение. Теорема о корректности метода резолюций.

Раздел 3. Модели Эрбрана. Интерпретация Эрбрана. Модель Эрбрана. Существование модели Эрбрана для выполнимого множества предложений.

Раздел 4. Наименьшая модель Эрбрана. Теорема Тарского. Оператор непосредственного следствия. Теорема о наименьшей модели Эрбрана.

Раздел 5. Полнота метода резолюций. Лемма о mgu. Лемма о подъеме. Решение программы. Теорема о множестве решений программы. Теорема о полноте резолюций.

Раздел 6. Алгоритмические свойства наименьшей модели Эрбрана. Рекурсивная перечислимость наименьшей модели Эрбрана. Теорема о вычислимости ч.р.ф., ее следствие.

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

Раздел 8. Язык и семантика темпоральной логики программ. Язык и семантика пропозициональной темпоральной логики. Примеры общезначимых формул.

Раздел 9. Исчисление темпоральной логики программ. Исчисление, теорема о корректности. Теоремы о дедукции и слабой полноте. Отсутствие сильной полноты.
ДЕНОТАЦИОННАЯ СЕМАНТИКА
1. Бестиповое λ-исчисление. Синтаксис. λ–Термы. Подтермы. Вхождение подтерма в терм. Множество свободных переменных терма. Свободные и связанные вхождения переменных, а также области действия для λ. α–Эквивалентность λ–термов. Терм свободный для подстановки. Операция подстановки терма в терм вместо всех свободных вхождений переменной. Свойства подстановки. β–Редукции. Редексы. Нормальные формы. Нормализуемые термы. Теорема Чёрча-Россера (доказательство через параллельные редукции и их свойства). Единственность нормальной формы. β–Эквивалентность и ее свойствами.

2. λ-Исчисление как язык программирования. Натуральные числа Чёрча и определение представимых функций. Представимость любых всюду определенных рекурсивных функций. Термы True, False, Cond и их свойства. Свойства терма IsNull. Кодировка пар: термы First, Second, Pair и их свойства. Отнимание 1 в λ–исчислении. Теорема о неподвижной точке. Представимость простейших функций. Представимость композиции. Представимость примитивной рекурсии. Представимость μ–оператора. Неразрешимость проблемы существования нормальной формы для термов.

3. Типизированное λ–исчисление. Простые и составные типы. Правила приписывания типов. Типизируемые термы. Теорема о нормализации типизируемых термов (без доказательства).

4. Семантика Скотта для бестипового λ-исчисления. Направленные множества, Полные частично упорядоченные множества (пчум). Топология Скотта. Критерий непрерывности в топологии Скотта. Монотонность непрерывных отображений. Декартовым произведением семейств пчум. Пчум всех непрерывных отображений полных чум. Теорема о непрерывности функций от двух аргументов. Теорема о непрерывности аппликации. Теорема о непрерывности λ–абстракции. Проекция полных чумов. Ретракты и ретракции. Свойства проекций полных чумов. Перенесение проекций с полных чум на пчумы их непрерывных отображений. Определение пчум D_∞. Определение отображений Φ_mn и их свойства. Определение операции · на D_∞, ее непрерывность, связь с операцией применения (аппликации) на D_n₊₁×D_n. Связь операции · и упорядочения. Теорема о функциональной полноте

. Изоморфизм и гомеоморфизм упорядоченных множеств D_∞ и [D_∞→ D_∞]. Представление непрерывных функций на

с помощью операции ·. Определение семантики Скотта для λ–термов. Теорема о связи β–эквивалентности и семантики Скотта.

5. Графиковая модель λ–исчисления. Определение графиковой модели, ее отличие от модели Скотта.
ДОПОЛНИТЕЛЬНЫЕ ГЛАВЫ ЛИНЕЙНОЙ АЛГЕБРЫ

1. Введение. Особенности компьютерных вычислений. Обратная устойчивость. Гарантированная оценка точности.
2.1 Системы с квадратной матрицей, число обусловленности, определитель, упрощение с помощью ортогональных преобразований. Решение систем
2.2 Решение систем полного ранга. Метод регуляризации
3.1 Особенности спектра симметричных матриц. Теорема Штурма, последовательности Штурма
3.2 Вычисление собственных значений симметричных матриц. Примеры
3.3 Двусторонние последовательности Штурма и собственные векторы симметричных матриц.
3.4 Примеры: собственные функции оператора Лапласа, полиномы Лежандра и др.
4.1 Теорема Шура. Уравнение Сильвестра
4.2 Эпсилон-спектр, примеры, критерий отсутствия спектра на кривой.
4.3 Обобщенные уравнения Ляпунова
4.4 Задача дихотомии спектра, проекторы на инвариантные подпространства.
4.5 Дихотомия окружностью
4.6 Линейная дихотомия, эллиптическая дихотомия.
4.7 Одномерные спектральные портреты и канонический вид матриц.
4.8 Разложение полинома на множители
ИСТОРИЯ МАТЕМАТИКИ
1. История Российской академии наук.
2. Сибирское отделение Российской АН.
3. Новосибирский государственный университет.
4. Институт гидродинамики СО РАН.
5. Институт математики СО РАН.
6. История алгебры.
7. История геометрии.
8. История математического анализа.
9. История кибернетики.
10. История математической экономики.
11. История дискретной математики.
12. История комбинаторики.
13. История теории вероятностей.
14. История теории чисел
15. История криптографии.
16. История теоремы Ферма.
17. История гипотезы Римана.
18. История гипотезы Пуанкаре.
ТЕОРИЯ ГРАФОВ

Основные определения и обозначения, связанные с графами, орграфами и мультиграфами.
Способы задания графов. Матрицы смежности и инцидентности, их свойства. Связь между матрицей смежности и числом маршрутов заданной длины.
Графы пересечений множеств. Представление произвольного графа в виде графа пересечений.
Степенные последовательности графов, мультиграфов и псевдографов, их характеризация.
Двудольные графы. Критерий двудольности графа. Однозначность разбиения связного графа на доли.
Экстремальные по числу ребер графы. Экстремальные графы без треугольников. Теорема Турана и граф Турана.
Леса и деревья. Теорема о характеризации деревьев. Корневые и остовные деревья.
Вершинная и реберная древесность графов. Теорема Нэш-Уильямса о реберной древесности. Понятие линейной древесности.
Перечисление и кодирование деревьев. Код Прюффера. Теорема Кэли о числе помеченных деревьев.
Проблема изоморфизма графов. Гипотеза Улама. Полные системы инвариантов для деревьев.
Вершинная и реберная k-связность графов, числа вершинной и реберной связности, их свойства.
Точки сочленения, мосты и блоки графа. Теорема о характеризации вершинно двусвязных графов. Взаимное расположение двух блоков в графе. Дерево блоков и точек сочленения.
Сети и потоки в сетях. Задача о максимальном потоке. Остаточные сети, дополняющие пути и разрезы. Теорема Форда-Фалкерсона о максимальном потоке и минимальном разрезе.
Наборы непересекающихся цепей, соединяющих два подмножества вершин графа (орграфа). Вершинная и реберная теоремы Менгера. Критерии вершинной и реберной k-связности графа (теоремы Уитни).
Обходы графов. Гамильтоновы циклы и цепи. Простейшие необходимые условия гамильтоновости графа. Достаточные условия: теоремы Оре и Дирака. Задача коммивояжера.
Эйлеровы циклы и цепи. Критерий эйлеровости графа. Алгоритм Флери.
Независимые множества вершин и ребер графа. Вершинные и реберные покрытия, факторы и паросочетания. Числовые параметры, связанные с независимостью и покрытиями, их свойства. Теорема Галлаи.
Наибольшие паросочетания и чередующиеся цепи. Характеризация наибольших паросочетаний в терминах чередующиеся цепей.
Паросочетания, покрывающие долю двудольного графа. Связь с системами различных представителей. Теоремы Холла, Кенига-Холла и Кенига-Оре.
Теоремы Кенига о числе реберной независимости двудольного графа и (0,1)-матрицах. Связь между задачами о наибольшем паросочетании, о наименьшем вершинном покрытии и о максимальном потоке. Задача о назначениях.
Критерий Татта существования 1-фактора в произвольном графе. Теоремы Петерсена о 2-факторах. Теоремы об 1-факторизуемости и 2-факторизуемости полных графов.
Плоские и планарные графы. Грани плоского графа. Нормальные карты и эйлеровы многогранники.
Формула Эйлера и ее следствия. Оценки для числа ребер планарных графов. Максимальные планарные графы, плоские триангуляции и четыреангуляции.
Понятие k-вырожденного графа. Оценки для числа вырожденности планарных графов.
Критерий планарности Понтрягина-Куратовского.
Геометрическая двойственность плоских графов. Двойственность платоновых многогранников.
Укладки графов на двумерных поверхностях. Эйлерова характеристика поверхности. Род, крупность, толщина и число скрещиваний графа.
Раскраски вершин графов, k-раскрашиваемые, k-хроматические и критические графы. Хроматическое числа графа, его простейшие оценки. Раскраска k-вырожденных графов. Теорема Брукса.
Вершинные раскраски графов без треугольников. Графы Мцельского. Хроматическое число графа с большим обхватом.
Совершенные графы. Теорема о дополнении совершенного графа (малая гипотеза Бержа). Теорема о характеризации совершенных графов (большая гипотеза Бержа). Хордальные графы, их характеризация и совершенство.
Хроматические полиномы, их свойства. Нерешенные задачи, связанные с хроматическими полиномами.
Раскраски планарных графов и карт. Теорема о четырех красках, ее эквивалентные формулировки: теорема Тейта и гипотеза Хадвигера.
Доказательство теоремы о пяти красках. Достаточные условия Грецша и Грюнбаума 3-раскрашиваемости плоских графов.
Раскраски графов, уложенных на двумерных поверхностях. Хроматическое число поверхности. Теорема Хивуда о раскраске карт.
Раскраски ребер графов и мультиграфов. Понятие хроматического индекса. Теоремы Визинга и Шэннона, неулучшаемость их оценок. Хроматический индекс двудольного графа.
Предписанные раскраски вершин и ребер графов. Связь между обычными и предписанными раскрасками. Оценка предписанного хроматического числа через число вырожденности графа.
Предписанное хроматическое число полного двудольного графа. Критерий предписанной 2-раскрашиваемости.
Теорема Томассена о предписанной 5-раскрашиваемости плоских графов.
Предписанный хроматический индекс двудольного графа. Гипотеза о предписанном хроматическом индексе.
Теорема Рамсея для множеств и графов. Оценки для чисел Рамсея. Обобщения чисел Рамсея.
Вероятностные методы в теории графов. Моделирование случайных графов. Некоторые свойства "почти всех” графов.

ДИСКРЕТНЫЙ АНАЛИЗ И КОМБИНАТОРИКА
1. Комбинаторика перечисления и кодирование.

Системы счисления и кодирование натуральных чисел. Задачи о нумерациях подмножеств конечного множества. Коды Грея. Нумерации объектов в порядке минимального изменения. -нумерации множества слов. Алгоритмы построения нумерующих отображений. Отображения конечных множеств, их кодирование и подсчет числа. Кодирование деревьев. Число деревьев. Примеры подсчёта с помощью рекуррентных уравнений и производящих функций.

Комбинаторика слов.

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

Универсальные слова. Задачи восстановления символьных последовательностей по их фрагментам. Коды без перекрытий. Комбинаторная сложность слов. Псевдослучайные последовательности. Последовательности де Брейна и их число. Графы перекрытия подслов символьных последовательностей. Задачи быстрой сборки слов. Алгоритмы сборки. Аддитивная сложность символьных последовательностей и ее связь с задачами быстрого умножения и вычисления полиномов. Оценки аддитивной сложности индивидуальных последовательностей.

3. Кодирование структурированной информации и вложения дискретных пространств.

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

Гиперкубовая архитектура вычислительных систем. Графы гиперкубов. Кодирование дискретных объектов и вложения в гиперкубы. Изоморфные и изометрические вложения. Вложения с растяжением ребер. Алгоритмы построения вложений.

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

4. Булевы функции и дискретные модели генных сетей.

Булевы функции, их число, способы задания. Представление формулами. Нормальные формы. Единственность совершенной и сокращённой форм. Представления многочленами Жегалкина. Полнота систем булевых функций. Теорема Поста. K-значные логические функции. Схемы из функциональных элементов. Конечные автоматы.

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

Группы: основные понятия, определения
1. Симметрическая группа
2. Гипероктаэдральная группа
Графы: основные понятия, определения
1. Регулярные и транзитивные графы
2. Дистанционно–регулярные и дистанционно–транзитивные графы
Графы Кэли
1. Простейшие примеры графов Кэли
2. Основные свойства графов Кэли
3. Граф Хэмминга: дистанционно-транзитивный граф Кэли
4. Граф Джонсона: дистанционно-транзитивный граф, не являющийся

графом Кэли

Граф Кнезера: когда он является графом Кэли?
Графы Кэли на симметрической группе
Графы Кэли на гипероктаэдральной группе

2. Гамильтоновость. Графов Кэли

Гамильтоновость гиперкуба
Комбинаторные условия гамильтоновости
Гипотезы Ловаса и Бабаи
Гамильтоновость графов Кэли на произвольной конечной группе
Гамильтоновость графов Кэли на симметрической группе
Гамильтоновость Pancake графа
Другие циклы Pancake графа
1. Циклы длины шесть
2. Циклы длины семь

3. Задача определения диаметра графов Кэли

Диаметр графов Кэли на абелевых и неабелевых группах.
Диаметр графов Кэли на симметрической и знакопеременной группах
Pancake problem: комбинаторная задача в информатике и биоинформатике
1. Оценки Гейтса и Пападимитроу на диаметр Pancake графа
2. Улучшенные оценки Садбороу
3. Точные значения диаметра Pancake графа
Burnt Pancake problem: обобщение Pancake problem
1. Оценки Кохена и Блюма на диаметр Burnt Pancake граф
2. Улучшенные оценки Хейдари и Садбороу
3. Точные значения диаметра Burnt Pancake графа

1 2 3 4 5 6 7 8 9 10 11

	Российской федерации приказ Российской Федерации об охране здоровья граждан от 22 июля 1993 г. N 5487-1 (Ведомости Съезда народных депутатов Российской Федерации...		Без гражданства в российской федерации Российской Федерации, на свободное передвижение, выбор места пребывания и жительства в пределах Российской Федерации и других прав...
	Доклад Правительства Российской Федерации Президенту Российской Федерации... «О мерах по реализации Указа Президента Российской Федерации от 28 июня 2007 г. №825 «Об оценке эффективности деятельности органов...		Национальный стандарт российской федерации Цели и принципы стандартизации в Российской Федерации установлены Федеральным законом от 27 декабря 2002 г. N 184-фз "О техническом...
	Национальный стандарт российской федерации Цели и принципы стандартизации в российской Федерации установлены Федеральным законом от 27 декабря 2002 г. №184-фз «О техническом...		Министерство экономического развития российской федерации Указом Президента Российской Федерации от 01. 02. 2005 n 112 "О конкурсе на замещение вакантной должности государственной гражданской...
	Комплексная программа 5-11 классы Под общей редакцией А. Т. Смирнова Конституции Российской Федерации и федеральных законов Российской Федерации в области безопасности жизнедеятельности, Стратегии национальной...		Национальный стандарт российской федерации автомобили скорой медицинской помощи Цели и принципы стандартизации в Российской Федерации установлены Федеральным законом от 27 декабря 2002 г. N 184-фз "О техническом...
	Комментарий к уголовно-процессуальному кодексу российской федерации Смирнов А. В., доктор юридических наук, профессор, советник Конституционного Суда Российской Федерации, действительный государственный...		Министерство здравоохранения российской федерации главный государственный санитарный врач Российской Федерации, 1999, n 14, ст. 1650) и "Положения о государственном санитарно-эпидемиологическом нормировании", утвержденного...
	Министерство здравоохранения российской федерации главный государственный санитарный врач Российской Федерации, 1999, n 14, ст. 1650) и "Положения о государственном санитарно-эпидемиологическом нормировании", утвержденного...		Министерство здравоохранения российской федерации главный государственный санитарный врач Российской Федерации, 1999, n 14, ст. 1650) и "Положения о государственном санитарно-эпидемиологическом нормировании", утвержденного...
	Утверждаю Президент Российской Федерации В. Путин стратегия развития... Российской Федерации в Арктике на период до 2020 года и дальнейшую перспективу, утвержденных Президентом Российской Федерации 18...		Министерство связи и массовых коммуникаций российской федерации Российской Федерации от 1 февраля 2005 г n 112 "О конкурсе на замещение вакантной должности государственной гражданской службы Российской...
	Национальный стандарт российской федерации гост р 53423- 2009 Цели и принципы стандартизации в Российской Федерации установлены Федеральным законом от 27 декабря 2002 г. №184-фз «О техническом...		Об утверждении порядка Основ законодательства Российской Федерации об охране здоровья граждан от 22 июля 1993 г. N 5487-1 (Ведомости Съезда народных депутатов...

Российской федерации

Похожие: