Математические модели информационных процессов и управления

Семестр 6 – 7

Составил Г.Ю. Дорошкова, ассистент

Учебная программа составлена на основе учебной программы, утвержденной _____________, регистрационный номер _______________

Рассмотрена и рекомендована к утверждению в качестве рабочего варианта на заседании кафедры автоматизированных систем обработки информации

___ __________ 2010 г., протокол № __

доцент ____________ В.Д.Левчук

___ __________ 2010 г., протокол № __

доцент ____________ Е.А. Дей

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

Целью изучения дисциплины является усвоение студентами теоретических основ и математического аппарата для описания данных, их преобразования и передачи.

Задачами дисциплины являются:

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

Содержание учебного материала

Понятие множества. Способы задания. Сравнение множеств. Подмножества. Операции над множествами: пересечение, объединение. Свойства. Универсальное множество. Дополнение. Правила де Моргана. Представление подмножества формулой. Преобразование формул. Выражение свойств множеств через уравнения. Решение уравнений. Декартово произведение множеств. Свойства.

Определение соответствия. Определение отображения. Инъекция. Сюръекция. Биекция. Функция. Обратное отображение. Композиция отображений. Свойства отображений. Способы задания функций. Отношения. Бинарные отношения. Свойства отношений. Рефлексивные, симметричные, транзитивные отношения.

Отношение эквивалентности. Классы эквивалентности. Фактор-множество. Разбиение множества. Классы разбиения. Разбиение и отношение эквивалентности. Отношение порядка: частичный порядок, строгий порядок. Понятие о максимальном и минимальном элементах. Минимум и максимум.

Понятие реляционной модели данных. Реляционное исчисление кортежей. Реляционное исчисление доменов. Реляционная алгебра. Функциональные зависимости. Аксиомы вывода. Замыкания. Нормализация отношений. Первая, вторая, третья нормальные формы. Нормальная форма Бойса-Кодда. Многозначные зависимости. Аксиомы вывода. Четвертая нормальная форма.

История возникновения теории графов. Применения теории графов. Основные определения теории графов. Способы задания графов. Специальные виды графов. Эйлеровы и гамильтоновы графы. Подграфы и дополнения. Связность графов. Планарность графов. Маршруты, цепи, пути и циклы. Операции над графами.

Определение дерева. Свойства деревьев. Глубина и яруса деревьев. Корневые деревья. Бинарные деревья. Способы представления бинарных деревьев. Полные бинарные деревья и их представление. Бинарные поисковые деревья. Сбалансированные деревья. Способы обхода узлов в бинарных деревьях. Представление множеств с помощью деревьев. Бинарные кучи. Операции с бинарными кучами. Базовые операции над бинарными поисковыми деревьями.

Понятие ориентированного графа. Полустепени исхода и захода вершины графа. Способы задания орграфа. Ориентированные маршруты. Сильная, слабая и односторонняя связность. Графы и бинарные отношения. Ориентированные деревья.

Понятие раскраски. Правильная раскраска. Понятие хроматического числа. Оптимальная раскраска. Свойства хроматического числа. Проблема четырех красок. Решение задач с использованием понятия раскраски графов. Задача составления расписаний. Задача распределения ресурсов. Задача экономии памяти.

Задача о нахождении наикратчайшего пути в графах. Волновой алгоритм. Алгоритм Дейкстры. Алгоритм Форда-Беллмана. Алгоритм Флойда.

Определение сети. Полустепени исхода и захода вершины. Понятия истока и стока. Пропускная способность. Поток через сеть. Величина потока. Понятие разреза. Пропускная способность разреза. Максимальный и минимальный разрезы. Алгоритмы нахождения максимального потока.

Конъюнкция, дизъюнкция, импликация, эквивалентность. Определение булевой функции. Элементарные булевы функции. Теорема о числе булевых функций.

Формулы алгебры логики. Законы алгебры логики. Законы коммутативности, ассоциативности, дистрибутивности, законы де Моргана. Двойственные функции. Принцип двойственности.

Дизъюнктивная нормальная форма. Конъюнктивная нормальная форма. Теоремы о ДНФ и КНФ. Разложение булевых функций по переменным. Совершенная дизъюнктивная нормальная форма, конъюнктивная нормальная форма. Сложение по модулю 2. Полином Жегалкина. Теорема Жегалкина. Законы алгебры Жегалкина.

Задача минимизации булевых функций. Сокращенная дизъюнктивная нормальная форма. Тупиковая дизъюнктивная нормальная форма. Алгоритмы построения сокращенной и тупиковой ДНФ. Хорновские дизъюнкты и КС - грамматики. Теорема компактности.

Основные понятия. Логические операции над предикатами: конъюнкция, дизъюнкция, импликация, эквивалентность, отрицание. Одноместные и многоместные предикаты. Кванторные операции над предикатами: общности, существования, численные кванторы, ограниченные кванторы.

Понятие формул логики предикатов. Классификация формул логики предикатов. Тавтологии логики предикатов. Законы алгебры логики предикатов. Равносильность преобразования формул. Приведенная форма логики предикатов, предваренная и нормальная формы логики предикатов. Сколемовские и клаузальные формы.

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

Понятие формальной аксиоматической теории. Метаматематика. Формализованное исчисление высказываний как формальная аксиоматическая теория. Формальное исчисление предикатов как формальная аксиоматическая теория. Формальные теории первого порядка. Формальная арифметика и теорема Геделя о ее не полноте. Алгоритм и разрешимость. Алгоритмический язык Тъюринга. Машины Тъюринга и операции над ними. Функции, выполняемые на машинах Тъюринга.

Основные понятия теории формальных грамматик. Регулярные Грамматики. Автоматные грамматики. Примеры. КС – грамматики и стековые автоматы. Автоматы Милли и Мура. Грамматики и языки Хомского тика 1. Машины Тъюринга и грамматики типа 0. Вероятностные автоматы.

Резольвенты. Унификация. Унификаторы. Алгоритм унификации предложений. Суть принципа резолюции. Доказательство теорем путем опровержения. Стратегии просмотром предложений в ширину. Стратегии использования опорного множества. Линейная стратегия. Системы прямой дедукции. Системы обратной дедукции. Примеры использования метода резолюций.

Модальные высказывания. Модальные операторы. Примеры модальных операторов. Синтаксис модальной логики предикатов. Трехзначная семантика для модальной логики предикатов.

Понятие нечеткой логики. Ненадежные знания и выводы. Коэффициенты уверенности. Факторы уверенности. Метод Демпстера-Шефера: фреймы различия, функция вероятности и незнания, комбинирование свидетельств, нормализация доверия.

Нечеткие числовые данные. Интервалы доверия. Нечеткие подмножества. Операции пересечения, объединения, равенства, включения, дополнения, дизъюнктивной суммы, перемещения, уплотнения, растяжения множеств.

Нечеткие отношения. Операции пересечения, объединения, алгебраического произведения, алгебраической суммы, композиции отношений. Метод max-min. Теория возможностей.

Понятие сигнала. Шумы и помехи. Размерность сигналов. Математическое описание сигналов. Спектральное представление сигналов. Математические модели сигналов. Виды моделей. Классификация сигналов. Типы сигналов. Аналоговый сигнал. Дискретный сигнал. Цифровой сигнал. Преобразования типа сигналов. Графическое отображение сигналов. Тестовые сигналы. Системы преобразования сигналов. Общее понятие систем. Основные системные операции. Линейные системы.

Основные понятия и определения. Принципы построения и классификация систем управления. Обобщенная структурная схема автоматической системы управления. Схемы функциональных структур систем управления.

Общие понятия о передаточных свойствах элементов и систем. Временные и спектральные характеристики типовых воздействий и сигналов. Линейные дифференциальные уравнения. Временные характеристики. Операционный метод и передаточная функция. Частотные характеристики. Статические и динамические характеристики типовых соединений элементов.

Правила преобразования алгоритмических схем и сигнальных графов. Вспомогательные правила структурных преобразований. Алгоритмические схемы и передаточные функции типовой одноконтурной системы. Типовые законы регулирования, применяемые в линейных системах. Точность статических и астатических систем управления при типовых воздействиях. Статическая точность. Динамическая точность. Точность при гармонических воздействиях.

Понятие, виды и общее условие устойчивости. Алгебраические критерии устойчивости: критерий Гурвица, критерий Рауса. Критерий Михайлова. Критерий Найквиста. Построение областей устойчивости.

Понятие и показатели качества управления. Частотные показатели. Корневые показатели. Интегральные показатели качества.

Сущность статистического подхода к расчету систем управления. Характеристики случайных сигналов. Числовые характеристики. Корреляционная функция. Спектральная плотность. Взаимосвязь между функциональными характеристиками случайного сигнала. Характеристики связи двух случайных сигналов. Типовые случайные воздействия. Преобразования случайного сигнала линейным динамическим звеном. Преобразования во временной области. Законы преобразования в частной области. Метод формирующего фильтра.

Знакоопределенные, знакопостоянные и знакопеременные функции. Функция Ляпунова и ее производная по времени. Теорема Ляпунова об устойчивости нелинейных систем. Теорема Ляпунова о неустойчивости нелинейных систем. Теорема Ляпунова об устойчивости движения. Критерий Сильвестра. Метод фазовых траекторий. Фазовое пространство. Метод фазовой плоскости. Связь временного процесса с фазовой траекторией. Частотный метод В.М.Попова.

Классификация дискретных систем: импульсные, релейные, цифровые системы. Особенности дискретных систем и области применения Методы исследования линейных импульсных систем. Уравнения импульсных систем. Дискретное преобразование Лапласа, Z-преобразование. Использование разностных уравнений замкнутой импульсной СУ. Устойчивость дискретных систем. Исследование качества дискретных СУ.

Определение временных характеристик СУ детерминистическими и статистическими методами. Метод наименьших квадратов: определение, способы применения.

Информационно-методическая часть

1. 
   Основные понятия теории множеств
   
2. 
   Раскраска графов
   
3. 
   Кратчайшие пути в графах
   
4. 
   Нормальные формы
   
5. 
   Кванторные операции над предикатами.
   
6. 
   Доказательство теорем методом резолюций
   
7. 
   Методы математического описания линейных элементов и систем управления
   
8. 
   Оценка качества управления
   

1. 
   Excel
   
2. 
   Mathcad
   
3. 
   Delphi
   

Отчеты по контрольным работам

1. 
   Теория множеств и отношений, логика высказываний и предикатов
   
2. 
   Теория графов и теория систем управления
   

Основная

1. 
   Аверин, А.Н. Нечеткие множества в моделях управления и искусственного интеллекта / А.Н. Аверин. – М.: Наука, 1986. – 305 с.
   
2. 
   Баскаков, С.И. Радиотехнические цепи и сигналы: учебник для вузов / С.И. Баскаков – М.: Высшая школа, 1988. – 448 с.
   
3. 
   Бесекерский, В.А. Теория систем автоматического регулирования / В.А. Бесекерский, Е.П. Попов – М.: Наука, 1975. – 371 с.
   
4. 
   Гаврилов, Г.П. Сборник задач по дискретной математике / Г.П. Гаврилов, А.А. Сапоженко – М.: Наука, 1977. – 406 с.
   
5. 
   Евстигнеев, В.А. Теория графов. Алгоритмы обработки деревьев / В.А. Евстегнеев, В.Н. Касьянов – Новосибирск: Наука, 1994. – 360 с.
   
6. 
   Емеличев, В.А. Лекции по теории графов / В.А. Емельчев, О.И. Мельников –М.: Наука, 1990. – 407 с.
   
7. 
   Змитрович, А.И. Интеллектуальные информационные системы. / А.И. Змитрович – Мн.: Выш. шк., 1997. – 367 с.
   
8. 
   Изерман, Р. Цифровые системы управления / Р. Изерман – М.: Мир, 1984. – 418 с.
   
9. 
   Кофман, А. Введение в теорию нечетких множеств / А. Кофман – М.: Радио и связь, 1982. – 432с.
   
10. 
    Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кристофидес – М.: Мир, 1978. – 284 с.
    
11. 
    Кузнецов, О.П. Дискретная математика для инженеров / О.П. Кузнецов – М: Энергоатомиздат, 1988. – 479 с.
    
12. 
    Куо, Б. Теория и проектирование цифровых систем управления / Б. Куо – М.: Машиностроение, 1986. – 452 с.
    
13. 
    Лавров, И.А. Задачи по теории множеств, математической логике и теории алгоритмов / И.А. Лавров, Л.Л. Максимов – М.: Наука, 1984. – 298 с.
    
14. 
    Лукас, В.А. Теория автоматического управления: учебник для вузов / В.А. Лукас – М.: Недра, 1990. – 389 с.
    
15. 
    Острем, К. Системы управление с ЭВМ: / К. Острем, Б.Виттенмарк – М.: Мир, 1987. – 482 с.
    
16. 
    Сергиенко, А.Б. Цифровая обработка сигналов: учебник для вузов / А.Б. Сергиенко – СПб.: Питер, 2003. – 608 с.
    
17. 
    Татт , У. Теория графов / У. Татт – М.: Мир, 1988. – 368 с.
    
18. 
    Тей, А. Логический подход к искусственному интеллекту: от классической логики к логическому программированию / А. Тей – М.: Мир, 1990. – 240 с.
    
19. 
    Чемоданова, Б.К. Математические основы теории автоматического регулирования: учебное пособие для вузов / Б.К. Чемоданова – М.: Высшая школа, 1977. – 479 с.
    

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

20. 
    Берж, К. Теория графов и ее применения / К. Берж – М.: Изд-во иностр. лит., 1962. – 387 с.
    
21. 
    Ковальски, Р. Логика в решении проблем / Р. Ковальски – М.: Наука, 1981. – 343 с.
    
22. 
    Розенвансеер, Е.Н. Чувствительность СУ / Е.Н. Розенвансеер. – М.: Наука, 1981. – 384 с.
    
23. 
    Тарасик, В.П. Математическое моделирование технических систем: учебник для вузов / В.П. Тарасик – Мн.: Выш.шк., 1997. – 640 с.
    
24. 
    Фейс, Р. Модальная логика / Р. Фейс – М.: Наука, 1974. – 520 с.
    
25. 
    Форд, Л.Р. Потоки в сетях / Л.Р. Форд, Д.Р. Фалкерсон – М.: Мир, 1966. – 465 с.
    
26. 
    Холодниюк, М.С. Методы анализа нелинейных систем / М.С. Холодниюк – М.: Мир, 1981. – 366 с.
    
27. 
    Шноль, Э.Э. Методы анализа нелинейных динамических моделей / Э.Э. Шноль – М.: Мир, 1991. – 296 с.
    
28. 
    Яблонский, С.В. Введение в дискретную математику / С.В. Яблонский – М.: Наука, 1979. – 261 с.
    

по изучаемой учебной дисциплине

«Математические модели информационных процессов и управления»

с другими дисциплинами специальности

1-53 01 02 – «Автоматизированные системы обработки информации»