Алгоритмы, модели, алгебры (курс лекций, Ю.И. Журавлев, А.Г. Дьяконов)

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: == АЛГОРИТМЫ, МОДЕЛИ, АЛГЕБРЫ == * Обязательный курс для студентов каф. ММП 3 курса, читается в 6-м семестр...)
(Содержание курса)
(377 промежуточных версий не показаны.)
Строка 1: Строка 1:
-
== АЛГОРИТМЫ, МОДЕЛИ, АЛГЕБРЫ ==
+
== ПРИКЛАДНЫЕ ЗАДАЧИ АНАЛИЗА ДАННЫХ (курс для магистров ММП ВМК МГУ) ==
-
* Обязательный курс для студентов каф. ММП 3 курса, читается в 6-м семестре.
+
* Обязательный курс для магистров каф. [[ММП]] 1 г/о, читается в 1(9-м) семестре.
-
* Лекции – 32 часа, семинаров нет.
+
* Лекции — 36 часов, семинаров - 36 часов.
* Экзамен.
* Экзамен.
* За курс отвечает кафедра Математических методов прогнозирования.
* За курс отвечает кафедра Математических методов прогнозирования.
-
* Авторы программы: академик РАН Ю.И.Журавлёв, доцент А.Г. Дьяконов.
+
* Автор программы: профессор [[Участник:Dj|{{S|А. Г. Дьяконов}}]].
-
* Лектор 2007/08 уч. года: доцент А.Г. Дьяконов.
+
 +
 +
 +
 +
{{notice|
 +
'''Как будет проходить экзамен:'''
 +
 +
* Есть система штрафных баллов, по ней формируется итоговая оценка.
 +
* Пороги для конкретных оценок (по сумме баллов) объявлены изначально, но могут быть откорректированы лектором в пользу студентов.
 +
* Сам экзамен проводится письменно - на нём (при желании) можно улучшить итоговую оценку
 +
 +
хорошее написание письменного экзамена увеличивает итоговую оценку на 1 балл (порог будет заранее объявлен), безупречное написание - на 2 балла.
 +
 +
* Итоговая "отлично" ставится автоматом.
 +
* Итоговая "неудовлетворительно" также ставится автоматом и означает недопуск к экзамену, чтобы получить допуск надо сдать все несданные задания (итоговая оценка при этом не меняется и может быть исправлена только на самом экзамене). Перечень заданий для допуска определяется персонально с учётом заданий, сданных во время семестра.
 +
 +
 +
'''Содержание экзамена:''' задания эквивалентные заданиям со всех контрольных и семинаров (плюс задания по спектральной теории графов, плюс задания на знания теории и определений, если они были на лекциях и продублированы в списке рекомендуемой литературы, плюс задания на знания языков/библиотек, если они обсуждались на семинарах и лекциях)
 +
 +
 +
 +
* Экзамен проходит по жёсткой схеме: нельзя пользоваться ничем (кроме ручки и листка бумаги). Аналогично контроль сдаваемых заданий после окончания семестра жёсткий: лектор уже не консультирует по самим заданиям, презентации оцениваются по формальным критериям: наличие постановки задачи, описание предложенных методов, их обоснование, подробное изложение экспериментов (с графиками и таблицами), формирование итоговой модели, выводы. Оценивается и сам доклад по задаче!
 +
 +
}}
== Аннотация ==
== Аннотация ==
-
Первая часть курса «Алгоритмы, модели, алгебры» для студентов каф. ММП посвящена алгебраическому подходу к решению задач распознавания образов. Основы этого подхода заложены в работах академика РАН Ю.И. Журавлёва и развиты затем его учениками. Сам подход имеет приложения не только в теории распознавания образов, но и в теории коррекции алгоритмов, которые на выходе получают числовую информацию. Студентам излагается новая техника построения и исследования алгоритмических конструкций. Для иллюстрации её «мощности» приведены решения нескольких достаточно сложных проблем: оценки степени корректного полинома, получения критериев корректности и квазикорректности.
+
Курс посвящён решению прикладных задач анализа данных.
-
Вторая часть курса посвящена логическим алгоритмам распознавания, основанным на синтезе ДНФ. Описываются модели алгоритмов, способы решения задачи построения ДНФ по перечню её нулевых наборов. Особое внимание уделяется практическим вопросам: как на ЭВМ реализовать эффективный алгоритм синтеза ДНФ специального вида. Рассматриваются также вопросы построения нормальных форм в k-значном случае.
+
Разбираются реальные задачи и бизнес-кейсы.
-
Несмотря на отсутствие семинаров по курсу, студентам на каждой лекции даются достаточно сложные задания, выполнение которых «моделирует исследовательскую научную работу». Решения заданий потом подробно разбираются.
+
Студенты пишут и настраивают алгоритмы на языках Python, R, M (Matlab).
-
По материалам курса составлено учебное пособие. В настоящее время ведётся подготовка ещё одного пособия (по дискретной части) и задачника.
+
 
 +
Семинары посвящены
 +
* докладам по решению прикладных задач (с презентациями),
 +
* опросам по выполнению домашнего задания,
 +
* обучению программированию на скриптовых языках (для тех, у кого их не было в бакалавриате),
 +
* мозговому штурму по решению задач и обсуждению решений,
 +
* написанию контрольных работ, решению аналитических задач, работе над ошибками.
 +
 
 +
== Система оценивания ==
 +
 
 +
В течение семестра студенты получают задания.
 +
 
 +
При сдаче правильно выполненного задания '''в срок''' студент не получает штрафных баллов.
 +
 
 +
В противном случае - он получает от 1 до 10 штрафных баллов.
 +
 
 +
Штраф в 10 баллов допустим за позднюю сдачу (даже если решение верное)
 +
в случае отсутствия уважительных причин (болезнь, подтверждаемая справкой, и т.п. -
 +
см. требования учебной части).
 +
 
 +
В некоторых случаях (на усмотрение лектора), магистру, который лучше всех выполнил конкретное задание,
 +
списываются штрафные баллы (до 10).
 +
 
 +
На экзамене также за неверные ответы студент получает штрафные баллы.
 +
 
 +
 
 +
Итоговая оценка формируется следующим образом:
 +
* до 10 штрафных баллов включительно - отлично,
 +
* до 20 штрафных баллов включительно - хорошо,
 +
* до 30 штрафных баллов включительно - удовлетворительно.
== Содержание курса ==
== Содержание курса ==
-
Лекции, 6 семестр
+
 
-
=== 1. Введение ===
+
В этом году все материалы выкладываются здесь: https://github.com/Dyakonov/PZAD.
-
1.1. Введение. Задача распознавания образов с прецедентной информацией (напоминание постановки, введение терминологии, обозначений). Направления исследований в теории распознавания: синтез алгоритмов, оценка надёжности обучения, анализ конфигураций точек в признаковых пространствах.
+
 
-
1.2. Алгебраический подход к проблеме распознавания.
+
Сдача ДЗ:
-
1.3. Пример анализа конфигураций точек в признаковых пространствах: получение критерия разделимости точек.
+
* Необязательное (лекция-1): https://www.kaggle.com/c/pzadbabki/discussion/65863/
-
=== 2. Алгоритмы вычисления оценок (АВО), алгебраические замыкания ===
+
* Игра "Что за данные" ('''к 23.09.2018'''): https://www.kaggle.com/c/pzadbabki/discussion/66104
-
2.1. Модель АВО (введение, основные обозначения, примеры, общие принципы).
+
* Необязательное (лекция-2): https://www.kaggle.com/c/pzadbabki/discussion/65863 (та же ветка, что и для )
-
2.2. Линейное и алгебраическое замыкание модели алгоритмов распознавания.
+
* Визуализация внешних данных ('''к 30.09.2018'''): - https://www.kaggle.com/c/pzadbabki/discussion/66107
-
2.3. Техника представления алгоритмов из линейного замыкания АВО.
+
 
-
2.4. Функция близости (определение, примеры, общие принципы). Сведение к задачам с определённой функцией близости.
+
Все вопросы можно задавать в соответствующих ветках форума.
-
=== 3. Корректность, операторы разметки ===
+
 
-
3.1. Операторы разметки. Матрицы оценок операторов. Теорема о реализации любых матриц (для любой матрицы из описанного класса существует соответствующая задача распознавания).
+
== Успеваемость ==
-
3.2. Корректность (определение). Критерий корректности (теорема Ю.И. Журавлёва).
+
 
-
3.3. Оценка степени корректного алгоритма.
+
Здесь будет рейтинг студентов...
-
3.4. Построение корректных алгоритмов распознавания (метод Ю.И. Журавлёва – И.В. Исаева).
+
 
-
=== 4. Метрики алгебраических замыканий модели АВО ===
+
-
4.1. Метрики алгебраических замыканий, метрические критерии корректности.
+
-
4.2. Обзор (без доказательства) некоторых результатов теории жёсткой интерполяции.
+
-
4.3. Анализ некоторых классов точечных конфигураций (включая задания для самостоятельной работы).
+
-
=== 5. Решающие правила, квазикорректность ===
+
-
5.1. Решающие правила.
+
-
5.2. Критерии квазикорректности (корректности относительно семейства решающих правил). Обзор (без доказательств) некоторых современных результатов.
+
-
5.3. Пополнение стандартной алгебры над АВО.
+
-
=== 6. Логические алгоритмы распознавания ===
+
-
6.1. Логические алгоритмы распознавания (напоминания, краткий обзор, основные определения и обозначения).
+
-
6.2. Алгоритмы, основанные на синтезе ДНФ. Задача синтеза ДНФ по перечню нулевых наборов (обзор некоторых методов). Формула С.В. Яблонского. Методы Ю.И. Журавлёва, А.Ю. Когана.
+
-
=== 7. Синтез ДНФ по перечню нулевых наборов ===
+
-
7.1. Тестовый подход к задаче ДНФ-реализации. Оценка сложности. Построение тупиковых ДНФ. Построение ДНФ специального вида. Построение явных ДНФ-формул.
+
-
7.2. Построение ДНФ последовательным умножением. Умножение ДНФ. Обобщение метода С.В. Яблонского. Эффективная реализация метода Нельсона.
+
-
7.3. ДНФ-реализация функций k-значной логики. Различные определения ДНФ в k-значном случае. Кодировки.
+
== Литература ==
== Литература ==
-
* 1. Дьяконов А.Г. Алгебра над алгоритмами вычисления оценок: Учебное пособие.– М.: Издательский отдел ф-та ВМиК МГУ им. М.В. Ломоносова, 2006. – 72с. (ISBN 5-89407-252-2)
+
Указана локально - в слайдах / сетке расписания.
-
* 2. Журавлёв Ю.И. Избранные научные труды. – М.: «Магистр», 1998.– 420с.
+
 
-
* 3. Черников С.Н. Линейные неравенства. М. Наука. 1968. 488 с.
+
== История ==
-
* 4. Дискретная математика и математические вопросы кибернетики / Под ред. С.В. Яблонского и О.Б. Лупанова. – М.: Наука, 1974. – 312с.
+
Программы прошлых лет см. здесь:
-
* 5. Дюкова Е.В. Дискретные (логические) процедуры распознавания: принципы конструирования, сложность реализации и основные модели / Учебное пособие для студентов математических факультетов педвузов. – М.: Прометей, 2003. – С. 29. (ISBN 5-70420-1092-9)
+
* [[Прикладные задачи анализа данных (курс на ВМК 2017 года)]]
 +
* [[Прикладные задачи анализа данных (курс на ВМК 2016 года)]]
 +
* [[Алгоритмы, модели, алгебры (курс на ВМК 2015 года)]]
 +
* [[Алгоритмы, модели, алгебры (курс на ВМК до 2015 года)]]
 +
 
 +
[[Категория:Учебные курсы]]
 +
[[Категория:МГУ]]

Версия 10:19, 18 сентября 2018

Содержание

ПРИКЛАДНЫЕ ЗАДАЧИ АНАЛИЗА ДАННЫХ (курс для магистров ММП ВМК МГУ)

  • Обязательный курс для магистров каф. ММП 1 г/о, читается в 1-м (9-м) семестре.
  • Лекции — 36 часов, семинаров - 36 часов.
  • Экзамен.
  • За курс отвечает кафедра Математических методов прогнозирования.
  • Автор программы: профессор А. Г. Дьяконов.



Как будет проходить экзамен:
  • Есть система штрафных баллов, по ней формируется итоговая оценка.
  • Пороги для конкретных оценок (по сумме баллов) объявлены изначально, но могут быть откорректированы лектором в пользу студентов.
  • Сам экзамен проводится письменно - на нём (при желании) можно улучшить итоговую оценку

хорошее написание письменного экзамена увеличивает итоговую оценку на 1 балл (порог будет заранее объявлен), безупречное написание - на 2 балла.

  • Итоговая "отлично" ставится автоматом.
  • Итоговая "неудовлетворительно" также ставится автоматом и означает недопуск к экзамену, чтобы получить допуск надо сдать все несданные задания (итоговая оценка при этом не меняется и может быть исправлена только на самом экзамене). Перечень заданий для допуска определяется персонально с учётом заданий, сданных во время семестра.


Содержание экзамена: задания эквивалентные заданиям со всех контрольных и семинаров (плюс задания по спектральной теории графов, плюс задания на знания теории и определений, если они были на лекциях и продублированы в списке рекомендуемой литературы, плюс задания на знания языков/библиотек, если они обсуждались на семинарах и лекциях)


  • Экзамен проходит по жёсткой схеме: нельзя пользоваться ничем (кроме ручки и листка бумаги). Аналогично контроль сдаваемых заданий после окончания семестра жёсткий: лектор уже не консультирует по самим заданиям, презентации оцениваются по формальным критериям: наличие постановки задачи, описание предложенных методов, их обоснование, подробное изложение экспериментов (с графиками и таблицами), формирование итоговой модели, выводы. Оценивается и сам доклад по задаче!


Аннотация

Курс посвящён решению прикладных задач анализа данных. Разбираются реальные задачи и бизнес-кейсы. Студенты пишут и настраивают алгоритмы на языках Python, R, M (Matlab).

Семинары посвящены

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

Система оценивания

В течение семестра студенты получают задания.

При сдаче правильно выполненного задания в срок студент не получает штрафных баллов.

В противном случае - он получает от 1 до 10 штрафных баллов.

Штраф в 10 баллов допустим за позднюю сдачу (даже если решение верное) в случае отсутствия уважительных причин (болезнь, подтверждаемая справкой, и т.п. - см. требования учебной части).

В некоторых случаях (на усмотрение лектора), магистру, который лучше всех выполнил конкретное задание, списываются штрафные баллы (до 10).

На экзамене также за неверные ответы студент получает штрафные баллы.


Итоговая оценка формируется следующим образом:

  • до 10 штрафных баллов включительно - отлично,
  • до 20 штрафных баллов включительно - хорошо,
  • до 30 штрафных баллов включительно - удовлетворительно.

Содержание курса

В этом году все материалы выкладываются здесь: https://github.com/Dyakonov/PZAD.

Сдача ДЗ:

Все вопросы можно задавать в соответствующих ветках форума.

Успеваемость

Здесь будет рейтинг студентов...


Литература

Указана локально - в слайдах / сетке расписания.

История

Программы прошлых лет см. здесь:

Личные инструменты