5.1. Наименование тем, их содержание и объем
Курс 1 Семестр № 2
№ п/п | Тема лекции (краткое содержание лекции) | К-во лекционных часов | Объем на тематический раздел, час | ||
Практические и др. занятия | Лабора торные занятия | Само стоятель ная работа | |||
1 | 2 | 3 | 4 | 5 | 6 |
1 | Введение | 1 | |||
2 | Основы теории множеств. Понятие множества. Операции нал множествами. Подмножества. Отношения между множествами. Число подмножеств данного множества. Декартово произведение множеств. Отношения на множестве. Понятие функции. | 4 | 2 | 2 | |
3 | Комбинаторика. Размещения, сочетания, перестановки с повторениями и без повторений. Формулы для вычисления их числа. | 5 | 3 | 2 | |
4 | Высказывания. Основные логические операции. Формулы логики. Таблицы истинности. | 4 | 3 | 2 | |
5 | Законы логики. Упрощение формул логики с помощью равносильных преобразований конъюнктивная и дизъюнктивная нормальные формы. (КНФ и ДНФ) | 5 | 4 | 3 | |
6 | Булевы функции. Понятие функции. Представление булевой функции в виде минимальной ДНФ. Анализ рассуждений. | 6 | 3 | 3 | |
7 | Предикаты. Логика предикатов; синтаксис и семантика языка логики предикатов; принцип логического программирования; аксиоматические системы, формальный вывод; метатеория формальных систем; | 6 | 3 | 4 | |
Бинарные отношения | 2 | 1 | |||
Понятие алгоритмической системы. Рекурсивные функции. Машины Тьюринга. | 3 | 1 | |||
Всего | 36 | 18 | 18 |
Курс 2 Семестр №3
№ п/п | Тема лекции (краткое содержание лекции) | К-во лекционных часов | Объем на тематический раздел, час | ||
Практические и др. занятия | Лабора торные занятия | Само стоятель ная работа | |||
1 | 2 | 3 | 4 | 5 | 6 |
1 | Алгоритмически неразрешимые проблемы; меры сложности алгоритмов; легко и трудноразрешимые задачи. | 1 | 1 | ||
2 | Элементы теории кодирования. Задача кодирования. Разделимые схемы. Префиксное кодирование. Алгоритм Фано. | 2 | 4 | 6 | |
3 | Оптимальное кодирование. Алгоритм Хаффмена. | 3 | 6 | 14 | |
4 | Помехоустойчивое кодирование. | 1 | 6 | ||
5 | Основы теории графов. Понятие неориентированного графа. Теорема о сумме степеней вершин графа. Изоморфные графы. | 2 | 6 | ||
6 | Алгоритм фронта волны. Метрические характеристики графа. Двудольные графы, Задача о числе внутренних пересечений ребер графа. | 2 | 6 | ||
7 | Алгоритмы на сетях. Оптимизационные задачи на графах. Алгоритмы поиска кратчайшего расстояния и наибольшего потока | 2 | 8 | 16 | |
8 | Деревья. Бинарные деревья. Алгоритм Краскала поиска наименьшего дерева. | 2 | 6 | ||
9 | Эйлеровы и гамильтоновы графы. | 1 | 6 | ||
ВСЕГО | 18 | 18 | 84 |
5.2. Перечень практических (семинарских) занятий.
Их содержание и объем в часах (аудиторных).
Курс 1 Семестр №2
№ п/п | Тема практического (семинарского) занятия | К-во часов |
1 | Операции над множествами | 4 |
2 | Решение комбинаторных задач | 4 |
3 | Преобразование формул логики высказываний. ДНФ и КНФ. | 6 |
4 | Логические задачи. Анализ рассуждений | 4 |
5.3. Перечень лабораторных занятий, их наименования и объем в часах
Курс 2 Семестр №3
№ п/п | № раздела дисциплины | Наименование лабораторной работы | К-во часов |
1 | Комбинаторика | Генерирование сочетаний, перестановок, размещений | 6 |
2 | Кодирование | Алгоритмы кодирования Фано и Хаффменна | 6 |
3 | Сети | Поиск кратчайшего пути по алгоритму Форда | 6 |
5.4. Матрица соотнесения тем/разделов (модулей) учебной дисциплины и формируемых в них общекультурных и профессиональных компетенций
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 |
