Требования к результатам освоения содержания дисциплины

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФГБОУ ВПО Кубанский государственный университет

ФАКУЛЬТЕТ КОМПЬЮТЕРНЫХ ТЕХНОЛОГИЙ

И ПРИКЛАДНОЙ МАТЕМАТИКИ

КАФЕДРА ВЫЧИСЛИТЕЛЬНЫХ ТЕХНОЛОГИЙ

РАБОЧАЯ ПРОГРАММА

Дисциплины Б3.Б.2 «Дискретная математика»

По направлению подготовки 010300.62 Фундаментальные информатика и информационные технологии

Квалификация (степень) выпускника: бакалавр

Факультет компьютерных технологий и прикладной математики

Форма обучения: дневная

Курс 1, 2; семестры 1, 2, 3

Экзамен – 1, 3 семестры

Зачет – 1, 2, 3 семестры

Краснодар 2011

Рецензенты:

Программа составлена в соответствии с федеральным государственным образовательным стандартом высшего профессионального образования по направлению подготовки 010300.62 Фундаментальные информатика и информационные технологии, утвержденным приказом Министерства образования и науки Российской Федерации от 8 декабря 2009 г, номер 712, и на основе примерных образовательных программ.

Составитель: заведующий кафедрой вычислительных технологий,

профессор, доктор физико-математических наук Миков А.И.

Рабочая программа утверждена на заседании кафедры вычислительных технологий 1 сентября 2011 г. (протокол № 1).

Заведующий кафедрой, д.ф.-м.н., профессор Миков А.И.

Рабочая программа утверждена на заседании методической комиссии факультета компьютерных технологий и прикладной математики 15 января 2012 г. (протокол № 2).

Председатель комиссии, к.ф.-м.н. Малыхин К.В.

ЦЕЛИ И ЗАДАЧИ ОСВОЕНИЯ ДИСЦИПЛИНЫ

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

Основные задачи освоения дисциплины.

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

МЕСТО ДИСЦИПЛИНЫ В СТРУКТУРЕ ООП ВПО

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

ТРЕБОВАНИЯ К РЕЗУЛЬТАТАМ ОСВОЕНИЯ СОДЕРЖАНИЯ ДИСЦИПЛИНЫ

В процессе освоения дисциплины у студента формируются следующие компетенции:

· ОК-10: Способность использовать основные законы естественнонаучных дисциплин в профессиональной деятельности, применять методы математического анализа и моделирования, теоретического и экспериментального исследования;

· ПК-2: Способность профессионально решать задачи производственной и технологической деятельности с учётом современных достижений науки и техники, включая: разработку алгоритмических и программных решений в области системного и прикладного программирования; разработку математических, информационных и имитационных моделей по тематике выполняемых исследований; создание информационных ресурсов глобальных сетей, образовательного контента, прикладных баз данных; разработку тестов и средств тестирования систем и средств на соответствие стандартам и исходным требованиям; разработку эргономичных человеко-машинных интерфейсов (в соответствии с профилизацией);

· ПК-4: Способность понимать и применять в исследовательской и прикладной деятельности современный математический аппарат, фундаментальные концепции и системные методологии, международные и профессиональные стандарты в области информационных технологий, способность использовать современные инструментальные и вычислительные средства (в соответствии с профилем подготовки);

· ПК-8: Способность профессионально владеть базовыми математическими знаниями и информационными технологиями, эффективно применять их для решения научно-технических задач и прикладных задач, связанных с развитием и использованием информационных технологий;

· ПК-15: Понимание концепций и абстракций, способность использовать на практике базовые математические дисциплины:

· ПК-25: Уверенное знание теоретических и методических основ, понимание функциональных возможностей, следующих предметных областей:

o разработка информационных систем (в части математической логики, теории отношений, теории кодирования);

o моделирование и анализ программного обеспечения (в части теории графов, комбинаторики, дискретных вероятностей);

o технологии мультимедиа (в части теории множеств, теории функций, теории кодирования);

o архитектура и организация компьютеров (в части булевых функций);

o конфигурирование и использование операционных систем (в части теории графов);

o разработка и принципы сетевых технологий (в части теории графов и кодирования);

o человеко-машинное взаимодействие (в части теории кодирования);

o приложения и использование баз данных (в части теории отношений);

o интеллектуальные системы (в части математической логики);

o теория баз данных (в части теории отношений).

СОДЕРЖАНИЕ И СТРУКТУРА ДИСЦИПЛИНЫ

Содержание разделов дисциплины

Таблица 1.

№ раздела	Наименование раздела	Содержание раздела	Форма текущего контроля	Разработано с участием представи-телей работода-телей
	Язык математики и основные операции над множествами	Математический язык. Имена, именные формы, высказывательные формы. Логические знаки. Таблицы истинности для отрицания, конъюнкции, дизъюнкции, импликации, эквивалентности. Логика Аристотеля. Понятие класса и множества. Отличия. Диаграммы Венна. Подмножества. Равенство множеств. Операции над множествами: превращение элемента в множество, объединение и пересечение множеств, свойства; разность, дополнение, симметрическая разность множеств, свойства. Законы де Моргана.	К
	Логика высказываний	Понятие п.п.ф. логики высказываний. Подформулы. Интерпретации переменных. Таблицы истинности. Интерпретации формул. Построение таблицы истинности для формул. Тавтологии, выполнимые и невыполнимые формулы. Важнейшие тавтологии. Теорема о тавтологии и невыполнимой формуле. Операция подстановки в формулу. Получение новых тавтологий. Выполнимое множество формул. Выполнение набора формул. Логическое следование и эквивалентность формул. Теоремы о выводимости и тавтологиях. Второе правило подстановки. Правила логического вывода. Нормальные формы. Построение формулы по таблице. Литерал. Конъюнкт. ДНФ. СДНФ. Теорема о выполнимой формуле и СДНФ. Дизъюнкт. КНФ. СКНФ. Построение по таблице истинности. Теорема о представлении формулы с помощью набора логических связок. Булевы функции. Несущественные переменные. Суперпозиция функций. Замкнутый класс. Полная система. Полином Жегалкина. Предполные замкнутые классы. Замкнутость классов T0 и T1. Двойственные функции. Класс самодвойственных функций. Лемма о несамодвойственной функции. Класс M. Лемма о немонотонной функции. Класс L. Лемма о нелинейной функции. Теорема о функциональной полноте. Разложение функции по переменной. Схемы из функциональных элементов. Построение схем по формулам. Полусумматор, полный сумматор. Метод резолюций.	К, ЛР, РГЗ
	Логика предикатов	Понятие предиката. Основные понятия. Примеры предикатов. Связь с высказываниями. Кванторы. Свободные и связанные переменные. Конечные предметные области. Двойной квантор общности, коммутативность. Двойной квантор существования, коммутативность. Разноименные кванторы, импликации. Законы де Моргана для кванторов. Применение кванторов к выражениям с конъюнкцией и дизъюнкцией. Случаи эквивалентности и случаи импликации. Классификация предикатов: тождественно истинные и ложные, выполнимые. Множество истинности предикатов. Равносильность предикатов. Следование предикатов. Теорема. Формулы логики предикатов. Интерпретация формулы на множестве. Выполнимость формул, тождественная истинность и общезначимость формул. Формулы логики предикатов, включающие логическую связку импликации и кванторы. Приведенная форма. Предваренная нормальная форма.	К, ЛР, РГЗ
	Теория множеств	Система аксиом теории множеств. Свойства операций над множествами. Понятие упорядоченного множества. Упорядоченная пара К.Куратовского. Теорема о равенстве упорядоченных множеств. Декартово произведение. Свойства декартова произведения. Мощность конечного множества. Основная теорема о подсчетах. Мощность степени. Мощность декартова произведения. Принцип включения-исключения. Разбиения и покрытия.	К, ЛР, РГЗ

№ раздела	Наименование раздела	Содержание раздела	Форма текущего контроля	Разработано с участием представи-телей работода-телей
	Отношения	Понятие отношения. Запись отношения. Бинарные отношения. Тривиальное, универсальное и тождественное отношения. Связь отношения и предиката. Операции на бинарных отношениях: обратные отношения, свойства; композиция отношений, свойства. Специальные виды отношений: рефлексивные и антирефлексивные; симметричные и антисимметричные; транзитивные отношения. Операция «степень отношения». Рефлексивные, симметричные и транзитивные замыкания. Проекции отношений. Отношения эквивалентности. Свойства. Классы эквивалентности. Фактор-множество. Теорема о классах эквивалентности. Отношения порядка. Отношения частичного порядка. Свойства. Отношения строгого частичного порядка. Отношения линейного порядка. Свойства. Сравнимые элементы. Организация таблицы идентификаторов в виде бинарного дерева. Процедура включения элемента в дерево. Упорядоченные множества. Минимум, максимум, минимальный и максимальный элементы. Грани. Цепи. Постулат Куратовского – Цорна.	К, ЛР, РГЗ
	Функции	Понятие функции. Области определения и значений. Всюду определенная функция. Образы, прообразы. Графики функций. Частичные и всюду определенные функции. Сужения функций. Инъективные, сюръективные, биективные функции. Пример: шифр Цезаря. Монотонные функции. Неубывающая, строго возрастающая, невозрастающая и строго убывающая функции. Композиция функций. Обратные функции. Последовательности и подпоследовательности как функции специального вида. Функции k в 1. Принцип Дирихле, обобщенный принцип Дирихле. Теорема Эрдёша и Секереша о возрастающей (убывающей) подпоследовательности. Понятие мощности для бесконечных множеств. Определение Г.Кантора. Свойства мощностей. Счетные (À0) множества. Счетность множеств четных чисел и целых чисел. Доказательство счетности множества рациональных чисел. Первая диагональная процедура Г.Кантора. Несчетные множества. Несчетность множества вещественных чисел. Вторая диагональная процедура Г.Кантора. Иррациональные числа. Алгебраические числа. Трансцендентные числа. Мощность булеана бесконечного множества. Кардинальные числа. Континуум-гипотеза.	К, ЛР, РГЗ
	Исчисления высказываний и предикатов	Алфавит исчисления высказываний. Формулы исчисления высказываний. Аксиомы исчисления высказываний. Правила вывода исчисления высказываний. Теоремы. Автоматическое доказательство теорем. Алфавит исчисления предикатов. Формулы исчисления предикатов. Аксиомы исчисления предикатов. Правила вывода исчисления предикатов.	К, ЛР, РГЗ
	Алфавитное кодирование	Критерий однозначности декодирования. Алгоритм проверки однозначности декодирования. Неравенство Макмиллана. Коды с минимальной избыточностью. Самокорректирующиеся коды. Код Хэмминга.	К, ЛР, РГЗ
	Симметричное шифрование	Шифрование и дешифрование. Однозначность. Секретный ключ и открытый алгоритм. Блочные коды. Длина блока и длина ключа. Схема Фейстеля. Кодирование по алгоритму DES. Основные методы криптоанализа.	К, ЛР, РГЗ
	Введение в теорию графов	Основные понятия. Граф, мультиграф, псевдограф. Ориентированные, неориентированные графы. Смежность, инцидентность, степень вершины. Изолированные, концевые вершины. Регулярные графы. Граф Kp , число ребер. Теорема Эйлера о сумме степеней. Графическая последовательность чисел. Маршрут, путь, контур, цикл. Расстояние между вершинами. Гамильтонов цикл. Эйлеров контур. Подграф. Остовный и индуцированный подграфы. Объединение и пересечение графов. Изоморфизм графов. Инварианты. Представление графов матрицами смежности, инциденций. Дополнение графа. Самодополнительные графы. Теорема о количестве вершин в самодополнительном графе. Двудольные графы. Теорема о характеризации двудольных графов циклами. Теорема о треугольниках в графе с 6 вершинами. Операция «произведение графов». Количество вершин и ребер в произведении. Гиперкубы Qn , количество вершин и ребер, нумерация вершин двоичными числами. Связный граф. Компоненты связности. Алгоритмы поиска в глубину и в ширину в неориентированном графе. Алгоритм отыскания связных компонент. Точки сочленения и мосты. Числа вершинной и реберной связности, неравенства. Пара связностей, функция связности. Дерево, лес. Теорема о характеризации деревьев. Дерево как двудольный граф. Остовные деревья. Взвешенные графы. Алгоритм Краскала построения остовного дерева минимального веса. Корневые деревья. Бинарные деревья. Обходы. Ориентированные графы. Представление матрицами. Слабая и сильная связность. Алгоритм Э. Дейкстры поиска кратчайшего пути. Вложение частичного порядка в линейный. Алгоритм топологической сортировки. Планарность графов. Формула Л.Эйлера. Максимальное число ребер в планарных графах с треугольниками и без треугольников. Теорема Понтрягина - Куратовского.	К, ЛР, РГЗ
	Элементы комбинаторики	Правило суммы. Правило прямого произведения. Размещения с повторениями. Размещения без повторений. Перестановки. Сочетания. Бином Ньютона. Биномиальные коэффициенты. Треугольник Паскаля. Комбинаторные тождества с биномиальными коэффициентами. Сочетания с повторениями. Количество целочисленных решений уравнения. Автоморфизмы. Группы автоморфизмов графов. Группа полного графа. Асимметрические графы. Перестановки с повторениями. Мультимножества. Полиномиальный коэффициент. Связь с сочетаниями. Полиномиальная формула. Упорядоченные и неупорядоченные разбиения множеств. Разложение подстановки (перестановки) на циклы. Число перестановок.	К, ЛР, РГЗ
	Комбинаторный анализ	Понятие производящей функции. Основные свойства производящей функции. Производящая функция биномиальных коэффициентов. Метод подсчета количества помеченных графов. Изоморфизм помеченных графов. Производящая функция помеченных графов. Число Gp . Примеры. Число способов приписывания пометок.	К, ЛР, РГЗ
	Дискретные вероятности	Массовые случайные явления. Пространство элементарных событий. Понятие события, сумма, произведение, разность событий. Вероятности элементарных событий. Распределение вероятностей. Вероятности событий. Свойства. Вероятность суммы n событий. Задача о совпадениях и ее решение. Равномерное дискретное распределение. Частотная интерпретация вероятностей. Применения. Повторение экспериментов. Произведение пространств элементарных событий. Последовательность испытаний Бернулли. Биномиальное распределение. Независимые события. Зависимые события. Условная вероятность. Теорема о полной вероятности. Теорема Байеса. Пример: передача информации по каналу связи с ошибками. Понятие о дискретной случайной величине. Функция распределения вероятностей целочисленной с. в. Сумма случайных величин. Постоянная с. в. Математическое ожидание с.в. Свойства. Дисперсия случайной величины. Стандартное отклонение. Свойства. Генерация псевдослучайных чисел. Схема Лемера.	К, ЛР, РГЗ

Структура дисциплины

Таблица 2.