Лекции 34 часа Экзамен нет семинары 17 часов Зачет с оценкой 7 семестр лабораторные занятия нет
|
Скачать 42.31 Kb.
|
министерство образования и науки российской федерации Московский физико-технический институт (государственный университет) УТВЕРЖДАЮ Проректор по учебной работе Ю.А. Самарский « 20 » июня 2011 г. П Р О Г Р А М М Апо курсу КОЛМОГОРОВСКАЯ СЛОЖНОСТЬ И ЕЕ ПРИЛОЖЕНИЯ по направлению 010900 факультет ФУПМ кафедра математических основ управления курс IV семестр 7 лекции – 34 часа Экзамен – нет семинары – 17 часов Зачет с оценкой – 7 семестр лабораторные занятия – нет Самостоятельная работа – 2 часа в неделю ВСЕГО ЧАСОВ – 51 Программу составил д.ф.-м.н., проф. В.В. Вьюгин Программа обсуждена на заседании кафедры математических основ управления 17 мая 2011 года Заведующий кафедрой С.А. Гуз I. Определение колмогоровской сложности и ее свойства 1. Алфавиты, конструктивные объекты, их примеры. Понятие алгоритма, вычислимые функции. Формализация понятия алгоритма: частично-рекурсивные функции, машины Тьюринга и др. Идея построения универсальной машины Тьюринга. Универсальная функция. 2. Простая колмогоровская сложность. Теорема инвариантности (теорема существования). Простейшие свойства колмогоровской сложности. Невычислимость сложности. Верхние оценки сложности. Несжимаемые последовательности. 3. Сложность пары конечных объектов. Условная сложность. Теорема Колмогорова–Левина о сложности пары. Количество информации. Свойство симметричности функции информации. Энтропия Шеннона. Связь сложности и энтропии Шеннона. 4. Колмогоровский сложностной подход к обоснованию теории вероятностей. Разбиения конечного множества. Дефект случайности по Колмогорову. Определение случайной конечной последовательности по Колмогорову. Бернуллиевские последовательности по Колмогорову. Стохастические по Колмогорову последовательности. Существование нестохастических последовательностей. Колмогоровская достаточная статистика. Как возникают распределения вероятностей? II. Случайность по Мартин-Лефу и сложность 5. Конструктивный анализ теории вероятностей. Пространство бесконечных двоичных последовательностей, задание мер на нем. Вычислимые меры. Эффективно нулевые множества. Существование максимального по включению эффективно-нулевого множества. Случайность по Мартин-Лефу. Дефект случайности. Логика теории вероятностей. Законы теории вероятностей, их формулировки для индивидуальных случайных последовательностей. Закон больших чисел и закон повторного логарифма. 6. Методы кодирования: код Шеннона и код Хаффмана. Неравенство Крафта. Префиксная сложность, ее существание и свойства. Перечислимые множества и предельно вычислимые функции. Априорная полумера на конечных последовательностях и ее связь с префиксной сложностью. Префиксные машины Тьюринга (машины с самоограниченным входом). Соотношение между префиксной и простой колмогоровской сложностью. Условная префиксная сложность. Представление префиксной сложности пары. Количество информации и префиксная сложность. Симметричность функции информации. 7. Монотонная сложность, ее существование. Вычислимые монотонные операции на последовательностях. Соотношение между монотонной, префиксной и простой колмогоровской сложностями. Эквивалентные определения случайной по Мартин-Лефу последовательности с помощью префиксной и монотонной сложности (теорема Левина–Шнорра). 8. Априорная перечислимая полумера на последовательностях, ее построение и свойства. Связь с монотонной сложностью. Определение случайной последовательности с помощью априрной полумеры. Перечислимые снизу супермартингалы. Вычислимые мартингалы. III. Применения колмогоровской сложности в различных областях математики 9. Нижняя граница для числа сравнений при сортировке. Плотность простых чисел. Случайные графы. Нижние оценки для расстояния между точками при заполнении плоской решетки. Средняя длина наиболее длинной общей подпоследовательности. Оценки уклонений для многомерного случайного блуждания. 10. Объекты и модели для их описания. Принцип минимальной длины описания MDL и колмогоровская сложность. 11. Правила выбора по Мизесу и Колмогорову–Лавлэнду. Свойство устойчивости частот в подпоследовательностях для конечных последовательностей с малым дефектом случайности. Сложностные доказательства законов больших чисел, закона повторного логарифма. Литература
Доступно онлайн: http://www.lif.univ-mrs.fr/~ashen/nafit/kolmbook.pdf 3. Li M., Vitanyi P. An Introduction to Kolmogorov Complexity and Its Applications, 2nd ed. – New York: Springer – Verlag, 1997. 4. V'yugin V.V. Algorithmic complexity and stochastic properties of finite binary sequences // The Computer Journal. – 1999. – V. 42, N 4. – P. 294–317. Доступно онлайн: http://www.iitp.ru/upload/publications/1629/surv3.pdf 5. Колмогоров А.Н. Три подхода к определению понятия «количество нформации» // Проблемы передачи информации, Т. 1, № 1, 1965. – С. 3–11. Подписано в печать 20.06.11. Формат 60 ´ 84  . Бумага офсетная. Печать офсетная. Усл. печ. л. 0,25. Уч.-изд. л. 0,2. Тираж 200 экз. Заказ № 42 Государственное образовательное учреждение высшего профессионального образования «Московский физико-технический институт (государственный университет)» Отдел оперативной полиграфии 141700, Московская обл., г. Долгопрудный, Институтский пер., 9 |
Похожие:
 | Лекции 34 часа Экзамен нет семинары 34 часа Зачет с оценкой 3 семестр лабораторные занятия нет Программа обсуждена на заседании кафедры математических основ управления 15 мая 2011 г | | Лекции 32 часа Экзамен нет семинары 32 часа Зачет с оценкой 8 семестр лабораторные занятия нет Охватывает более простые, главным образом «одномерные» методы; третье задание относится к анализу существенно многомерных данных |
| Лекции 32 часа Экзамен 8 семестр семинары -нет Зачет с оценкой нет лабораторные занятия нет Некоторые задачи, приводящие к стохастическим аналогам обыкновенных дифференциальных уравнений (стохастические модели, возникающие... | | Лекции 32 часа Экзамен нет семинары нет Зачёт с оценкой 4 семестр лабораторные занятия 32 часа Понятия базы данных, системы баз данных и субд. Требования к субд. Характеристики, функции субд |
| Лекции 64 часа Экзамен 5,6 семестр семинары 64 часа Зачет нет лабораторные занятия нет Постановка задач оптимизации. Локальный и глобальный экстремумы. Классификация экстремальных задач. Примеры | | Лекции 34 часов Экзамен 11 семестр семинары нет Зачет нет лабораторные занятия нет Приближенные алгоритмы с гарантированными оценками точности. Анализ точности жадного алгоритма в задачах о покрытии, вершинном покрытии... |
| Лекции 50 часов Экзамен 8 семестр семинары 50 часов Зачет нет лабораторные занятия нет Основная задача оптимального управления. Понятие слабого и сильного минимума. Задача Лагранжа и задача вариационного исчисления.... |  | Семинары нет Зачёт нет лабораторные занятия 16 часов самостоятельная работа 2 часа в неделю Программа утверждена на заседании кафедры математических основ управления 18 марта 2005 г |
| Лекции 66 часов Экзамен 5,6 семестр практические занятия 66 часа Диф зачет нет самостоятельная работа 20 часов Постановка задач оптимизации. Локальный и глобальный экстремумы. Классификация экстремальных задач. Примеры | | Лекции 32 часа Экзамен нет практические (семинарские ) занятия 32 часа Диф зачет 4 семестр Асимптотические обозначения (O, Ω, θ, o, ω) и их свойства (транзитивность, рефлексивность, симметричность, обращение) |