Дискретная математика

Курс предназначен для студентов, изучающих основные темы ИТ-направлений бакалавриата. Дается содержательно-формальная основа представления знаний и манипулирования ими с использованием математически обоснованных основных «строительных блоков» или «единиц знаний».

Десять последовательно связанных модуля (наименования есть в программе курса), контрольные вопросы, зачетные материалы в электронной форме. 

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

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

[1] Marvin Minsky Semantic information processing. Cambridge, Mass., MIT Press, 1968. - 440 p.

[2] Alexander T. Borgida, Vinay K. Chaudhri, Paolo Giorgini, and Eric S. Yu (Eds.). 2009. Conceptual Modeling: Foundations and Applications: Essays in Honor of John Mylopoulos. Springer-Verlag, Berlin, Heidelberg. – 503 p.

[3] Nick Roussopoulos, John Mylopoulos Using Semantic Networks for Database Management. VLDB 1975: 144-172

[4] Nick Roussopoulos, Dimitris Karagiannis: Conceptual Modeling: Past, Present and the Continuum of the Future. Conceptual Modeling: Foundations and Applications 2009: 139-152

[5] E. F. Codd: Relational Completeness of Data Base Sublanguages. Research Report / RJ / IBM / San Jose, California RJ987 (1972)

[6] E. F. Codd: Further Normalization of the Data Base Relational Model. Research Report / RJ / IBM / San Jose, California RJ909 (1971)

[7] Daniel J. Dougherty and Claudio Gutiérrez. 2000. Normal Forms and Reduction for Theories of Binary Relations. In Proceedings of the 11th International Conference on Rewriting Techniques and Applications (RTA ’00). Springer-Verlag, Berlin, Heidelberg, 95–109.

[8] F. Palermo, "A Database Search Problem", Information Systems: COINS IV, J. Tou ed., Plenum, 1974. – pp. 67-101

[9] Robert Bosak, Richard F. Clippinger, Carey Dobbs, Roy Goldfinger, Renee B. Jasper, William Keating, George Kendrick, and Jean E. Sammet. 1962. An information algebra: phase 1 report—language structure group of the CODASYL development committee. Commun. ACM 5, 4 (April 1962), 190–204. DOI:https://doi.org/10.1145/366920.366935

Знание английского языка на уровне не ниже Intermediate.

Часть 1. Элементы семантического моделирования.

Модуль 1. Введение в представление интенсиональных знаний и экстенсиональных знаний. Интенсиональные знания представляются с использованием концептов и фреймов. Экстенсиональные знания используют сгенерированные расширения базовых единиц знаний.

Модуль 2. Обзор основных строительных блоков. Они моделируют события, характеристики концептов и функциональные фреймы.

Модуль 3. Вводятся логические и причинные связки между единицами знаний. Целевая конструкция соответствует сложным предложениям на естественном языке и представлена исчислением предикатов как предложения.

Модуль 4. Приведены процедурные дополнения. Дается представление контейнеров знаний, а также портфелей и других конструкций высшего порядка.

Часть 2. Зависимости данных

Модуль 5. Реляционная схема определена и снабжена математическим аппаратом, основанным на математической теории отношений. Функциональные зависимости (ФЗ) задаются соответствующими нормальными формами.

Модуль 6. Сформулированы математические требования к реляционной схеме. Определяется и анализируется процесс создания реляционной схемы. Созданные таким образом отношения классифицируются.

Часть 3. Семантические операторы

Модуль 7. Описана и определена интенсиональная алгебра, позволяющая давать определения абстрактных операторов над единицами знаний. Этот вид алгебры используется для получения знаний, производных от исходных знаний.

Модуль 8. Объединение и разность концептов осуществляется в рамках интенсиональных операций. Логические операции над фреймами определяются и переходят к операции квантификации.

Модуль 9. Изучаются операторы в режимах манипулирования данными, определения данных и «законность». Вводятся начала ассоциированной экстенсиональной алгебры.

Модуль 10. Изучается выделение концептуальных отношений. Рассмотрена оценка (расширений) фреймов. Рассматривается полученный алгоритм квантификации.

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

• основные дискретные структуры и примитивы семантического моделирования;
• системы и структуры концептов и концептуальных связей, ISA-измерение и дефинициональное (определительное) измерения, принципы построения семантической модели;
• семейства зависимостей данных, функциональные зависимости и их основные свойства;
• интенсиональные и экстенсиональные операторы, принципы построения оценки выражений;
• основные свойства частично-упорядоченных структур;

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

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