Алгоритмы, модели, алгебры (курс на ВМК до 2015 года)

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

Содержание 1 АЛГОРИТМЫ, МОДЕЛИ, АЛГЕБРЫ 2 Аннотация 3 Содержание курса 3.1 Введение 3.2 Алгоритмы вычисления оценок (АВО), алгебраические замыкания 3.3 Корректность, операторы разметки 3.4 Метрики алгебраических замыканий модели АВО 3.5 Решающие правила, квазикорректность 3.6 Логические алгоритмы распознавания 3.7 Синтез ДНФ по перечню нулевых наборов 4 Литература

АЛГОРИТМЫ, МОДЕЛИ, АЛГЕБРЫ

• Обязательный курс для студентов каф. ММП 3 курса, читается в 6-м семестре.
• Лекции — 32 часа, семинаров нет.
• Экзамен.
• За курс отвечает кафедра Математических методов прогнозирования.
• Авторы программы: академик РАН Ю. И. Журавлёв, доцент А. Г. Дьяконов.

• Лекции второй части курса
• Задания «на каникулы»
• Задачи на экзамен (версия 2009 года!)

Задание студентам 317 группы на 10-24 апреля 2012 года Повторить все лекции Прочитать первую главу учебного пособия (стр. 3-8). Решить все задачи из задачника.

Аннотация

Первая часть курса «Алгоритмы, модели, алгебры» для студентов каф. ММП посвящена алгебраическому подходу к решению задач распознавания образов. Основы этого подхода заложены в работах академика РАН Ю.И. Журавлёва и развиты затем его учениками. Сам подход имеет приложения не только в теории распознавания образов, но и в теории коррекции алгоритмов, которые на выходе получают числовую информацию. Студентам излагается новая техника построения и исследования алгоритмических конструкций. Для иллюстрации её «мощности» приведены решения нескольких достаточно сложных проблем: оценки степени корректного полинома, получения критериев корректности и квазикорректности. Вторая часть курса посвящена логическим алгоритмам распознавания, основанным на синтезе ДНФ. Описываются модели алгоритмов, способы решения задачи построения ДНФ по перечню её нулевых наборов. Особое внимание уделяется практическим вопросам: как на ЭВМ реализовать эффективный алгоритм синтеза ДНФ специального вида. Рассматриваются также вопросы построения нормальных форм в k-значном случае. Несмотря на отсутствие семинаров по курсу, студентам на каждой лекции даются достаточно сложные задания, выполнение которых «моделирует исследовательскую научную работу». Решения заданий потом подробно разбираются. По материалам курса составлено учебное пособие. В настоящее время ведётся подготовка ещё одного пособия (по дискретной части) и задачника.

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

Лекции, 6 семестр

Введение

1.1. Введение. Задача распознавания образов с прецедентной информацией (напоминание постановки, введение терминологии, обозначений). Направления исследований в теории распознавания: синтез алгоритмов, оценка надёжности обучения, анализ конфигураций точек в признаковых пространствах. 1.2. Алгебраический подход к проблеме распознавания. 1.3. Пример анализа конфигураций точек в признаковых пространствах: получение критерия разделимости точек.

Алгоритмы вычисления оценок (АВО), алгебраические замыкания

2.1. Модель АВО (введение, основные обозначения, примеры, общие принципы). 2.2. Линейное и алгебраическое замыкание модели алгоритмов распознавания. 2.3. Техника представления алгоритмов из линейного замыкания АВО. 2.4. Функция близости (определение, примеры, общие принципы). Сведение к задачам с определённой функцией близости.

Корректность, операторы разметки

3.1. Операторы разметки. Матрицы оценок операторов. Теорема о реализации любых матриц (для любой матрицы из описанного класса существует соответствующая задача распознавания). 3.2. Корректность (определение). Критерий корректности (теорема Ю.И. Журавлёва). 3.3. Оценка степени корректного алгоритма. 3.4. Построение корректных алгоритмов распознавания (метод Ю.И. Журавлёва – И.В. Исаева).

Метрики алгебраических замыканий модели АВО

4.1. Метрики алгебраических замыканий, метрические критерии корректности. 4.2. Обзор (без доказательства) некоторых результатов теории жёсткой интерполяции. 4.3. Анализ некоторых классов точечных конфигураций (включая задания для самостоятельной работы).

Решающие правила, квазикорректность

5.1. Решающие правила. 5.2. Критерии квазикорректности (корректности относительно семейства решающих правил). Обзор (без доказательств) некоторых современных результатов. 5.3. Пополнение стандартной алгебры над АВО.

Логические алгоритмы распознавания

6.1. Логические алгоритмы распознавания (напоминания, краткий обзор, основные определения и обозначения). 6.2. Алгоритмы, основанные на синтезе ДНФ. Задача синтеза ДНФ по перечню нулевых наборов (обзор некоторых методов). Формула С.В. Яблонского. Методы Ю.И. Журавлёва, А.Ю. Когана.

Синтез ДНФ по перечню нулевых наборов

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)