ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«МАТИ» - РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ
имени К. Э. ЦИОЛКОВСКОГО
Кафедра «Проектирование вычислительных комплексов»
РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА
по дисциплине «Дискретная математика»
Направление № 000 «Информатика и вычислительная техника»
Шифр учебного плана: 230100.05пвк
Факультет № 6
Выпускающая кафедра: Проектирование вычислительных комплексов
Форма обучения: очная
Количество часов по дисциплине: 144
Цикл дисциплин: Е
Распределение времени студента по видам учебных занятий
(часы аудиторных занятий/самостоятельная работа)
Семестр | 3 | |
По учебному плану (АР/СР) | 64/80 | |
Лекции (АР/СР) | 32/40 | |
Лабораторные работы (АР/СР) | - | |
Практические занятия (АР/СР) | 32/40 | |
Курсовая работа (0/СР) | - | |
Форма контроля | экзамен |
Москва 2006 г.
1. ЦЕЛЬ И ЗАДАЧИ ДИСЦИПЛИНЫ, ЕЕ МЕСТО В УЧЕБНОМ ПРОЦЕССЕ
Цель преподавания дисциплины
Цель курса - научить студентов основам дискретной математики для использования ее аппарата в создании информационных систем, базирующихся на компьютерной технике, которая изначально явились результатом развития математической логики с ее революционным формулированием машины Тьюринга и ее строгим обоснованием в возможности решать практические, прикладные задачи на подобной машине. В свою очередь развитие компьютеров повлекло ускоренное развитие самой математической логики и ее приложений с формированием самостоятельных областей таких как: теория алгебраических систем, теория функциональных систем, теория графов и сетей, теория кодирования, теория алгоритмов, комбинаторный анализ, целочисленное программирование. Изучение теоретических вопросов сопровождается решением практических заданий, которые близки к задачам, имеющим практическое применение, в особенности в области теории графов и сетей, теории кодирования и других разделов дискретной математики. Это в свою очередь облегчает задачу освоения прикладных областей информатики, в особенности языков программирования, баз данных, операционных систем.
1.1. Задачи изучения дисциплины
В процессе изучения курса студенты, в первую очередь, должны получить ясное понимание теоретических основ в области дискретной математики и научиться ее строгой логике и последовательности при формулировании задач возникающих в практической сфере.
Знание в области кодирования и графов и сетей имеет ярко выраженный прикладной характер в области программирования и создания компьютерных сетей и это определяет круг решаемых задач, как на семинарских занятиях, так и при самостоятельной работе.
1.2. Перечень тем и разделов предшествующих дисциплин, освоение которых необходимо для изучения данной дисциплины
Для изучения данной дисциплины необходимо знакомство с курсами информатики, математического анализа, алгебры и геометрии.
2. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ
2.1. Наименования разделов и тем, объем в часах лекционных занятий.
3 семестр (32 часа)
№ | Тема и содержание | Кол-во часов |
Алгебра логики (алгебра высказываний). Функции алгебры логики. Формулы. Реализация функций формулами. Эквивалентность формул. Свойства элементарных функций. Принцип двойственности. | 4 | |
Разложение булевых функций по переменным. Совершенная дизъюнктивная нормальная форма. Полнота и замкнутость. | 4 | |
Важнейшие замкнутые классы. Теорема о полноте. Представление о результатах Поста. Представление о к-значной логике | 4 | |
Исчисление предикатов (логика предикатов). Формулы исчисления предикатов. Замена переменных в формулах. Аксиомы исчисления предикатов. Правила образования выводимых формул. | 4 | |
Непротиворечивость исчисления предикатов. Полнота в узком смысле. Некоторые теоремы исчисления предикатов. Теорема дедукции. Эквивалентные формулы. Закон двойственности. Нормальная форма. | 4 | |
Графы. Реализация в евклидовом пространстве. Изоморфизм. Оценка числа графов. | 4 | |
Сети и их свойства. Оценка числа сетей. Двухполюсные сети из двухобъектных наборов. П - сети. | 4 | |
Теория кодирования. Критерий однозначности декодирования. Об одном свойстве взаимно однозначных кодов. Коды с минимальной избыточностью. Самокорректирующие коды. Коды Хэмминга. | 4 |
2.2. Практические занятия, их содержание и объем в часах
3 семестр (32 часа)
№ | Тема и содержание | Кол-во часов |
Практическое занятие на тему: Функции алгебры логики. Формулы. Реализация функций формулами. Эквивалентность формул. Свойства элементарных функций. Принцип двойственности. | 4 | |
Практическое занятие на тему: Разложение булевых функций по переменным. Совершенная дизъюнктивная нормальная форма. | 4 | |
Практическое занятие на тему: Важнейшие замкнутые классы. Теорема о полноте. Представление о результатах Поста. Представление о к-значной логике. | 4 | |
Практическое занятие на тему: Исчисление предикатов (логика предикатов). Формулы исчисления предикатов. Замена переменных в формулах. Аксиомы исчисления предикатов. Правила образования выводимых формул. | 4 | |
Практическое занятие на тему: Эквивалентные формулы. Закон двойственности. Нормальная форма. | 4 | |
Практическое занятие на тему: Графы. Реализация в евклидовом пространстве. Изоморфизм. Оценка числа графов. | 4 | |
Практическое занятие на тему: Сети и их свойства. Оценка числа сетей. Двухполюсные сети из двухобъектных наборов. П - сети. | 4 | |
Практическое занятие на тему: Освоение навыков программирования на языке Теория кодирования. Критерий однозначности декодирования. Об одном свойстве взаимно однозначных кодов. Коды с минимальной избыточностью. Самокорректирующие коды. Коды Хэмминга. | 4 |
3. САМОСТОЯТЕЛЬНАЯ РАБОТА
5 семестр
3.1. Проработка конспекта лекций и изучение дополнительной литературы по основным темам лекций (40 часов).
3.2. Подготовка к практическим занятиям (40 часов)
4. УЧЕБНО-МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ ПО ДИСЦИПЛИНЕ
4.1. Обязательная литература
1. Новиков математика для программистов. М.2000
2. Акимов математика. Логика, группы, графы. М. 2001
4.2 Рекомендуемая литература
1. Иванов математика. Алгоритмы и программа. М. 2003
2. Андесон Дж. Дискретная математика М. 2003
3. Введение в дискретную математику. Москва «Наука» 1996 г. 272 с
4. Элементы математической логики. Москва «Наука» 1993 г., 400 с.
5. Теория кодирования и теория информации Москва «Радио и связь» 1993 г. 176 с.
