Лекции 34 часа Экзамен нет семинары 17 часов Зачет с оценкой 7 семестр лабораторные занятия нет



Скачать 42.31 Kb.
Дата20.05.2013
Размер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. Правила выбора по Мизесу и КолмогоровуЛавлэнду. Свойство устойчивости частот в подпоследовательностях для конечных последовательностей с малым дефектом случайности. Сложностные доказательства законов больших чисел, закона повторного логарифма.

Литература


  1. Вьюгин В.В. Алгоритмическая энтропия (сложность) конечных объектов и ее применения к определению случайности и количества информации // Семиотика и информатика: сб. научн. тр.: вып. 16 /ВИНИТИ – М., 1981. – C.14–43.

  2. Успенский В.А., Верещагин Н.К., Шень А. Колмогоровская сложность и алгоритмическая случайность. – М.: МЦНМО, 2010. – 556 с.

Доступно онлайн:
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 часа Экзамен нет семинары 17 часов Зачет с оценкой 7 семестр лабораторные занятия нет iconЛекции 34 часа Экзамен нет семинары 34 часа Зачет с оценкой 3 семестр лабораторные занятия нет
Программа обсуждена на заседании кафедры математических основ управления 15 мая 2011 г
Лекции 34 часа Экзамен нет семинары 17 часов Зачет с оценкой 7 семестр лабораторные занятия нет iconЛекции 32 часа Экзамен нет семинары 32 часа Зачет с оценкой 8 семестр лабораторные занятия нет
Охватывает более простые, главным образом «одномерные» методы; третье задание относится к анализу существенно многомерных данных
Лекции 34 часа Экзамен нет семинары 17 часов Зачет с оценкой 7 семестр лабораторные занятия нет iconЛекции 32 часа Экзамен 8 семестр семинары -нет Зачет с оценкой нет лабораторные занятия нет
Некоторые задачи, приводящие к стохастическим аналогам обыкновенных дифференциальных уравнений (стохастические модели, возникающие...
Лекции 34 часа Экзамен нет семинары 17 часов Зачет с оценкой 7 семестр лабораторные занятия нет iconЛекции 32 часа Экзамен нет семинары нет Зачёт с оценкой 4 семестр лабораторные занятия 32 часа
Понятия базы данных, системы баз данных и субд. Требования к субд. Характеристики, функции субд
Лекции 34 часа Экзамен нет семинары 17 часов Зачет с оценкой 7 семестр лабораторные занятия нет iconЛекции 64 часа Экзамен 5,6 семестр семинары 64 часа Зачет нет лабораторные занятия нет
Постановка задач оптимизации. Локальный и глобальный экстремумы. Классификация экстремальных задач. Примеры
Лекции 34 часа Экзамен нет семинары 17 часов Зачет с оценкой 7 семестр лабораторные занятия нет iconЛекции 34 часов Экзамен 11 семестр семинары нет Зачет нет лабораторные занятия нет
Приближенные алгоритмы с гарантированными оценками точности. Анализ точности жадного алгоритма в задачах о покрытии, вершинном покрытии...
Лекции 34 часа Экзамен нет семинары 17 часов Зачет с оценкой 7 семестр лабораторные занятия нет iconЛекции 50 часов Экзамен 8 семестр семинары 50 часов Зачет нет лабораторные занятия нет
Основная задача оптимального управления. Понятие слабого и сильного минимума. Задача Лагранжа и задача вариационного исчисления....
Лекции 34 часа Экзамен нет семинары 17 часов Зачет с оценкой 7 семестр лабораторные занятия нет iconСеминары нет Зачёт нет лабораторные занятия 16 часов самостоятельная работа 2 часа в неделю
Программа утверждена на заседании кафедры математических основ управления 18 марта 2005 г
Лекции 34 часа Экзамен нет семинары 17 часов Зачет с оценкой 7 семестр лабораторные занятия нет iconЛекции 66 часов Экзамен 5,6 семестр практические занятия 66 часа Диф зачет нет самостоятельная работа 20 часов
Постановка задач оптимизации. Локальный и глобальный экстремумы. Классификация экстремальных задач. Примеры
Лекции 34 часа Экзамен нет семинары 17 часов Зачет с оценкой 7 семестр лабораторные занятия нет iconЛекции 32 часа Экзамен нет практические (семинарские ) занятия 32 часа Диф зачет 4 семестр
Асимптотические обозначения (O, Ω, θ, o, ω) и их свойства (транзитивность, рефлексивность, симметричность, обращение)
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org