Лекции 34 часа Экзамен нет семинары 17 часов Зачет с оценкой 7 семестр лабораторные занятия нет - polpoz.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
4 зачетных единицы, общий объем часов 144, в том числе: 36 часов... 1 577.9kb.
Лекции 28 коллоквиумы 8 практические занятия нет лабораторные занятия... 1 117.38kb.
Лекции: 32 часа практические занятия: 32 часа курсовая работа: 6... 1 46.14kb.
Модуль Общие положения бренд-менеджмента – 2 зет лекция Бренд-менеджмент... 1 62.33kb.
Лекции 4, Установочные лекции 4, Лабораторные работы 8, Практические... 1 31.33kb.
Количество часов: 144( в т ч.: 8 ч лекции, 6 ч практические занятия... 1 11.46kb.
Рабочая программа специальность 080504 государственное и мунииципальное... 1 231.41kb.
Дисциплина трудоёмкостью 5,5 зачётных единиц или 216 часов. 1 25.35kb.
Лекции 14 (час.) практические занятия 14 час семинарские занятия... 1 177.86kb.
Нет – Новому Царю! нет – Изменению Конституции! нет – Наш ответ на... 1 19.91kb.
Лекции: 36 Семинары: 36 Форма итогового контроля: зачет Структура... 1 52.82kb.
Урок математики в 5 классе по теме «Среднее арифметическое» Дата... 1 45.31kb.
1. На доске выписаны n последовательных натуральных чисел 1 46.11kb.

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



министерство образования и науки российской федерации

Московский физико-технический институт

(государственный университет)
УТВЕРЖДАЮ

Проректор по учебной работе

Ю.А. Самарский

« 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