Программа дисциплины Упорядоченные множества для анализа данных для направления 010500. 68 Прикладная математика и информатика подготовки магистра Автор Кузнецов С. О. () Рекомендована секцией умс «Прикладная математика и информатика»




Скачать 272.09 Kb.
НазваниеПрограмма дисциплины Упорядоченные множества для анализа данных для направления 010500. 68 Прикладная математика и информатика подготовки магистра Автор Кузнецов С. О. () Рекомендована секцией умс «Прикладная математика и информатика»
страница1/3
Дата26.09.2012
Размер272.09 Kb.
ТипПрограмма дисциплины
  1   2   3
Правительство Российской Федерации


Государственное образовательное бюджетное учреждение
высшего профессионального образования


Государственный университет –

Высшая школа экономики


Факультет БИЗНЕС-ИНФОРМАТИКИ


Программа дисциплины


Упорядоченные множества для анализа данных

для направления 010500.68 – Прикладная математика и информатика подготовки магистра


Автор Кузнецов С.О. (skuznetsov@hse.ru)


Рекомендована секцией УМС

«Прикладная математика

и информатика»


Председатель

__________________ Кузнецов С.О.

«_____» __________________ 2010 г.

Одобрена на заседании кафедры

Анализа данных

и искусственного интеллекта


Зав. кафедрой

__________________ Кузнецов С.О.

«_____» __________________ 2010 г.



Утверждена УС факультета

бизнес-информатики


Ученый секретарь

__________________ Фомичев В.А.

« ____» ___________________2010 г.






Москва


Программа дисциплины «Упорядоченные множества для анализа данных» для подготовки магистров по направлению 010500.68 (магистерская программа «математическое моделирование»)


I. Пояснительная записка

Автор программы: Доктор физико-математических наук С.О. Кузнецов

Требования к студентам: Изучение курса «Упорядоченные множества для анализа данных» требует предварительных знаний по элементарной теории множеств и отношений, булевой алгебре и теории алгоритмов (курс «Дискретная математика»).


Аннотация. Дисциплина «Упорядоченные множества для анализа данных» предназначена для подготовки магистров по направлению 010500.68 (магистерская программа «математическое моделирование»)

Теория решеток замкнутых множеств и зависимостей предоставляет математические основы современных методов поиска зависимостей в данных – импликаций и ассоциативных правил на множествах признаков. Поиск ассоциативных правил находится в центре внимания методов разработки данных (data mining). Изложение курса начинается с повторения основных понятий теории отношений, теории графов, теории упорядоченных множеств и решеток. Одним из разделов современной теории решеток является анализ формальных понятий, исходным объектом которого служит бинарное отношение на множествах объектов и их свойств (признаков). На основе отношения определяется соответствие Галуа и оператор замыкания. Замкнутые множества объектов (признаков) образуют решетку (понятий), которая, с одной стороны, позволяет наглядно представлять иерархию классов объектов, а с другой – зависимости на признаках, определяемых в терминах импликаций и ассоциативных правил (частичных импликаций). Решетки формальных понятий дают удобный формализм для описания ряда моделей машинного обучения, таких как пространства версий, деревья решений, ДСМ-гипотезы, а также онтологий – современного средства представления знаний. Серьезным ограничением в применении решеток понятий является сложность вычислительных задач, связанных с алгоритмическим порождением решеток и базисов импликаций. В связи с этим важно изучение сложности задач и сложности различных алгоритмов порождения решеток и базисов импликаций.


Учебные задачи курса.

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


II. Тематический план курса «Упорядоченные множества для анализа данных»





Название темы

Всего часов по дисциплине

Аудиторные часы

Самостоятельная работа










Лекции

Сем. и практика занятия




1

Введение. Отношения и графы

12

2

2

8

2

Порядки и графы

14

2

2

10

3

Решетки и полурешетки

20

3

3

14

4

Бинарные отношения и соответствия Галуа

20

3

3

14

5

Анализ формальных понятий (АФП)

28

6

6

16

6

Импликации и функциональные зависимости

22

4

4

14

7

Ассоциативные правила через соответствия Галуа и решетки понятий

14

4

4

6

8

Алгоритмические проблемы построения решеток замкнутых множеств и базисов импликаций

28

8

8

12

9

Кластеризация и устойчивость

14

4

4

6

10

Модели машинного обучения через соответствия Галуа и решетки понятий

28

8

6

14

11

Представление знаний с

помощью решеток понятий

16

4

4

8




Итого

216

48

46

122



Базовый учебник по курсу – ридер «Дискретные структуры», составленный по следующим источникам:


1. Биркгоф Г., Теория решеток. - М.: Наука, 1984. - 568 с.

2. Биркгоф Г., Барти Т., Современная прикладная алгебра, М., Лань, 2005 – 400 с.

3. Гретцер Г., Общая теория решеток. - М.: Мир, 1982. - 452 с.

4. B. Ganter and R. Wille, Formal Concept Analysis: Mathematical

Foundations, Springer, 1999.

5. Ф.Т. Алескеров, Э.Л. Хабина, Д.А. Шварц, Бинарные отношения, графы и коллективные решения, М., ГУ-ВШЭ, 2006.

6. А.А. Зыков, Основы теории графов, М., Наука, 1987.

7. О. Оре, Теория графов, М., Мир, 1965.

8. Ф. Харари, Теория графов, М., Мир, 1973.


Дополнительная литература по курсу


1. V. Duquenne and J.-L. Guigues, Familles minimales d'implications informatives resultant d'un tableau de donnees binaires, Math. Sci. Humaines, vol. 95, pp. 5-18, 1986.

2. U.M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, R. Uthurusamy, Advances in Knowledge Discovery and Data Mining, AAAI Press, 1996.

3. S.O. Kuznetsov, On Computing the Size of a Lattice and Related Decision Problems, Order, 2001, vol. 18 (4), pp. 313-321.

4. S.O. Kuznetsov, S.A. Obiedkov, Comparing performance of algorithms for generating concept lattices, J. Exp. Theor. Artif. Intell., 2002, vol. 14, 2-3, pp. 189-216.

5. M. Luxenburger, Implications partielle dans un contexte, Math. Sci. Hum., 1991.

6. Кузнецов С.О. Автоматическое обучение на основе анализа

формальных понятий // Автоматика и телемеханика. 2001. - N 10. - с.

3-27.

T.S. Blyth, M.F. Janowitz, Residuation Theory, Pergamon Press, 1972.

7. P. Buitelaar, P. Cimiano, B. Magnini, Eds., Ontology Learning from Text: Methods, Evaluation and Applications, IOS Press, 2005.

8. C. Carpineto and G. Romano, Concept Data Analysis: Theory and Applications, Wiley, 2004.

9. B. Ganter, G. Stumme, R. Wille, Eds., Formal Concept Analysis: Foundations and Applications, Lecture Notes in Artificial Intelligence, State-of-the Art Series (2005), vol. 3626, pp. 196-225.

10. T. Mitchell, Machine Learning, Mc Graw Hill, 1997.

11. B. A. Davey and H. A. Priestley, Introduction to Lattices and

Order, Cambridge University Press, 1990.


Формы контроля и структура итоговой оценки.


Текущий контроль - 2 письменные контрольные работы (90 мин) и 2 домашних задания.

Промежуточный контроль - зачет в конце первого и второго модуля;

Итоговый контроль – письменный экзамен в конце третьего модуля (120 мин.)

Итоговая оценка складывается из следующих элементов:

  • работа на семинарах - 10%;

  • письменный зачет – 20%;

  • 2 письменные контрольные работы – 20% (10% каждая);

  • 2 домашнее задания – 25 %;

  • письменный экзамен – 25%



Программа курса


Упорядоченные множества в анализе данных.


Тема 1. Введение: обзор курса. Отношения и графы.

Бинарные отношения. Графы, подграфы, части, циклы, клики, деревья, двудольные графы. Графы бинарных отношений. Свойства бинарных отношений (рефлексивность, симметричность, асимметричность, антисимметричность, транзитивность, связность, ацикличность, полнота) и их теоретико-графовое выражение. Важные виды бинарных отношений: эквивалентность, толерантность, частичный порядок.

Дополнительное отношение, обратное (дуальное) отношение, кодуальное отношение, симметрическое дополнение.

Свойства бинарных отношений: рефлексивность, транзитивность, симметричность, асимметричность, антисиметричность. Иллюстрация свойств на графе отношения.

Важные виды отношений: эквивалентность (классы эквивалентности), толерантность (классы толерантности),


Основная литература


1. Биркгоф Г., Барти Т., Современная прикладная алгебра, М., Лань, 2005 – 400 с.

2. Ф.Т. Алескеров, Э.Л. Хабина, Д.А. Шварц, Бинарные отношения, графы и коллективные решения, М., ГУ-ВШЭ, 2006.

3. А.А. Зыков, Основы теории графов, М., Наука, 1987.

4. О. Оре, Теория графов, М., Мир, 1965.

5. Ф. Харари, Теория графов, М., Мир, 1973.


Тема 2. Частично-упорядоченные множества и графы.

Частичный порядок, строгий порядок, квазипорядок, линейный порядок, отношение покрытия (доминирования), ориентированный граф порядка, диаграмма (Хассе) порядка.

Частичный порядок как транзитивное замыкание отношения покрытия (также через произведение матриц), квазипорядок, отношение несравнимости, частичный порядок на элементах фактор-множества по отношению эквивалентности в квазипорядке.

Примеры порядков в математике и приложениях: порядок на мультимножествах, порядок на разбиениях, (квази)порядок на помеченнных (раскрашенных) графах. Размерность упорядоченного множества (порядковая и мультипликативная). Топологическая сортировка


Основная литература


1. Биркгоф Г., Теория решеток. - М.: Наука, 1984. - 568 с.

2. Биркгоф Г., Барти Т., Современная прикладная алгебра, М., Лань, 2005 – 400 с.

3. Гретцер Г., Общая теория решеток. - М.: Мир, 1982. - 452 с.

4. Ф.Т. Алескеров, Э.Л. Хабина, Д.А. Шварц, Бинарные отношения, графы и коллективные решения, М., ГУ-ВШЭ, 2006.

5. А.А. Зыков, Основы теории графов, М., Наука, 1987.

6. О. Оре, Теория графов, М., Мир, 1965.


Дополнительная литература


1. B. A. Davey and H. A. Priestley, Introduction to Lattices and

Order, Cambridge University Press, 1990.

2. T.S. Blyth, M.F. Janowitz, Residuation Theory, Pergamon Press, 1972.


Тема 3. Решетки и полурешетки.

Инфимум, супремум, полурешетки, квазирешетки, два определения решеток. Диаграммы полурешеток решеток. Виды решеток (полные, модулярные, матроиды, дистрибутивные, булевы) и их диаграммы. (Порядковые) фильтры и идеалы решеток. Пополнения частичных порядков до решеток (пополнение Дедекинда-Макнила) и дистрибутивных решеток (Теорема Биркгофа).


Основная литература


1. Биркгоф Г., Теория решеток. - М.: Наука, 1984. - 568 с.

2. Биркгоф Г., Барти Т., Современная прикладная алгебра, М., Лань, 2005 – 400 с.

3. Гретцер Г., Общая теория решеток. - М.: Мир, 1982. - 452 с.

4. О. Оре, Теория графов, М., Мир, 1965.


Дополнительная литература


1. B. A. Davey and H. A. Priestley, Introduction to Lattices and

Order, Cambridge University Press, 1990.

2. T.S. Blyth, M.F. Janowitz, Residuation Theory, Pergamon Press, 1972.


Тема 4. Бинарные отношения и соответствия Галуа.

Соответствия Галуа и их свойства. Соответствие Галуа, основанное на бинарном отношении. Оператор замыкания и система замыканий (семейство Мура). Замкнутые множества, решетка замкнутых множеств.


Основная литература


1. Биркгоф Г., Теория решеток. - М.: Наука, 1984. - 568 с.

2. Биркгоф Г., Барти Т., Современная прикладная алгебра, М., Лань, 2005 – 400 с.

3. Гретцер Г., Общая теория решеток. - М.: Мир, 1982. - 452 с.

4. О. Оре, Теория графов, М., Мир, 1965.


Дополнительная литература


1. B. A. Davey and H. A. Priestley, Introduction to Lattices and

Order, Cambridge University Press, 1990.

2. T.S. Blyth, M.F. Janowitz, Residuation Theory, Pergamon Press, 1972.


  1   2   3

Похожие:

Программа дисциплины Упорядоченные множества для анализа данных для направления 010500. 68 Прикладная математика и информатика подготовки магистра Автор Кузнецов С. О. () Рекомендована секцией умс «Прикладная математика и информатика» iconПрограмма дисциплины Упорядоченные множества для анализа данных для направления 010500. 68 Прикладная математика и информатика подготовки магистра Автор Кузнецов С. О. () Рекомендована секцией умс «Прикладная математика и информатика»
Программа дисциплины «Упорядоченные множества для анализа данных» для подготовки магистров по направлению 010500. 68 (магистерская...
Программа дисциплины Упорядоченные множества для анализа данных для направления 010500. 68 Прикладная математика и информатика подготовки магистра Автор Кузнецов С. О. () Рекомендована секцией умс «Прикладная математика и информатика» iconПрограмма дисциплины История и методология прикладной математики и информатики для направления 010400. 68 “ Прикладная математика и информатика ” подготовки магистра Автор Миркин Б. Г. () Рекомендована секцией умс «Прикладная математика и информатика»
Федеральное государственное автономное образовательное учреждение высшего профессионального образования
Программа дисциплины Упорядоченные множества для анализа данных для направления 010500. 68 Прикладная математика и информатика подготовки магистра Автор Кузнецов С. О. () Рекомендована секцией умс «Прикладная математика и информатика» iconПрограмма дисциплины Обучение машин и восстановление зависимостей для направления 010500. 68- прикладная математика и информатика подготовки магистров Автор Михальский А. И. () Рекомендована секцией умс «Прикладная математика и информатика»
Вапник В. Н. Восстановление зависимостей по эмпирическим данным. Москва, Наука 1979
Программа дисциплины Упорядоченные множества для анализа данных для направления 010500. 68 Прикладная математика и информатика подготовки магистра Автор Кузнецов С. О. () Рекомендована секцией умс «Прикладная математика и информатика» iconПрограмма дисциплины: Моделирование Бизнес-процессов  для направления 010500. 62 «Прикладная математика и информатика»
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 010500....
Программа дисциплины Упорядоченные множества для анализа данных для направления 010500. 68 Прикладная математика и информатика подготовки магистра Автор Кузнецов С. О. () Рекомендована секцией умс «Прикладная математика и информатика» iconПрограмма дисциплины Дискретная математика для направления Прикладная математика и информатика 010500
Автор программы: Доктор технических наук, профессор, академик Российской Академии естественных наук О. П. Кузнецов
Программа дисциплины Упорядоченные множества для анализа данных для направления 010500. 68 Прикладная математика и информатика подготовки магистра Автор Кузнецов С. О. () Рекомендована секцией умс «Прикладная математика и информатика» iconПрограмма дисциплины Объектно-ориентированные case-технологии для направления 010500. 62 Прикладная математика и информатика подготовки бакалавров Автор Незнанов А. А. ()
Программа дисциплины Объектно-ориентированные case-технологии (Технологии разработки сложных программных систем) для подготовки бакалавров...
Программа дисциплины Упорядоченные множества для анализа данных для направления 010500. 68 Прикладная математика и информатика подготовки магистра Автор Кузнецов С. О. () Рекомендована секцией умс «Прикладная математика и информатика» iconПрограмма дисциплины иностранный язык (английский) для направления 010500. 62 "Прикладная математика и информатика"
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 010500. 62 "Прикладная...
Программа дисциплины Упорядоченные множества для анализа данных для направления 010500. 68 Прикладная математика и информатика подготовки магистра Автор Кузнецов С. О. () Рекомендована секцией умс «Прикладная математика и информатика» iconПрограмма дисциплины иностранный язык (английский) для направления 010500. 62 "Прикладная математика и информатика"
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 010500. 62 "Прикладная...
Программа дисциплины Упорядоченные множества для анализа данных для направления 010500. 68 Прикладная математика и информатика подготовки магистра Автор Кузнецов С. О. () Рекомендована секцией умс «Прикладная математика и информатика» iconПрограмма дисциплины «Дополнительные главы дифференциальных уравнений» для направления 010400. 68 «Прикладная математика и информатика» подготовки магистра
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 010400. 62 «Прикладная...
Программа дисциплины Упорядоченные множества для анализа данных для направления 010500. 68 Прикладная математика и информатика подготовки магистра Автор Кузнецов С. О. () Рекомендована секцией умс «Прикладная математика и информатика» iconПрограмма дисциплины «Проблемы современной компаративистики» для направления 010400. 68 «Прикладная математика и информатика»
Программа предназначена для преподавателей, ведущих данную дисциплину, и студентов направления подготовки 010400. 68 "Прикладная...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница