Дисциплина «Дискретная математика, математическая логика и их приложения в информатике и компьютерных науках» обеспечивает изучение следующих дисциплин: 1) Математический анализ, 2) Теория функций комплексной переменной, 3) Функциональный анализ, 4) Теория автоматов и формальных языков, 5) Теория вероятностей и математическая статистика.
Модели на гиперграфах, Введение в управление инфокоммуникациями, Проектирование корпоративных систем, Прикладные задачи ТМО, Прикладные протоколы Интернет WWW, курсовая работа.
№ п/п | Наименование обеспечиваемых (последующих) дисциплин | № № разделов данной дисциплины, необходимых для изучения обеспечиваемых (последующих) дисциплин | |||||||||||||
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | ||
1. | Математический анализ | + | + | + | + | + | + | + | + | + | |||||
2. | Теория функций комплексной переменной | + | + | + | + | + | + | + | + | + | + | ||||
3. | Функциональный анализ | + | + | + | + | + | + | + | + | ||||||
4. | Теория автоматов и формальных языков | + | + | + | + | + | + | + | + | + | + | + | + | + | |
5. | Теория вероятностей и математическая статистика | + | + | + | + | + | + | + | + | + | + | ||||
6. | Модели на гиперграфах | + | + | + | + | + | |||||||||
7. | Введение в управление инфокоммуникациями | + | + | + | + | ||||||||||
8. | Прикладные протоколы Интернет WWW | + | + | + | + | ||||||||||
9. | Прикладные задачи ТМО | + | + | + | + | + | |||||||||
10. | Курсовая работа | + | + | + | + | + | + | + | + | + | + | + | + | + | + |
5.3. Разделы дисциплин и виды занятий
№ п/п | Наименование раздела дисциплины | Лекц. | Практ. Зан. | Лаб. Зан. | Семин | СРС | Все-го час. |
1. | Введение в комбинаторику. Правило суммы и правило произведения. | 2 | 2 | 4 | 8 | ||
2. | Перестановки и сочетания. Мультимножества. Биномиальные коэффициенты. | 6 | 6 | 12 | 24 | ||
3. | Треугольник Паскаля. Разбиения множеств. Числа Стирлинга первого и второго рода. | 6 | 6 | 12 | 24 | ||
4. | Принцип включения и исключения | 6 | 6 | 12 | 24 | ||
5. | Производящие функции. Схемы выбора. | 6 | 6 | 12 | 24 | ||
6. | Однородные и неоднородные линейные рекуррентные соотношения | 6 | 6 | 12 | 24 | ||
7. | Поиск с возвращением. Генерация перестановок и сочетаний | 4 | 4 | 8 | 16 | ||
8. | Введение в алгебру логики | 8 | 8 | 16 | 32 | ||
9. | Минимизация булевых функций | 10 | 10 | 20 | 40 | ||
10. | Полнота и замкнутость систем логических функций | 4 | 4 | 8 | 16 | ||
11. | Исчисление высказываний и предикатов | 14 | 14 | 28 | 56 | ||
12. | Элементы теории графов | 12 | 12 | 24 | 48 | ||
13. | Алгоритмы на графах | 12 | 12 | 24 | 48 | ||
14. | Потоки в сетях | 12 | 12 | 24 | 48 | ||
108 | 108 | 216 | 432 |
6. Лабораторный практикум
№ п/п | № раздела дисциплины | Наименование лабораторных работ | Трудо-емкость (час.) |
1. | Введение в комбинаторику. Правило суммы и правило произведения. | Решение задач на прямое произведение множеств, правило суммы и правило произведения. Решение задач на сочетания, перестановки и размещения, мультимножество. | 2 |
2. | Перестановки и сочетания. Мультимножества. Биномиальные коэффициенты. | Решение задач на сочетания, перестановки и размещения, мультимножество. Доказательства тождеств при помощи формулы Бинома Ньютона. | 6 |
3. | Треугольник Паскаля. Разбиения множеств. Числа Стирлинга первого и второго рода. | Свойство шестиугольника для треугольника Паскаля. Доказательство свойств биномиальных коэффициентов. Вычисление чисел Стирлинга 1 и 2-го рода. Вычисление чисел Белла. Применение чисел Стирлинга 1 и 2-го рода, чисел Белла. | 6 |
4. | Принцип включения и исключения | Решение задач на свойство включения и исключения. Задача о шляпах. Вычисление числа предметов, обладающих ровно n свойствами. Вычисление числа предметов, обладающих не менее, чем k свойствами в рамках типовых задач. | 6 |
5. | Производящие функции. Схемы выбора. | Решение задач на использование полиномиальной теоремы. Таблица производящих функций. Вычисление производящих функций для последовательностей. | 6 |
6. | Однородные и неоднородные линейные рекуррентные соотношения | Задачи на нахождение формулы для членов последовательности через соответствующую производящую функцию. | 6 |
7. | Поиск с возвращением. Генерация перестановок и сочетаний | Задачи на генерацию сочетаний и перестановки и метод поиска с возвращением. Разбор алгоритмов. | 4 |
8. | Алгебра логики | Решение примеров на прямое произведение множеств. Задача на истинность соответствия. Поиск подалгебры в алгебре. Суперпозиции и формулы. Решение задач на принцип двойственности и правило двойственности. Нахождение совершенной дизъюнктивной нормальной формы (СДНФ). Нахождение совершенной конъюнктивной нормальной формы (СКНФ). Разложение булевых функций по переменным. Построение СДНФ для функции, заданной таблично. | 8 |
9. | Минимизация булевых функций | Минимизация функций. Порождение простых импликантов. Алгоритм Куайна и Мак-Клоски. Таблицы простых импликантов. | 10 |
10. | Полнота и замкнутость систем логических функций | Решение задач на доказательство замкнутости класса. Класс самодвойственных функций. Решение задач с несамодвойственными функциями. Класс монотонных функций. Решение задач с немонотонными функциями. Класс линейных функций. Решение задач с нелинейными функциями. | 4 |
11. | Исчисление высказываний и предикатов | Решение задач с использованием метода резолюций для исчисления высказываний. Применение кванторов. Поиск предваренной нормальной формы (ПНФ). Поиск скулемовской стандартной формы. Подстановка и унификация для ПНФ. Применение алгоритма унификации. Применение метода резолюций в исчислении предикатов. | 14 |
12. | Элементы теории графов | Разбор основных понятий и определений на неориентированных и ориентированных графах. Матрицы смежности и матрицы инцидентности для неориентированных и ориентированных графов. Поиск маршрутов, цепей и циклов для графов. Нахождение связных компонент в графе. Метрические характеристики графов. Эйлеровы графы. Эйлеровы пути и циклы. Нахождение кратчайших путей в ориентированном графе | 12 |
13. | Алгоритмы на графах | Алгоритм Краскала. Алгоритм Прима. Алгоритм Дейкстры. Алгоритм нахождения эйлерова цикла в графе. Алгоритм построения кратчайшего пути от фиксированной вершины до всех остальных вершин в ориентированном графе, случай неотрицательных весов ребер. Построение матрицы связности (достижимости для графа). Алгоритм Уоршалла-Флойда. | 12 |
14. | Потоки в сетях | Прикладные модели и задачи. Оценка структурных компонент графа. Задача о максимальном потоке и о минимальном разрезе в сети. Максимальный поток в транспортной сети. Задача на нахождение «узких» мест в сети. Задача о потоке минимальной стоимости. | 12 |
Итого: | 108 |
7. Практические занятия (семинары)
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 |
